simple_graph_alg.h File Reference

Declaration of simple graph algorithms. More...

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

Go to the source code of this file.

Namespaces
namespace	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.
bool	ogdf::isBipartite (const Graph &G)
	Checks whether a graph is bipartite.
bool	ogdf::isBipartite (const Graph &G, NodeArray< bool > &color)
	Checks whether a graph is bipartite.
bool	ogdf::isRegular (const Graph &G)
	Checks if a graph is regular.
bool	ogdf::isRegular (const Graph &G, int d)
	Checks if a graph is d-regular.
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.
Methods for loops
bool	ogdf::hasNonSelfLoopEdges (const Graph &G)
	Returns whether G has edges which are not self-loops.
bool	ogdf::isLoopFree (const Graph &G)
	Returns true iff G contains no self-loop.
void	ogdf::makeLoopFree (Graph &G)
	Removes all self-loops from G.
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.
void	ogdf::removeSelfLoops (Graph &graph, node v)
	Removes all self-loops for a given node v in graph.
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.
bool	ogdf::isParallelFree (const Graph &G)
	Returns true iff G contains no parallel edges.
bool	ogdf::isParallelFreeUndirected (const Graph &G)
	Returns true iff G contains no undirected parallel edges.
void	ogdf::makeParallelFree (Graph &G)
	Removes all but one edge of each bundle 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.
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.
template<bool ONLY_ONCE = false>
int	ogdf::numParallelEdges (const Graph &G)
	Returns the number of parallel edges in G.
template<bool ONLY_ONCE = false>
int	ogdf::numParallelEdgesUndirected (const Graph &G)
	Returns the number of undirected parallel edges in G.
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.
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.
Methods for simple graphs
bool	ogdf::isSimple (const Graph &G)
	Returns true iff G contains neither self-loops nor parallel edges.
bool	ogdf::isSimpleUndirected (const Graph &G)
	Returns true iff G contains neither self-loops nor undirected parallel edges.
void	ogdf::makeSimple (Graph &G)
	Removes all self-loops and all but one edge of each bundle of parallel edges.
void	ogdf::makeSimpleUndirected (Graph &G)
	Removes all self-loops and all but one edge of each bundle of undirected parallel edges.
Methods for connectivity
int	ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component)
	Computes the biconnected components of G.
int	ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component, int &nonEmptyComponents)
	Computes the biconnected components of G.
int	ogdf::connectedComponents (const Graph &G)
	Computes the amount of connected components of G.
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.
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.
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.
bool	ogdf::isBiconnected (const Graph &G)
	Returns true iff G is biconnected.
bool	ogdf::isBiconnected (const Graph &G, node &cutVertex)
	Returns true iff G is biconnected.
bool	ogdf::isConnected (const Graph &G)
	Returns true iff G is connected.
bool	ogdf::isTriconnected (const Graph &G)
	Returns true iff G is triconnected.
bool	ogdf::isTriconnected (const Graph &G, node &s1, node &s2)
	Returns true iff G is triconnected.
bool	ogdf::isTriconnectedPrimitive (const Graph &G)
	Returns true iff G is triconnected (using a quadratic time algorithm!).
bool	ogdf::isTriconnectedPrimitive (const Graph &G, node &s1, node &s2)
	Returns true iff G is triconnected (using a quadratic time algorithm!).
bool	ogdf::isTwoEdgeConnected (const Graph &graph)
	Returns true iff graph is 2-edge-connected.
bool	ogdf::isTwoEdgeConnected (const Graph &graph, edge &bridge)
	Returns true iff graph is 2-edge-connected.
void	ogdf::makeBiconnected (Graph &G)
	Makes G biconnected by adding edges.
void	ogdf::makeBiconnected (Graph &G, List< edge > &added)
	Makes G biconnected by adding edges.
void	ogdf::makeConnected (Graph &G)
	makes G connected by adding a minimum number of edges.
void	ogdf::makeConnected (Graph &G, List< edge > &added)
	Makes G connected by adding a minimum number of edges.
void	ogdf::triangulate (Graph &G)
	Triangulates a planarly embedded graph G by adding edges.
Methods for directed graphs
bool	ogdf::hasSingleSink (const Graph &G)
	Returns true iff the digraph G contains exactly one sink node (or is empty).
bool	ogdf::hasSingleSink (const Graph &G, node &sink)
	Returns true iff the digraph G contains exactly one sink node (or is empty).
bool	ogdf::hasSingleSource (const Graph &G)
	Returns true iff the digraph G contains exactly one source node (or is empty).
bool	ogdf::hasSingleSource (const Graph &G, node &source)
	Returns true iff the digraph G contains exactly one source node (or is empty).
bool	ogdf::isAcyclic (const Graph &G)
	Returns true iff the digraph G is acyclic.
bool	ogdf::isAcyclic (const Graph &G, List< edge > &backedges)
	Returns true iff the digraph G is acyclic.
bool	ogdf::isAcyclicUndirected (const Graph &G)
	Returns true iff the undirected graph G is acyclic.
bool	ogdf::isAcyclicUndirected (const Graph &G, List< edge > &backedges)
	Returns true iff the undirected graph G is acyclic.
bool	ogdf::isStGraph (const Graph &G)
	Returns true if G is an st-digraph.
bool	ogdf::isStGraph (const Graph &G, node &s, node &t, edge &st)
	Returns true iff G is an st-digraph.
void	ogdf::makeAcyclic (Graph &G)
	Makes the digraph G acyclic by removing edges.
void	ogdf::makeAcyclicByReverse (Graph &G)
	Makes the digraph G acyclic by reversing edges.
void	ogdf::makeBimodal (Graph &G)
	Makes the digraph G bimodal.
void	ogdf::makeBimodal (Graph &G, List< edge > &newEdges)
	Makes the digraph G bimodal.
int	ogdf::strongComponents (const Graph &G, NodeArray< int > &component)
	Computes the strongly connected components of the digraph G.
void	ogdf::topologicalNumbering (const Graph &G, NodeArray< int > &num)
	Computes a topological numbering of an acyclic digraph G.
Methods for trees and forests
bool	ogdf::isArborescence (const Graph &G)
	Returns true iff G represents an arborescence.
bool	ogdf::isArborescence (const Graph &G, node &root)
	Returns true iff G represents an arborescence.
bool	ogdf::isArborescenceForest (const Graph &G)
	Returns true iff G is a forest consisting only of arborescences.
bool	ogdf::isArborescenceForest (const Graph &G, List< node > &roots)
	Returns true iff G is a forest consisting only of arborescences.
bool	ogdf::isForest (const Graph &G)
bool	ogdf::isForest (const Graph &G, List< node > &roots)
bool	ogdf::isFreeForest (const Graph &G)
bool	ogdf::isTree (const Graph &G)
	Returns true iff G is a tree, i.e. contains no undirected cycle and is connected.

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.