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.

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

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.

OpenGraph DrawingFramework

Methods for loops

Methods for parallel edges

Methods for simple graphs

Detailed Description

Function Documentation

◆ getParallelFreeUndirected()

◆ hasNonSelfLoopEdges()

◆ isLoopFree()

◆ isParallelFree()

◆ isParallelFreeUndirected()

◆ isSimple()

◆ isSimpleUndirected()

◆ makeLoopFree() [1/2]

◆ makeLoopFree() [2/2]

◆ makeParallelFree() [1/2]

◆ makeParallelFree() [2/2]

◆ makeParallelFreeUndirected() [1/3]

◆ makeParallelFreeUndirected() [2/3]

◆ makeParallelFreeUndirected() [3/3]

◆ makeSimple()

◆ makeSimpleUndirected()

◆ numParallelEdges()

◆ numParallelEdgesUndirected()

◆ parallelFreeSort()

◆ parallelFreeSortUndirected()

◆ removeSelfLoops()

Open
Graph Drawing
Framework