# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

simple_graph_alg.h File Reference

Declaration of simple graph algorithms. More...

#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/tuples.h>

Go to the source code of this file.

## Namespaces

ogdf
The namespace for all OGDF objects.

## Functions

void ogdf::degreeDistribution (const Graph &G, Array< int > &degdist)
Fills degdist with the degree distribution of graph G. More...

bool ogdf::isBipartite (const Graph &G)
Checks whether a graph is bipartite. More...

bool ogdf::isBipartite (const Graph &G, NodeArray< bool > &color)
Checks whether a graph is bipartite. More...

bool ogdf::isRegular (const Graph &G)
Checks if a graph is regular. More...

bool ogdf::isRegular (const Graph &G, int d)
Checks if a graph is d-regular. More...

void ogdf::nodeDistribution (const Graph &G, Array< int > &degdist, std::function< int(node)> func)
Fills dist with the distribution given by a function func in graph G. More...

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

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

void ogdf::makeLoopFree (Graph &G)
Removes all self-loops from G. 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...

void ogdf::removeSelfLoops (Graph &graph, node v)
Removes all self-loops for a given node v in graph. More...

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

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

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

void ogdf::makeParallelFree (Graph &G)
Removes all but one edge of each bundle 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...

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)

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<bool ONLY_ONCE = false>
int ogdf::numParallelEdges (const Graph &G)
Returns the number of parallel edges in G. More...

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

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

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

Methods for simple graphs
bool ogdf::isSimple (const Graph &G)
Returns true iff G contains neither self-loops nor parallel edges. More...

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

void ogdf::makeSimple (Graph &G)
Removes all self-loops and all but one edge of each bundle of 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...

Methods for connectivity
int ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component)
Computes the biconnected components of G. More...

int ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component, int &nonEmptyComponents)
Computes the biconnected components of G. More...

int ogdf::connectedComponents (const Graph &G)
Computes the amount of connected components of G. More...

int ogdf::connectedComponents (const Graph &G, NodeArray< int > &component, List< node > *isolated=nullptr)
Computes the connected components of G and optionally generates a list of isolated nodes. More...

int ogdf::connectedIsolatedComponents (const Graph &G, List< node > &isolated, NodeArray< int > &component)
Computes the connected components of G and optionally generates a list of isolated nodes. More...

bool ogdf::findCutVertices (const Graph &G, ArrayBuffer< node > &cutVertices, ArrayBuffer< Tuple2< node, node >> &addEdges, bool onlyOne=false)
Finds cut vertices and potential edges that could be added to turn the cut vertices into non-cut vertices. More...

bool ogdf::findCutVertices (const Graph &G, ArrayBuffer< node > &cutVertices, bool onlyOne=false)
Finds cut vertices and potential edges that could be added to turn the cut vertices into non-cut vertices. More...

bool ogdf::isBiconnected (const Graph &G)
Returns true iff G is biconnected. More...

bool ogdf::isBiconnected (const Graph &G, node &cutVertex)
Returns true iff G is biconnected. More...

bool ogdf::isConnected (const Graph &G)
Returns true iff G is connected. More...

bool ogdf::isTriconnected (const Graph &G)
Returns true iff G is triconnected. More...

bool ogdf::isTriconnected (const Graph &G, node &s1, node &s2)
Returns true iff G is triconnected. More...

bool ogdf::isTriconnectedPrimitive (const Graph &G)
Returns true iff G is triconnected (using a quadratic time algorithm!). More...

bool ogdf::isTriconnectedPrimitive (const Graph &G, node &s1, node &s2)
Returns true iff G is triconnected (using a quadratic time algorithm!). More...

bool ogdf::isTwoEdgeConnected (const Graph &graph)
Returns true iff graph is 2-edge-connected. More...

bool ogdf::isTwoEdgeConnected (const Graph &graph, edge &bridge)
Returns true iff graph is 2-edge-connected. More...

void ogdf::makeBiconnected (Graph &G)
Makes G biconnected by adding edges. More...

void ogdf::makeBiconnected (Graph &G, List< edge > &added)
Makes G biconnected by adding edges. More...

void ogdf::makeConnected (Graph &G)
makes G connected by adding a minimum number of edges. More...

void ogdf::makeConnected (Graph &G, List< edge > &added)
Makes G connected by adding a minimum number of edges. More...

void ogdf::triangulate (Graph &G)
Triangulates a planarly embedded graph G by adding edges. More...

