The Old Joel on Software Forum: Part 4 (of 5) - Graphs, Nodes, Edges, Groups, Connections.

Graphs, Nodes, Edges, Groups, Connections.

I am looking for something that find's connections between nodes of the graph.
In the graph where nodes are connected via edges and some edges form a group and each connecting path should not have more than one edge from the respective edge-groups.

Programmer
Wednesday, March 24, 2004

Look for a book on Algorithms. There's one by MIT press that is generally regarded as THE algo book. IIRC it has a chapter or two on graphs. Or you could always look online. You should be able to find something relevant either on someone's personal webpage or (more likely) on any random college's cs classes webpages.

tim
Wednesday, March 24, 2004

Here's a classic:

http://www.amazon.com/exec/obidos/tg/detail/-/0898711878

This was just published on MSDN:

http://msdn.microsoft.com/vcsharp/default.aspx?pull=/library/en-us/dv_vstechart/html/datastructures_guide5.asp

mb
Wednesday, March 24, 2004

I guess it's not simple as I didn't find in textbooks.
Anyone know the name for this method/algorithm?

Programmer
Wednesday, March 24, 2004

Edge-groups form what is called an equivalence class. If you have a list of these equivalence classes you can do the following:

Walk the graph to enumerate each path. Along each path collect the set of edges that forms the path. Take the intersection of this set with each of the equivalence class sets. If the cardinality of any intersection is greater than one, you have a case that violates your criteria.

Without more specific detail, it's difficult to say how to do this optimally, but that should be enough to work from.

bud
Wednesday, March 24, 2004

Find yourself a textbook on Discrete Math (assuming your post isn't related to doing homework in said class already!); this should cover the basics of how graphs work.

Also, check out this essay by Guido van Rossum, which presents a short example of a path-finding algorithm on a directed graph using Python:

http://www.python.org/doc/essays/graphs.html

Sam Livingston-Gray
Saturday, March 27, 2004