How to best improve results of an algorithm (get nodes and order in path)

[luminize]

Dear developers,
First; thank you for this library. Much leaner than boost :)

I use the Bellman Ford algorithm with negative edges to find the longest path in a directed graph. Great out of the box. For future work I would like to get the nodes that lie on the longest (or shortest) path. Think multiple jobs with (sequential) tasks on machines and finding the critical path. Might even get the delayed start times out as a result for all nodes.

I've been looking thru the source, and for starters I'm thinking of adding a vector of visited nodes or something to the results of the algorithm.

What would be the best way to work on this? Update the algorithm in the source code? Is there maybe a more general solution (already in the making)?

Best,
Bas

[ZigRazor]

Hi @luminize,

There is no work that actually contemplate this.
Maybe in the result struct can be added an additional info section that is specific for each algorithm, that add some information to the result.
I think that modify too much the current interface is not really good, but we can think about some flags to activate some piece of code in the function so that the result can return these additional info.

Let me know how you want to contribute to this, or open a PR and then we can discuss it.

Thank you in advance

[luminize]

Hi @ZigRazor I'll dive into how to solve finding the node identities that are on the critical path for my "problem". That might to clarify what I think I need.
My thought now is to remove node V after finding the longest path and then find the longest paths to the resulting end nodes (3,1), (3,2) and (4,3) minus the weight of the outgoing edge to V. That should tell which of those nodes are on the critical path. Then repeat until I reach U. (see picture)

But I can imagine running the algorithm a lot of times with bigger graphs can take up a lot of time. So that might not be the best way.

How about remembering the itermediate_weight of a node (sum of all edges to that node)? That could be helpfull for introspection of the results of an algorithm afterwards? Or maybe a callback when a node intermediate_weight is changed (your remark about flags enabling this).

[luminize]

Hi @ZigRazor,
I've added a vector of std::pair of the node user id and it's value to the result of the Bellman Ford algorithm.
That helps in traversing (back to front) the path(s) that are critical.

I have in Typedef.hpp added to the BellmanFordResult_struct:

std::vector<std::pair <std::string, double>> node_and_value{};

And in the algorithm if the result is successfull

    auto edgeSet = Graph<T>::getEdgeSet();
    for (const auto &edge : edgeSet) {
      auto elem = edge->getNodePair();
      result.node_and_value.push_back(std::pair(elem.first.get()->getUserId(), dist[elem.first]) );
      }

What would help your project? Me adding a PR for this?

I'm writing code for finding all critical path(s if there are) with inspecting the edgeset of the graph. Would this have a place in your codebase? An example or helper functions maybe?

[ZigRazor]

Yes, you can provide a new file with your helper function.
The library have a folder for algorithm, then i think this folder could be named additional_algorithm, with the file with your implementation