Using ReversedBidirectionalGraph in Search

[thempen]

Hi,

I am a little confused with building and using the ReversedBidirectionalGraph. I came on to that through #46 .

What i have: A directed graph with loops and parallel edges. I do have a single root vertex and a single final vertex.

What i want to do:

• Building a BFS tree from the root vertex.
• Building a BFS tree from the final vertex reversed edges. (considering the final vertex would be the new root and every paths in the graph to search is pointing in the opposit direction.

My approach and problem:
I tried to use the ReversedBidirctionalGraph with the intention on not needing to build a reversed graph manually. This would also be problematic because i do some dynamic Id Management in that, referencing to certain objects. With building new Vertices and Edges, there would be new unique Ids, not referencing to the correct objects anymore. So... yeah...

I tried to do something like this (just pseudocode, because i didn't get it running in a clean way):

ReversedBidirectionalGraph<MyNode, MyEdge> reversedGraph; // somehow filled
BFS<MyNode, MyEdge> topDown = new BFS<MyNode, MyEdge>(reversedGraph.Original)
//adding topDown to some observer

BFS<MyNode, MyEdge> bottomUp= new BFS<MyNode, MyEdge>(reversedGraph)
//adding bottomUp to some observer

I don't know how to do this in a clean way, because I always run in to data type problems with the SReversedEdge struct leading to a mess of type conversions and castings on my side.

Can you give me an Idea on how to work with the reversed graph?

[KeRNeLith]

Hello!

The ReversedBidirectionalGraph is indeed dynamic representation of a graph as a reversed one. BTW it indeed use some struct (SReversedEdge) to not create/alterate objects from the original graph. I would say that it's the cost of dynamic feature.

Otherwise we would need a representation that create edge object by reverting Source and Target. The main issue would certainly be that this would imply using reflection to make the ctor call and also assuming that the edge object has a ctor with source and target in this order.
Hum or maybe by giving an edge factory so that this would solve the reflection issue. BTW we will end having different edge instances. Wouldn't it be an issue for you if I understand well?

There are several possible additions that can be made for the library:

• Dynamic representation with specific edge structure (current implementation)
• Dynamic representation with similar edge structure
• Static representation with specific edge structure (reversed edge creation is done only once)
• Static representation with similar edge structure (alternate edge creation is done only once)

I'm not sure how useful each would be?