# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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.

bool ogdf::isLoopFree (const Graph &G)
Returns true iff G contains no self-loop.

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.

bool ogdf::hasNonSelfLoopEdges (const Graph &G)
Returns whether G has edges which are not self-loops.

void ogdf::makeLoopFree (Graph &G)
Removes all self-loops from G.

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

bool ogdf::isParallelFree (const Graph &G)
Returns true iff G contains no parallel edges.

template<bool ONLY_ONCE = false>
int ogdf::numParallelEdges (const Graph &G)
Returns the number of parallel edges in G.

template<class EDGELIST >
void ogdf::makeParallelFree (Graph &G, EDGELIST &parallelEdges)
Removes all but one of each bundle of parallel edges.

void ogdf::makeParallelFree (Graph &G)
Removes all but one edge of each bundle of parallel edges in G.

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.

bool ogdf::isParallelFreeUndirected (const Graph &G)
Returns true iff G contains no undirected parallel edges.

template<bool ONLY_ONCE = false>
int ogdf::numParallelEdgesUndirected (const Graph &G)
Returns the number of undirected parallel edges in G.

template<class EDGELIST >
void ogdf::getParallelFreeUndirected (const Graph &G, EdgeArray< EDGELIST > &parallelEdges)
Computes the bundles of undirected parallel edges in G.

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.

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.

void ogdf::makeSimple (Graph &G)
Removes all self-loops and all but one edge of each bundle of parallel edges.

bool ogdf::isSimpleUndirected (const Graph &G)
Returns true iff G contains neither self-loops nor undirected parallel edges.

void ogdf::makeSimpleUndirected (Graph &G)
Removes all self-loops and all but one edge of each bundle of undirected parallel edges.

## Detailed Description

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

## ◆ 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
 EDGELIST is the type of edge list that is assigned the list of edges.
Parameters
 G is the input graph. parallelEdges is assigned for each reference edge the list of edges belonging to the bundle of undirected parallel edges.

Definition at line 295 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
 G is 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
 G is 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
 G is 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
 G is the input graph.
Returns
true if G is simple, i.e. contains neither self-loops nor parallel edges, false otherwise.

Definition at line 394 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
 G is 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 415 of file simple_graph_alg.h.

## ◆ makeLoopFree() [1/2]

 void ogdf::makeLoopFree ( Graph & G )

Removes all self-loops from G.

Parameters
 G is 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
 NODELIST is the type of the node list for returning the nodes with self-loops.
Parameters
 G is the input graph. L is 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
 G is the input graph.

Definition at line 210 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
 EDGELIST is the type of edge list that will be assigned the list of parallel edges.
Parameters
 G is the input graph. parallelEdges is 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 372 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 378 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
 EDGELIST is the type of edge list that will be assigned the list of edges.
Parameters
 G is the input graph. parallelEdges is assigned the list of remaining edges that were part of a bundle of undirected parallel edges in the input graph. cardPositive contains for each edge the number of removed undirected parallel edges pointing in the same direction. cardNegative contains for each edge the number of removed undirected parallel edges pointing in the opposite direction.

Definition at line 335 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
 G is the input graph.

Definition at line 402 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
 G is the input graph.

Definition at line 425 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
 G is the input graph.
Template Parameters
 ONLY_ONCE Whether 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 135 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
 G is the input graph.
Template Parameters
 ONLY_ONCE Whether 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 257 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
 G is the input graph. edges is 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
 G is the input graph. edges is assigned the list of sorted edges. minIndex is assigned for each edge (v,w) the index min(index(v),index(w)). maxIndex is 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.