The starred algorithms are finished, and the other algorithms are ranked in order of urgency. Hopefully these rankings will not be necessary after July 31st, 1996.
Priority | Algorithm/Property | input | output | attr's & algs used |
2 | Biconnected | Undir. | Set<Set<Vertex*> > | DFS - back |
Components | G | DFS - low | ||
DFS - discovery_time | ||||
5 | Bipartite Matching | Undir. | Set<Edge*> | weight |
G | Ford-Fulkerson - flow | |||
* | Breadth-First Search | G,v | Sequence<Vertex*> | color |
distance | ||||
??? | ||||
* | Depth-First Search | G | Sequence<Vertex*> | color |
starttime | ||||
finishtime | ||||
back | ||||
low | ||||
pred | ||||
3 | Dijkstra's Single | G, v | Set<double> | weight |
Source Shortest | distance | |||
Paths | pred | |||
4 | Ford-Fulkerson | Network | double | flow |
Maximum Flow | s, t | capacity | ||
partition | ||||
7* | Floyd-Warshall | G | Matrix<double> | weight |
All Pairs Shortest | distance | |||
Paths | pred | |||
* | Kruskal's MST | G | Set<Edge*> | weight |
mark | ||||
parent | ||||
pred | ||||
6 | Prim's MST | G | Set<Edge*> | weight |
key | ||||
pred | ||||
1 | Strongly-Connected | Digraph | Set<Set<Vertex*> > | DFS - mark |
Components | DFS - finishtime | |||
* | TopSort | DAG | Sequence<Vertex*> | DFS - finishtime |