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.

See Also:
  • Field Details

    • nodeNum

      private final int nodeNum
    • arcNum

      private final int arcNum
    • sourceNum

      private final int sourceNum
    • sinkNum

      private final int sinkNum
    • transshipSourceNum

      private final int transshipSourceNum
    • transshipSinkNum

      private final int transshipSinkNum
    • totalSupply

      private final int totalSupply
    • minCap

      private final int minCap
    • maxCap

      private final int maxCap
    • minCost

      private final int minCost
    • maxCost

      private final int maxCost
    • percentCapacitated

      private final int percentCapacitated
    • percentWithInfCost

      private final int percentWithInfCost
  • Constructor Details

    • NetworkGeneratorConfig

      NetworkGeneratorConfig(int nodeNum, int arcNum, int sourceNum, int sinkNum, int transshipSourceNum, int transshipSinkNum, int totalSupply, int minCap, int maxCap, int minCost, int maxCost, int percentCapacitated, int percentWithInfCost)
      Constructs a new NetworkGeneratorConfig
      Parameters:
      nodeNum - number of nodes
      arcNum - number of arcs
      sourceNum - number of network sources
      sinkNum - number of network sinks
      transshipSourceNum - number of transshipment sources
      transshipSinkNum - number of transshipment sinks
      totalSupply - total supply of all network sources
      minCap - arc capacity lower bound
      maxCap - arc capacity upper bound
      minCost - arc cost lower bound
      maxCost - arc cost upper bound
      percentCapacitated - percent of arcs to have finite capacity
      percentWithInfCost - percent of arcs to have infinite cost
  • 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.
    • transportationProblemCondition

      private boolean transportationProblemCondition()
      Checks if the network satisfies the transportation problem conditions.

      In transportation problem the sum of network sources and network sinks equals to the number of nodes (no transshipment nodes) and the network doesn't contain transshipment sources and sinks. In essence, the network is a bipartite graph.

      Returns:
      true if the network specifies a transportation problem, false otherwise.
    • assignmentProblemCondition

      private boolean assignmentProblemCondition()
      Checks if the transportation network is a bipartite matching problem.

      A transportation problem is a bipartite matching problem, if the bipartite graph partitions are of equal size, every source supply is equal to 1 (thus the demand of every sink is equal to 1 as well), and the capacity of every arc is 1.

      Returns:
      true if the transportation problem is a bipartite matching problem, false otherwise.
    • 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.