QuikGraph
QuikGraph copied to clipboard
Longest path length per vertex?
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");