public class NetworkSimplex extends 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
|
protected class |
NetworkSimplex.NSArc
Internal representation of the graph arcs.
|
protected class |
NetworkSimplex.NSNode
Internal representation of the graph nodes.
|
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 |
---|---|
protected long |
animationDelay
If this delay is positive, sleeps at the end of each pivot and updates UI
classes
|
protected Map<String,NetworkSimplex.NSArc> |
arcs
Stores the arcs
|
protected String |
capacityName
Name of the attribute used to store the capacity of each arc
|
protected String |
costName
Name of the attribute used to store the cost per unit flow of each arc
|
protected BigMNumber |
cycleFlowChange
Maximum allowed flow change on the cycle formed by adding
enteringArc to the BFS tree. |
protected NetworkSimplex.NSArc |
enteringArc
Entering arc for the next pivot.
|
protected NetworkSimplex.NSNode |
first
The first node of
enteringArc when traversing it in the
direction of the cycle. |
protected boolean |
fromSink
True if pivot is called from sink method.
|
protected Graph |
graph
A reference to the original graph
|
protected static int |
INFINITE_CAPACITY
Used as capacity value for uncapacitated arcs
|
protected NetworkSimplex.NSNode |
join
The nearest common predecessor of the extremities of
enteringArc
. |
protected NetworkSimplex.NSArc |
leavingArc
Leaving arc for the next pivot.
|
protected PrintStream |
log
Log stream
|
protected int |
logFreq
Log frequency.
|
protected NetworkSimplex.NSNode |
newSubtreeRoot
The node of the detached subtree which must be re-attached to the BFS
tree using
enteringArc . |
protected Map<String,NetworkSimplex.NSNode> |
nodes
Stores the nodes
|
protected Set<NetworkSimplex.NSArc> |
nonBasicArcs
Stores the non basic arcs.
|
protected BigMNumber |
objectiveValue
The objective value of the current solution
|
protected NetworkSimplex.NSNode |
oldSubtreeRoot
The root of the subtree detached from the BFS tree when removing
leavingArc . |
static String |
PREFIX
The algorithm maintains some internal data whose names start with this
prefix.
|
protected NetworkSimplex.PricingStrategy |
pricingStrategy
Current pricing strategy
|
protected NetworkSimplex.NSNode |
root
Artificial root;
|
protected NetworkSimplex.NSNode |
second
The second node of
enteringArc when traversing it in the
direction of the cycle. |
protected NetworkSimplex.SolutionStatus |
solutionStatus
The status of the current BFS
|
protected String |
supplyName
Name of the attribute used to store the supply of each node
|
protected BigMNumber |
work1
Working variable, used to avoid frequent instantiations of local
variables.
|
protected BigMNumber |
work2
Working variable, used to avoid frequent instantiations of local
variables.
|
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 |
---|---|
protected void |
addArc(NetworkSimplex.NSArc arc) |
protected void |
addNode(NetworkSimplex.NSNode node) |
protected void |
changeCapacity(NetworkSimplex.NSArc arc,
int newCapacity) |
protected void |
changeCost(NetworkSimplex.NSArc arc,
BigMNumber newCost)
Changes the cost of an arc
|
protected void |
changeFlows()
Changes the flows on the arcs belonging to the cycle and updates the
objective value.
|
protected void |
changeSupply(NetworkSimplex.NSNode node,
int newSupply) |
protected void |
clearGraph() |
protected void |
cloneGraph()
Creates copies of all graph arcs and edges.
|
void |
compute()
Run the algorithm.
|
protected void |
createInitialBFS()
Creates artificial root and arcs and sets up the initial BFS
|
void |
edgeAdded(String sourceId,
long timeId,
String edgeId,
String fromNodeId,
String toNodeId,
boolean directed)
An edge was inserted in graph.
|
void |
edgeAttributeAdded(String sourceId,
long timeId,
String edgeId,
String attribute,
Object value)
A edge attribute was added.
|
void |
edgeAttributeChanged(String sourceId,
long timeId,
String edgeId,
String attribute,
Object oldValue,
Object newValue)
A edge attribute was changed.
|
void |
edgeAttributeRemoved(String sourceId,
long timeId,
String edgeId,
String attribute)
A edge attribute was removed.
|
void |
edgeRemoved(String sourceId,
long timeId,
String edgeId)
An edge of graph was removed.The nodes the edge connects may already have
been removed from the graph.
|
protected void |
findJoinNode()
Finds the nearest common predecessor of the two nodes of
enteringArc . |
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 Edge> |
getEdgeFromParent(Node node)
Returns the edge to the parent of a node in the current BFS tree.
|
int |
getFlow(Edge edge)
Returns the flow on an edge from its source node to its target node.
|
int |
getFlow(Edge edge,
boolean sameDirection)
Returns the flow on an edge.
|
Graph |
getGraph()
Returns the graph on which the algorithm is applied.
|
int |
getInfeasibility(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 Node> |
getParent(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(Edge edge)
Returns the status of an edge in the current solution.
|
NetworkSimplex.ArcStatus |
getStatus(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)
The whole graph was cleared.
|
void |
init(Graph graph)
Initialization of the algorithm.
|
void |
nodeAdded(String sourceId,
long timeId,
String nodeId)
A node was inserted in the given graph.
|
void |
nodeAttributeAdded(String sourceId,
long timeId,
String nodeId,
String attribute,
Object value)
A node attribute was added.
|
void |
nodeAttributeChanged(String sourceId,
long timeId,
String nodeId,
String attribute,
Object oldValue,
Object newValue)
A node attribute was changed.
|
void |
nodeAttributeRemoved(String sourceId,
long timeId,
String nodeId,
String attribute)
A node attribute was removed.
|
void |
nodeRemoved(String sourceId,
long timeId,
String nodeId)
A node was removed from the graph.
|
protected static double |
objectToDouble(Object o)
Utility method trying to convert object to double in the same way as
AbstractElement.getNumber(String)
does. |
protected void |
pivot()
Performs a pivot when the entering arc and the leaving arc are known.
|
void |
printBFS(PrintStream ps)
Prints a table containing informations about the current basic feasible
solution.
|
protected void |
removeArc(NetworkSimplex.NSArc arc) |
protected void |
removeNode(NetworkSimplex.NSNode node) |
protected void |
selectEnteringArc()
Selects entering arc among the candidates (non-basic arcs with negative
reduced costs).
|
protected void |
selectEnteringArcFirstNegative()
"First negative" pricing strategy
|
protected void |
selectEnteringArcMostNegative()
"Most negative" pricing strategy
|
protected void |
selectLeavingArc()
Selects the leaving arc, that is the arc belonging to the cycle with
minimum allowed flow change.
|
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.
|
protected void |
simplex()
The main simplex method loop.
|
void |
terminate()
Terminate the dynamic algorithm.
|
protected void |
updateBFS()
Turns upside-down the part of the tree between the entering arc and the
leaving arc.
|
graphAttributeAdded, graphAttributeChanged, graphAttributeRemoved, stepBegins
public static final String PREFIX
protected static final int INFINITE_CAPACITY
protected String supplyName
protected String capacityName
protected String costName
protected NetworkSimplex.PricingStrategy pricingStrategy
protected Map<String,NetworkSimplex.NSNode> nodes
protected Map<String,NetworkSimplex.NSArc> arcs
protected Set<NetworkSimplex.NSArc> nonBasicArcs
protected NetworkSimplex.NSNode root
protected BigMNumber objectiveValue
protected NetworkSimplex.SolutionStatus solutionStatus
protected NetworkSimplex.NSArc enteringArc
null
if no candidates.
Set in selectEnteringArc()
protected NetworkSimplex.NSNode join
enteringArc
. Set in findJoinNode()
protected NetworkSimplex.NSNode first
enteringArc
when traversing it in the
direction of the cycle. Set in selectLeavingArc()
.protected NetworkSimplex.NSNode second
enteringArc
when traversing it in the
direction of the cycle. Set in selectLeavingArc()
.protected NetworkSimplex.NSNode oldSubtreeRoot
leavingArc
. Set in selectLeavingArc()
.protected NetworkSimplex.NSNode newSubtreeRoot
enteringArc
. Set in selectLeavingArc()
.protected BigMNumber cycleFlowChange
enteringArc
to the BFS tree. If infinite, the problem is
unbounded. Set in selectLeavingArc()
.protected NetworkSimplex.NSArc leavingArc
selectLeavingArc()
.protected BigMNumber work1
protected BigMNumber work2
protected long animationDelay
protected boolean fromSink
protected int logFreq
protected PrintStream log
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.protected void cloneGraph()
protected void createInitialBFS()
protected void selectEnteringArcFirstNegative()
protected void selectEnteringArcMostNegative()
protected void selectEnteringArc()
enteringArc
. If
there are no candidates, enteringArc
is set to null
.protected void findJoinNode()
enteringArc
. Puts it in join
.protected void selectLeavingArc()
join
. Sets up
first
, second
, cycleFlowChange
,
oldSubtreeRoot
, newSubtreeRoot
and leavingArc
.protected void changeFlows()
protected void updateBFS()
protected void pivot()
protected void simplex()
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 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(Node node)
node
- A nodepublic <T extends Edge> T getEdgeFromParent(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 Node> T getParent(Node node)
null
.node
- A nodepublic int getFlow(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(Edge edge)
getFlow(Edge, true)
.edge
- An edgegetFlow(Edge, boolean)
public NetworkSimplex.ArcStatus getStatus(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(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(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)
AttributeSink
edgeAttributeAdded
in interface AttributeSink
edgeAttributeAdded
in class SinkAdapter
sourceId
- Identifier of the graph where the change occurred.edgeId
- Identifier of the edge whose attribute changed.attribute
- The attribute name.value
- The attribute new value.public void edgeAttributeChanged(String sourceId, long timeId, String edgeId, String attribute, Object oldValue, Object newValue)
AttributeSink
edgeAttributeChanged
in interface AttributeSink
edgeAttributeChanged
in class SinkAdapter
sourceId
- Identifier of the graph where the change occurred.edgeId
- Identifier of the edge whose attribute changed.attribute
- The attribute name.oldValue
- The attribute old value.newValue
- The attribute new value.public void edgeAttributeRemoved(String sourceId, long timeId, String edgeId, String attribute)
AttributeSink
edgeAttributeRemoved
in interface AttributeSink
edgeAttributeRemoved
in class SinkAdapter
sourceId
- Identifier of the graph where the attribute was removed.edgeId
- Identifier of the edge whose attribute was removed.attribute
- The removed attribute name.public void nodeAttributeAdded(String sourceId, long timeId, String nodeId, String attribute, Object value)
AttributeSink
nodeAttributeAdded
in interface AttributeSink
nodeAttributeAdded
in class SinkAdapter
sourceId
- Identifier of the graph where the change occurred.nodeId
- Identifier of the node whose attribute changed.attribute
- The attribute name.value
- The attribute new value.public void nodeAttributeChanged(String sourceId, long timeId, String nodeId, String attribute, Object oldValue, Object newValue)
AttributeSink
nodeAttributeChanged
in interface AttributeSink
nodeAttributeChanged
in class SinkAdapter
sourceId
- Identifier of the graph where the change occurred.nodeId
- Identifier of the node whose attribute changed.attribute
- The attribute name.oldValue
- The attribute old value.newValue
- The attribute new value.public void nodeAttributeRemoved(String sourceId, long timeId, String nodeId, String attribute)
AttributeSink
nodeAttributeRemoved
in interface AttributeSink
nodeAttributeRemoved
in class SinkAdapter
sourceId
- Identifier of the graph where the attribute was removed.nodeId
- Identifier of the node whose attribute was removed.attribute
- The removed attribute name.public void edgeAdded(String sourceId, long timeId, String edgeId, String fromNodeId, String toNodeId, boolean directed)
ElementSink
edgeAdded
in interface ElementSink
edgeAdded
in class SinkAdapter
sourceId
- Identifier of the graph where the edge was added.edgeId
- Identifier of the added edge.fromNodeId
- Identifier of the first node of the edge.toNodeId
- Identifier of the second node of the edge.directed
- If true, the edge is directed.public void edgeRemoved(String sourceId, long timeId, String edgeId)
ElementSink
edgeRemoved
in interface ElementSink
edgeRemoved
in class SinkAdapter
sourceId
- The graph where the edge will be removed.edgeId
- The edge that will be removed.public void nodeAdded(String sourceId, long timeId, String nodeId)
ElementSink
nodeAdded
in interface ElementSink
nodeAdded
in class SinkAdapter
sourceId
- Identifier of the graph where the node was added.nodeId
- Identifier of the added node.public void nodeRemoved(String sourceId, long timeId, String nodeId)
ElementSink
nodeRemoved
in interface ElementSink
nodeRemoved
in class SinkAdapter
sourceId
- Identifier of the graph where the node will be removed.nodeId
- Identifier of the removed node.public void graphCleared(String sourceId, long timeId)
ElementSink
graphCleared
in interface ElementSink
graphCleared
in class SinkAdapter
sourceId
- The graph cleared.protected static double objectToDouble(Object o)
AbstractElement.getNumber(String)
does.o
- The object to be convertedprotected void changeCost(NetworkSimplex.NSArc arc, BigMNumber newCost)
arc
- The arc that changes costnewCost
- The new costprotected void changeSupply(NetworkSimplex.NSNode node, int newSupply)
protected void changeCapacity(NetworkSimplex.NSArc arc, int newCapacity)
protected void addArc(NetworkSimplex.NSArc arc)
protected void removeArc(NetworkSimplex.NSArc arc)
protected void addNode(NetworkSimplex.NSNode node)
protected void removeNode(NetworkSimplex.NSNode node)
protected void clearGraph()
public void printBFS(PrintStream ps)
ps
- A stream where the output goes.WebARTS Library Licensed Under the GNU - General Public License. Other Libraries licensed under their respective Open Source Licenses