public class APSP extends SinkAdapter implements Algorithm
This class implements the FloydWarshall all pair shortest path algorithm where the shortest path from any node to any destination in a given weighted graph (with positive or negative edge weights) is performed.
The computational complexity is O(n^3), this may seems a very large, however this algorithm may perform better than running several Dijkstra on all node pairs of the graph (that would be of complexity O(n^2 log(n))) when the graph becomes dense.
Note that all the possible paths are not explicitly computed and stored. Instead, the weight is computed and a data structure similar to network routing tables is created directly on the graph. This allows a linear reconstruction of the wanted paths, on demand, minimizing the memory consumption.
For each node of the graph, a APSP.APSPInfo
attribute is stored. The name of
this attribute is APSP.APSPInfo.ATTRIBUTE_NAME
.
The implementation of this algorithm is made with two main classes that reflect the two main steps of the algorithm that are:
For the first step (the real shortest path computation) you need to create an APSP object with 3 parameters:
Those 3 parameters can be set in a ran in the constructor
APSP(Graph,String,boolean)
or by using separated setters (see example
below).
Then the actual computation takes place by calling the compute()
method
which is implemented from the "Algorithm" interface. This method actually
does the computation.
Secondly, when the weights are computed, one can retrieve paths with the help of another class: "APSPInfo". Such object are stored in each node and hold routing tables that can help rebuild shortest paths.
Retrieving an "APSPInfo" instance from a node is done for instance for a node of id "F", like this::
APSPInfo info = graph.getNode("F").getAttribute(APSPInfo.ATTRIBUTE_NAME);
then the shortest path from a "F" to another node (say "A") is given by::
info.getShortestPathTo("A")
import java.io.ByteArrayInputStream; import java.io.IOException; import org.graphstream.algorithm.APSP; import org.graphstream.algorithm.APSP.APSPInfo; import org.graphstream.graph.Graph; import org.graphstream.graph.implementations.DefaultGraph; import org.graphstream.stream.file.FileSourceDGS; public class APSPTest { // B(1)C // / \ // (1) (10) // / \ // A F // \ / // (1) (1) // \ / // D(1)E static String my_graph = "DGS004\n" + "my 0 0\n" + "an A \n" + "an B \n" + "an C \n" + "an D \n" + "an E \n" + "an F \n" + "ae AB A B weight:1 \n" + "ae AD A D weight:1 \n" + "ae BC B C weight:1 \n" + "ae CF C F weight:10 \n" + "ae DE D E weight:1 \n" + "ae EF E F weight:1 \n"; public static void main(String[] args) throws IOException { Graph graph = new DefaultGraph("APSP Test"); ByteArrayInputStream bs = new ByteArrayInputStream(my_graph.getBytes()); FileSourceDGS source = new FileSourceDGS(); source.addSink(graph); source.readAll(bs); APSP apsp = new APSP(); apsp.init(graph); // registering apsp as a sink for the graph apsp.setDirected(false); // undirected graph apsp.setWeightAttributeName("weight"); // ensure that the attribute name // used is "weight" apsp.compute(); // the method that actually computes shortest paths APSPInfo info = graph.getNode("F") .getAttribute(APSPInfo.ATTRIBUTE_NAME); System.out.println(info.getShortestPathTo("A")); } }
This algorithm can use directed graphs and only compute paths according to
this direction. You can choose to ignore edge orientation by calling
setDirected(boolean)
method with "false" as value (or use the
appropriate constructor).
You can also specify that edges have "weights" or "importance" that value
them. You store these values as attributes on the edges. The default name for
these attributes is "weight" but you can specify it using the
setWeightAttributeName(String)
method (or by using the appropriate
constructor). The weight attribute must contain an object that implements
java.lang.Number.
All the shortest paths are not literally stored in the graph because it would require to much memory to do so. Instead, only useful data, allowing the fast reconstruction of any path, is stored. The storage approach is alike network routing tables where each node maintains a list of all possible targets linked with the next hop neighbor to go through.
Technically, on each node, for each target, we only store the target node name and if the path is made of more than one edge, one "passby" node. As all shortest path that is made of more than one edge is necessarily made of two other shortest paths, it is easy to reconstruct a shortest path between two arbitrary nodes knowing only a passby node. This approach still stores a lot of data on the graph, however far less than if we stored complete paths.
Modifier and Type  Class and Description 

static class 
APSP.APSPInfo
Information stored on each node of the graph giving the length of the
shortest paths toward each other node.

static interface 
APSP.Progress
Interface allowing to be notified of the algorithm progress.

static class 
APSP.TargetPath
Description of a path to a target node.

Modifier and Type  Field and Description 

protected boolean 
directed
If false, do not take edge orientation into account.

protected Graph 
graph
The graph to use.

protected boolean 
graphChanged
Does the graph changed between two calls to
compute() ?. 
protected APSP.Progress 
progress 
protected String 
weightAttributeName
Name of the attribute on each edge indicating the weight of the edge.

Constructor and Description 

APSP() 
APSP(Graph graph)
New APSP algorithm working on the given graph.

APSP(Graph graph,
String weightAttributeName,
boolean directed)
New APSP algorithm working on the given graph.

Modifier and Type  Method and Description 

void 
compute()
Run the APSP computation.

void 
edgeAdded(String graphId,
long timeId,
String edgeId,
String fromNodeId,
String toNodeId,
boolean directed)
An edge was inserted in graph.

void 
edgeAttributeAdded(String graphId,
long timeId,
String edgeId,
String attribute,
Object value)
A edge attribute was added.

void 
edgeAttributeChanged(String graphId,
long timeId,
String edgeId,
String attribute,
Object oldValue,
Object value)
A edge attribute was changed.

void 
edgeRemoved(String graphId,
long timeId,
String edgeId)
An edge of graph was removed.The nodes the edge connects may already have
been removed from the graph.

Graph 
getGraph()
Access to the working graph.

String 
getWeightAttributeName()
The name of the attribute to use for retrieving edge weights.

void 
graphCleared(String graphId,
long timeId)
The whole graph was cleared.

void 
init(Graph graph)
Initialization of the algorithm.

boolean 
isDirected()
True if the algorithm must take edge orientation into account.

void 
nodeAdded(String graphId,
long timeId,
String nodeId)
A node was inserted in the given graph.

void 
nodeRemoved(String graphId,
long timeId,
String nodeId)
A node was removed from the graph.

void 
registerProgressIndicator(APSP.Progress progress)
Specify an interface to call in order to indicate the algorithm progress.

void 
setDirected(boolean on)
Choose to use or ignore edge orientation.

void 
setWeightAttributeName(String name)
Choose the name of the attribute used to retrieve edge weights.

edgeAttributeRemoved, graphAttributeAdded, graphAttributeChanged, graphAttributeRemoved, nodeAttributeAdded, nodeAttributeChanged, nodeAttributeRemoved, stepBegins
protected boolean graphChanged
compute()
?.protected boolean directed
protected String weightAttributeName
protected APSP.Progress progress
public APSP()
public APSP(Graph graph)
graph
 The graph to use.public APSP(Graph graph, String weightAttributeName, boolean directed)
graph
 The graph to use.weightAttributeName
 The edge weight attribute name.directed
 If false, edge orientation is ignored.public boolean isDirected()
public String getWeightAttributeName()
public void setDirected(boolean on)
on
 If true edge orientation is used.bpublic void registerProgressIndicator(APSP.Progress progress)
public void setWeightAttributeName(String name)
name
 The attribute name.public void init(Graph graph)
Algorithm
Algorithm.compute()
method to initialize or reset the algorithm according
to the new given graph.init
in interface Algorithm
graph
 The graph this algorithm is using.Algorithm.init(Graph)
public void compute()
APSP.APSPInfo
. These attributes contain
a map of length toward each other attainable node. The attribute name is
given by APSP.APSPInfo.ATTRIBUTE_NAME
.compute
in interface Algorithm
Algorithm.init(Graph)
public void nodeAdded(String graphId, long timeId, String nodeId)
ElementSink
nodeAdded
in interface ElementSink
nodeAdded
in class SinkAdapter
graphId
 Identifier of the graph where the node was added.nodeId
 Identifier of the added node.public void nodeRemoved(String graphId, long timeId, String nodeId)
ElementSink
nodeRemoved
in interface ElementSink
nodeRemoved
in class SinkAdapter
graphId
 Identifier of the graph where the node will be removed.nodeId
 Identifier of the removed node.public void edgeAdded(String graphId, long timeId, String edgeId, String fromNodeId, String toNodeId, boolean directed)
ElementSink
edgeAdded
in interface ElementSink
edgeAdded
in class SinkAdapter
graphId
 Identifier of the graph where the edge was added.edgeId
 Identifier of the added edge.fromNodeId
 Identifier of the first node of the edge.toNodeId
 Identifier of the second node of the edge.directed
 If true, the edge is directed.public void edgeRemoved(String graphId, long timeId, String edgeId)
ElementSink
edgeRemoved
in interface ElementSink
edgeRemoved
in class SinkAdapter
graphId
 The graph where the edge will be removed.edgeId
 The edge that will be removed.public void graphCleared(String graphId, long timeId)
ElementSink
graphCleared
in interface ElementSink
graphCleared
in class SinkAdapter
graphId
 The graph cleared.public void edgeAttributeAdded(String graphId, long timeId, String edgeId, String attribute, Object value)
AttributeSink
edgeAttributeAdded
in interface AttributeSink
edgeAttributeAdded
in class SinkAdapter
graphId
 Identifier of the graph where the change occurred.edgeId
 Identifier of the edge whose attribute changed.attribute
 The attribute name.value
 The attribute new value.public void edgeAttributeChanged(String graphId, long timeId, String edgeId, String attribute, Object oldValue, Object value)
AttributeSink
edgeAttributeChanged
in interface AttributeSink
edgeAttributeChanged
in class SinkAdapter
graphId
 Identifier of the graph where the change occurred.edgeId
 Identifier of the edge whose attribute changed.attribute
 The attribute name.oldValue
 The attribute old value.value
 The attribute new value.WebARTS Library Licensed Under the GNU  General Public License. Other Libraries licensed under their respective Open Source Licenses