Fog Creek Software
Discussion Board

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.

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.

Wednesday, March 24, 2004

Here's a classic:

This was just published on MSDN:

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?

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.

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:

Sam Livingston-Gray
Saturday, March 27, 2004

*  Recent Topics

*  Fog Creek Home