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

Class 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:
    NetworkGenerator, NetworkGeneratorConfigBuilder, MinimumCostFlowProblem, MaximumFlowProblem, BipartiteMatchingProblem

    • Method Detail

      • 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.