org.graphstream.algorithm.networksimplex

Class DynamicOneToAllShortestPath

java.lang.Object

org.graphstream.stream.SinkAdapter

org.graphstream.algorithm.networksimplex.NetworkSimplex

org.graphstream.algorithm.networksimplex.DynamicOneToAllShortestPath

All Implemented Interfaces:

Algorithm, DynamicAlgorithm, org.graphstream.stream.AttributeSink, org.graphstream.stream.ElementSink, org.graphstream.stream.Sink

public class DynamicOneToAllShortestPath
extends NetworkSimplex

Nested Class Summary

Nested classes/interfaces inherited from class org.graphstream.algorithm.networksimplex.NetworkSimplex

NetworkSimplex.ArcStatus, NetworkSimplex.PricingStrategy, NetworkSimplex.SolutionStatus

Field Summary

Fields inherited from class org.graphstream.algorithm.networksimplex.NetworkSimplex

PREFIX

Constructor Summary

Constructors

Constructor and Description
DynamicOneToAllShortestPath(String costName)

Method Summary

Methods

Modifier and Type	Method and Description
org.graphstream.graph.Path	getPath(org.graphstream.graph.Node target) Returns the shortest path from the source node to a given target node.
<T extends org.graphstream.graph.Edge> Iterable<T>	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.
<T extends org.graphstream.graph.Edge> Iterator<T>	getPathEdgesIterator(org.graphstream.graph.Node target) This iterator traverses the edges on the shortest path from the source node to a given target node.
long	getPathLength(org.graphstream.graph.Node node)
<T extends org.graphstream.graph.Node> Iterable<T>	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.
<T extends org.graphstream.graph.Node> Iterator<T>	getPathNodesIterator(org.graphstream.graph.Node target) This iterator traverses the nodes on the shortest path from the source node to a given target node.
String	getSource()
void	init(org.graphstream.graph.Graph graph) Initialization of the algorithm.
void	nodeAdded(String sourceId, long timeId, String nodeId)
void	nodeRemoved(String sourceId, long timeId, String nodeId)
void	setSource(String sourceId)

Methods inherited from class org.graphstream.algorithm.networksimplex.NetworkSimplex

compute, edgeAdded, edgeAttributeAdded, edgeAttributeChanged, edgeAttributeRemoved, edgeRemoved, getCapacityName, getCostName, getEdgeFromParent, getFlow, getFlow, getGraph, getInfeasibility, getNetworkBalance, getParent, getPricingStrategy, getSolutionCost, getSolutionInfeasibility, getSolutionStatus, getStatus, getStatus, getSupplyName, graphCleared, nodeAttributeAdded, nodeAttributeChanged, nodeAttributeRemoved, printBFS, setAnimationDelay, setLogFrequency, setLogStream, setPricingStrategy, setUIClasses, terminate

Methods inherited from class org.graphstream.stream.SinkAdapter

graphAttributeAdded, graphAttributeChanged, graphAttributeRemoved, stepBegins

Methods inherited from class java.lang.Object

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

Constructor Detail

DynamicOneToAllShortestPath

public DynamicOneToAllShortestPath(String costName)

Method Detail

getSource

public String getSource()

setSource

public void setSource(String sourceId)

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

Overrides:

init in class NetworkSimplex

Parameters:

graph - The graph this algorithm is using.

nodeAdded

public void nodeAdded(String sourceId,
             long timeId,
             String nodeId)

Specified by:

nodeAdded in interface org.graphstream.stream.ElementSink

Overrides:

nodeAdded in class NetworkSimplex

nodeRemoved

public void nodeRemoved(String sourceId,
               long timeId,
               String nodeId)

Specified by:

nodeRemoved in interface org.graphstream.stream.ElementSink

Overrides:

nodeRemoved in class NetworkSimplex

getPathLength

public long getPathLength(org.graphstream.graph.Node node)

getPathNodesIterator

public <T extends org.graphstream.graph.Node> Iterator<T> getPathNodesIterator(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 <T extends org.graphstream.graph.Node> Iterable<T> 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 getPathNodesIterator(Node).

Parameters:

target - a node

Returns:

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

See Also:

getPathNodesIterator(Node)

getPathEdgesIterator

public <T extends org.graphstream.graph.Edge> Iterator<T> getPathEdgesIterator(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 <T extends org.graphstream.graph.Edge> Iterable<T> 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 getPathEdgesIterator(Node).

Parameters:

target - a node

Returns:

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

See Also:

getPathEdgesIterator(Node)

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