     Next: Markov Chains ( markov_chain Up: Graphs and Related Data Previous: Graph Generators ( graph_gen   Contents   Index

# Miscellaneous Graph Functions ( graph_misc )

Operations

#include < LEDA/graph/graph_misc.h >

 void CopyGraph(graph& H, const graph& G) constructs a copy H of graph G. void CopyGraph(GRAPH& H, const graph& G) constructs a copy H of graph G such that H[v] is the node of G that corresponds to v and H[e] is the edge of G that corresponds to e. void CopyGraph(GRAPH& H, const graph& G, const list& V, const list& E) constructs a copy H of the subgraph (V, E) of G such that H[v] is the node of G that corresponds to v and H[e] is the edge of G that corresponds to e. Precondition V is a subset of the nodes of G and E is a subset of V x V. void CopyGraph(GRAPH& H, const graph& G, const list& E) constructs a copy H of the subgraph of G induced by the edges in E. bool Is_Simple(const graph& G) returns true if G is simple, i.e., has no parallel edges, false otherwise. bool Is_Simple(const graph& G, list& el) as above, but returns in addition the list of all edges sorted lexicographically by source and target node, i.e, all parallel edges appear consecutively in el. bool Is_Loopfree(const graph& G) returns true if G is loopfree, i.e., has no edge whose source is equal to its target. bool Is_Simple_Loopfree(const graph& G) returns true if G is simple and loopfree. bool Is_Undirected_Simple(const graph& G) returns true if G viewed as an undirected graph is simple, i.e., G is loopfree, simple, and has no anti-parallel edges. bool Is_Bidirected(const graph& G) returns true if every edge has a reversal and false otherwise. bool Is_Bidirected(const graph& G, edge_array& rev) computes for every edge e = (v, w) in G its reversal rev[e] = (w, v) in G (nil if not present). Returns true if every edge has a reversal and false otherwise. bool Is_Map(const graph& G) tests whether G is a map. int Genus(const graph& G) computes the genus of G. Precondition G must be a map. bool Is_Plane_Map(const graph& G) tests whether G is a plane map, i.e, whether G is a map of genus zero. bool Is_Planar_Map(const graph& G) old name for Is_Plane_Map bool Is_Acyclic(const graph& G) returns true if the directed G is acyclic and false otherwise. bool Is_Acyclic(const graph& G, list& L) as above; in addition, constructs a list of edges L whose deletion makes G acyclic. bool Is_Connected(const graph& G) returns true if the undirected graph underlying G is connected and false otherwise. bool Is_Biconnected(const graph& G) returns true if the undirected graph underlying G is biconnected and false otherwise. bool Is_Biconnected(const graph& G, node& s) as above, computes a split vertex s if the result is false. bool Is_Triconnected(const graph& G) returns true if the undirected graph underlying G is triconnected and false otherwise. The running time is O(n(n + m))). bool Is_Triconnected(const graph& G, node& s1, node& s2) as above, computes a split pair s1, s2 if the result is false. bool Is_Bipartite(const graph& G) returns true if G is bipartite and false otherwise. bool Is_Bipartite(const graph& G, list& A, list& B) returns true if G is bipartite and false otherwise. If G is bipartite the two sides are returned in A and B, respectively. If G is not bipartite the node sequence of an odd-length circle is returned in A.. bool Is_Planar(const graph& G) returns true if G is planar and false otherwise. bool Is_Series_Parallel(const graph& G) returns true if G is series-parallel and false otherwise. void Make_Acyclic(graph& G) makes G acyclic by removing all DFS back edges. list Make_Simple(graph& G) makes G simple by removing all but one from each set of parallel edges. Returns the list of remaining edges with parallel edges in the original graph. void Make_Bidirected(graph& G, list& L) makes G bidirected by inserting missing reversal edges. Appends all inserted edges to list L. list Make_Bidirected(graph& G) makes G bidirected by inserting missing reversal edges. Returns the list of inserted edges. void Make_Connected(graph& G, list& L) makes G connected; appends all inserted edges to list L. list Make_Connected(graph& G) makes G connected; returns the list of inserted edges. void Make_Biconnected(graph& G, list& L) makes G biconnected; appends all inserted edges to list L. list Make_Biconnected(graph& G) makes G biconnected; returns the list of inserted edges. list Delete_Loops(graph& G) returns the list of nodes with self-loops and deletes all self-loops.     Next: Markov Chains ( markov_chain Up: Graphs and Related Data Previous: Graph Generators ( graph_gen   Contents   Index