org.graphstream.algorithm

Class Dijkstra

java.lang.Object

org.graphstream.algorithm.AbstractSpanningTree

org.graphstream.algorithm.Dijkstra

All Implemented Interfaces:

Algorithm, SpanningTree

public class Dijkstra
extends AbstractSpanningTree

Dijkstra's algorithm computes the shortest paths from a given node called source to all the other nodes in a graph. It produces a shortest path tree rooted in the source. This algorithm works only for nonnegative lengths.

This implementation uses internally Fibonacci Heap, a data structure that makes it run faster for big graphs.

Length of a path

Traditionally the length of a path is defined as the sum of the lengths of its edges. This implementation allows to take into account also the "lengths" of the nodes. This is done by a parameter of type Dijkstra.Element passed in the constructors.

The lengths of individual elements (edges or/and nodes) are defined using another constructor parameter called lengthAttribute. If this parameter is null, the elements are considered to have unit lengths. In other words, the length of a path is the number of its edges or/and nodes. If the parameter is not null, the elements are supposed to have a numeric attribute named lengthAttribute used to store their lengths.

Solutions

Internal solution data is stored in attributes of the nodes of the underlying graph. The name of this attribute is another constructor parameter called resultAttribute. This name must be specified in order to avoid conflicts with existing attributes, but also to distinguish between solutions produced by different instances of this class working on the same graph (for example when computing shortest paths from two different sources). If not specified, a unique name is chosen automatically based on the hash code of the Dijkstra instance. The attributes store opaque internal objects and must not be accessed, modified or deleted. The only way to retrieve the solution is using different solution access methods.

Usage

A typical usage of this class involves the following steps:

• Instantiation using one of the constructors with appropriate parameters
• Initialization of the algorithm using AbstractSpanningTree.init(Graph)
• Computation of the shortest paths using compute()
• Retrieving the solution using different solution access methods
• Cleaning up using clear()

Note that if the graph changes after the call of compute() the computed solution is no longer valid. In this case the behavior of the different solution access methods is undefined.

