Non-simple paths in a directed graph.

• Download GraphPuzzle.zip - 2.5 MB

Introduction

In this article I would like to discuss how you can find all non-simple paths from a starting node to an end node in a directed graph. Non-simple path is a path that can include cycles and can have the edges with negative weight. The solution to the classic version of the problem that is about finding all simple paths between two arbitrary nodes in a directed graph is well - known and there are many examples of how to do this; however, I could not find anything helpful about how to find paths that are not simple. So, I decided to put together this article to demonstrate how can you tackle the problem. To make the article more interesting, I will use a programming puzzle to show how can you solve the non-simple paths problem.

Puzzle:

A cab driver needs to find a route from one city to another without running out of gas. Between each pair of cities are possible clients ready to pay for a drive, allowing the cab driver to accumulate a certain amount of money each time it travels from one city to another. Some routes charge a toll, resulting in losing a certain amount of money. You have to compute a route maximizing the profit. Your program takes the name of the starting city, the name of the destination city, the distance between them and the possible profit from a route.

Example:

Assume that we have the following connections:

A --------->B distance: 10 profit: 40

B --------->C distance: 15 profit: 5

C --------->B distance: 15 profit: 30

A --------->C distance: 30 profit: 50

If cab driver has gas for 40 miles and travels from A to C, the best trip is A -> B -> C -> B -> C with profit 55.

As you see, it is a complex problem: the paths have to maximize profit, can include cycles, can visit the end node more than one time and can have negative weight. It is obvious that such algorithms as Dijkstra's or Bellman-Ford will not work here; also, it is obvious that it cannot be solved in exactly the same way as the problem with finding a simple connections between two arbitrary nodes.

Solution:

What we want to do is find all the possible paths going from point A to point B that don't exceed a specified distance. Although there can be cycles involved and the end node can be visited more than once, the distance limitation allows us to enumerate them all, since each of them is uniquely identified by its length. In other words, the atomicity of the paths is determined not simply by the starting and ending points but also by their length.

In order to get all the paths starting from point A, we are going to traverse the graph using depth-first search that begins at the point A. While going through a child, we are going to make a link child -> parent in order to know all the edges we have already visited. Before we go to that child, we must traverse that linked list and make sure the specified edges are in acceptable distance limit. When we arrive to the destination point that is in the distance limit, we can store the path we found. If the distance limit is exceeded, the search begins tracing back to find the next path.

private void Search(Graph g, LinkedList<int> visited)
{
          var nodes =  g.Adj(visited.Last.Value);
           foreach (var edge in nodes)
           {
              if (_pathDistance + edge.Distance > _maxDistance)
                   continue;

              int w = edge.To;
               if (w  == _target)
               {
                   visited.AddLast(w);
                   _pathDistance += edge.Distance;
                   _pathProfit += edge.Profit;
                   SavePath(visited);
                   Print(visited);
                   visited.RemoveLast();
                   _pathDistance -= edge.Distance;
                   _pathProfit -= edge.Profit;
               }
           }

           foreach (var edge in nodes)
           {

               if (_pathDistance + edge.Distance > _maxDistance)
               {
                   continue;
               }

                 int w = edge.To;
               visited.AddLast(w);
               _pathDistance += edge.Distance;
               _pathProfit += edge.Profit;
               Search(g, visited);
               visited.RemoveLast();
               _pathDistance -= edge.Distance;
               _pathProfit -= edge.Profit;
           }
  }

As you can see, the solution to the problem is a depth-first search that finds all the paths between the two vertices that don't exceed the specified max distance between them. The end of a path is not determined simply by hitting the destination node but by distance that can be covered during a trip. The search keeps the track of the amount of profit gained during the traversal. In the result, each selected path is associated with its total weight.

When we know all the possible connection, we can find which one is the most profitable. To accomplish these we store the paths in priority queue.

private void SavePath(LinkedList<int> visited)
{
           _paths.Add(visited.ToArray());

           // priority queue
           _pq.Add(new State(_paths.Count() - 1, _pathProfit, _pathDistance ));
}

Now, we can query the queue to find the most optimal connection.

public double BestProfit()
{
         return _pq.FindMax().Profit;
}

Example:

We feed our program with the following connections:

start end distance profit

Alicetown Bobville 10 50

Alicetown Carolina 30 60

Bobville Carolina 15 5

Carolina Bobville 15 5

Bobville Danburg 20 75

Danburg Bobville 20 40

Bobville Eveland 25 15

Carolina Danburg 10 20

Carolina Eveland 30 20

Danburg Eveland 40 40

Eveland Danburg 20 40

Eveland Frank City 15 -10

Frank City Danburg 10 35

Then, we request the following trips: