Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

Self-Loops and Multi-Edges

Functions dealing with self-loops and multiple (parallel) edges in graphs. More...

Methods for loops

void ogdf::removeSelfLoops (Graph &graph, node v)
 Removes all self-loops for a given node v in graph. More...
 
bool ogdf::isLoopFree (const Graph &G)
 Returns true iff G contains no self-loop. More...
 
template<class NODELIST >
void ogdf::makeLoopFree (Graph &G, NODELIST &L)
 Removes all self-loops from G and returns all nodes with self-loops in L. More...
 
bool ogdf::hasNonSelfLoopEdges (const Graph &G)
 Returns whether G has edges which are not self-loops. More...
 
void ogdf::makeLoopFree (Graph &G)
 Removes all self-loops from G. More...
 

Methods for parallel edges

void ogdf::parallelFreeSort (const Graph &G, SListPure< edge > &edges)
 Sorts the edges of G such that parallel edges come after each other in the list. More...
 
bool ogdf::isParallelFree (const Graph &G)
 Returns true iff G contains no parallel edges. More...
 
template<bool ONLY_ONCE = false>
int ogdf::numParallelEdges (const Graph &G)
 Returns the number of parallel edges in G. More...
 
template<class EDGELIST >
void ogdf::makeParallelFree (Graph &G, EDGELIST &parallelEdges)
 Removes all but one of each bundle of parallel edges. More...
 
void ogdf::makeParallelFree (Graph &G)
 Removes all but one edge of each bundle of parallel edges in G. More...
 
void ogdf::parallelFreeSortUndirected (const Graph &G, SListPure< edge > &edges, EdgeArray< int > &minIndex, EdgeArray< int > &maxIndex)
 Sorts the edges of G such that undirected parallel edges come after each other in the list. More...
 
bool ogdf::isParallelFreeUndirected (const Graph &G)
 Returns true iff G contains no undirected parallel edges. More...
 
template<bool ONLY_ONCE = false>
int ogdf::numParallelEdgesUndirected (const Graph &G)
 Returns the number of undirected parallel edges in G. More...
 
template<class EDGELIST >
void ogdf::getParallelFreeUndirected (const Graph &G, EdgeArray< EDGELIST > &parallelEdges)
 Computes the bundles of undirected parallel edges in G. More...
 
template<class EDGELIST = SListPure<edge>>
void ogdf::makeParallelFreeUndirected (Graph &G, EDGELIST *parallelEdges=nullptr, EdgeArray< int > *cardPositive=nullptr, EdgeArray< int > *cardNegative=nullptr)
 Removes all but one edge of each bundle of undirected parallel edges. More...
 
template<class EDGELIST >
void ogdf::makeParallelFreeUndirected (Graph &G, EDGELIST &parallelEdges)
 
template<class EDGELIST >
void ogdf::makeParallelFreeUndirected (Graph &G, EDGELIST &parallelEdges, EdgeArray< int > &cardPositive, EdgeArray< int > &cardNegative)
 

Methods for simple graphs

bool ogdf::isSimple (const Graph &G)
 Returns true iff G contains neither self-loops nor parallel edges. More...
 
void ogdf::makeSimple (Graph &G)
 Removes all self-loops and all but one edge of each bundle of parallel edges. More...
 
bool ogdf::isSimpleUndirected (const Graph &G)
 Returns true iff G contains neither self-loops nor undirected parallel edges. More...
 
void ogdf::makeSimpleUndirected (Graph &G)
 Removes all self-loops and all but one edge of each bundle of undirected parallel edges. More...
 

Detailed Description

Functions dealing with self-loops and multiple (parallel) edges in graphs.

Function Documentation

◆ getParallelFreeUndirected()

template<class EDGELIST >
void ogdf::getParallelFreeUndirected ( const Graph G,
EdgeArray< EDGELIST > &  parallelEdges 
)

Computes the bundles of undirected parallel edges in G.

Stores for one (arbitrarily chosen) reference edge all edges belonging to the same bundle of undirected parallel edges; no edge is removed from the graph.

Template Parameters
EDGELISTis the type of edge list that is assigned the list of edges.
Parameters
Gis the input graph.
parallelEdgesis assigned for each reference edge the list of edges belonging to the bundle of undirected parallel edges.

Definition at line 297 of file simple_graph_alg.h.

◆ hasNonSelfLoopEdges()

bool ogdf::hasNonSelfLoopEdges ( const Graph G)

Returns whether G has edges which are not self-loops.

◆ isLoopFree()

bool ogdf::isLoopFree ( const Graph G)

Returns true iff G contains no self-loop.

Parameters
Gis the input graph.
Returns
true if G contains no self-loops (edges whose two endpoints are the same), false otherwise.

◆ isParallelFree()

bool ogdf::isParallelFree ( const Graph G)

Returns true iff G contains no parallel edges.

A parallel edge is an edge e1=(v,w) such that there exists another edge e2=(v,w) in the graph. Reversal edges (e.g. (v,w) and (w,v)) are not parallel edges. If you want to test if a graph contains no undirected parallel edges, use isParallelFreeUndirected().

Parameters
Gis the input graph.
Returns
true if G contains no multi-edges (edges with the same source and target).

◆ isParallelFreeUndirected()

bool ogdf::isParallelFreeUndirected ( const Graph G)

Returns true iff G contains no undirected parallel edges.

An undirected parallel edges is an edge e1=(v,w) such that there exists another edge e2=(v,w) or (w,v) in the graph.

Parameters
Gis the input graph.
Returns
true if G contains no undirected parallel edges.

◆ isSimple()

bool ogdf::isSimple ( const Graph G)
inline

Returns true iff G contains neither self-loops nor parallel edges.

Parameters
Gis the input graph.
Returns
true if G is simple, i.e. contains neither self-loops nor parallel edges, false otherwise.

Definition at line 399 of file simple_graph_alg.h.

◆ isSimpleUndirected()

bool ogdf::isSimpleUndirected ( const Graph G)
inline

Returns true iff G contains neither self-loops nor undirected parallel edges.

Parameters
Gis the input graph.
Returns
true if G is (undirected) simple, i.e. contains neither self-loops nor undirected parallel edges, false otherwise.

Definition at line 424 of file simple_graph_alg.h.

◆ makeLoopFree() [1/2]

void ogdf::makeLoopFree ( Graph G)

Removes all self-loops from G.

Parameters
Gis the input graph.

◆ makeLoopFree() [2/2]

template<class NODELIST >
void ogdf::makeLoopFree ( Graph G,
NODELIST &  L 
)

Removes all self-loops from G and returns all nodes with self-loops in L.

Template Parameters
NODELISTis the type of the node list for returning the nodes with self-loops.
Parameters
Gis the input graph.
Lis assigned the list of nodes with self-loops.

Definition at line 69 of file simple_graph_alg.h.

◆ makeParallelFree() [1/2]

void ogdf::makeParallelFree ( Graph G)
inline

Removes all but one edge of each bundle of parallel edges in G.

A parallel edge is an edge e1=(v,w) such that there exists another edge e2=(v,w) in the graph. Reversal edges (e.g. (v,w) and (w,v)) are not parallel edges. If you want to remove parallel and reversal edges, use ogdf::makeParallelFreeUndirected().

Parameters
Gis the input graph.

Definition at line 206 of file simple_graph_alg.h.

◆ makeParallelFree() [2/2]

template<class EDGELIST >
void ogdf::makeParallelFree ( Graph G,
EDGELIST &  parallelEdges 
)

Removes all but one of each bundle of parallel edges.

A parallel edge is an edge e1=(v,w) such that there exists another edge e2=(v,w) in the graph. Reversal edges (e.g. (v,w) and (w,v)) are not multi-edges. If you want to remove parallel and reversal edges, use ogdf::makeParallelFreeUndirected().

Template Parameters
EDGELISTis the type of edge list that will be assigned the list of parallel edges.
Parameters
Gis the input graph.
parallelEdgesis assigned the list of remaining edges in G that were part of a bundle of parallel edges in the input graph.

Definition at line 173 of file simple_graph_alg.h.

◆ makeParallelFreeUndirected() [1/3]

template<class EDGELIST >
void ogdf::makeParallelFreeUndirected ( Graph G,
EDGELIST &  parallelEdges 
)
Deprecated:
"The pointer-based makeParallelFreeUndirected() should be used instead."

Definition at line 375 of file simple_graph_alg.h.

◆ makeParallelFreeUndirected() [2/3]

