Darwin  1.10(beta)
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
Classes | Typedefs | Enumerations | Functions
drwnGraphUtils.h File Reference

Generic graph utilities. More...

Go to the source code of this file.


class  drwnWeightedEdge


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


enum  _drwnTriangulationHeuristic { DRWN_MAXCARDSEARCH, DRWN_MINFILLIN }


ostream & operator<< (ostream &os, const drwnEdge &e)
vector< drwnCliquefindNeighbors (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< drwnEdgeminSpanningTree (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< drwnCliquevariableEliminationCliques (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


maximum cardinality search (MCS)


minimum fill-in heuristic