Skip to content
New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

[Bug] EdgeDepthFirstSearchAlgorithm does not find multiple paths when the root vertex has parallel edges #20

Closed
TheDudeCode opened this issue Nov 5, 2020 · 1 comment

Comments

@TheDudeCode
Copy link

Considering the following graph
7fd72cc1ace4f41a

For this graph we would like to know all possible paths between two nodes. So for the example below the resulting paths between nodes 0 and 2 would be:

  • 0 -> 2
    
  • 0 -edge A-> 1 -> 2
    
  • 0 -edge B-> 1 -> 2
    

The code to accomplish this is:

var startNode = "0";
var endNode = "2";

var graph = new AdjacencyGraph<string, TaggedEdge<string, string>>(allowParallelEdges: true);

var edges = new List<TaggedEdge<string, string>>{
    new TaggedEdge<string, string>("0", "1", "edge A"),
    new TaggedEdge<string, string>("0", "1", "edge B"),
    new TaggedEdge<string, string>("1", "2", string.Empty),
    new TaggedEdge<string, string>("0", "2", string.Empty),
    new TaggedEdge<string, string>("0", "3", string.Empty),
    new TaggedEdge<string, string>("1", "3", string.Empty), };
edges.ForEach(x => graph.AddVerticesAndEdge(x));

var algo = new EdgeDepthFirstSearchAlgorithm<string, TaggedEdge<string, string>>(graph);
var observer = new EdgePredecessorRecorderObserver<string, TaggedEdge<string, string>>();

using (observer.Attach(algo))
{
    algo.Compute(startNode);
}

var allPaths = observer.AllPaths().Where(x => x.Last().Target == endNode)
```;

However only 2 paths are found, not finding the one that has edge B:
-     0 -> 2
-     0 -edge A-> 1 -> 2

Would we add a parallel edge between nodes 1 and 2, then indeed 3 paths are found.
@KeRNeLith
Copy link
Owner

Closing because it is a duplicate of #21.

# for free to join this conversation on GitHub. Already have an account? # to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants