drwnGraphUtils.h

Go to the documentation of this file.

/******************************************************************************
** DARWIN: A FRAMEWORK FOR MACHINE LEARNING RESEARCH AND DEVELOPMENT
** Distributed under the terms of the BSD license (see the LICENSE file)
** Copyright (c) 2007-2015, Stephen Gould
** All rights reserved.
**
******************************************************************************
** FILENAME:    drwnGraphUtils.h
** AUTHOR(S):   Stephen Gould <stephen.gould@anu.edu.au>
** DESCRIPTION:
**  Generic graph utilities.
**
*****************************************************************************/

#pragma once

#include <cassert>
#include <vector>
#include <map>
#include <set>

using namespace std;

// basic data types ---------------------------------------------------------

typedef std::pair<int, int> drwnEdge;
ostream& operator<<(ostream& os, const drwnEdge& e);

typedef std::set<int> drwnClique;

class drwnWeightedEdge {
 public:
    int nodeA;    
    int nodeB;    
    double wAB;   
    double wBA;   

 public:
    drwnWeightedEdge() : 
        nodeA(-1), nodeB(-1), wAB(0.0), wBA(0.0) { /* do nothing */ };
    drwnWeightedEdge(int a, int b, double w = 0.0, double v = 0.0) :
        nodeA(a), nodeB(b), wAB(w), wBA(v) { /* do nothing */ };
    ~drwnWeightedEdge() { /* do nothing */ };
};

typedef enum _drwnTriangulationHeuristic {
    DRWN_MAXCARDSEARCH, 
    DRWN_MINFILLIN      
} drwnTriangulationHeuristic;

// graph utilities ----------------------------------------------------------

vector<drwnClique> findNeighbors(const vector<drwnEdge>& graph);

int findSuperset(const vector<drwnClique>& cliques, const drwnClique& subclique);

vector<drwnEdge> minSpanningTree(int numNodes, const vector<drwnEdge>& edges,
    const vector<double>& weights);

bool maxCardinalitySearch(int numNodes, const vector<drwnEdge>& edges,
    vector<int>& perfectOrder, int startNode = -1);

void triangulateGraph(int numNodes, vector<drwnEdge>& edges,
    drwnTriangulationHeuristic method = DRWN_MINFILLIN);

vector<drwnClique> variableEliminationCliques(const vector<drwnEdge>& edges,
    const vector<int>& nodeOrder);

vector<vector<double> > allShortestPaths(int numNodes, const vector<drwnEdge>& edges,
    const vector<double>& weights);

vector<int> shortestPath(int numNodes, const vector<drwnEdge>& edges,
    const vector<double>& weights, int source, int sink);