On the graph, find the longest path with a specific property?
I have a directed graph (more precisely, a control flow graph) and each of the vertices has a set of properties.
I would like to find (or write) an algorithm that, given a vertex V
with a property P
, finds the longest path to some vertex E
, so that all vertices along the all
possible paths from V
to E
contain the property P
.
Example 1
Let's say I had the following schedule. (Please excuse the bad ascii drawing.)
+----+
+--------+P +--------+
| +----+ |
| V1 |
| |
| |
+--v--+ |
+----+P ++ |
| +-----++ +--v--+
| | +----+P |
| | | +-----+
+--v--+ +--v--+ |
|P +-+ +-+P | |
+-----+ | | +-----+ |
| | |
| | |
+v-v--+ |
V6 |P +---------+ |
+-----+ | |
| |
| |
| |
| |
+-v--v-+
V7 |P |
+---+--+
|
|
+---v--+
V8 |!P |
+------+
Starting from V1
, the longest path where P
it is always executed on all possible paths is V1
→ V7
. Note that other paths, such as V1
→ V6
, are "valid" because they are P
always executed, but V1
→ V7
is the longest.
Example 2
This example is the same as above, except it now P
fails in V3
:
+----+
+--------+P +--------+
| +----+ |
| V1 |
| |
| |
+--v--+ |
+----+P ++ |
| +-----++ +--v--+
| | +----+!P | V3
| | | +-----+
+--v--+ +--v--+ |
|P +-+ +-+P | |
+-----+ | | +-----+ |
| | |
| | |
+v-v--+ |
V6 |P +---------+ |
+-----+ | |
| |
| |
| |
| |
+-v--v-+
V7 |P |
+---+--+
|
|
+---v--+
V8 |!P |
+------+
In this case, starting with V1
, the longest path, where P
it is always executed on all possible paths, is V1
→ V6
. Path V1
→ V7
invalid as there is a path between V1
and V7
, which P
is not performed.
Further notes on my situation
- The schedule can be cyclical.
- The graph will be small to medium in size, perhaps 1000 vertices or less.
- The graph does not necessarily always have one root and one leaf, like my examples above.
Question
Is there a standard algorithm for computing such paths?
source to share
The problem has no effective efficient solution , since it is easily smoothed out from the Hamiltonian path problem , which says: a given graph - is there a path that goes through all vertices exactly once?
The reduction is simple - given a Hamiltonian p
Way problem, label all nodes with and find the longest path. Since the path of the Hamiltonian is NP-Complete , both this problem and there is no known polynomial solution.
An alternative is brute force search (the simplest form will generate all permutations and choose the most appropriate one), but this will become impossible for large graphs. You may also need to use a heuristic approach (which finds a "good" solution, but not optimal), such as genetic algorithms.
Another possible solution is to reduce the problem to "Problem with the seller" and use some existing TSP solver. Note that although this problem is also NP-hard as it has been well studied, there are fairly efficient solutions for medium-sized charts.
Also, if your graph is somehow "special" (eg DAG ), you can use some smart techniques to achieve significant speed up to polynomial time, eg dynamic programming.
source to share