Basic question about bidirectional graphs

Topics: algorithm, graph
Jun 19, 2012 at 8:08 PM

Hi everyone, sorry for what may be a brutally (I hope) simple question.

I have a class called Datapoint that I am using for both the nodes and edges in my QuickGraph code.  The class overloads the 'Source' and 'Target' fields as required by the QuickGraph IEdge interface.

Fundamentally, however, my data is undirected, and I want to find the shortest paths between various sets of nodes.  I am currectly using the RankedShortestPathHoffmanPavley function.  So the 'Source' and 'Target' are making me a bit nervous because it feels very directional and the answers returned from a directed graph will be different from an undirected graph.

So, here is my question.  If I make a BidirectionalGraph and give it nodes and edges, do I need to double all my edges (i.e. A->B AND B->A) or is the BidirectionalGraph class smart enough to figure that out, despite the fact that my edges only represent the A->B case via the 'Source' and 'Target' fields?






Jul 14, 2012 at 4:01 PM

as i know and have tried, BidirectionalGraph stores a directed graph, and you can get both InEdges and OutEdges of a node. that is very different from AdjacencyGraph, in which you can get only OutEdges of a node.

so, A->B and B->A is two different edges in BidirectionalGraph