drwnGraphUtils.h File Reference

Generic graph utilities. More...

Go to the source code of this file.

Classes
class	drwnWeightedEdge

Typedefs
typedef std::pair< int, int >	drwnEdge
	directed or undirected edges
typedef std::set< int >	drwnClique
	variable clique
typedef enum _drwnTriangulationHeuristic	drwnTriangulationHeuristic

Enumerations
enum	_drwnTriangulationHeuristic { DRWN_MAXCARDSEARCH, DRWN_MINFILLIN }

Functions
ostream &	operator<< (ostream &os, const drwnEdge &e)
vector< drwnClique >	findNeighbors (const vector< drwnEdge > &graph)
	Finds the neighbors for each node in a graph.
int	findSuperset (const vector< drwnClique > &cliques, const drwnClique &subclique)
	Find a clique containing the subclique.
vector< drwnEdge >	minSpanningTree (int numNodes, const vector< drwnEdge > &edges, const vector< double > &weights)
	Finds the minimum weight spanning tree (forest) given a graph structure and weights for each edge (missing edges are assumed to have infinite weight). Implementation is based on Kruskal's algorithm.
bool	maxCardinalitySearch (int numNodes, const vector< drwnEdge > &edges, vector< int > &perfectOrder, int startNode=-1)
	Maximum cardinality search. Returns an elimination ordering for a chordal graph (true) or three nodes that need to be triangulated for non-chordal graphs (return value false). The user can supply the starting node for the search.
void	triangulateGraph (int numNodes, vector< drwnEdge > &edges, drwnTriangulationHeuristic method=DRWN_MINFILLIN)
	Triangulate an undirected graph. Modifies the adjacency list inline. The resulting graph contains no cycles of length four or more without a chord. Different triangulation methods are supported.
vector< drwnClique >	variableEliminationCliques (const vector< drwnEdge > &edges, const vector< int > &nodeOrder)
	Finds cliques obtained by variable elimination.
vector< vector< double > >	allShortestPaths (int numNodes, const vector< drwnEdge > &edges, const vector< double > &weights)
	Floyd-Warshall algorithm for all paths shortest path.
vector< int >	shortestPath (int numNodes, const vector< drwnEdge > &edges, const vector< double > &weights, int source, int sink)
	Dijkstra's shortest path algorithm.

Detailed Description

Generic graph utilities.

Enumeration Type Documentation

enum _drwnTriangulationHeuristic

Enumerator
DRWN_MAXCARDSEARCH	maximum cardinality search (MCS)
DRWN_MINFILLIN	minimum fill-in heuristic