wnlp3

Usage

#include <wn/wnspmat.h>
#include <wn/wnlp.h>

wn_longest_path(&code,&len,&result,length_mat,start_node,fin_node)
int code;
double len;
wn_sll result; /* list of edges */
wn_sparse_matrix length_mat;
int start_node,fin_node;

Overview

This package solves the "longest path" problem easily using exponential search. length_mat is treated as a DIRECTED GRAPH; thus it must be square. The matrix entry length_mat[i][j] gives the length of the directed edge from node i to node j. Negative edge lengths are allowed. result is the list of edges in the longest path, ordered starting from start_node. len is set to the total length of the solution.

The longest path problem is the following optimization problem:

Choose the path in the graph length_mat from start_node to fin_node which is the longest possible path.

If the graph is DAG (that is, it lacks cycles and undirected edges), it can be solved more efficiently using wncp.

Resources

Solving a longest path problem requires

WORST and AVERAGE CASE:

time = n^(e/n)
stack memory = n
dynamic memory = n

where e is the number of matrix entries, and n is the number of nodes in the graph represented by length_mat. (n == len_i == len_j).

Note: the longest path problem is NP-complete [1], and thus no algorithms faster than exponential are known for the general problem.

Diagnostics

code == WN_SUCCESS for successful solution. code == WN_INFEASIBLE if no path from start_node to fin_node exists.

len_i != len_j causes a crash.

References

[1] Garey & Johnson