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. |