Example

 Graph graph = ...;
 
 // Edge lengths are stored in an attribute called "length"
 // The length of a path is the sum of the lengths of its edges
 // The algorithm will store its results in attribute called "result"
 Dijkstra dijkstra = new Dijkstra(Dijkstra.Element.edge, "result", "length");
        
 // Compute the shortest paths in g from A to all nodes
 dijkstra.init(graph);
 dijkstra.setSource(graph.getNode("A"));
 dijkstra.compute();
        
 // Print the lengths of all the shortest paths
 for (Node node : graph)
     System.out.printf("%s->%s:%6.2f%n", dijkstra.getSource(), node, dijkstra.getPathLength(node));
        
 // Color in blue all the nodes on the shortest path form A to B
 for (Node node : dijkstra.getPathNodes(graph.getNode("B")))
     node.addAttribute("ui.style", "fill-color: blue;");
        
 // Color in red all the edges in the shortest path tree
 for (Edge edge : dijkstra.getTreeEdges())
     edge.addAttribute("ui.style", "fill-color: red;");
 
 // Print the shortest path from A to B
 System.out.println(dijkstra.getPath(graph.getNode("B"));
 
 // Build a list containing the nodes in the shortest path from A to B
 // Note that nodes are added at the beginning of the list
 // because the iterator traverses them in reverse order, from B to A
 List <Node> list1 = new ArrayList<Node>();
 for (Node node : dijkstra.getPathNodes(graph.getNode("B")))
     list1.add(0, node);
 
 // A shorter but less efficient way to do the same thing
 List<Node> list2 = dijkstra.getPath(graph.getNode("B")).getNodePath();
 

Author:

Stefan Balev

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Dijkstra.Element This enumeration is used to specify how the length of a path is computed

Constructor Summary

Constructors

Constructor and Description
Dijkstra() Constructs an instance in which the length of the path is considered to be the number of edges.
Dijkstra(Dijkstra.Element element, java.lang.String resultAttribute, java.lang.String lengthAttribute) Constructs an instance with the specified parameters.
Dijkstra(Dijkstra.Element element, java.lang.String resultAttribute, java.lang.String lengthAttribute, java.lang.String flagAttribute, java.lang.Object flagOn, java.lang.Object flagOff) Constructs an instance with the specified parameters.

Method Summary

Modifier and Type	Method and Description
void	clear() Removes the attributes used to store internal solution data in the nodes of the graph.
void	compute() Computes the shortest paths from the source node to all nodes in the graph.
java.lang.String	defaultResult()
java.lang.Iterable<org.graphstream.graph.Path>	getAllPaths(org.graphstream.graph.Node target) An iterable view of of all the shortest paths from the source node to a given target node.
java.util.stream.Stream<org.graphstream.graph.Path>	getAllPathsStream(org.graphstream.graph.Node target) This iterator traverses all the shortest paths from the source node to a given target node.
org.graphstream.graph.Edge	getEdgeFromParent(org.graphstream.graph.Node target) Returns the edge between the target node and the previous node in the shortest path from the source to the target.
org.graphstream.graph.Node	getParent(org.graphstream.graph.Node target) Returns the node preceding the target in the shortest path from the source to the target.
org.graphstream.graph.Path	getPath(org.graphstream.graph.Node target) Returns the shortest path from the source node to a given target node.
java.lang.Iterable<org.graphstream.graph.Edge>	getPathEdges(org.graphstream.graph.Node target) An iterable view of the edges on the shortest path from the source node to a given target node.
java.util.stream.Stream<org.graphstream.graph.Edge>	getPathEdgesStream(org.graphstream.graph.Node target) This iterator traverses the edges on the shortest path from the source node to a given target node.
double	getPathLength(org.graphstream.graph.Node target) Returns the length of the shortest path from the source node to a given target node.
java.lang.Iterable<org.graphstream.graph.Node>	getPathNodes(org.graphstream.graph.Node target) An iterable view of the nodes on the shortest path from the source node to a given target node.
java.util.stream.Stream<org.graphstream.graph.Node>	getPathNodesStream(org.graphstream.graph.Node target) This iterator traverses the nodes on the shortest path from the source node to a given target node.
<T extends org.graphstream.graph.Node> T	getSource() Dijkstra's algorithm computes shortest paths from a given source node to all nodes in a graph.
java.util.stream.Stream<org.graphstream.graph.Edge>	getTreeEdgesStream() Dijkstra's algorithm produces a shortest path tree rooted in the source node.
double	getTreeLength() Dijkstra's algorithm produces a shortest path tree rooted in the source node.
void	setSource(org.graphstream.graph.Node source) Dijkstra's algorithm computes shortest paths from a given source node to all nodes in a graph.
void	setSource(java.lang.String source)
void	setTarget(java.lang.String target)

Methods inherited from class org.graphstream.algorithm.AbstractSpanningTree

getFlagAttribute, getFlagOff, getFlagOn, getTreeEdges, init, setFlagAttribute, setFlagOff, setFlagOn

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Dijkstra

public Dijkstra(Dijkstra.Element element,
                java.lang.String resultAttribute,
                java.lang.String lengthAttribute)

Constructs an instance with the specified parameters. The edges of the shortest path tree are not tagged.

Parameters:

element - Graph elements (edges or/and nodes) used to compute the path lengths. If null, the length of the path is computed using edges.

resultAttribute - Attribute name used to store internal solution data in the nodes of the graph. If null, a unique name is chosen automatically.

lengthAttribute - Attribute name used to define individual element lengths. If null the length of the elements is considered to be one.

Dijkstra

public Dijkstra()

Constructs an instance in which the length of the path is considered to be the number of edges. Unique result attribute is chosen automatically. The edges of the shortest path tree are not tagged.

Dijkstra

public Dijkstra(Dijkstra.Element element,
                java.lang.String resultAttribute,
                java.lang.String lengthAttribute,
                java.lang.String flagAttribute,
                java.lang.Object flagOn,
                java.lang.Object flagOff)

Constructs an instance with the specified parameters.

Parameters:

element - Graph elements (edges or/and nodes) used to compute the path lengths. If null, the length of the path is computed using edges.

resultAttribute - Attribute name used to store internal solution data in the nodes of the graph. If null, a unique name is chosen automatically.

lengthAttribute - Attribute name used to define individual element lengths. If null the length of the elements is considered to be one.

flagAttribute - attribute used to set if an edge is in the spanning tree

flagOn - value of the flagAttribute if edge is in the spanning tree

flagOff - value of the flagAttribute if edge is not in the spanning tree

Method Detail

getSource

public <T extends org.graphstream.graph.Node> T getSource()

Dijkstra's algorithm computes shortest paths from a given source node to all nodes in a graph. This method returns the source node.

Returns:

the source node

See Also:

setSource(Node)

setSource

public void setSource(org.graphstream.graph.Node source)

Dijkstra's algorithm computes shortest paths from a given source node to all nodes in a graph. This method sets the source node.

Parameters:

source - The new source node.

See Also:

getSource()

setSource

public void setSource(java.lang.String source)

setTarget

public void setTarget(java.lang.String target)

clear

public void clear()

Removes the attributes used to store internal solution data in the nodes of the graph. Use this method to free memory. Solution access methods must not be used after calling this method.

Specified by:

clear in interface SpanningTree

Overrides:

clear in class AbstractSpanningTree

compute

public void compute()

Computes the shortest paths from the source node to all nodes in the graph.

Specified by:

compute in interface Algorithm

Overrides:

compute in class AbstractSpanningTree

Throws:

java.lang.IllegalStateException - if AbstractSpanningTree.init(Graph) or setSource(Node) have not been called before or if elements with negative lengths are discovered.

See Also:

Algorithm.compute()

Computational Complexity:

O(m + nlogn) where m is the number of edges and n is the number of nodes in the graph.

getPathLength

public double getPathLength(org.graphstream.graph.Node target)

Returns the length of the shortest path from the source node to a given target node.

Parameters:

target - A node

Returns:

the length of the shortest path or Double.POSITIVE_INFINITY if there is no path from the source to the target

Computational Complexity:

O(1)

getTreeLength

public double getTreeLength()

Dijkstra's algorithm produces a shortest path tree rooted in the source node. This method returns the total length of the tree.

Returns:

the length of the shortest path tree

Computational Complexity:

O(n) where n is the number of nodes is the graph.

getEdgeFromParent

public org.graphstream.graph.Edge getEdgeFromParent(org.graphstream.graph.Node target)

Returns the edge between the target node and the previous node in the shortest path from the source to the target. This is also the edge connecting the target to its parent in the shortest path tree.

Parameters:

target - a node

Returns:

the edge between the target and its predecessor in the shortest path, null if there is no path from the source to the target or if the target and the source are the same node.

See Also:

getParent(Node)

Computational Complexity:

O(1)

getParent

public org.graphstream.graph.Node getParent(org.graphstream.graph.Node target)

Returns the node preceding the target in the shortest path from the source to the target. This node is the parent of the target in the shortest path tree.

Parameters:

target - a node

Returns:

the predecessor of the target in the shortest path, null if there is no path from the source to the target or if the target and the source are the same node.

See Also:

getEdgeFromParent(Node)

Computational Complexity:

O(1)

getPathNodesStream

public java.util.stream.Stream<org.graphstream.graph.Node> getPathNodesStream(org.graphstream.graph.Node target)

This iterator traverses the nodes on the shortest path from the source node to a given target node. The nodes are traversed in reverse order: the target node first, then its predecessor, ... and finally the source node. If there is no path from the source to the target, no nodes are traversed. This iterator does not support Iterator.remove().

Parameters:

target - a node

Returns:

an iterator on the nodes of the shortest path from the source to the target

See Also:

getPathNodes(Node)

Computational Complexity:

Each call of Iterator.next() of this iterator takes O(1) time

getPathNodes

public java.lang.Iterable<org.graphstream.graph.Node> getPathNodes(org.graphstream.graph.Node target)

An iterable view of the nodes on the shortest path from the source node to a given target node. Uses getPathNodesStream(Node).

Parameters:

target - a node

Returns:

an iterable view of the nodes on the shortest path from the source to the target

See Also:

getPathNodesStream(Node)

getPathEdgesStream

public java.util.stream.Stream<org.graphstream.graph.Edge> getPathEdgesStream(org.graphstream.graph.Node target)

This iterator traverses the edges on the shortest path from the source node to a given target node. The edges are traversed in reverse order: first the edge between the target and its predecessor, ... and finally the edge between the source end its successor. If there is no path from the source to the target or if he source and the target are the same node, no edges are traversed. This iterator does not support Iterator.remove().

Parameters:

target - a node

Returns:

an iterator on the edges of the shortest path from the source to the target

See Also:

getPathEdges(Node)

Computational Complexity:

Each call of Iterator.next() of this iterator takes O(1) time

getPathEdges

public java.lang.Iterable<org.graphstream.graph.Edge> getPathEdges(org.graphstream.graph.Node target)

An iterable view of the edges on the shortest path from the source node to a given target node. Uses getPathEdgesStream(Node).

Parameters:

target - a node

Returns:

an iterable view of the edges on the shortest path from the source to the target

See Also:

getPathEdgesStream(Node)

getAllPathsStream

public java.util.stream.Stream<org.graphstream.graph.Path> getAllPathsStream(org.graphstream.graph.Node target)

This iterator traverses all the shortest paths from the source node to a given target node. If there is more than one shortest paths between the source and the target, other solution access methods choose one of them (the one from the shortest path tree). This iterator can be used if one needs to know all the paths. Each call to Iterator.next() method of this iterator returns a shortest path in the form of Path object. This iterator does not support Iterator.remove().

Parameters:

target - a node

Returns:

an iterator on all the shortest paths from the source to the target

See Also:

getAllPaths(Node)

Computational Complexity:

Each call of Iterator.next() of this iterator takes O(m) time in the worst case, where m is the number of edges in the graph

getAllPaths

public java.lang.Iterable<org.graphstream.graph.Path> getAllPaths(org.graphstream.graph.Node target)

An iterable view of of all the shortest paths from the source node to a given target node. Uses getAllPathsStream(Node)

Parameters:

target - a node

Returns:

an iterable view of all the shortest paths from the source to the target

See Also:

getAllPathsStream(Node)

getTreeEdgesStream

public java.util.stream.Stream<org.graphstream.graph.Edge> getTreeEdgesStream()

Dijkstra's algorithm produces a shortest path tree rooted in the source node. This iterator traverses the edges of this tree. The edges are traversed in no particular order.

Specified by:

getTreeEdgesStream in interface SpanningTree

Specified by:

getTreeEdgesStream in class AbstractSpanningTree

Returns:

an iterator on the edges of the shortest path tree

See Also:

AbstractSpanningTree.getTreeEdges()

Computational Complexity:

Each call of Iterator.next() of this iterator takes O(1) time

getPath

public org.graphstream.graph.Path getPath(org.graphstream.graph.Node target)

Returns the shortest path from the source node to a given target node. If there is no path from the source to the target returns an empty path. This method constructs a Path object which consumes heap memory proportional to the number of edges and nodes in the path. When possible, prefer using getPathNodes(Node) and getPathEdges(Node) which are more memory- and time-efficient.

Parameters:

target - a node

Returns:

the shortest path from the source to the target

Computational Complexity:

O(p) where p is the number of the nodes in the path

defaultResult

public java.lang.String defaultResult()