next up previous contents index
Next: Miscellaneous Graph Functions ( Up: Graphs and Related Data Previous: Bounded Node Priority Queues   Contents   Index


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 pedagogical 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 n x n nodes.

void grid_graph(graph& G, node_array<double>& xcoord, node_array<double>& ycoord, int n)
    creates a grid graph G of size n x n embedded into the unit square. The embedding is given by xcoord[v] and ycoord[v] for every node v of G.

void d3_grid_graph(graph& G, int n)
    creates a three-dimensional grid graph G with n x n x n nodes.

void d3_grid_graph(graph& G, node_array<double>& xcoord, node_array<double>& ycoord, node_array<double>& zcoord, int n)
    creates a three-dimensional grid graph G of size n x n x n embedded into the unit cube. The embedding is given by xcoord[v], ycoord[v], and zcoord[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   $\longrightarrow$ test_graph()
prog n $\longrightarrow$ complete_graph(n)
prog n m $\longrightarrow$ test_graph(n, m)
prog file $\longrightarrow$ G.read_graph(file)

Planar graph: 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 graph: Geometric Constructions

We have two kinds of geometric constructions: triangulations of point sets and intersection graph 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 graph 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 = 220 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.

Series-Parallel Graphs

void random_sp_graph(graph& G, int n, int m)
    creates a random series-parallel graph G with n nodes and m edges.


next up previous contents index
Next: Miscellaneous Graph Functions ( Up: Graphs and Related Data Previous: Bounded Node Priority Queues   Contents   Index