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

Class NetworkGenerator<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    public class NetworkGenerator<V,​E>
extends Object
    NETGEN-style network generator. This generator is capable of generating bipartite matching problems (both weighted and unweighted), maximum flow problems and minimum cost flow problems. Note, that this generator works only with directed graphs. The algorithm is originally described in: D. Klingman, A. Napier, and J. Shutz, "NETGEN - A program for generating large scale (un)capacitated assignment, transportation, and minimum cost flow network problems", Management Science 20, 5, 814-821 (1974)

    This generator is not completely equivalent to the original implementation. A number of changes has been made to remove bugs and ensure parameter constraints. For a complete parameter description and constraints on them, see NetworkGeneratorConfig. Under an assumption that this generator receives a valid config, the following properties of the resulting minimum cost flow network are guaranteed:

    1. Network has exactly the same number of nodes, network sources, transshipment sources, network sinks, transshipment sinks, and transshipment nodes;
    2. Network has exactly the same number of arcs;
    3. Pure network sources don't have incoming arcs; pure network sinks don't have outgoing arcs;
    4. Capacity lower and upper bounds are satisfied for all arcs except for a subset of skeleton arcs, for which the capacity lower bound is equal to the supply of the source arc's chain is originating from. The description of the skeleton network and source chains follows. This is done to ensure that the generated network is feasible with respect to the node supplies. You can find out which arcs belong to the skeleton network by using NetworkInfo. For example, if there is only one network source, network supply is equal to 10, minCap = 1, maxCap = 5, then some of the arcs will have the capacity equal to 10;
    5. If percentCapacitated is 100, then all arcs have finite capacity (which is bounded by minCap and maxCap). If percent capacitated is 0, every arc is uncapacitated;
    6. Cost lower and upper bound are satisfied;
    7. If percentWithInfCost is 100, then all arcs have infinite cost. If percentWithInfCost is 0, then every arc has finite cost (which is bounded by minCost and maxCost).
    8. Every source's supply is at least 1;
    9. Every sink's supply is at most -1 (equivalently, demand is at least 1);
    10. The resulting network is feasible meaning that there exist a network flow satisfying the source supply, sink demand and arc capacity constraints.
    Note, that transshipment sources and transshipment sinks can have incoming and outgoing arcs respectively, but this property is optional.

    The maximum flow networks, that are generated by this algorithm, are guaranteed to have following properties:

    1. Properties 1-5 are equivalent to the properties of the generated minimum cost flow networks;
    2. The maximum flow is greater that or equal to the value of the total supply specified in the network config.

    The bipartite matching problems, that are generated by this algorithm, are guaranteed to following properties:

    1. Properties 1, 2, 6, 7 are equivalent to the properties of the generated minimum cost flow networks;
    2. For the generated problem, there exist a perfect matching meaning that every vertex can be matched.

    Now a brief description of the algorithm will be provided. The generator begins by distributing supply among network sources. Every source gets at least 1 unit of supply. After that, approximately 60% of transshipment nodes are evenly separated between sources. For every source, an initial chain is built using these transshipment nodes. A chain is effectively a path. Remaining 40% of transshipment nodes are randomly distributed among source chains.

    Now every chain has to be connected to at least one sink and every sink has to be connected to at least on chain. For every chain a random number of arcs is generated. This number is at least 1. The total number of generated arcs is max(sourceNum, sinkNum). Every chain is connected to random sinks such that above constraints are satisfied. The network source supply is distributed among network sinks such that every sink received at least 1 unit of supply (with negative sign).

    After the skeleton network is generated, the network is guaranteed to be feasible. The remaining arcs are randomly distributed between remaining pairs of vertices. The algorithm tries to distribute them evenly to avoid large arc clusters.

    Author:
    Timofey Chudakov
    See Also:
    NetworkGeneratorConfig, NetworkInfo

    • Field Detail

      • MAX_NODE_NUM

        public static final int MAX_NODE_NUM
        Upper bound on the number of nodes in the network this generator can work with.
        See Also:
        Constant Field Values

      • MAX_SUPPLY

        public static final int MAX_SUPPLY
        Upper bound on the number of supply units in the network this generator can work with.
        See Also:
        Constant Field Values

      • MAX_ARC_NUM

        public static final int MAX_ARC_NUM
        Upper bound on the number of arcs in the network this generator can work with.
        See Also:
        Constant Field Values

      • CAPACITY_COST_BOUND

        public static final int CAPACITY_COST_BOUND
        Upper bound on the arc capacities and costs values in the network this generator can work with.
        See Also:
        Constant Field Values

    • Constructor Detail

      • NetworkGenerator

        public NetworkGenerator​(NetworkGeneratorConfig config)
        Creates a new network generator using specified config. The created generator uses random seed for the random number generator. Thus the code using this generator won't produce the same networks between different invocations.
        Parameters:
        config - the network configuration for this generator.

      • NetworkGenerator

        public NetworkGenerator​(NetworkGeneratorConfig config,
                        long seed)
        Creates a new network generator using specified config and seed. As the seed for the random number generator is fixed, the code using this generator will produce the same networks between different invocations.
        Parameters:
        config - the network configuration for this generator.
        seed - the seed for the random number generator.

      • NetworkGenerator

        public NetworkGenerator​(NetworkGeneratorConfig config,
                        Random rng)
        Creates a new network generator using specified config and random number generator rng. The network generated by this algorithm depends entirely on the random number sequences produced by rng given a fixed network config.
        Parameters:
        config - the network configuration for this generator.
        rng - the random number generator for this algorithm.

    • Method Detail

      • generateBipartiteMatchingProblem

        public BipartiteMatchingProblem<V,​E> generateBipartiteMatchingProblem​(Graph<V,​E> graph)
        Generates a bipartite matching problem satisfying the parameters specified in the config provided to this generator. The provided network config must specify a bipartite matching problem, otherwise an exception will be throws by this method. For a description of the bipartite matching problem, see BipartiteMatchingProblem.
        Parameters:
        graph - the target graph which will represent the generated problem.
        Returns:
        generated bipartite matching problem.

      • generateMaxFlowProblem

        public MaximumFlowProblem<V,​E> generateMaxFlowProblem​(Graph<V,​E> graph)
        Generates a maximum flow problem satisfying the parameters specified in the config provided to this generator. The provided network config must specify a maximum flow problem, otherwise an exception will be throws by this method. For a description of the maximum flow problem, see MaximumFlowProblem.
        Parameters:
        graph - the target graph which will represent the generated problem.
        Returns:
        generated maximum flow problem.

      • generateMinimumCostFlowProblem

        public MinimumCostFlowProblem<V,​E> generateMinimumCostFlowProblem​(Graph<V,​E> graph)
        Generates a minimum cost flow problem satisfying the parameters specified in the config provided to this generator. For a description of the minimum cost flow problem, see MinimumCostFlowProblem.
        Parameters:
        graph - the target graph which will represent the generated problem.
        Returns:
        generated minimum cost flow problem.

      • getNetworkInfo

        public NetworkInfo<V,​E> getNetworkInfo()
        Returns the network information computed for the last generated problem. Call this method only after the first invocation of any generating method.
        Returns:
        network information.