Archived

This topic is now archived and is closed to further replies.

specific Graph problem

This topic is 5047 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have googled on this, but since I'm a hobby programmer, I just can't find the right algorithm for my problem. Given an undirected Graph that is incomplete(thus not all nodes can be reached from another node). I now want to assign numbers from an array to the nodes(one node one number). I have a 'condition' like one in an if-statement. This condition should be furfilled for all nodes. Now I assume theres some standard approach, some standard algorithm on this. EDIT: More info Well theres only two types of connection length between the nodes: 1 and 2 Id like to keep the 'condition' general however heres one example: - All connecting nodes differ in vlaue as much as their distance. (so delta value is >= distance to node) And so on... Anything along this line. Oh the case that its impossible cant occur. Any ideas Thnakjs for your time. -CProgrammer [edited by - CProgrammer on February 20, 2004 12:29:00 AM]

Share this post


Link to post
Share on other sites
Well theres only two types of connection length between the nodes: 1 and 2
Id like to keep the 'condition' general however heres one example:
- All connecting nodes differ in vlaue as much as their distance.
(so delta value is >= distance to node)

And so on... Anything along this line.
Oh the case that its impossible cant occur.
edit: oh and thanks for the link.
-CProgrammer

[edited by - CProgrammer on February 20, 2004 12:19:09 AM]

Share this post


Link to post
Share on other sites
Could you be more specific.
dfs?
what root? Its not a tree graph.
PS: About labeling nodes. No problem, the nodes are
represented by a class so anything can be changed
or precalculated.
Thanks for the reply
-CProgrammer

[edited by - CProgrammer on February 22, 2004 9:54:32 AM]

Share this post


Link to post
Share on other sites
How is your graph stored?
Is the graph acyclic?
Does it matter what order you visit the nodes in?

[edited by - arm on February 23, 2004 5:45:07 AM]

Share this post


Link to post
Share on other sites
The graph is cyclic in some areas and its incomplete.
Meaning not all nodes are reachable from all other nodes.
The Graph is stored as follows: A node is represented by a class, all nodes are a array of the class. Each objekt has information saved including information about the attaching nodes.
The order is irrelevant as long as the problem is solved.
-CProgrammer

Share this post


Link to post
Share on other sites
Two questions:

1.) Are you just trying to determine if two nodes are connected?
2.) What programming language?


int N = Integer.parseInt(args[0]);
int id[] = new int[N];
for (int i = 0; i < N ; i++) id = i;
for( In.init(); !In.empty(); )
{ int p = In.getInt(), q = In.getInt();
int t = id[p];
if (t == id[q]) continue;
for (int i = 0;i if (id[i] == t) id[i] = id[q];
Out.println(" " +p+""+q);
}

This will color each node the same if it has been seen in a previous pair. Its a little hard to explain -- and written in java. In is just standard in that takes a pair of numbers like 9-1, or 5-6, or 2-3, which say that the two pairs are connected.
Then it assigns q, to p as number assignments. p being the first number in the pair and q being the second. So if you are querying if p-q (ie p is connected to q) then p will eventually have the same value as q after running the algorithm otherwise its not connected.


" ''No one has control -- control is just a fantasy. And being human is difficult.'' "

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites