Class NetworkGenerator<V,E>

java.lang.Object
org.jgrapht.generate.netgen.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.

See Also:
  • Field Details

    • 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:
    • 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:
    • 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:
    • 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:
    • config

      private final NetworkGeneratorConfig config
      User-provided network configuration.
    • rng

      private final 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 List<NetworkGenerator<V,E>.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 Map<V,NetworkGenerator<V,E>.Node> graphVertexMapping
      Mapping for converting graph vertices to their internal representation as nodes.
    • supplyMap

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

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

      private Map<E,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 Details

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

    • 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(List<NetworkGenerator<V,E>.Node> tails, List<NetworkGenerator<V,E>.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<V,E>.Node node, Set<NetworkGenerator<V,E>.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<V,E>.Node tail, NetworkGenerator<V,E>.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<V,E>.Node chainSource, NetworkGenerator<V,E>.Node tail, NetworkGenerator<V,E>.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.
    • addArc

      private void addArc(NetworkGenerator<V,E>.Node tail, NetworkGenerator<V,E>.Node head)
      Adds a simple arc to the network. The arc isn't registered.
      Parameters:
      tail - arc tail.
      head - arc head.
    • registerSkeletonArc

      private void registerSkeletonArc(NetworkGenerator<V,E>.Node tail, NetworkGenerator<V,E>.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 List<NetworkGenerator<V,E>.Node> getTransshipSources()
      Returns a list containing generated transshipment sources.
      Returns:
      a list containing generated transshipment sources.
    • getSources

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

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

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

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