How to find the longest path in an acyclic directed graph using OGDF library?

Question

I'm new to OGDF library and need to find the longest path in an acyclic directed graph (I want to use OGDF built in functions). I know, it is possible to find longest path using shortest path algorithms with negative weights for edges, but also could not find a proper function for it. Does OGDF has a specific function to do that? If yes, how can I use it?

Hamed Hamed · Accepted Answer · 2012-08-11T20:44:24

In OGDF, you can find the shortest path between node s and other nodes using ShortestPathWithBFM. The lengths (weights) of edges should be passed to the function, using EdgeArray<int>. Here is the class definition from its source code:

namespace ogdf {

class OGDF_EXPORT ShortestPathWithBFM : public ShortestPathModule
{
public:
 ShortestPathWithBFM() { }

 // computes shortest paths
 // Precond.:
 //
 // returns false iff the graph contains a negative cycle
 bool call(
 const Graph          &G,      // directed graph
 const node           s,       // source node
 const EdgeArray<int> &length, // length of an edge
 NodeArray<int>       &d,      // contains shortest path distances after call
 NodeArray<edge>      &pi
 );


};


} // end namespace ogdf

The algorithm would compute the longest path if you pass lengths in negative. For more information, please refer to: http://www.ogdf.net/doc-ogdf/classogdf_1_1_shortest_path_with_b_f_m.html

How to find the longest path in an acyclic directed graph using OGDF library?

1 Answers