Jump to content
  • Advertisement

Archived

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

CProgrammer

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.

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
Advertisement
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
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 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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!