simple_graph_alg.h File Reference

Declaration of simple graph algorithms. More...

#include <ogdf/basic/Array.h>
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/internal/graph_iterators.h>
#include <ogdf/basic/internal/list_templates.h>
#include <ogdf/basic/tuples.h>
#include <functional>

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.