BellmanFord

java.lang.Object
- org.graphstream.algorithm.BellmanFord

All Implemented Interfaces:: Algorithm

public class BellmanFord
extends java.lang.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.

Field Summary

Fields
Modifier and Type Field and Description

static java.lang.String DEFAULT_WEIGHT_ATTRIBUTE
Default weight attribute

Fields
Modifier and Type	Field and Description
`static java.lang.String`	`DEFAULT_WEIGHT_ATTRIBUTE` Default weight attribute

Constructor Summary

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

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`compute()` Run the algorithm.
`java.lang.String`	`defaultResult()`
`java.lang.String`	`getIdentifier()` The unique identifier of this instance.
`java.util.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.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.
`java.lang.String`	`getSource()` Get the id of node used as source.
`void`	`init(org.graphstream.graph.Graph graph)` Initialization of the algorithm.
`void`	`setIdentifier(java.lang.String identifier)` Set the unique identifier for this instance.
`void`	`setSource(java.lang.String nodeId)` Set the id of the node used as source.
`void`	`setTarget(java.lang.String target)`
`void`	`setWeightAttribute(java.lang.String weightAttribute)`

Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - DEFAULT_WEIGHT_ATTRIBUTE
```
public static final java.lang.String DEFAULT_WEIGHT_ATTRIBUTE
```
    Default weight attribute
    
    See Also:
    
    Constant Field Values
- Constructor Detail
  - BellmanFord
```
public BellmanFord()
```
    Build a new BellmanFord algorithm with default parameters.
  - BellmanFord
```
public BellmanFord(java.lang.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(java.lang.String attribute,
                   java.lang.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(java.lang.String nodeId)
```
    Set the id of the node used as source.
    
    Parameters:
    
    nodeId - id of the source node
  - setTarget
```
public void setTarget(java.lang.String target)
```
  - setWeightAttribute
```
public void setWeightAttribute(java.lang.String weightAttribute)
```
  - getSource
```
public java.lang.String getSource()
```
    Get the id of node used as source.
    
    Returns:
    
    id of the source node
  - getPathSetShortestPaths
```
public java.util.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(java.lang.String identifier)
```
    Set the unique identifier for this instance.
    
    Parameters:
    
    identifier - the unique identifier to set
    
    See Also:
    
    getIdentifier()
  - getIdentifier
```
public java.lang.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.
  - getShortestPath
```
public org.graphstream.graph.Path getShortestPath()
```
    See Also:
    
    getShortestPath(Node target)
  - defaultResult
```
public java.lang.String defaultResult()
```
  - 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)

Class BellmanFord

Example

Warning

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

DEFAULT_WEIGHT_ATTRIBUTE

Constructor Detail

BellmanFord

BellmanFord

BellmanFord

Method Detail

setSource

setTarget

setWeightAttribute

getSource

getPathSetShortestPaths

init

setIdentifier

getIdentifier

getShortestPathValue

getShortestPath

getShortestPath

defaultResult

compute