Search code examples
c#graphingquickgraph

How to find out if there is a connection between two arbitrary vertices in direction graph?

I would like to know which classes and functions in Quickgraph library (C#) should I use, to find out, if there exists a connection between two arbitrary vertices in a directional graph?

I am a beginner at programming, especially programming alghorithms, so I would kindly ask you if you can provide me a sample code for mentioned problem, mainly because Quickgraph library doesn't have many problem-specific tutorials for beginners.ecially

Graph specification:

  • Directed
  • Not weighted (distance is not important, just connectivity between vertices/edges)
  • Graph is dynamic so vertices/edges can be added/removed or edited.
Solution

  • Hm, I haven't tested it, but basic DFS/BFS should do the trick, as such:

    var tryGetPaths = _graph.TreeBreadthFirstSearch(__source__);
IEnumerable<Edge<YourItemType>> path;
if (tryGetPaths(__target__, out path))
{
    // we have connectivity!
}

    That one checks if there is any connectivity from source to target. You might want to run that check vice versa too.