Package net.walend.measured

This package contains a kit for working with measured paths on directed graphs.

See:
Description

Interface Summary

CEPathMeter	PathMeters measure the cost to enter and leave nodes and cross edges.
GEPathMeter	PathMeters measure the cost to enter and leave nodes and cross edges.
MeasuredCEPath
MeasuredGEPath
PathMeter	Deprecated. Use CEPathMeter.
ShortestCEDistances	This interface describes methods to find the shortest distances on a CE digraph.
ShortestCEPaths	This interface is a DigraphOfCEPaths that contains the shortest paths in available in the base digraph as measured by a PathMeter.
ShortestGEDistances	This interface describes methods to find the shortest distances on a GE digraph.
ShortestGEPaths	This interface is a DigraphOfGEPaths that contains the shortest paths in available in the base digraph as measured by a PathMeter.
TieBreaker	TieBreakers break ties when finding paths within CEPathsFromShortestDistances and GEPathsFromShortestDistances.

Class Summary

AbstractShortestCEDistances	AbstractShortestCEDistances contains a 2D array of distances between nodes in a directed graph.
AbstractShortestCEPaths	AbstractShortestCEPaths is a CEDigraph containing the nodes from the base digraph and edges that are the shortest paths between some pairs of nodes.
AbstractShortestGEDistances	AbstractShortestGEDistances contains a 2D array of distances between nodes in a directed graph.
AbstractShortestGEPaths	AbstractShortestGEPaths is a CEDigraph containing the nodes from the base digraph and edges that are the shortest paths between some pairs of nodes.
BellmanFordTest	Deprecated. Use CEBellmanFordTest
CEBellmanFordTest	Performs the Bellman-Ford test for a given digraph and pathmeter.
CEBellmanFordTest.BFCEDigraph	This is simply a wrapper of a CEDigraph that has a BFNode and BFEdges from that node to all nodes.
CEBellmanFordTest.BFEdge	A marker object used in the bellman-ford algorithm.
CEBellmanFordTest.BFNode	A marker object used in the bellman-ford algorithm.
CEBellmanFordTest.BFPathMeter	A special path meter for the Bellman Ford algorithm that wraps another path meter.
CEPathsFromShortestDistances	CEPathsFromShortestDistances wraps a ShortestCEDistances object to provide a full ShortestCEPaths interface.
CEPathTraverser	PathTraverser traverses a Path with an iterator and measures its length using a PathMeter.
DijkstraShortestCEDistances	DijkstraShortestCEDistances is an abstract class that holds Dijkstra's algorithm.
DijkstraShortestCEPaths	DijkstraShortestCEPaths is an abstract class that contains Dijkstra's algorithm for shortest paths, plus supporting code for solutions with nodes must go inside a hash table.
DijkstraShortestGEDistances	DijkstraShortestGEDistances is an abstract class that holds Dijkstra's algorithm.
DijkstraShortestGEPaths	DijkstraShortestGEPaths is an abstract class that contains Dijkstra's algorithm for shortest paths, plus supporting code for solutions with nodes must go inside a hash table.
FloydWarshallShortestCEDistances	FloydWarshallShortestCEDistances uses the very simple Floyd-Warshall algorithm to find the shortest distances.
FloydWarshallShortestCEPaths	FloydWarshallShortestCEPaths uses the very simple Floyd-Warshall algorithm to find the shortest paths.
FloydWarshallShortestGEDistances	FloydWarshallShortestGEDistances uses the very simple Floyd-Warshall algorithm to find the shortest distances.
FloydWarshallShortestGEPaths	FloydWarshallShortestGEPaths uses the very simple Floyd-Warshall algorithm to find the shortest paths.
GEBellmanFordTest	Performs the Bellman-Ford test for a given digraph and pathmeter.
GEBellmanFordTest.BFGEDigraph	This is simply a wrapper of a GEDigraph that has a BFNode and BFEdges from that node to all nodes.
GEBellmanFordTest.BFNode	A marker object used in the bellman-ford algorithm.
GEBellmanFordTest.BFPathMeter	A special path meter for the Bellman Ford algorithm that wraps another path meter.
GEPathTraverser	PathTraverser traverses a GEPath with an iterator and measures its length using a PathMeter.
JITShortestCEDistances	JITShortestCEDistances is an implementation of ShortestCEDistances that uses Dijkstra's algorithm to find the shortest distances just in time.
JITShortestCEPaths	JITShortestCEPaths is an implementation of ShortestCEPaths that uses Dijkstra's algorithm to find the shortest paths just in time.
JITShortestGEDistances	JITShortestGEDistances is an implementation of ShortestGEDistances that uses Dijkstra's algorithm to find the shortest distances just in time.
JITShortestGEPaths	JITShortestGEPaths is an implementation of ShortestGEPaths that uses Dijkstra's algorithm to find the shortest paths just in time.
JohnsonShortestCEDistances	JohnsonShortestCEDistances uses Johnson's algorithm to find the shortest distances during construction.
JohnsonShortestCEPaths	JohnsonShortestCEPaths uses Johnson's algorithm to find the shortest paths during construction.
JohnsonShortestGEDistances	JohnsonShortestGEDistances uses Johnson's algorithm to find the shortest distances during construction.
JohnsonShortestGEPaths	JohnsonShortestGEPaths uses Johnson's algorithm to find the shortest paths during construction.
PathTraverser	Deprecated. Use CEPathTraverser
SimpleCEPathMeter	This simple path meter returns 1 for the cost to cross an edge and 0 for everything else.
SimpleGEPathMeter	This simple path meter returns 1 for the cost to cross an edge and 0 for everything else.
SimplePathMeter	Deprecated. Use SimpleCEPathMeter.

Exception Summary

CENegativeWeightCycleException	An exception thrown by the Bellman-Ford test.
GENegativeWeightCycleException	An exception thrown by the Bellman-Ford test.
MeasuredPathException
NegativeWeightCycleException	An exception thrown by the Bellman-Ford test.

Package net.walend.measured Description

This package contains a kit for working with measured paths on directed graphs.

The main interface, PathMeter, measures the cost to travers from one node accross and edge to another node.

PathTraverser actually measures the whole path.

The MeasuredCEPath interface includes a method to get the lenght of the path.

MeasuredCEPaths defines an interface for CEDigraphs where nodes are the same nodes as in another CEDigraph, and edges are measured paths between those edges.

Floyd-WarshallShortestPaths uses the Floyd-Warshall algorithm in its constructor to compute the shortest paths. It is O(n^3) on IndexedCEDigraphs.

JohnsonShortestPaths uses Johnson's algorithm to compute the shortest paths. It should be O(n^2 ln(n) + ne) on LMCEDigraphs.

DijkstraShortestPaths uses Dijkstra's algorithm to compute only the shrotest paths from a given node to all other nodes. It should be O(n ln(n) + e) on LMCEDigraphs.

The constructors do throw NegativeWeightCycleExceptions if the results contain a negative weight cycle.