NetworkGenerator
. Any valid
configuration specifies a minimum cost flow network to generate. Under additional constraints the
minimum cost flow networks can be interpreted as maximum flow problems or bipartite matching
problems.
In the following parameter definition the term
 nodeNum  number of all nodes in the network;
 arcNum  number of all arcs in the network;
 sourceNum  number of source nodes in the network. Source node is node that has positive supply value;
 sinkNum  number of sink nodes in the network. Sink node is a node that has negative supply value (i.e. it has demand);
 transshipSourceNum  number of transshipment sources. These source nodes compose a subtype of all source nodes, which means that the number of these nodes must not exceed the number of sources. This parameter can be called tSourceNum as well, the transshipment sources can be called tsources;
 transshipSinkNum  number of transshipment sinks. As with transshipment sources, these sinks are a subtype of all sinks and thus their number must not exceed the number of all sinks. This parameter can be called tSinkNum as well, the transshipment sinks can be called tsinks;
 totalSupply  the sum of supplies od all source nodes. This value is distributed among source nodes. The same amount is distributed among sink nodes with negative sign;
 minCap  a lower bound on the arc capacities;
 maxCap  an upper bound on the arc capacities;
 minCost  a lower bound on the arc costs;
 maxCost  an upper bound on the arc costs;
 percentCapacitated  a value between 0 and 100 which specifies an approximate ratio of arcs which have finite capacity. Other arcs will have infinite capacity;
 percentWithInfCost  a value between 0 and 100 which specifies an approximate ratio of arcs which have infinite cost. All other arcs will have finite cost.
This parameter set specifies certain amount of implicit parameters:
 pureSourceNum  number of sources, which are guaranteed to have no incoming arcs. This value is equal to the sourceNum  transshipSourceNum;
 pureSinkNum  number of sinks, which are guaranteed to have no outcoming arcs. This value is equal to the sinkNum  transshipSinkNum;
 transshipNodeNum  number of nodes in the network which are neither sources now sinks. These nodes can have both incoming and outcoming arcs and their supply values are equal to 0. The number of these nodes is equal to the nodeNum  sourceNum  sinkNum. This parameter can be called tNodeNum as well, transshipment nodes can be called tnodes.
Not every parameter combination specifies a valid config for a network generator. The following are existing parameter constraints:
 transshipSourceNum $\leq$ sourceNum;
 transshipSinkNum $\leq$ sinkNum;
 sourceNum $+$ sinkNum $\leq$ nodeNum;
 max(sourceNum, sinkNum) $\leq$ totalSupply;
 minArcNum $\leq$ arcNum $\leq$ maxArcNum;
 minCap $\leq$ maxCap;
 minCost $\leq$ maxCost;
 0 $\leq$ percentCapacitated $\leq$ 100;
 0 $\leq$ percentWithInfCost $\leq$ 100;
 all parameters are nonnegative except for minCost and maxCost (the are costs may be negative).
MinArcNum is a number of arcs that is needed to make every node connected to at least one source
and one sink. This value is equal to transshipNodeNum + max(sourceNum, sinkNum). This value can
be computed using getMinimumArcNum()
for a specific network. This
value can be computes using getMinimumArcNum(long, long, long)
as
well. MaxArcNum is a number of arcs that makes it impossible to add more arcs to the network
without violating the constraints. This value consists of 3 quantities:
 sourceArcs = pureSourceNum*tSourceNum + tSourceNum*(tSourceNum  1) + sourceNum * (tNodeNum + sinkNum)
 tNodeArcs = tNodeNum*(tSourceNum + (tNodeNum  1) + sinkNum)
 tSinkArcs = tSinkNum*(tSourceNum + tNodeNum + (tSinkNum  1))
The maximum number of arcs is therefore equal to sourceArcs + tNodeArcs + tSinkArcs. This values
can be computed for a specific network configuration using
getMaximumArcNum()
, or for specified node quantity parameters
using getMaximumArcNum(long, long, long, long, long)
.
The general purpose of this config is to specify parameters for the minimum cost flow network. At the same time, this config can specify parameters for the max flow network or bipartite matching problems if additional parameter constraints are imposed. If minCost = maxCost, then the network is called unweighted. An unweighted network specifies a maximum flow problem, it the supply values are additionally removed. To specify a bipartite matching problem, the parameters must satisfy:
 tSourceNum = tSinkNum = 0;
 sourceNum = sinkNum = nodeNum/2 (nodeNum must be even);
 totalSupply = sourceNum;
 minCap = maxCap = 1.
Note that bipartite matching problem can be both weighted and unweighted.
To construct instances of the NetworkGeneratorConfig
, use
NetworkGeneratorConfigBuilder
. It performs all the parameter validation and provides
meaningful error messages in the cases something is going wrong.
 Author:
 Timofey Chudakov
 See Also:

Method Summary
Modifier and TypeMethodDescriptionint
Returns the number of arcs in the network.int
Returns arc capacity upper bound.int
Returns arc cost upper bound.long
Returns maximum number of nodes this network can contain.static long
getMaximumArcNum
(long sourceNum, long tNodeNum, long sinkNum) Returns maximum number of arcs a network with specified node parameters can contain.static long
getMaximumArcNum
(long sourceNum, long tSourceNum, long tNodeNum, long tSinkNum, long sinkNum) Returns maximum number of arcs a network with specified node parameters can contain.long
Returns maximum number of arcs between network sinks and all other nodes.long
Returns maximum number of arcs between network sources and all other nodes.long
Returns maximum number of arcs between network sources and network sinks.long
Returns maximum number of arcs this network can contain between network sources and transshipment nodes.long
Returns maximum possible number of arcs this network can contain between the source nodes.long
Returns maximum number of arcs between transshipment nodes and network sinks.long
Returns maximum number of arcs between transshipment nodes of this networklong
Returns maximum number of arcs between transshipment nodes and network sources.long
Returns maximum number of arcs between transshipment nodes and all other nodes.long
Returns maximum number of arcs between network sinks.long
Returns maximum number of arcs between network sinks and transshipment nodes.long
Returns maximum number of arcs between network sinks and network sources.int
Returns arc capacity lower bound.int
Returns arc cost lower bound.long
Returns minimum number of nodes this network can contain.static long
getMinimumArcNum
(long sourceNum, long tNodeNum, long sinkNum) Returns minimum number of arcs a network with specifies node parameters can contain.int
Returns the number of nodes in the network.int
Returns percent of arcs that have finite capacity.int
Returns percent of arcs that have infinite cost.int
Returns number of pure sinks in the network.int
Returns number of pure sources in the network.int
Returns the number of sinks in the network.int
Returns the number of sources in the network.int
Returns the total supply of the network.int
Returns the number of transshipment nodes in the network.int
Returns the number of transshipment sinks in the network.int
Returns the number of transshipment sources in the network.boolean
Checks if the network is a bipartite matching problem (assignment problem).boolean
Checks if the network allows different arc costs.boolean
Checks if a network can be interpreted as a maximum flow problem.

Method Details

getMaxSource2TSourceArcNum
public long getMaxSource2TSourceArcNum()Returns maximum possible number of arcs this network can contain between the source nodes. This number is 0 if network doesn't contain transshipment sources. Returns:
 maximum number of arcs between network sources.

getMaxSource2TNodeArcNum
public long getMaxSource2TNodeArcNum()Returns maximum number of arcs this network can contain between network sources and transshipment nodes. Returns:
 maximum number of arcs between network sources and transshipment nodes.

getMaxSource2SinkArcNum
public long getMaxSource2SinkArcNum()Returns maximum number of arcs between network sources and network sinks. Returns:
 maximum number of arcs between network sources and network sinks.

getMaxTNode2TSourceArcNum
public long getMaxTNode2TSourceArcNum()Returns maximum number of arcs between transshipment nodes and network sources. Returns:
 maximum number of arcs between transshipment nodes and network sources.

getMaxTNode2TNodeArcNum
public long getMaxTNode2TNodeArcNum()Returns maximum number of arcs between transshipment nodes of this network Returns:
 maximum number of arcs between transshipment nodes of this network

getMaxTNode2SinkArcNum
public long getMaxTNode2SinkArcNum()Returns maximum number of arcs between transshipment nodes and network sinks. Returns:
 maximum number of arcs between transshipment nodes and network sinks.

getMaxTSink2TSourceArcNum
public long getMaxTSink2TSourceArcNum()Returns maximum number of arcs between network sinks and network sources. Returns:
 maximum number of arcs between network sinks and network sources.

getMaxTSink2TNodeArcNum
public long getMaxTSink2TNodeArcNum()Returns maximum number of arcs between network sinks and transshipment nodes. Returns:
 maximum number of arcs between network sinks and transshipment nodes.

getMaxTSink2SinkArcNum
public long getMaxTSink2SinkArcNum()Returns maximum number of arcs between network sinks. Returns:
 maximum number of arcs between network sinks.

getMaxSource2AllArcNum
public long getMaxSource2AllArcNum()Returns maximum number of arcs between network sources and all other nodes. Returns:
 maximum number of arcs between network sources and all other nodes.

getMaxTransshipNode2AllArcNum
public long getMaxTransshipNode2AllArcNum()Returns maximum number of arcs between transshipment nodes and all other nodes. Returns:
 maximum number of arcs between transshipment nodes and all other nodes.

