- 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
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:- 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 1-5 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.
- See Also:
NetworkGeneratorConfig
,NetworkInfo
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
NetworkGenerator.Node
Internal representation of network nodes.private static class
NetworkGenerator.NodeType
Enum specifying the nodes type.
-
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.private java.util.Map<E,java.lang.Integer>
capacityMap
Arc capacity mapping which is used to define arc capacity function.private NetworkGeneratorConfig
config
User-provided network configuration.private java.util.Map<E,java.lang.Integer>
costMap
Arc cost mapping which is used to define arc cost function.private Graph<V,E>
graph
A network that is being generated.private java.util.Map<V,NetworkGenerator.Node>
graphVertexMapping
Mapping for converting graph vertices to their internal representation as nodes.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.private NetworkInfo<V,E>
networkInfo
Network structure information obtained during generation process.private java.util.List<NetworkGenerator.Node>
nodes
Network nodes stored in a list.private java.util.Random
rng
Random number generator used to create a network.private long
source2SinkUB
Maximum number of arcs a network can contain between source nodes and sink nodes.private long
source2TNodeUB
Maximum number of arcs a network can contain between source nodes and t-nodes.private long
source2TSourceUB
Maximum number of arcs a network can contain between source nodes and t-source nodes.private java.util.Map<V,java.lang.Integer>
supplyMap
Supply vertex mapping which is used to define node supplies.private long
tNode2SinkUB
Maximum number of arcs a network can contain between t-nodes and sink nodes.private long
tNode2TNodeUB
Maximum number of arcs a network can contain between t-nodes.private long
tNode2TSourceUB
Maximum number of arcs a network can contain between t-nodes and t-sources.private long
tSink2SinkUB
Maximum number of arcs a network can contain between t-sinks and sink nodes.private long
tSink2TNodeUB
Maximum number of arcs a network can contain between t-sinks and t-nodes.private long
tSink2TSourceUB
Maximum number of arcs a network can contain between t-sinks and t-sources.
-
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 private void
addAllRemainingArcs()
Generates remaining arcs to satisfy the arcNum constraint.private void
addArc(NetworkGenerator.Node tail, NetworkGenerator.Node head)
Adds a simple arc to the network.private void
addSkeletonArc(NetworkGenerator.Node chainSource, NetworkGenerator.Node tail, NetworkGenerator.Node head)
Adds an arc between thetail
andhead
.private void
connectChainsToSinks()
Connects generated chains to sinks and distributes network supply among sinks.private void
createNodes(int num, NetworkGenerator.NodeType type)
Createsnum
nodes of the specifiedtype
.private void
createSupply()
Distributes supply units among source nodes.private void
generate(Graph<V,E> graph)
Runs all the steps of the generator algorithm.private void
generateArcs(java.util.List<NetworkGenerator.Node> tails, java.util.List<NetworkGenerator.Node> heads, int arcsToGenerate)
GeneratesarcsToGenerate
number of arcs between nodes fromtails
andheads
.private int
generateBetween(int startInclusive, int endInclusive)
Generates a random number using random number generator betweenstartInclusive
andendInclusive
.BipartiteMatchingProblem<V,E>
generateBipartiteMatchingProblem(Graph<V,E> graph)
Generates a bipartite matching problem satisfying the parameters specified in the config provided to this generator.private void
generateChains()
Generates source chains using all t-nodes.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.private int
generatePositiveRandom(int boundInclusive)
private int
generateRandom(int endExclusive)
Generates a random number using random number generator between 0 andendExclusive
.private int
getCapacity()
Generates an arc capacity.private int
getCost()
Generates an arc cost.NetworkInfo<V,E>
getNetworkInfo()
Returns the network information computed for the last generated problem.private int
getPossibleArcNum(NetworkGenerator.Node node, java.util.Set<NetworkGenerator.Node> nodes)
Returns the number of arcs it is possible to generate fromnode
to thenodes
set.private java.util.List<NetworkGenerator.Node>
getSinks()
Returns a list containing generated sinks (pure sinks + t-sinks).private java.util.List<NetworkGenerator.Node>
getSources()
Returns a list containing generated source (pure sources + t-sources).private java.util.List<NetworkGenerator.Node>
getTransshipNodes()
Returns a list containing generated t-nodes.private java.util.List<NetworkGenerator.Node>
getTransshipSinks()
Returns a list containing generated transshipment sinks.private java.util.List<NetworkGenerator.Node>
getTransshipSources()
Returns a list containing generated transshipment sources.private void
init(Graph<V,E> graph)
Initializes internal datastructures.private void
initChains()
Initializes source chains by adding source nodes as 1-st nodes of their chains.private boolean
isValidArc(NetworkGenerator.Node tail, NetworkGenerator.Node head)
Checks if it is possible to add an arc betweentail
andhead
to the network.private void
registerSkeletonArc(NetworkGenerator.Node tail, NetworkGenerator.Node head)
Registers an arc betweentail
andhead
by decreasing one of the upper bounds by 1.
-
-
-
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
-
config
private final NetworkGeneratorConfig config
User-provided network configuration.
-
rng
private final java.util.Random rng
Random number generator used to create a network.
-
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 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.
-
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 thegenerate(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)
Createsnum
nodes of the specifiedtype
.- 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)
GeneratesarcsToGenerate
number of arcs between nodes fromtails
andheads
. 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 fromnode
to thenodes
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 betweentail
andhead
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 thetail
andhead
. 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.Node tail, NetworkGenerator.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.Node tail, NetworkGenerator.Node head)
Registers an arc betweentail
andhead
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 betweenstartInclusive
andendInclusive
.- Parameters:
startInclusive
- lower boundendInclusive
- upper bound- Returns:
- the generated number
-
generateRandom
private int generateRandom(int endExclusive)
Generates a random number using random number generator between 0 andendExclusive
.- 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.
-
-