New questions: are you trying to determine the distance between the nodes as well? Like shortest distance? Longest distance? Or which nodes are passed through on the shortest route?... or complete route?
You do have to determine if two nodes are connected first before determining the distance between, right?
specific Graph problem
Author
I think you misunderstood the question.
Ill explain again:
Whats given: The undirected incomplete graph;
Each node knows about its connecting nodes
including the distance...
What I need:
I have: An array of numbers.
I want: each node to be assigned any number in the array whilst furfilling a ''condition'' like explained in the first post.
It would be something along the line of assigning from the worst to the best node. But how can the worst node be defined. dfs doesnt seem an option to me, cause there is no base node.
-CProgrammer
Ill explain again:
Whats given: The undirected incomplete graph;
Each node knows about its connecting nodes
including the distance...
What I need:
I have: An array of numbers.
I want: each node to be assigned any number in the array whilst furfilling a ''condition'' like explained in the first post.
It would be something along the line of assigning from the worst to the best node. But how can the worst node be defined. dfs doesnt seem an option to me, cause there is no base node.
-CProgrammer
As far as I can think of, there are 2 types of graph algorithms specifically relavant to incomplete graphs ... or possible 3.
1. For some types of problems, there is a "start" node, such as to answer the questions "is X reachable from Y" .. you start at X or Y and work a depth or bredth first search until you have visited all reachable nodes or found the target ... (this type does not apply to your problem).
2. For other types of problems, there is no frame of reference, and the problem is about the whole graph, not some particular subset of it ... for these problems you (in the naive version) start at EVERY node .. in other words you run the algorithm from each node in the graph. Usually for this to work, your algorithm needs to be of a type that the results can be "updated" with better results, such as shortest distance type problems ... Obviously for most algorithms in which this type of method applies, you do not need to run the whole algorithm again with each node as a start .. you can short circuit whenever you are attempting to start with a node you had already visited in a previous iteration ... just like you do to stop forever traversing a cyclic graph, here you do it also for efficiency ... no need to recompute the same distance for a given subgraph that you''ve already computed.
For undirected graphs, you can also run a seperation / grouping / partitioning algorithm, which will yield a list of complete sub graphs ... in other words you can run an algorithm of type 2 above, whos output is a set of graphs, each of which is a complete, connected graph ... then each of these is suitable for applying all algorithms which work on complete graphs .. and therefore they can be individually solved for many interesting things ...
Put another way .. and possibly INCOMPLETE UNDIRECTED graph, is essentially 1 or more COMPLETE UNDIRECTED graph ... and could also be decomposed into a INCOMPLETE DIRECTED graph, or 1 or more COMPLETE DIRECTED graphs .. (of course in THEORY going from an undirected graph to directed is useless, because it doesn''t allow you to do any additional set of operations / problems ... but in PRACTICE it is usefull to no, because if you have an implemented algorithm lying around which works on directed graphs, you can apply it to your undirected graph as well - obviously).
1. For some types of problems, there is a "start" node, such as to answer the questions "is X reachable from Y" .. you start at X or Y and work a depth or bredth first search until you have visited all reachable nodes or found the target ... (this type does not apply to your problem).
2. For other types of problems, there is no frame of reference, and the problem is about the whole graph, not some particular subset of it ... for these problems you (in the naive version) start at EVERY node .. in other words you run the algorithm from each node in the graph. Usually for this to work, your algorithm needs to be of a type that the results can be "updated" with better results, such as shortest distance type problems ... Obviously for most algorithms in which this type of method applies, you do not need to run the whole algorithm again with each node as a start .. you can short circuit whenever you are attempting to start with a node you had already visited in a previous iteration ... just like you do to stop forever traversing a cyclic graph, here you do it also for efficiency ... no need to recompute the same distance for a given subgraph that you''ve already computed.
For undirected graphs, you can also run a seperation / grouping / partitioning algorithm, which will yield a list of complete sub graphs ... in other words you can run an algorithm of type 2 above, whos output is a set of graphs, each of which is a complete, connected graph ... then each of these is suitable for applying all algorithms which work on complete graphs .. and therefore they can be individually solved for many interesting things ...
Put another way .. and possibly INCOMPLETE UNDIRECTED graph, is essentially 1 or more COMPLETE UNDIRECTED graph ... and could also be decomposed into a INCOMPLETE DIRECTED graph, or 1 or more COMPLETE DIRECTED graphs .. (of course in THEORY going from an undirected graph to directed is useless, because it doesn''t allow you to do any additional set of operations / problems ... but in PRACTICE it is usefull to no, because if you have an implemented algorithm lying around which works on directed graphs, you can apply it to your undirected graph as well - obviously).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
