 java.lang.Object

 org.jgrapht.generate.netgen.NetworkGenerator<V,E>

 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
public class NetworkGenerator<V,E> extends java.lang.Object
NETGENstyle 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, 814821 (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: Network has exactly the same number of nodes, network sources, transshipment sources, network sinks, transshipment sinks, and transshipment nodes;
 Network has exactly the same number of arcs;
 Pure network sources don't have incoming arcs; pure network sinks don't have outgoing arcs;
 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;  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;
 Cost lower and upper bound are satisfied;
 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).
 Every source's supply is at least 1;
 Every sink's supply is at most 1 (equivalently, demand is at least 1);
 The resulting network is feasible meaning that there exist a network flow satisfying the source supply, sink demand and arc capacity constraints.
The maximum flow networks, that are generated by this algorithm, are guaranteed to have following properties:
 Properties 15 are equivalent to the properties of the generated minimum cost flow networks;
 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:
 Properties 1, 2, 6, 7 are equivalent to the properties of the generated minimum cost flow networks;
 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 Summary
Fields Modifier and Type Field Description static int
CAPACITY_COST_BOUND
Upper bound on the arc capacities and costs values in the network this generator can work with.static int
MAX_ARC_NUM
Upper bound on the number of arcs in the network this generator can work with.static int
MAX_NODE_NUM
Upper bound on the number of nodes in the network this generator can work with.static int
MAX_SUPPLY
Upper bound on the number of supply units in the network this generator can work with.

Constructor Summary
Constructors Constructor Description NetworkGenerator(NetworkGeneratorConfig config)
Creates a new network generator using specifiedconfig
.NetworkGenerator(NetworkGeneratorConfig config, long seed)
Creates a new network generator using specifiedconfig
andseed
.NetworkGenerator(NetworkGeneratorConfig config, java.util.Random rng)
Creates a new network generator using specifiedconfig
and random number generatorrng
.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description BipartiteMatchingProblem<V,E>
generateBipartiteMatchingProblem(Graph<V,E> graph)
Generates a bipartite matching problem satisfying the parameters specified in the config provided to this generator.MaximumFlowProblem<V,E>
generateMaxFlowProblem(Graph<V,E> graph)
Generates a maximum flow problem satisfying the parameters specified in the config provided to this generator.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.NetworkInfo<V,E>
getNetworkInfo()
Returns the network information computed for the last generated problem.



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 specifiedconfig
. 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 specifiedconfig
andseed
. 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 specifiedconfig
and random number generatorrng
. The network generated by this algorithm depends entirely on the random number sequences produced byrng
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, seeBipartiteMatchingProblem
. 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, seeMaximumFlowProblem
. 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, seeMinimumCostFlowProblem
. 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.

