#### Archived

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

# specific Graph problem

This topic is 5260 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
25
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 14
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631757
• Total Posts
3002125
×