Methods for directed graphs
bool ogdf::hasSingleSink (const Graph &G)
Returns true iff the digraph G contains exactly one sink node (or is empty). More...

bool ogdf::hasSingleSink (const Graph &G, node &sink)
Returns true iff the digraph G contains exactly one sink node (or is empty). More...

bool ogdf::hasSingleSource (const Graph &G)
Returns true iff the digraph G contains exactly one source node (or is empty). More...

bool ogdf::hasSingleSource (const Graph &G, node &source)
Returns true iff the digraph G contains exactly one source node (or is empty). More...

bool ogdf::isAcyclic (const Graph &G)
Returns true iff the digraph G is acyclic. More...

bool ogdf::isAcyclic (const Graph &G, List< edge > &backedges)
Returns true iff the digraph G is acyclic. More...

bool ogdf::isAcyclicUndirected (const Graph &G)
Returns true iff the undirected graph G is acyclic. More...

bool ogdf::isAcyclicUndirected (const Graph &G, List< edge > &backedges)
Returns true iff the undirected graph G is acyclic. More...

bool ogdf::isStGraph (const Graph &G)
Returns true if G is an st-digraph. More...

bool ogdf::isStGraph (const Graph &G, node &s, node &t, edge &st)
Returns true iff G is an st-digraph. More...

void ogdf::makeAcyclic (Graph &G)
Makes the digraph G acyclic by removing edges. More...

void ogdf::makeAcyclicByReverse (Graph &G)
Makes the digraph G acyclic by reversing edges. More...

void ogdf::makeBimodal (Graph &G)
Makes the digraph G bimodal. More...

void ogdf::makeBimodal (Graph &G, List< edge > &newEdges)
Makes the digraph G bimodal. More...

int ogdf::strongComponents (const Graph &G, NodeArray< int > &component)
Computes the strongly connected components of the digraph G. More...

void ogdf::topologicalNumbering (const Graph &G, NodeArray< int > &num)
Computes a topological numbering of an acyclic digraph G. More...

Methods for trees and forests
bool ogdf::isArborescence (const Graph &G)
Returns true iff G represents an arborescence. More...

bool ogdf::isArborescence (const Graph &G, node &root)
Returns true iff G represents an arborescence. More...

bool ogdf::isArborescenceForest (const Graph &G)
Returns true iff G is a forest consisting only of arborescences. More...

bool ogdf::isArborescenceForest (const Graph &G, List< node > &roots)
Returns true iff G is a forest consisting only of arborescences. More...

bool ogdf::isForest (const Graph &G)
Returns true iff G is a forest consisting only of arborescences. More...

bool ogdf::isForest (const Graph &G, List< node > &roots)
Returns true iff G is a forest consisting only of arborescences. More...

bool ogdf::isFreeForest (const Graph &G)
Returns true iff the undirected graph G is acyclic. More...

bool ogdf::isTree (const Graph &G)
Returns true iff G is a tree, i.e. contains no undirected cycle and is connected. 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...

Methods for connectivity
bool ogdf::isConnected (const Graph &G)
Returns true iff G is connected. More...

void ogdf::makeConnected (Graph &G, List< edge > &added)
Makes G connected by adding a minimum number of edges. More...

void ogdf::makeConnected (Graph &G)
makes G connected by adding a minimum number of edges. More...

int ogdf::connectedComponents (const Graph &G, NodeArray< int > &component, List< node > *isolated=nullptr)
Computes the connected components of G and optionally generates a list of isolated nodes. More...

int ogdf::connectedComponents (const Graph &G)
Computes the amount of connected components of G. More...

int ogdf::connectedIsolatedComponents (const Graph &G, List< node > &isolated, NodeArray< int > &component)
Computes the connected components of G and optionally generates a list of isolated nodes. More...

bool ogdf::findCutVertices (const Graph &G, ArrayBuffer< node > &cutVertices, ArrayBuffer< Tuple2< node, node >> &addEdges, bool onlyOne=false)
Finds cut vertices and potential edges that could be added to turn the cut vertices into non-cut vertices. More...

bool ogdf::findCutVertices (const Graph &G, ArrayBuffer< node > &cutVertices, bool onlyOne=false)
Finds cut vertices and potential edges that could be added to turn the cut vertices into non-cut vertices. More...

bool ogdf::isBiconnected (const Graph &G, node &cutVertex)
Returns true iff G is biconnected. More...

