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 edgegroups.
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/enus/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
Edgegroups 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 pathfinding algorithm on a directed graph using Python:
http://www.python.org/doc/essays/graphs.html
Sam LivingstonGray
Saturday, March 27, 2004
Recent Topics
Fog Creek Home