getMaxSink2ALlArcNum
public long getMaxSink2ALlArcNum()Returns maximum number of arcs between network sinks and all other nodes. Returns:
 maximum number of arcs between network sinks and all other nodes.

getMinimumArcNum
public long getMinimumArcNum()Returns minimum number of nodes this network can contain. Returns:
 minimum number of nodes this network can contain.

getMaximumArcNum
public long getMaximumArcNum()Returns maximum number of nodes this network can contain. Returns:
 maximum number of nodes this network can contain.

getMinimumArcNum
public static long getMinimumArcNum(long sourceNum, long tNodeNum, long sinkNum) Returns minimum number of arcs a network with specifies node parameters can contain. Note, that the number of transshipment sources and sinks doesn't affect this quantity. Parameters:
sourceNum
 number of sources in the networktNodeNum
 number of transshipment nodes in the networksinkNum
 number of sinks in the network Returns:
 minimum number of arcs a network with specifies nodes parameters can contain.

getMaximumArcNum
public static long getMaximumArcNum(long sourceNum, long tNodeNum, long sinkNum) Returns maximum number of arcs a network with specified node parameters can contain. Use this network in situation when number of transshipment sources and sinks is zero. Parameters:
sourceNum
 number of sources in the networktNodeNum
 number of transshipment nodes in the networksinkNum
 number of sinks in the network Returns:
 maximum number of arcs a network with specified node parameters can contain.

getMaximumArcNum
public static long getMaximumArcNum(long sourceNum, long tSourceNum, long tNodeNum, long tSinkNum, long sinkNum) Returns maximum number of arcs a network with specified node parameters can contain. Parameters:
sourceNum
 number of sources in the networktSourceNum
 number of transshipment sources in the networktNodeNum
 number of transshipment nodes in the networktSinkNum
 number of transshipment sinks in the networksinkNum
 number of sinks in the network Returns:
 maximum number of arcs a network with specified node parameters can contain.

getPureSourceNum
public int getPureSourceNum()Returns number of pure sources in the network. Pure sources are network sources which can't have incoming arcs. Returns:
 number of pure sources in the network.

getPureSinkNum
public int getPureSinkNum()Returns number of pure sinks in the network. Pure sinks are network sinks which can't have outgoing arcs. which can't have outgoing arcs. Returns:
 number of pure sinks in the network.

isCostWeighted
public boolean isCostWeighted()Checks if the network allows different arc costs. Returns:
true
if the network allows different arc costs,false
otherwise.

getTransshipNodeNum
public int getTransshipNodeNum()Returns the number of transshipment nodes in the network. Returns:
 the number of transshipment nodes in the network.

isMaxFlowProblem
public boolean isMaxFlowProblem()Checks if a network can be interpreted as a maximum flow problem.The only condition for a minimum cost flow to be interpreted as a maximum flow problem is that the arc costs are constant for all arcs.
 Returns:
true
if the network can be interpreted as a max flow problem,false
otherwise.

isAssignmentProblem
public boolean isAssignmentProblem()Checks if the network is a bipartite matching problem (assignment problem). The problem can we both weighted and unweighted. Returns:
true
if the network specifies a bipartite matching problem,false
otherwise.

getNodeNum
public int getNodeNum()Returns the number of nodes in the network. Returns:
 the number of nodes in the network.

getArcNum
public int getArcNum()Returns the number of arcs in the network. Returns:
 the number of arcs in the network.

getSourceNum
public int getSourceNum()Returns the number of sources in the network. Returns:
 the number of sources in the network.

getSinkNum
public int getSinkNum()Returns the number of sinks in the network. Returns:
 the number of sinks in the network.

getTransshipSourceNum
public int getTransshipSourceNum()Returns the number of transshipment sources in the network. Returns:
 the number of transshipment sources in the network.

getTransshipSinkNum
public int getTransshipSinkNum()Returns the number of transshipment sinks in the network. Returns:
 the number of transshipment sinks in the network.

getTotalSupply
public int getTotalSupply()Returns the total supply of the network. Returns:
 the total supply of the network.

getMinCap
public int getMinCap()Returns arc capacity lower bound. Returns:
 arc capacity lower bound.

getMaxCap
public int getMaxCap()Returns arc capacity upper bound. Returns:
 arc capacity upper bound.

getMinCost
public int getMinCost()Returns arc cost lower bound. Returns:
 arc cost lower bound.

getMaxCost
public int getMaxCost()Returns arc cost upper bound. Returns:
 arc cost upper bound.

getPercentCapacitated
public int getPercentCapacitated()Returns percent of arcs that have finite capacity. Returns:
 percent of arcs that have finite capacity.

getPercentWithInfCost
public int getPercentWithInfCost()Returns percent of arcs that have infinite cost. Returns:
 percent of arcs that have infinite cost.
