QuikGraph icon indicating copy to clipboard operation
QuikGraph copied to clipboard

Longest path length per vertex?

Open Bouke opened this issue 2 years ago • 5 comments

I'd like to record the longest path length per vertex in my graph. Using the original package I could call EdgeDepthFirstSearchAlgorithm.Visit, to re-visit edges when I came across a longer path, but it has been made private. How would I now do this?

Below an example of what used to work:

var edges = new(string Source, string Target)[] {
    ("A", "D"),
    ("A", "B"),
    ("B", "C"),
    ("C", "E"),
    ("D", "E"),
};
var graph = new BidirectionalGraph<string, Edge<string>>();
graph.AddVerticesAndEdgeRange(edges.Select(edge => new Edge<string>(edge.Source, edge.Target)));

var pathLengths = new Dictionary<string, int>(graph.VertexCount);
foreach(var vertex in graph.Vertices)
    pathLengths[vertex] = 0;

var edfs = new EdgeDepthFirstSearchAlgorithm<string, Edge<string>>(graph);
edfs.TreeEdge += edge =>
{
    if (pathLengths[edge.Target] <= pathLengths[edge.Source])
    {
        pathLengths[edge.Target] = pathLengths[edge.Source] + 1;
    }
};
edfs.ForwardOrCrossEdge += edge =>
{
    if (pathLengths[edge.Target] <= pathLengths[edge.Source])
    {
        edfs.Visit(edge, pathLengths[edge.Source]);
    }
};
edfs.Compute("A");

Bouke avatar Sep 22 '21 18:09 Bouke