Class NetworkGenerator<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    public class NetworkGenerator<V,​E>
    extends java.lang.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.

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

        private final java.util.Random rng
        Random number generator used to create a network.
      • graph

        private Graph<V,​E> graph
        A network that is being generated.
      • networkInfo

        private NetworkInfo<V,​E> networkInfo
        Network structure information obtained during generation process.
      • nodes

        private java.util.List<NetworkGenerator.Node> nodes
        Network nodes stored in a list. Nodes of the same type are located in the continuous segments. There are 5 segments in this list:

        [ pureSources | tSources | tNodes | tSinks | pureSinks ]

        - [ 0, pureSourceNum ) - pure source nodes - [ pureSourceNum, sourceNum ) - transshipment source nodes - [ sourceNum, sourceNum + transshipNodeNum ) - transshipment nodes - [ sourceNum + transshipNodeNum, nodeNum - pureSinkNum ) - transshipment sink nodes - [ nodeNum - pureSinkNum, nodeNum ) - pure sink nodes

      • graphVertexMapping

        private java.util.Map<V,​NetworkGenerator.Node> graphVertexMapping
        Mapping for converting graph vertices to their internal representation as nodes.
      • supplyMap

        private java.util.Map<V,​java.lang.Integer> supplyMap
        Supply vertex mapping which is used to define node supplies.
      • capacityMap

        private java.util.Map<E,​java.lang.Integer> capacityMap
        Arc capacity mapping which is used to define arc capacity function.
      • costMap

        private java.util.Map<E,​java.lang.Integer> costMap
        Arc cost mapping which is used to define arc cost function.
      • source2TSourceUB

        private long source2TSourceUB
        Maximum number of arcs a network can contain between source nodes and t-source nodes.
      • source2TNodeUB

        private long source2TNodeUB
        Maximum number of arcs a network can contain between source nodes and t-nodes. This value is decreased during skeleton network generation whenever an arc between corresponding pair of nodes is generated.
      • source2SinkUB

        private long source2SinkUB
        Maximum number of arcs a network can contain between source nodes and sink nodes. This value is decreased during skeleton network generation whenever an arc between corresponding pair of nodes is generated.
      • tNode2TSourceUB

        private long tNode2TSourceUB
        Maximum number of arcs a network can contain between t-nodes and t-sources.
      • tNode2TNodeUB

        private long tNode2TNodeUB
        Maximum number of arcs a network can contain between t-nodes. This value is decreased during skeleton network generation whenever an arc between corresponding pair of nodes is generated.
      • tNode2SinkUB

        private long tNode2SinkUB
        Maximum number of arcs a network can contain between t-nodes and sink nodes. This value is decreased during skeleton network generation whenever an arc between corresponding pair of nodes is generated.
      • tSink2TSourceUB

        private long tSink2TSourceUB
        Maximum number of arcs a network can contain between t-sinks and t-sources.
      • tSink2TNodeUB

        private long tSink2TNodeUB
        Maximum number of arcs a network can contain between t-sinks and t-nodes.
      • tSink2SinkUB

        private long tSink2SinkUB
        Maximum number of arcs a network can contain between t-sinks and sink nodes.
    • 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,
                                java.util.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.
      • generate

        private void generate​(Graph<V,​E> graph)
        Runs all the steps of the generator algorithm. For the brief description of the algorithm, see the class documentation. The complete NETGEN algorithm description is given in the original paper.
        Parameters:
        graph - the target graph which will represent the generated problem.
      • init

        private void init​(Graph<V,​E> graph)
        Initializes internal datastructures. This method gets called during every invocation of the generate(Graph) to clear information from previous invocation.
        Parameters:
        graph - the target graph which will represent the generated problem.
      • createNodes

        private void createNodes​(int num,
                                 NetworkGenerator.NodeType type)
        Creates num nodes of the specified type.
        Parameters:
        num - the number of nodes to generate.
        type - the type of nodes to generate.
      • createSupply

        private void createSupply()
        Distributes supply units among source nodes.

        The precondition for this method is that totalSupply >= max(sourceNum, sinkNum). This method guarantees that every sourceNode received at least one unit of supply.

      • initChains

        private void initChains()
        Initializes source chains by adding source nodes as 1-st nodes of their chains.
      • generateChains

        private void generateChains()
        Generates source chains using all t-nodes. The generated chains are disjoint and not yet connected to sinks.
      • connectChainsToSinks

        private void connectChainsToSinks()
        Connects generated chains to sinks and distributes network supply among sinks. This method guarantees that:

        1. Every source chain is connected to at least one sink. 2. Every sink is connected to at least one source chain. 3. Every sink's supply is at most -1 (or its demand is at least 1).

      • addAllRemainingArcs

        private void addAllRemainingArcs()
        Generates remaining arcs to satisfy the arcNum constraint.
      • generateArcs

        private void generateArcs​(java.util.List<NetworkGenerator.Node> tails,
                                  java.util.List<NetworkGenerator.Node> heads,
                                  int arcsToGenerate)
        Generates arcsToGenerate number of arcs between nodes from tails and heads. A node can belong to both lists at the same time.
        Parameters:
        tails - list of possible arc tails.
        heads - list of possible arc heads.
        arcsToGenerate - number of arcs to generate
      • getPossibleArcNum

        private int getPossibleArcNum​(NetworkGenerator.Node node,
                                      java.util.Set<NetworkGenerator.Node> nodes)
        Returns the number of arcs it is possible to generate from node to the nodes set.
        Parameters:
        node - an arc tail.
        nodes - set of possible arc heads.
        Returns:
        the computed number of arcs it's possible to generate.
      • 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.
      • isValidArc

        private boolean isValidArc​(NetworkGenerator.Node tail,
                                   NetworkGenerator.Node head)
        Checks if it is possible to add an arc between tail and head to the network.
        Parameters:
        tail - arc tail.
        head - arc head.
        Returns:
        true if it's possible to add an arc, false otherwise.
      • addSkeletonArc

        private void addSkeletonArc​(NetworkGenerator.Node chainSource,
                                    NetworkGenerator.Node tail,
                                    NetworkGenerator.Node head)
        Adds an arc between the tail and head. The added arc is registered to update upper bounds on the number of possible arcs to generate.
        Parameters:
        chainSource - the source of the chain.
        tail - arc tail.
        head - arc head.
      • registerSkeletonArc

        private void registerSkeletonArc​(NetworkGenerator.Node tail,
                                         NetworkGenerator.Node head)
        Registers an arc between tail and head by decreasing one of the upper bounds by 1.
        Parameters:
        tail - arc tail.
        head - arc head.
      • getCapacity

        private int getCapacity()
        Generates an arc capacity. This capacity can be infinite.
        Returns:
        the generated arc capacity.
      • getCost

        private int getCost()
        Generates an arc cost. This cost can be infinite.
        Returns:
        the generated arc cost.
      • generatePositiveRandom

        private int generatePositiveRandom​(int boundInclusive)
      • generateBetween

        private int generateBetween​(int startInclusive,
                                    int endInclusive)
        Generates a random number using random number generator between startInclusive and endInclusive.
        Parameters:
        startInclusive - lower bound
        endInclusive - upper bound
        Returns:
        the generated number
      • generateRandom

        private int generateRandom​(int endExclusive)
        Generates a random number using random number generator between 0 and endExclusive.
        Parameters:
        endExclusive - upper bound.
        Returns:
        the generated number.
      • getTransshipSources

        private java.util.List<NetworkGenerator.Node> getTransshipSources()
        Returns a list containing generated transshipment sources.
        Returns:
        a list containing generated transshipment sources.
      • getSources

        private java.util.List<NetworkGenerator.Node> getSources()
        Returns a list containing generated source (pure sources + t-sources).
        Returns:
        a list containing generated sources.
      • getTransshipNodes

        private java.util.List<NetworkGenerator.Node> getTransshipNodes()
        Returns a list containing generated t-nodes.
        Returns:
        a list containing generated t-nodes.
      • getTransshipSinks

        private java.util.List<NetworkGenerator.Node> getTransshipSinks()
        Returns a list containing generated transshipment sinks.
        Returns:
        a list containing generated transshipment sinks.
      • getSinks

        private java.util.List<NetworkGenerator.Node> getSinks()
        Returns a list containing generated sinks (pure sinks + t-sinks).
        Returns:
        a list containing generated sinks.