chomp/struct/digraph.h File Reference

This header file contains the definition of a weighted directed graph class and several algorithms on this graph, including some minimal path algorithms with rounding control to compute rigorous results. More...

#include <iostream>
#include <new>
#include <stack>
#include <set>
#include <memory>
#include "chomp/struct/multitab.h"
#include "chomp/struct/flatmatr.h"
#include "chomp/struct/bitfield.h"
#include "chomp/struct/bitsets.h"
#include "chomp/struct/fibheap.h"
#include "chomp/system/textfile.h"
#include "chomp/system/timeused.h"

Go to the source code of this file.

Namespaces

namespace  chomp
namespace  chomp::homology

Classes

class  chomp::homology::dummyRounding< numType >
 A dummy class for rounding operations which does not actually do any rounding. More...
class  chomp::homology::dummyArray
 A dummy array of integers that ignores all the assigned values. More...
class  chomp::homology::diGraph< wType >
 This class defines a directed graph with very limited number of operations, and a few specific algorithms implemented on it, like DFS. More...
struct  chomp::homology::diGraph< wType >::edgeTriple
 An edge with a weight (used by the Edmonds algorithm). More...
class  chomp::homology::diGraph< wType >::posWeight
 A class for representing a positive number with negative values serving as the infinity (used in the Dijkstra algorithm). More...

Functions

template<class wType1, class wType2>
bool chomp::homology::operator== (const diGraph< wType1 > &g1, const diGraph< wType2 > &g2)
template<class wType1, class wType2>
bool chomp::homology::operator!= (const diGraph< wType1 > &g1, const diGraph< wType2 > &g2)
template<class wType>
std::ostream & chomp::homology::operator<< (std::ostream &out, const diGraph< wType > &g)
 Writes a graph in the text mode to an output stream.
template<class wType, class Table1, class Table2>
int chomp::homology::SCC (const diGraph< wType > &g, Table1 &compVertices, Table2 &compEnds, diGraph< wType > *scc=0, diGraph< wType > *transposed=0, bool copyweights=false)
 Computes strongly connected components of the graph 'g'.
template<class wType>
int chomp::homology::addRenumEdges (const diGraph< wType > &g, int vertex, const int *newNum, int cur, int *srcVert, diGraph< wType > &result)
template<class wType, class Table1, class Table2>
int chomp::homology::collapseVertices (const diGraph< wType > &g, int compNum, Table1 &compVertices, Table2 &compEnds, diGraph< wType > &result, int *newNumbers=0)
 Collapses sets of vertices to single vertices and creates a corresponding graph in which the first vertices come from the collapsed ones.
template<class wType>
int chomp::homology::inclusionGraph (const diGraph< wType > &g, int nVert, diGraph< wType > &result)
 Computes the graph that represents flow-induced relations on Morse sets.
template<class wType, class TConn>
int chomp::homology::inclusionGraph (const diGraph< wType > &g, int nVert, diGraph< wType > &result, TConn &connections)
 A more complicated version of the 'inclusionGraph' function.
template<class wType, class matrix>
void chomp::homology::graph2matrix (const diGraph< wType > &g, matrix &m)
 Creates the adjacency matrix of the given graph.
template<class wType, class matrix>
void chomp::homology::matrix2graph (const matrix &m, int n, diGraph< wType > &g)
 Creates a graph based on the given adjacency matrix.
template<class matrix>
void chomp::homology::transitiveClosure (matrix &m, int n)
 Computes the transitive closure of an acyclic graph defined by its adjacency matrix, using the Warshall's algorithm: S.
template<class matrix>
void chomp::homology::transitiveReduction (matrix &m, int n)
 Computes the transitive reduction of a CLOSED acyclic graph defined by its adjacency matrix, using the algorithm by D.
template<class wType>
void chomp::homology::transitiveReduction (const diGraph< wType > &g, diGraph< wType > &gRed)
 Computes the transitive reduction of an arbitrary acyclic graph.


Detailed Description

This header file contains the definition of a weighted directed graph class and several algorithms on this graph, including some minimal path algorithms with rounding control to compute rigorous results.

Author:
Pawel Pilarczyk

Definition in file digraph.h.


Generated on Wed Nov 21 11:08:42 2007 for The Uniform Expansion Software by  doxygen 1.5.3