Module org.jgrapht.core
Package org.jgrapht.generate.netgen

Class NetworkGeneratorConfig

java.lang.Object
org.jgrapht.generate.netgen.NetworkGeneratorConfig
public class NetworkGeneratorConfig extends Object
Configuration class to specify network parameters for the 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 transshipment is used for nodes that have both incoming and outgoing arcs. This config is used to configure the following parameters:

  • 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 t-sources;
  • 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 t-sinks;
  • 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 t-nodes.

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 non-negative 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 Type
    Method
    Description
    int
    getArcNum()
    Returns the number of arcs in the network.
    int
    getMaxCap()
    Returns arc capacity upper bound.
    int
    getMaxCost()
    Returns arc cost upper bound.
    long
    getMaximumArcNum()
    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
    getMaxSink2ALlArcNum()
    Returns maximum number of arcs between network sinks and all other nodes.
    long
    getMaxSource2AllArcNum()
    Returns maximum number of arcs between network sources and all other nodes.
    long
    getMaxSource2SinkArcNum()
    Returns maximum number of arcs between network sources and network sinks.
    long
    getMaxSource2TNodeArcNum()
    Returns maximum number of arcs this network can contain between network sources and transshipment nodes.
    long
    getMaxSource2TSourceArcNum()
    Returns maximum possible number of arcs this network can contain between the source nodes.
    long
    getMaxTNode2SinkArcNum()
    Returns maximum number of arcs between transshipment nodes and network sinks.
    long
    getMaxTNode2TNodeArcNum()
    Returns maximum number of arcs between transshipment nodes of this network
    long
    getMaxTNode2TSourceArcNum()
    Returns maximum number of arcs between transshipment nodes and network sources.
    long
    getMaxTransshipNode2AllArcNum()
    Returns maximum number of arcs between transshipment nodes and all other nodes.
    long
    getMaxTSink2SinkArcNum()
    Returns maximum number of arcs between network sinks.
    long
    getMaxTSink2TNodeArcNum()
    Returns maximum number of arcs between network sinks and transshipment nodes.
    long
    getMaxTSink2TSourceArcNum()
    Returns maximum number of arcs between network sinks and network sources.
    int
    getMinCap()
    Returns arc capacity lower bound.
    int
    getMinCost()
    Returns arc cost lower bound.
    long
    getMinimumArcNum()
    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
    getNodeNum()
    Returns the number of nodes in the network.
    int
    getPercentCapacitated()
    Returns percent of arcs that have finite capacity.
    int
    getPercentWithInfCost()
    Returns percent of arcs that have infinite cost.
    int
    getPureSinkNum()
    Returns number of pure sinks in the network.
    int
    getPureSourceNum()
    Returns number of pure sources in the network.
    int
    getSinkNum()
    Returns the number of sinks in the network.
    int
    getSourceNum()
    Returns the number of sources in the network.
    int
    getTotalSupply()
    Returns the total supply of the network.
    int
    getTransshipNodeNum()
    Returns the number of transshipment nodes in the network.
    int
    getTransshipSinkNum()
    Returns the number of transshipment sinks in the network.
    int
    getTransshipSourceNum()
    Returns the number of transshipment sources in the network.
    boolean
    isAssignmentProblem()
    Checks if the network is a bipartite matching problem (assignment problem).
    boolean
    isCostWeighted()
    Checks if the network allows different arc costs.
    boolean
    isMaxFlowProblem()
    Checks if a network can be interpreted as a maximum flow problem.

    Methods inherited from class java.lang.Object

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

  • 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 network
      tNodeNum - number of transshipment nodes in the network
      sinkNum - 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 network
      tNodeNum - number of transshipment nodes in the network
      sinkNum - 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 network
      tSourceNum - number of transshipment sources in the network
      tNodeNum - number of transshipment nodes in the network
      tSinkNum - number of transshipment sinks in the network
      sinkNum - 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.