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 <queue>
#include <set>
#include <memory>
#include <vector>
#include <algorithm>
#include "chomp/struct/multitab.h"
#include "chomp/struct/hashsets.h"
#include "chomp/struct/flatmatr.h"
#include "chomp/struct/bitfield.h"
#include "chomp/struct/bitsets.h"
#include "chomp/struct/fibheap.h"
#include "chomp/struct/autoarray.h"
#include "chomp/system/textfile.h"
#include "chomp/system/timeused.h"

Go to the source code of this file.

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...
Namespaces
namespace	chomp
	This is the top-level namespace of the CHomP library interface; most classes and functions are contained in its sub-namespaces.
namespace	chomp::homology
	This is the main namespace that contains most of the CHomP library classes and functions, some of which are used in the Uniform Expansion project.
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_t	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 , class Table1 , class Table2 >
int_t	chomp::homology::SCC_Tarjan (const diGraph< wType > &g, Table1 &compVertices, Table2 &compEnds)
	Computes strongly connected components of the graph 'g' using Tarjan's algorithm (as described in the Wikipedia).
template<class wType >
int_t	chomp::homology::addRenumEdges (const diGraph< wType > &g, int_t vertex, const int_t *newNum, int_t cur, int_t *srcVert, diGraph< wType > &result)
	A helper function for "collapseVertices".
template<class wType , class Table1 , class Table2 >
int_t	chomp::homology::collapseVertices (const diGraph< wType > &g, int_t compNum, Table1 &compVertices, Table2 &compEnds, diGraph< wType > &result, int_t *newNumbers=0)
	Collapses disjoint subsets of vertices to single vertices and creates a corresponding graph in which the first vertices come from the collapsed ones.
template<class wType , class TabSets >
int_t	chomp::homology::addRenumEdges2 (const diGraph< wType > &g, int_t vertex, const int_t *newNum, TabSets &numSets, int_t cur, int_t *srcVert, diGraph< wType > &result)
	A helper function for "collapseVertices2".
template<class wType , class Table1 , class Table2 >
int_t	chomp::homology::collapseVertices2 (const diGraph< wType > &g, int_t compNum, Table1 &compVertices, Table2 &compEnds, diGraph< wType > &result)
	Collapses (possibly non-disjoint) subsets of vertices to single vertices and creates a corresponding graph in which the first vertices come from the collapsed ones.
template<class wType >
int_t	chomp::homology::connectionGraph (const diGraph< wType > &g, int_t nVert, diGraph< wType > &result)
	Computes the graph that represents connections between a number of the first vertices in the given graph.
template<class GraphType >
int_t	chomp::homology::computePeriod (const GraphType &g)
	Computes the period of a strongly connected graph.
template<class wType >
int_t	chomp::homology::inclusionGraph (const diGraph< wType > &g, int_t nVert, diGraph< wType > &result)
	Computes the graph that represents flow-induced relations on Morse sets.
template<class wType , class TConn >
int_t	chomp::homology::inclusionGraph (const diGraph< wType > &g, int_t 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_t n, diGraph< wType > &g)
	Creates a graph based on the given adjacency matrix.
template<class matrix >
void	chomp::homology::transitiveClosure (matrix &m, int_t 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_t 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.