Graph Generators (graph_gen)

void

complete_graph(graph& G, int n)

creates a complete graph G with n nodes.

void

complete_ugraph(graph& G, int n)

creates a complete undirected graph G with n nodes.

void

random_graph_noncompact(graph& G, int n, int m)

generates a random graph with n nodes and m edges. No attempt is made to store all edges in the same adjacency list consecutively. This function is only included for paedagocial reasons.

void

random_graph(graph& G, int n, int m, bool no_anti_parallel_edges, bool loopfree, bool no_parallel_edges)

generates a random graph with n nodes and m edges. All edges in the same adjacency list are stored consecutively.
If no_parallel_edges is true then no parallel edges are generated, if loopfree is true then no self loops are generated, and if no_anti_parallel_edges is true then no anti parallel edges are generated.

void

random_graph(graph& G, int n, int m)

same as random_graph(G,n,m,false,false,false).

void

random_simple_graph(graph& G, int n, int m)

same as random_graph(G,n,m,false,false,true).

void

random_simple_loopfree_graph(graph& G, int n, int m)

same as random_graph(G,n,m,false,true,true).

void

random_simple_undirected_graph(graph& G, int n, int m)

same as random_graph(G,n,m,true,true,true).

void

random_graph(graph& G, int n, double p)

generates a random graph with n nodes. Each edge of the complete graph with n nodes is included with probability p .

void

test_graph(graph& G)

creates interactively a user defined graph G.

void

complete_bigraph(graph& G, int a, int b, list<node>& A, list<node>& B)

creates a complete bipartite graph G with a nodes on side A and b nodes on side B. All edges are directed from A to B.

void

random_bigraph(graph& G, int a, int b, int m, list<node>& A, list<node>& B, int k = 1)

creates a random bipartite graph G with a nodes on side A, b nodes on side B, and m edges. All edges are directed from A to B.
If k > 1 then A and B are divided into k groups of about equal size and the nodes in the i-th group of A have their edges to nodes in the i-1-th and i+1-th group in B. All indices are modulo k.

void

test_bigraph(graph& G, list<node>& A, list<node>& B)

creates interactively a user defined bipartite graph G with sides A and B. All edges are directed from A to B.

void

grid_graph(graph& G, int n)

creates a grid graph G with nx n nodes.

void

grid_graph(graph& G, node_array<double>& xcoord, node_array<double>& ycoord, int n)

creates a grid graph G of size nx n embedded into the unit square. The embedding is given by xcoord[v] and ycoord[v] for every node v of G.

void

cmdline_graph(graph& G, int argc, char** argv)

builds graph G as specified by the command line arguments:

prog		->	test_graph()
prog	n	->	complete_graph(n)
prog	n m	->	test_graph(n,m)
prog	file	->	G.read_graph(file)

Planar graphs: Combinatorial Constructions A maximal planar map with n nodes, n >= 3, has 3n-6 uedges. It is constructed iteratively. For n = 1, the graph consists of a single isolated node, for n = 2, the graph consists of two nodes and one uedge, for n = 3 the graph consists of three nodes and three uedges. For n > 3, a random maximal planar map with n - 1 nodes is constructed first and then an additional node is put into a random face.

The generator with the additional parameter m first generates a maximal planar map and then deletes all but m edges.

The generators with the word map replaced by graph, first generate a map and then delete one edge from each uedge.

void	maximal_planar_map(graph& G, int n)
		creates a maximal planar map G with n nodes.
void	random_planar_map(graph& G, int n, int m)
		creates a random planar map G with n nodes and m edges.
void	maximal_planar_graph(graph& G, int n)
		creates a maximal planar graph G with n nodes.
void	random_planar_graph(graph& G, int n, int m)
		creates a random planar graph G with n nodes and m edges.

Planar graphs: Geometric Constructions

We have two kinds of geometric constructions: triangulations of point sets and intersection graphs of line segments. The functions triangulation_map choose points in the unit square and compute a triangulation of them and the functions random_planar_graph construct the intersection graphs of segments.

The generators with the word map replaced by graph, first generate a map and then delete one edge from each uedge.

void	triangulation_map(graph& G, node_array<double>& xcoord, node_array<double>& ycoord, int n)
		chooses n random points in the unit square and returns their triangulation as a plane map in G. The coordinates of node v are returned as xcoord[v] and ycoord[v]. The coordinates are random number of the form x/K where K = 2^20 and x is a random integer between 0 (inclusive) and K (exclusive).
void	triangulation_map(graph& G, list<node>& outer_face, node_array<double>& xcoord, node_array<double>& ycoord, int n)
		as above, in addition the list of nodes of the outer face ( convex hull) is returned in outer_face in clockwise order.
void	triangulation_map(graph& G, int n)
		as above, but only the map is returned.
void	random_planar_map(graph& G, node_array<double>& xcoord, node_array<double>& ycoord, int n, int m)
		chooses n random points in the unit square and computes their triangulation as a plane map in G. It then keeps all but m uedges. The coordinates of node v are returned as xcoord[v] and ycoord[v].
void	triangulation_graph(graph& G, node_array<double>& xcoord, node_array<double>& ycoord, int n)
		calls triangulation_map and keeps only one of the edges comprising a uedge.
void	triangulation_graph(graph& G, list<node>& outer_face, node_array<double>& xcoord, node_array<double>& ycoord, int n)
		calls triangulation_map and keeps only one of the edges comprising a uedge.
void	triangulation_graph(graph& G, int n)
		calls triangulation_map and keeps only one of the edges comprising a uedge.
void	random_planar_graph(graph& G, node_array<double>& xcoord, node_array<double>& ycoord, int n, int m)
		calls random_planar_map and keeps only one of the edges comprising a uedge.
void	triangulated_planar_graph(graph& G, int n)
		old name for triangulation_graph.
void	triangulated_planar_graph(graph& G, node_array<double>& xcoord, node_array<double>& ycoord, int n)
		old name for triangulation_graph.
void	triangulated_planar_graph(graph& G, list<node>& outer_face, node_array<double>& xcoord, node_array<double>& ycoord, int n)
		old name for triangulation_graph.
void	random_planar_graph(graph& G, node_array<double>& xcoord, node_array<double>& ycoord, int n)
		creates a random planar graph G with n nodes embedded into the unit sqare. The embedding is given by xcoord[v] and ycoord[v] for every node v of G. The generator chooses n segments whose endpoints have random coordinates of the form x/K, where K is the smallest power of two greater or equal to n, and x is a random integer in 0 to K -1. It then constructs the arrangement defined by the segments and keeps the n nodes with the smallest x-coordinates. Finally, it adds edges to make the graph connected.
void	random_planar_graph(graph& G, int n)
		creates a random planar graph G with n nodes. Uses the preceding function.