Longest path length per vertex?

[Bouke]

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");

[KeRNeLith]

Hello,

Ho indeed this is no more possible due to the move to private. I didn't thought about such use case when cleaning the library :-s

BTW this seems legit usage. I think we can move back to public callable method. Note that it may cause issues if it is called without having run the algorithm, I mean on a direct call to it.

[KeRNeLith]

Hi again @Bouke

Sorry for not having provided you an alternative earlier. I think what you're searching is something described there.

Here is a code sample using QuikGraph that should do the job, is it ok for you?

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 dfs = new DepthFirstSearchAlgorithm<string, Edge<string>>(graph);
dfs.TreeEdge += OnEdgeAction;
dfs.BackEdge += OnEdgeAction;
dfs.ForwardOrCrossEdge += OnEdgeAction;
dfs.Compute("A");

void OnEdgeAction(Edge<string> edge)
{
    pathLengths[edge.Target] = Math.Max(pathLengths[edge.Target], 1 + pathLengths[edge.Source]);
}

[Kemsekov]

Longest path per vertex will be any hamiltonian path that starts from this particular vertex, or if a hamiltonian cycle exists within graph, then longest path will be the same for all verticies and equal to a length of a this cycle.

But because there is a cases when nor hamiltonian path, nor cycle exists I propose different solution.

In order to build a longest path we can use Ant colony simulation. See TryFindHamiltonianPathByAntSimulation method

It will strike ants to do dfs with some prefering of choosing path depending on smell left on edge. After ant reached all nodes or stuck it will compute coefficient of it's path = (nodes count in path)/(path length) and if it is found path better than previous ants did it will update smell so this new path will be more preferable for other ants. This method allows to find a good approximation of longest path for any vertex.

[KeRNeLith]

Hum, interesting, do you suggest having this kind of algorithm implemented directly in QuikGraph or it was just for reference on that topic in order to share some knowledge and acts as a kind of sample?

[Kemsekov]

Just sharing my experience.