public class NetworkSimplex extends org.graphstream.stream.SinkAdapter implements DynamicAlgorithm
Network simplex method is an algorithm that solves the minimum cost flow (MCF) problem for an oriented graph.
The MCF problem can be stated as follows. Each node has associated number supply representing the available supply of or demand for flow at that node. If supply is positive, the node is a supply node, if supply is negative, the node is a demand node and if supply is zero, the node is a transshipment node. Each arc has associated capacity (possibly infinite) and cost per unit flow. The MCF problem is to send the required flows from supply nodes to demand nodes at minimum cost, respecting the capacities of the arcs. Note that if the sum of supply attributes of all nodes is nonzero, the problem is infeasible.
MCF framework can be used to model a broad variety of network problems, including matching, shortest path, transportation, etc. For example, if we want to find the shortest paths from a source to all other nodes in a graph with n nodes, we can set the supply to n-1 for the source and to -1 for all other nodes, set capacity to n-1 and cost to the weight for each arc. The solution of the MCF problem with these particular settings will be minimum cost unit flow from the source to all other nodes passing by the shortest paths.
The user of this class must store the problem data as attributes of the nodes
and the edges of the graph as described below. The names of these attributes
are specified in the constructor
NetworkSimplex(String, String, String)
. For efficiency reasons all
the data are supposed to be integer. If some of the attributes are real,
their fractional part is ignored. To avoid loss of precision, the user must
scale her data properly if they are real.
An attribute called supplyName
is used to store the supply (or demand
if negative) of each node. If a node has not an attribute with this name or
if the value of this attribute is not numeric, the node supply is considered
as zero (transshipment node).
An attribute called capacityName
is used to store the capacity of
each edge. If an edge has not an attribute with this name, or if the value of
this attribute is negative or not numeric, the edge capacity is considered as
infinite.
An attribute called costName
is used to store the cost per unit flow
of each edge. If an edge has not an attribute with this name or if the value
of this attribute is not numeric, the cost per unit flow of the edge is
considered 1.
The flow on a directed edge is always from its source node to its target node. Each undirected edge is considered as a couple of directed edges with the same capacity and cost per unit flow. In other words, there are possibly two independent flows on each undirected edge.
Modifier and Type | Class and Description |
---|---|
static class |
NetworkSimplex.ArcStatus
Arc status
|
static class |
NetworkSimplex.PricingStrategy
Pricing strategy used at each iteration of the algorithm.
|
static class |
NetworkSimplex.SolutionStatus
The status of the current solution.
|
Modifier and Type | Field and Description |
---|---|
static String |
PREFIX
The algorithm maintains some internal data whose names start with this
prefix.
|
Constructor and Description |
---|
NetworkSimplex(String supplyName,
String capaciyName,
String costName)
Creates a network simplex instance specifying attribute names to be used.
|
Modifier and Type | Method and Description |
---|---|
void |
compute()
Run the algorithm.
|
void |
edgeAdded(String sourceId,
long timeId,
String edgeId,
String fromNodeId,
String toNodeId,
boolean directed) |
void |
edgeAttributeAdded(String sourceId,
long timeId,
String edgeId,
String attribute,
Object value) |
void |
edgeAttributeChanged(String sourceId,
long timeId,
String edgeId,
String attribute,
Object oldValue,
Object newValue) |
void |
edgeAttributeRemoved(String sourceId,
long timeId,
String edgeId,
String attribute) |
void |
edgeRemoved(String sourceId,
long timeId,
String edgeId) |
String |
getCapacityName()
Returns the name of the attribute used to store the capacity of each
edge.
|
String |
getCostName()
Returns the name of the attribute used to store the cost per unit flow of
each edge.
|
<T extends org.graphstream.graph.Edge> |
getEdgeFromParent(org.graphstream.graph.Node node)
Returns the edge to the parent of a node in the current BFS tree.
|
int |
getFlow(org.graphstream.graph.Edge edge)
Returns the flow on an edge from its source node to its target node.
|
int |
getFlow(org.graphstream.graph.Edge edge,
boolean sameDirection)
Returns the flow on an edge.
|
org.graphstream.graph.Graph |
getGraph()
Returns the graph on which the algorithm is applied.
|
int |
getInfeasibility(org.graphstream.graph.Node node)
Returns the infeasibility of a node.
|
int |
getNetworkBalance()
Returns the sum of the supplies of all the nodes in the network.
|
<T extends org.graphstream.graph.Node> |
getParent(org.graphstream.graph.Node node)
Returns the parent of a node in the current BFS tree.
|
NetworkSimplex.PricingStrategy |
getPricingStrategy()
Returns the currently used pricing strategy.
|
long |
getSolutionCost()
Returns the total cost of the current network flow
|
long |
getSolutionInfeasibility()
Returns the infeasibility of the current solution.
|
NetworkSimplex.SolutionStatus |
getSolutionStatus()
If the current solution is up to date, returns the status of the problem.
|
NetworkSimplex.ArcStatus |
getStatus(org.graphstream.graph.Edge edge)
Returns the status of an edge in the current solution.
|
NetworkSimplex.ArcStatus |
getStatus(org.graphstream.graph.Edge edge,
boolean sameDirection)
Returns the status of an edge in the current solution.
|
String |
getSupplyName()
Returns the name of the attribute used to store the supply of each node.
|
void |
graphCleared(String sourceId,
long timeId) |
void |
init(org.graphstream.graph.Graph graph)
Initialization of the algorithm.
|
void |
nodeAdded(String sourceId,
long timeId,
String nodeId) |
void |
nodeAttributeAdded(String sourceId,
long timeId,
String nodeId,
String attribute,
Object value) |
void |
nodeAttributeChanged(String sourceId,
long timeId,
String nodeId,
String attribute,
Object oldValue,
Object newValue) |
void |
nodeAttributeRemoved(String sourceId,
long timeId,
String nodeId,
String attribute) |
void |
nodeRemoved(String sourceId,
long timeId,
String nodeId) |
void |
printBFS(PrintStream ps)
Prints a table containing informations about the current basic feasible
solution.
|
void |
setAnimationDelay(long millis)
When the animation delay is positive, the algorithm continuously updates
"ui.class" and "label" attributes of the edges and the
nodes of the graph and sleeps at the beginning of each simplex pivot. |
void |
setLogFrequency(int pivots)
Sets the log frequency.
|
void |
setLogStream(PrintStream log)
Sets the log stream.
|
void |
setPricingStrategy(NetworkSimplex.PricingStrategy pricingStrategy)
Sets the pricing strategy
|
void |
setUIClasses()
This method can be used to visualize the current solution.
|
void |
terminate()
Terminate the dynamic algorithm.
|
public static final String PREFIX
public NetworkSimplex(String supplyName, String capaciyName, String costName)
init(Graph)
to assign a graph to this instance.supplyName
- Name of the attribute used to store the supply of each node.capaciyName
- Name of the attribute used to store the capacity of each edge.costName
- Name of the attribute used to store the cost of each edge.public String getSupplyName()
public String getCapacityName()
public String getCostName()
public NetworkSimplex.PricingStrategy getPricingStrategy()
public void setPricingStrategy(NetworkSimplex.PricingStrategy pricingStrategy)
pricingStrategy
- The new pricing strategypublic void setAnimationDelay(long millis)
"ui.class"
and "label"
attributes of the edges and the
nodes of the graph and sleeps at the beginning of each simplex pivot.
This feature can be useful for visualizing the algorithm execution. The
user must provide a stylesheet defining the classes of the graph elements
as described in setUIClasses()
. This feature is disabled by
default.millis
- The time in milliseconds to sleep between two simplex pivots.setUIClasses()
public org.graphstream.graph.Graph getGraph()
init(Graph)
.public void setLogFrequency(int pivots)
pivots
- The log frequency in number of pivotssetLogStream(PrintStream)
public void setLogStream(PrintStream log)
System.err
.log
- The log streamsetLogFrequency(int)
public int getNetworkBalance()
public NetworkSimplex.SolutionStatus getSolutionStatus()
NetworkSimplex.SolutionStatus.UNDEFINED
.NetworkSimplex.SolutionStatus
public long getSolutionCost()
public long getSolutionInfeasibility()
getInfeasibility(Node)
public int getInfeasibility(org.graphstream.graph.Node node)
node
- A nodepublic <T extends org.graphstream.graph.Edge> T getEdgeFromParent(org.graphstream.graph.Node node)
null
. When the returned edge is undirected, use
getStatus(Edge, boolean)
to know which of the both arcs is
basic.node
- A nodepublic <T extends org.graphstream.graph.Node> T getParent(org.graphstream.graph.Node node)
null
.node
- A nodepublic int getFlow(org.graphstream.graph.Edge edge, boolean sameDirection)
sameDirection
is true, returns the flow from the source to the
target of the edge, otherwise returns the flow from the target to the
source of the edge. Note that for directed edges the flow can only pass
from the source node to the target node. For undirected edges there may
be independent flows in both directions.edge
- An edgesameDirection
- If true, returns the flow from the source to the target.public int getFlow(org.graphstream.graph.Edge edge)
getFlow(Edge, true)
.edge
- An edgegetFlow(Edge, boolean)
public NetworkSimplex.ArcStatus getStatus(org.graphstream.graph.Edge edge, boolean sameDirection)
sameDirection
is true, the method returns the status of the arc
from the source to the target of the edge, otherwise it returns the
status of the arc from the target to the source. If the edge is directed
and sameDirection
is false, returns null
.edge
- An edgesameDirection
- If true, returns the status of the arc from the source to the
target.public NetworkSimplex.ArcStatus getStatus(org.graphstream.graph.Edge edge)
getStatus(edge, true)
.edge
- An edgegetStatus(Edge, boolean)
public void setUIClasses()
It sets the attributes "label"
and "ui.class"
of the
nodes and the edges of the graph depending on the current solution. The
labels of the nodes are set to their balance (see
getInfeasibility(Node)
). The labels of the edges are set to the
flow passing through them. The "ui.class"
attribute of the nodes
is set to one of "supply_balanced"
, "supply_unbalanced"
,
"demand_balanced"
, "demand_unbalanced"
,
"trans_balanced"
or "trans_unbalanced"
depending on the
node type and the node status. The "ui.class"
attribute of the
edges is set to one of "basic"
, "nonbasic_lower"
or
"nonbasic_upper"
according to their status (see
getStatus(Edge)
.
The user must provide a stylesheet defining the visual appearance for
each of these node and edge classes. Note that if the animation delay is
positive (see setAnimationDelay(long)
), there is no need to call
this method, because in this case the labels and the UI classes of the
graph elements are set and updated during the algorithm execution.
Note that in the case of undirected edges the label and the UI class are set according to the status of one of the corresponding arcs (not specified which one).
public void init(org.graphstream.graph.Graph graph)
Algorithm
Algorithm.compute()
method to initialize or reset the algorithm according
to the new given graph.public void compute()
Algorithm
Algorithm.init(Graph)
method has to be called
before computing.compute
in interface Algorithm
Algorithm.init(Graph)
public void terminate()
DynamicAlgorithm
terminate
in interface DynamicAlgorithm
Algorithm.init(org.graphstream.graph.Graph)
public void edgeAttributeAdded(String sourceId, long timeId, String edgeId, String attribute, Object value)
edgeAttributeAdded
in interface org.graphstream.stream.AttributeSink
edgeAttributeAdded
in class org.graphstream.stream.SinkAdapter
public void edgeAttributeChanged(String sourceId, long timeId, String edgeId, String attribute, Object oldValue, Object newValue)
edgeAttributeChanged
in interface org.graphstream.stream.AttributeSink
edgeAttributeChanged
in class org.graphstream.stream.SinkAdapter
public void edgeAttributeRemoved(String sourceId, long timeId, String edgeId, String attribute)
edgeAttributeRemoved
in interface org.graphstream.stream.AttributeSink
edgeAttributeRemoved
in class org.graphstream.stream.SinkAdapter
public void nodeAttributeAdded(String sourceId, long timeId, String nodeId, String attribute, Object value)
nodeAttributeAdded
in interface org.graphstream.stream.AttributeSink
nodeAttributeAdded
in class org.graphstream.stream.SinkAdapter
public void nodeAttributeChanged(String sourceId, long timeId, String nodeId, String attribute, Object oldValue, Object newValue)
nodeAttributeChanged
in interface org.graphstream.stream.AttributeSink
nodeAttributeChanged
in class org.graphstream.stream.SinkAdapter
public void nodeAttributeRemoved(String sourceId, long timeId, String nodeId, String attribute)
nodeAttributeRemoved
in interface org.graphstream.stream.AttributeSink
nodeAttributeRemoved
in class org.graphstream.stream.SinkAdapter
public void edgeAdded(String sourceId, long timeId, String edgeId, String fromNodeId, String toNodeId, boolean directed)
edgeAdded
in interface org.graphstream.stream.ElementSink
edgeAdded
in class org.graphstream.stream.SinkAdapter
public void edgeRemoved(String sourceId, long timeId, String edgeId)
edgeRemoved
in interface org.graphstream.stream.ElementSink
edgeRemoved
in class org.graphstream.stream.SinkAdapter
public void nodeAdded(String sourceId, long timeId, String nodeId)
nodeAdded
in interface org.graphstream.stream.ElementSink
nodeAdded
in class org.graphstream.stream.SinkAdapter
public void nodeRemoved(String sourceId, long timeId, String nodeId)
nodeRemoved
in interface org.graphstream.stream.ElementSink
nodeRemoved
in class org.graphstream.stream.SinkAdapter
public void graphCleared(String sourceId, long timeId)
graphCleared
in interface org.graphstream.stream.ElementSink
graphCleared
in class org.graphstream.stream.SinkAdapter
public void printBFS(PrintStream ps)
ps
- A stream where the output goes.Copyright © 2015. All rights reserved.