next up previous contents index
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<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.


next up previous contents index
Next: Markov Chains ( markov_chain Up: Graphs and Related Data Previous: Graph Generators ( graph_gen   Contents   Index
root 2008-01-09