Archived

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

specific Graph problem

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

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 on other sites

[edited by - sjelkjd on February 20, 2004 12:08:29 AM]

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 on other sites
can you run dfs and label the nodes with their depth from the root(s)?

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.
-CProgrammer

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

Share on other sites
dfs = deepth first search

LizardCPP

Share on other sites
I have one problem with dfs. In my example what can i use as source vertex? There really isnt one.
-CProgrammer

[edited by - CProgrammer on February 23, 2004 5:35:31 AM]

Share on other sites
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 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 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.'' "

1. 1
Rutin
28
2. 2
3. 3
4. 4
5. 5

• 13
• 11
• 10
• 13
• 20
• Forum Statistics

• Total Topics
632948
• Total Posts
3009406
• Who's Online (See full list)

There are no registered users currently online

×