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<node,edge>& 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<node,edge>& H, const graph& G, const list<node>& V, const 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, const graph& G, const list<edge>& 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<edge>& 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<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(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<edge>& 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<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(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<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.