Open
Graph Drawing
Framework

  v.2012.05
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Namespaces | Defines | Functions
simple_graph_alg.h File Reference

Declaration of simple graph algorithms. More...

#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/BoundedStack.h>

Go to the source code of this file.

Namespaces

namespace  ogdf
 The namespace for all OGDF objects.

Defines

#define OGDF_SIMPLE_GRAPH_ALG_H

Functions

OGDF_EXPORT 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.
OGDF_EXPORT void ogdf::makeLoopFree (Graph &G)
 Removes all self-loops from G.
OGDF_EXPORT void ogdf::parallelFreeSort (const Graph &G, SListPure< edge > &edges)
OGDF_EXPORT bool ogdf::isParallelFree (const Graph &G)
 Returns true iff G contains no multi-edges.
OGDF_EXPORT int ogdf::numParallelEdges (const Graph &G)
 Returns the number of multi-edges in G.
template<class EDGELIST >
void ogdf::makeParallelFree (Graph &G, EDGELIST &parallelEdges)
 Removes all but one of each bundle of multi-edges.
void ogdf::makeParallelFree (Graph &G)
 Removes all but one edge of each bundle of multi-edges in G.
OGDF_EXPORT void ogdf::parallelFreeSortUndirected (const Graph &G, SListPure< edge > &edges, EdgeArray< int > &minIndex, EdgeArray< int > &maxIndex)
OGDF_EXPORT bool ogdf::isParallelFreeUndirected (const Graph &G)
 Returns true iff G contains neither multi-edges nor reversal edges.
OGDF_EXPORT int ogdf::numParallelEdgesUndirected (const Graph &G)
 return the number of multi- and reversal edges.
template<class EDGELIST >
void ogdf::makeParallelFreeUndirected (Graph &G, EDGELIST &parallelEdges)
 Removes all but one of each bundle of undirected multi-edges.
void ogdf::makeParallelFreeUndirected (Graph &G)
 Removes all but one of each bundle of undirected multi-edges.
template<class EDGELIST >
void ogdf::makeParallelFreeUndirected (Graph &G, EDGELIST &parallelEdges, EdgeArray< int > &cardPositive, EdgeArray< int > &cardNegative)
 Removes all but one of each bundle of undirected multi-edges.
template<class EDGELIST >
void ogdf::getParallelFreeUndirected (const Graph &G, EdgeArray< EDGELIST > &parallelEdges)
 Computes for each bundle of multi-edges the list of undirected multi-edges.
bool ogdf::isSimple (const Graph &G)
 Returns true iff G contains neither self-loops nor multi-edges.
void ogdf::makeSimple (Graph &G)
 Removes all self-loops and all but one edge of each bundle of multi-edges.
bool ogdf::isSimpleUndirected (const Graph &G)
 Returns true iff G contains neither self-loops nor undirected multi-edges.
void ogdf::makeSimpleUndirected (Graph &G)
 Removes all self-loops and all but one edge of each bundle of undirected multi-edges.
OGDF_EXPORT bool ogdf::isConnected (const Graph &G)
 Returns true iff G is connected.
OGDF_EXPORT void ogdf::makeConnected (Graph &G, List< edge > &added)
 Makes G connected by adding a minimum number of edges.
void ogdf::makeConnected (Graph &G)
 makes G connected by adding a minimum number of edges.
OGDF_EXPORT int ogdf::connectedComponents (const Graph &G, NodeArray< int > &component)
 Computes the connected components of G.
OGDF_EXPORT int ogdf::connectedIsolatedComponents (const Graph &G, List< node > &isolated, NodeArray< int > &component)
 Computes the connected components of G.
OGDF_EXPORT bool ogdf::isBiconnected (const Graph &G, node &cutVertex)
 Returns true if G is biconnected.
bool ogdf::isBiconnected (const Graph &G)
 Returns true iff G is biconnected.
OGDF_EXPORT void ogdf::makeBiconnected (Graph &G, List< edge > &added)
 Makes G biconnected by adding edges.
void ogdf::makeBiconnected (Graph &G)
 Makes G biconnected by adding edges.
OGDF_EXPORT int ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component)
 Computes the biconnected components of G.
OGDF_EXPORT bool ogdf::isTriconnected (const Graph &G, node &s1, node &s2)
 Returns true iff G is triconnected.
bool ogdf::isTriconnected (const Graph &G)
 Returns true iff G is triconnected.
OGDF_EXPORT bool ogdf::isTriconnectedPrimitive (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.
void ogdf::triangulate (Graph &G)
OGDF_EXPORT bool ogdf::isAcyclic (const Graph &G, List< edge > &backedges)
 Returns true if G is acyclic.
bool ogdf::isAcyclic (const Graph &G)
 Returns true iff G is acyclic.
OGDF_EXPORT bool ogdf::isAcyclicUndirected (const Graph &G, List< edge > &backedges)
 Returns true if G is acyclic (undirected version).
bool ogdf::isAcyclicUndirected (const Graph &G)
 Returns true iff G is acyclic (undirected version).
OGDF_EXPORT void ogdf::makeAcyclic (Graph &G)
 Makes G acyclic by removing edges.
OGDF_EXPORT void ogdf::makeAcyclicByReverse (Graph &G)
 Makes G acyclic by reversing edges.
OGDF_EXPORT bool ogdf::hasSingleSource (const Graph &G, node &source)
 Returns true iff G contains exactly one source node (or is empty).
bool ogdf::hasSingleSource (const Graph &G)
 Returns true iff G contains exactly one source node (or is empty).
OGDF_EXPORT bool ogdf::hasSingleSink (const Graph &G, node &sink)
 Returns true iff G contains exactly one sink node (or is empty).
bool ogdf::hasSingleSink (const Graph &G)
OGDF_EXPORT bool ogdf::isStGraph (const Graph &G, node &s, node &t, edge &st)
 Returns true if G is an st-graph.
bool ogdf::isStGraph (const Graph &G)
 Returns true if G is an st-graph.
OGDF_EXPORT void ogdf::topologicalNumbering (const Graph &G, NodeArray< int > &num)
 Computes a topological numbering of an acyclic graph G.
OGDF_EXPORT int ogdf::strongComponents (const Graph &G, NodeArray< int > &component)
 Returns the number of strongly connected components of G.
void ogdf::dfsStrongComponents (const Graph &G, node w, BoundedStack< node > &S, NodeArray< int > &pre, NodeArray< int > &low, int &cnt, int &scnt, NodeArray< int > &component)
 Computes the strongly connected components with the algorithm of Tarjan.
OGDF_EXPORT bool ogdf::isFreeForest (const Graph &G)
 Returns true iff G is a free forest, i.e., contains no undirect cycle.
OGDF_EXPORT bool ogdf::isForest (const Graph &G, List< node > &roots)
 Returns true iff G represents a forest, i.e., a collection of rooted trees.
bool ogdf::isForest (const Graph &G)
 Returns true iff G represents a forest, i.e., a collection of rooted trees.
OGDF_EXPORT bool ogdf::isTree (const Graph &G, node &root)
 Returns true iff G represents a tree.
bool ogdf::isTree (const Graph &G)
 Returns true iff G represents a tree.

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). All rights reserved. See README.txt in the root directory of the OGDF installation 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, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
See also:
http://www.gnu.org/copyleft/gpl.html

Definition in file simple_graph_alg.h.

Define Documentation

#define OGDF_SIMPLE_GRAPH_ALG_H

Definition at line 48 of file simple_graph_alg.h.