bool ogdf::isBiconnected (const Graph &G)
Returns true iff G is biconnected. More...

void ogdf::makeBiconnected (Graph &G, List< edge > &added)
Makes G biconnected by adding edges. More...

void ogdf::makeBiconnected (Graph &G)
Makes G biconnected by adding edges. More...

int ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component, int &nonEmptyComponents)
Computes the biconnected components of G. More...

int ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component)
Computes the biconnected components of G. More...

bool ogdf::isTwoEdgeConnected (const Graph &graph, edge &bridge)
Returns true iff graph is 2-edge-connected. More...

bool ogdf::isTwoEdgeConnected (const Graph &graph)
Returns true iff graph is 2-edge-connected. More...

bool ogdf::isTriconnected (const Graph &G, node &s1, node &s2)
Returns true iff G is triconnected. More...

bool ogdf::isTriconnected (const Graph &G)
Returns true iff G is triconnected. More...

bool ogdf::isTriconnectedPrimitive (const Graph &G, node &s1, node &s2)
Returns true iff G is triconnected (using a quadratic time algorithm!). More...

bool ogdf::isTriconnectedPrimitive (const Graph &G)
Returns true iff G is triconnected (using a quadratic time algorithm!). More...

void ogdf::triangulate (Graph &G)
Triangulates a planarly embedded graph G by adding edges. More...

Methods for directed graphs
bool ogdf::isAcyclic (const Graph &G, List< edge > &backedges)
Returns true iff the digraph G is acyclic. More...

bool ogdf::isAcyclic (const Graph &G)
Returns true iff the digraph G is acyclic. More...

bool ogdf::isAcyclicUndirected (const Graph &G, List< edge > &backedges)
Returns true iff the undirected graph G is acyclic. More...

bool ogdf::isAcyclicUndirected (const Graph &G)
Returns true iff the undirected graph G is acyclic. More...

void ogdf::makeAcyclic (Graph &G)
Makes the digraph G acyclic by removing edges. More...

void ogdf::makeAcyclicByReverse (Graph &G)
Makes the digraph G acyclic by reversing edges. More...

bool ogdf::hasSingleSource (const Graph &G, node &source)
Returns true iff the digraph G contains exactly one source node (or is empty). More...

bool ogdf::hasSingleSource (const Graph &G)
Returns true iff the digraph G contains exactly one source node (or is empty). More...

bool ogdf::hasSingleSink (const Graph &G, node &sink)
Returns true iff the digraph G contains exactly one sink node (or is empty). More...

bool ogdf::hasSingleSink (const Graph &G)
Returns true iff the digraph G contains exactly one sink node (or is empty). More...

bool ogdf::isStGraph (const Graph &G, node &s, node &t, edge &st)
Returns true iff G is an st-digraph. More...

bool ogdf::isStGraph (const Graph &G)
Returns true if G is an st-digraph. More...

void ogdf::topologicalNumbering (const Graph &G, NodeArray< int > &num)
Computes a topological numbering of an acyclic digraph G. More...

int ogdf::strongComponents (const Graph &G, NodeArray< int > &component)
Computes the strongly connected components of the digraph G. More...

void ogdf::makeBimodal (Graph &G, List< edge > &newEdges)
Makes the digraph G bimodal. More...

void ogdf::makeBimodal (Graph &G)
Makes the digraph G bimodal. More...

Methods for trees and forests
bool ogdf::isFreeForest (const Graph &G)
Returns true iff the undirected graph G is acyclic. More...

bool ogdf::isTree (const Graph &G)
Returns true iff G is a tree, i.e. contains no undirected cycle and is connected. More...

bool ogdf::isArborescenceForest (const Graph &G, List< node > &roots)
Returns true iff G is a forest consisting only of arborescences. More...

bool ogdf::isArborescenceForest (const Graph &G)
Returns true iff G is a forest consisting only of arborescences. More...

bool ogdf::isForest (const Graph &G, List< node > &roots)
Returns true iff G is a forest consisting only of arborescences. More...

bool ogdf::isForest (const Graph &G)
Returns true iff G is a forest consisting only of arborescences. More...

bool ogdf::isArborescence (const Graph &G, node &root)
Returns true iff G represents an arborescence. More...

bool ogdf::isArborescence (const Graph &G)
Returns true iff G represents an arborescence. More...

## Detailed Description

Declaration of simple graph algorithms.