Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

simple_graph_alg.h File Reference

Declaration of simple graph algorithms. More...

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, ArrayBuffer< node > *reprs=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)
 
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, ArrayBuffer< node > *reprs=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)
 
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.

Author
Carsten Gutwenger and Sebastian Leipert
License:
This file is part of the Open Graph Drawing Framework (OGDF).
Copyright (C)
See README.md in the OGDF root directory for details.
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License Version 2 or 3 as published by the Free Software Foundation; see the file LICENSE.txt included in the packaging of this file for details.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program; if not, see http://www.gnu.org/copyleft/gpl.html

Definition in file simple_graph_alg.h.