org.graphstream.algorithm

Class BellmanFord

java.lang.Object

org.graphstream.algorithm.BellmanFord

All Implemented Interfaces:

Algorithm

public class BellmanFord
extends Object
implements Algorithm

Implementation of the Bellman-Ford algorithm that computes single-source shortest paths in a weighted digraph

The Bellman-Ford algorithm computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). Dijkstra's algorithm accomplishes the same problem with a lower running time, but requires edge weights to be non-negative. Thus, Bellman-Ford is usually used only when there are negative edge weights (from the Wikipedia).

Example

 import java.io.IOException;
 import java.io.StringReader;
 
 import org.graphstream.algorithm.BellmanFord;
 import org.graphstream.graph.Graph;
 import org.graphstream.graph.implementations.DefaultGraph;
 import org.graphstream.stream.file.FileSourceDGS;
 
 public class BellmanFordTest {
        
        //     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("Bellman-Ford Test");
                StringReader reader  = new StringReader(my_graph);
                
                FileSourceDGS source = new FileSourceDGS();
                source.addSink(graph);
                source.readAll(reader);
 
                BellmanFord bf = new BellmanFord("weight","A");
                bf.init(graph);
                bf.compute();
 
                System.out.println(bf.getShortestPath(graph.getNode("F")));
        }
 }
 

Warning

This Implementation is only a stub. For the moment only attributes located on the edges are supported. If you need more features, consider using the Dijkstra implementation. If you really need that algorithm, please contact the team members through the mailing list.

Author:

Antoine Dutot, Yoann Pigné

Computational Complexity :

O(VxE) time, where V and E are the number of vertices and edges respectively.

Scientific Reference :

Bellman, Richard "On a routing problem", Quarterly of Applied Mathematics 16: 87–90. 1958.

Constructor Summary

Constructors

Constructor and Description
BellmanFord(String attribute) Build a new BellmanFord algorithm giving the name of the weight attribute for edges.
BellmanFord(String attribute, String sourceNode) Same that BellmanFord(String) but setting the id of the source node.

Method Summary

Methods

Modifier and Type	Method and Description
void	compute() Run the algorithm.
String	getIdentifier() The unique identifier of this instance.
List<org.graphstream.graph.Path>	getPathSetShortestPaths(org.graphstream.graph.Node end) Constructs all the possible shortest paths from the source node to the destination (end).
org.graphstream.graph.Path	getShortestPath(org.graphstream.graph.Node target) Returns the shortest path between the source node and one given target.
double	getShortestPathValue(org.graphstream.graph.Node target) Returns the value of the shortest path between the source node and the given target according to the attribute specified in the constructor.
String	getSource() Get the id of node used as source.
void	init(org.graphstream.graph.Graph graph) Initialization of the algorithm.
void	setIdentifier(String identifier) Set the unique identifier for this instance.
void	setSource(String nodeId) Set the id of the node used as source.

Methods inherited from class java.lang.Object

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

Constructor Detail

BellmanFord

public BellmanFord(String attribute)

Build a new BellmanFord algorithm giving the name of the weight attribute for edges.

Parameters:

attribute - weight attribute of edges

BellmanFord

public BellmanFord(String attribute,
           String sourceNode)

Same that BellmanFord(String) but setting the id of the source node.

Parameters:

attribute - weight attribute of edges

sourceNode - id of the source node

Method Detail

setSource

public void setSource(String nodeId)

Set the id of the node used as source.

Parameters:

nodeId - id of the source node

getSource

public String getSource()

Get the id of node used as source.

Returns:

id of the source node

getPathSetShortestPaths

public List<org.graphstream.graph.Path> getPathSetShortestPaths(org.graphstream.graph.Node end)

Constructs all the possible shortest paths from the source node to the destination (end). Warning: this construction is VERY HEAVY !

Parameters:

end - The destination to which shortest paths are computed.

Returns:

a list of shortest paths given with Path objects.

init

public void init(org.graphstream.graph.Graph graph)

Description copied from interface: Algorithm

Initialization of the algorithm. This method has to be called before the Algorithm.compute() method to initialize or reset the algorithm according to the new given graph.

Specified by:

init in interface Algorithm

Parameters:

graph - The graph this algorithm is using.

setIdentifier

public void setIdentifier(String identifier)

Set the unique identifier for this instance.

Parameters:

identifier - the unique identifier to set

See Also:

getIdentifier()

getIdentifier

public String getIdentifier()

The unique identifier of this instance. Used to tag attributes in the graph.

Returns:

the unique identifier of this graph.

getShortestPathValue

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

Returns the value of the shortest path between the source node and the given target according to the attribute specified in the constructor. If target is not in the same connected component as the source node, then the method returns Double.POSITIVE_INFINITY (Infinity).

Parameters:

target - The endpoint of the path to compute from the source node given in the constructor.

Returns:

A numerical value that represent the distance of the shortest path.

getShortestPath

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

Returns the shortest path between the source node and one given target. If multiple shortest paths exist, one of them is returned at random.

Parameters:

target - the target of the shortest path starting at the source node given in the constructor.

Returns:

A Path object that constrains the list of nodes and edges that constitute it.

compute

public void compute()

Description copied from interface: Algorithm

Run the algorithm. The Algorithm.init(Graph) method has to be called before computing.

Specified by:

compute in interface Algorithm

See Also:

Algorithm.init(Graph)