# OpenGraph DrawingFramework

v.2012.07

extended_graph_alg.h File Reference

Declaration of extended graph algorithms. More...

#include <ogdf/cluster/ClusterGraph.h>
#include <ogdf/basic/BinaryHeap2.h>
#include <ogdf/planarity/BoyerMyrvold.h>
#include <limits>

Go to the source code of this file.

## Namespaces

namespace  ogdf
The namespace for all OGDF objects.

## Macros

#define OGDF_EXTENDED_GRAPH_ALG_H

## Functions

template<typename T >
ogdf::computeMinST (const Graph &G, const EdgeArray< T > &weight, EdgeArray< bool > &isInTree)
Computes a minimum spanning tree using Prim's algorithm.
template<typename T >
ogdf::computeMinST (const Graph &G, const EdgeArray< T > &weight, NodeArray< edge > &pred, EdgeArray< bool > &isInTree)
Computes a minimum spanning tree (MST) using Prim's algorithm.
template<typename T >
ogdf::computeMinST (node s, const Graph &G, const EdgeArray< T > &weight, NodeArray< edge > &pred, EdgeArray< bool > &isInTree)
Computes a minimum spanning tree (MST) using Prim's algorithm.
template<class LISTITERATOR >
void ogdf::inducedSubGraph (const Graph &G, LISTITERATOR start, Graph &subGraph)
Computes the subgraph induced by a list of nodes.
template<class LISTITERATOR >
void ogdf::inducedSubGraph (const Graph &G, LISTITERATOR start, Graph &subGraph, NodeArray< node > &nodeTableOrig2New)
Computes the subgraph induced by a list of nodes (plus a mapping from original nodes to new copies).
template<class LISTITERATOR >
void ogdf::inducedSubGraph (const Graph &G, LISTITERATOR start, Graph &subGraph, NodeArray< node > &nodeTableOrig2New, EdgeArray< edge > &edgeTableOrig2New)
Computes the subgraph induced by a list of nodes (plus mappings from original nodes and edges to new copies).
template<class NODELISTITERATOR , class EDGELIST >
void ogdf::inducedSubgraph (Graph &G, NODELISTITERATOR &it, EDGELIST &E)
Computes the edges in a node-induced subgraph.
bool ogdf::isCConnected (const ClusterGraph &C)
Returns true iff cluster graph C is c-connected.
bool ogdf::isPlanar (const Graph &G)
Returns true, if G is planar, false otherwise.
void ogdf::makeCConnected (ClusterGraph &C, Graph &G, List< edge > &addedEdges, bool simple=true)
Makes a cluster graph c-connected by adding edges.
bool ogdf::planarEmbed (Graph &G)
Returns true, if G is planar, false otherwise. If true is returned, G will be planarly embedded.
bool ogdf::planarEmbedPlanarGraph (Graph &G)
Constructs a planar embedding of G. It assumes that G is planar!
int ogdf::stNumber (const Graph &G, NodeArray< int > &numbering, node s=0, node t=0, bool randomized=false)
Computes an st-Numbering of G.
bool ogdf::testSTnumber (const Graph &G, NodeArray< int > &st_no, int max)
Tests, whether a numbering of the nodes is an st-numbering.

## Detailed Description

Declaration of extended graph algorithms.

This file is part of the Open Graph Drawing Framework (OGDF).
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.