template<class EDGELIST >
void ogdf::makeParallelFreeUndirected ( Graph G,
EDGELIST &  parallelEdges,
EdgeArray< int > &  cardPositive,
EdgeArray< int > &  cardNegative 
)
Deprecated:
"The pointer-based makeParallelFreeUndirected() should be used instead."

Definition at line 381 of file simple_graph_alg.h.

◆ makeParallelFreeUndirected() [3/3]

template<class EDGELIST = SListPure<edge>>
void ogdf::makeParallelFreeUndirected ( Graph G,
EDGELIST *  parallelEdges = nullptr,
EdgeArray< int > *  cardPositive = nullptr,
EdgeArray< int > *  cardNegative = nullptr 
)

Removes all but one edge of each bundle of undirected parallel edges.

An undirected parallel edge is an edge e1=(v,w) such that there exists another edge e2=(v,w) or (w,v) in the graph. This function removes all but one of the edges with endpoints v and w for each unordered pair of nodes {v,w}.

Template Parameters
EDGELISTis the type of edge list that will be assigned the list of edges.
Parameters
Gis the input graph.
parallelEdgesis assigned the list of remaining edges that were part of a bundle of undirected parallel edges in the input graph.
cardPositivecontains for each edge the number of removed undirected parallel edges pointing in the same direction.
cardNegativecontains for each edge the number of removed undirected parallel edges pointing in the opposite direction.

Definition at line 339 of file simple_graph_alg.h.

◆ makeSimple()

void ogdf::makeSimple ( Graph G)
inline

Removes all self-loops and all but one edge of each bundle of parallel edges.

Parameters
Gis the input graph.

Definition at line 410 of file simple_graph_alg.h.

◆ makeSimpleUndirected()

void ogdf::makeSimpleUndirected ( Graph G)
inline

Removes all self-loops and all but one edge of each bundle of undirected parallel edges.

Parameters
Gis the input graph.

Definition at line 435 of file simple_graph_alg.h.

◆ numParallelEdges()

template<bool ONLY_ONCE = false>
int ogdf::numParallelEdges ( const Graph G)

Returns the number of parallel edges in G.

A parallel edge is an edge e1=(v,w) such that there exists another edge e2=(v,w) in the graph. Reversal edges (e.g. (v,w) and (w,v)) are not parallel edges. If you want to also take reversal edges into account, use numParallelEdgesUndirected().

Parameters
Gis the input graph.
Template Parameters
ONLY_ONCEWhether the searching for multi-edges should be stopped once a single multi-edge is found.
Returns
is the number of parallel edges: for each bundle of parallel edges between two nodes v and w, all but one are counted.

Definition at line 137 of file simple_graph_alg.h.

◆ numParallelEdgesUndirected()

template<bool ONLY_ONCE = false>
int ogdf::numParallelEdgesUndirected ( const Graph G)

Returns the number of undirected parallel edges in G.

An undirected parallel edges is an edge e1=(v,w) such that there exists another edge e2=(v,w) or (w,v) in the graph.

Parameters
Gis the input graph.
Template Parameters
ONLY_ONCEWhether the searching for multi-edges should be stopped once a single multi-edge is found.
Returns
the number of undirected parallel edges; for each unordered pair {v,w} of nodes, all but one of the edges with endpoints v and w (in any order) are counted.

Definition at line 259 of file simple_graph_alg.h.

◆ parallelFreeSort()

void ogdf::parallelFreeSort ( const Graph G,
SListPure< edge > &  edges 
)

Sorts the edges of G such that parallel edges come after each other in the list.

Parameters
Gis the input graph.
edgesis assigned the list of sorted edges.

◆ parallelFreeSortUndirected()

void ogdf::parallelFreeSortUndirected ( const Graph G,
SListPure< edge > &  edges,
EdgeArray< int > &  minIndex,
EdgeArray< int > &  maxIndex 
)

Sorts the edges of G such that undirected parallel edges come after each other in the list.

An undirected parallel edges is an edge e1=(v,w) such that there exists another edge e2=(v,w) or (w,v) in the graph.

Parameters
Gis the input graph.
edgesis assigned the list of sorted edges.
minIndexis assigned for each edge (v,w) the index min(index(v),index(w)).
maxIndexis assigned for each edge (v,w) the index max(index(v),index(w)).

◆ removeSelfLoops()

void ogdf::removeSelfLoops ( Graph graph,
node  v 
)

Removes all self-loops for a given node v in graph.