Return to Europa
When a shortest path between two vertices needs to be calculated, a programmer can turn to many standard and well know algorithms, some of which have been implemented in the various incarnations of the RESOLVE/C++ Component Least_Cost_Path_Machine. When a programmer wishes to calculate greatest-length paths between two vertices (in directed acyclic graphs; more on this later), other creative algorithms can be developped. Greatest-length paths can be useful in solving scheduling problems, among others. In fact, this project found its genesis while I was working on another project, Getting out of Ohio State.
I wrote the Greatest_Cost_Path_Machine for several reasons: I initially began with a custom algorthm to calculate the greatest cost path between all pairs of vertices (u,v) in O(|V|3) time. This algorithm was far superior to any of the other ones I had developped. I also had developped a particular datastructure that would allow for constant-time lookup of the algorithm's results (which only needed to be calculated once), using an enhanced version of the adjacency matrix representation for graphs. Finally. I chose to round out the graph theory components in the RESOLVE/C++ component library and reacquaint myself with its discipline.
The interface and mathematical model of the Greatest_Cost_Path_Machine are similar to those of the Least_Cost_Path machine. The inferface, however, has been augmented with There_Is_A_Connecting_Edge and Greatest_Cost_Of_An_Edge. Without these two operations, the entire math model of the Greatest_Cost_Path_Machine could not be accessed. The status of these two operations in the Least_Cost_Path_Machine is unknown.
There is also a small difference in the behaviour of Greatest_Cost_Path_Machine. The component requires graphs to be directed acyclic. This means that vertices do not have paths to themselves as this would represent a cycle. For example, there does not necessarily exist a path from vertex A to vertex A.
If a graph contains a positive-cost directed cycle, then the greatest-cost path between any two vertices becomes undefined. Indeed, the cycle can be traversed any number of times for arbitrarily large paths. Consequently, the Greatest_Cost_Path_Machine limits itself to acyclic graphs. (The problem of finding greatest-cost paths in a graph with cycles while traversing each edge only once is another problem for another day.) The checking component for the Greatest_Cost_Path_Machine checks that the graph contains no cycles. To do this, it traverses the graph. As it is traversing the graph down directed edges, it checks to see that no edge points to a vertex that has already been traversed, as this would indicate a cycle.
Forthcoming...
I have since learned that the algorithm detailed above is essentially a Topological sort of the vertices of the graph, followed by an edge traversal. The existing algorithm has been refined to incorporate these ideas.
The datastructure used to represent the Greatest_Cost_Path_Machine is an 'adjacency path matrix'. The development of this datastructure allows to compute the greatest cost paths between every pair of vertices only once, store the information in |V|2 space, and perform constant-time lookups of the results of running the algorithm. Specifically, besides storing the classical information found in an adjacency matrix representation of a graph for all pairs of vertices (u,v) (whether there is a directed edge or not and the cost of the edge if present), the datastructure also stores the name of the first vertex that needs to be visited on a greatest cost path from u to v, as well as the total cost of a greatest-cost path from u to v. This representation is made possible by the following observation: If vertex k is on a greatest-cost path from u to v, then a greatest-cost path from u to v can be built from the concatenation of the greatest-cost path from u to k and the greatest-cost path from k to v.
Note: I have since learned that the Least_Cost_Path_Machine also uses the same reasoning to use a similar datastructure in its implementation.
Greatest cost paths in directed acyclic graphs can be calculated for all vertex pairs (u,v) in O(|V|3) time. The results of the application of this algorithm can easily be looked up in contant time using an 'adjacency-path matrix' representation for graphs.
The souce code, as it currently stands, can be accessed here:
Greatest_Cost_Path_Machine source code