Miscellaneous Graph Functions ( graph_misc )

Operations

#include < LEDA/graph _misc.h >

void	CopyGraph(GRAPH<node,edge>& H, 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<node,edge>& H, graph G, list<node> V, list<edge> 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<node,edge>& H, graph G, list<edge> E)
		constructs a copy H of the subgraph of G induced by the edges in E.
bool	Is_Simple(graph G)	returns true if G is simple, i.e., has no parallel edges, false otherwise.
bool	Is_Loopfree(graph G)	returns true if G is loopfree, i.e., has no edge whose source is equal to its target.
bool	Is_Simple_Loopfree(graph G)
		returns true if G is simple and loopfree.
bool	Is_Simple_Undirected(graph G)
		returns true if G is simple, loopfree, and has no anti-parallel edges.
bool	Is_Bidirected(graph G)	returns true if every edge has a reversal and false otherwise.
bool	Is_Bidirected(graph G, edge_array<edge>& 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(graph G)	tests whether G is a map.
int	Genus(graph G)	computes the genus of G. Precondition: G must be a map.
bool	Is_Plane_Map(graph G)	tests whether G is a plane map, i.e, whether G is a map of genus zero.
bool	Is_Planar_Map(graph G)	old name for Is_Plane_Map
bool	Is_Acyclic(graph G)	returns true if the directed G is acyclic and false otherwise.
bool	Is_Acyclic(graph G, list<edge>& L)
		as above; in addition, constructs a list of edges L whose deletion makes G acyclic.
void	Make_Acyclic(graph& G)	makes G acyclic by removing all DFS back edges.
bool	Is_Connected(graph G)	returns true if the undirected graph underlying G is connected and false otherwise.
bool	Is_Biconnected(graph G)	returns true if the undirected graph underlying G is biconnected and false otherwise.
bool	Is_Biconnected(graph G, node& s)
		as above, computes a split vertex s if the result is false.
bool	Is_Triconnected(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(graph G, node& s1, node& s2)
		as above, computes a split pair s1, s2 if the result is false.
bool	Is_Bipartite(graph G)	returns true if G is bipartite and false otherwise.
bool	Is_Bipartite(graph G, list<node>& A, list<node>& 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(graph G)	returns true if G is planar and false otherwise.
list<edge>	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<edge>& L)
		makes G bidirected by inserting missing reversal edges. Appends all inserted edges to list L.
list<edge>	Make_Bidirected(graph& G)	makes G bidirected by inserting missing reversal edges. Returns the list of inserted edges.
void	Make_Connected(graph& G, list<edge>& L)
		makes G connected; appends all inserted edges to list L.
list<edge>	Make_Connected(graph& G)	makes G connected; returns the list of inserted edges.
void	Make_Biconnected(graph& G, list<edge>& L)
		makes G biconnected; appends all inserted edges to list L.
list<edge>	Make_Biconnected(graph& G)
		makes G biconnected; returns the list of inserted edges.
list<node>	Delete_Loops(graph& G)	returns the list of nodes with self-loops and deletes all self-loops.