drwnFactorGraph.h

/*****************************************************************************
** 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:    drwnFactorGraph.h
** AUTHOR(S):   Stephen Gould <stephen.gould@anu.edu.au>
**
*****************************************************************************/

#pragma once

#include <cstdlib>
#include <cassert>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <map>
#include <list>

#include "Eigen/Core"

#include "drwnBase.h"
#include "drwnIO.h"
#include "drwnGraphUtils.h"
#include "drwnTableFactor.h"

using namespace std;
using namespace Eigen;

// drwnFactorGraph ---------------------------------------------------------

class drwnFactorGraph : public drwnStdObjIface {
 protected:
    drwnVarUniversePtr _pUniverse;  
    vector<drwnTableFactor *> _factors;  

    typedef drwnTriplet<int, int, drwnClique> _drwnFactorEdge;
    vector<_drwnFactorEdge> _edges; 

 public:
    drwnFactorGraph();
    drwnFactorGraph(const drwnVarUniversePtr& u);
    drwnFactorGraph(const drwnFactorGraph& g);
    virtual ~drwnFactorGraph();

    // access functions
    virtual const char *type() const { return "drwnFactorGraph"; }
    virtual drwnFactorGraph *clone() const { return new drwnFactorGraph(*this); }

    const drwnVarUniversePtr& getUniverse() const { return _pUniverse; }
    int numVariables() const { return (_pUniverse == NULL) ? 0 : _pUniverse->numVariables(); }
    int numFactors() const { return (int)_factors.size(); }
    int numEdges() const { return (int)_edges.size(); }

    void addFactor(drwnTableFactor *psi);
    void copyFactor(const drwnTableFactor *psi);
    const drwnTableFactor* getFactor(int indx) const { return _factors[indx]; }
    void deleteFactor(int indx);
    int findFactor(const drwnClique& clique, bool bAllowSuperset = false) const;
    drwnClique getClique(int indx) const;
    drwnEdge getEdge(int eindx) const { return drwnEdge(_edges[eindx].first, _edges[eindx].second); }
    drwnClique getSepSet(int eindx) const { return _edges[eindx].third; }
    static drwnClique getSepSet(const drwnFactor& psiA, const drwnFactor& psiB);

    double getEnergy(const drwnFullAssignment& x) const;

    // graph connectivity
    bool addEdge(const drwnEdge& e);
    bool connectGraph(const set<drwnEdge>& edges);
    virtual bool connectGraph();
    bool connectBetheApprox();

    // check running intersection property
    /*
    bool checkRunIntProp();
    */

    // i/o
    bool save(drwnXMLNode& xml) const;
    bool load(drwnXMLNode& xml);

    // operators
    drwnTableFactor* operator[](unsigned indx) { return _factors[indx]; }
    const drwnTableFactor* operator[](unsigned indx) const { return _factors[indx]; }

    //bool operator==(const drwnFactorGraph& g) const;


 protected:
    void computeSeparatorSets();
};

// drwnFactorGraph utilities -----------------------------------------------

namespace drwnFactorGraphUtils {
    void writeDottyOutput(const char *filename, const drwnFactorGraph &graph);

    vector<set<int> > variableAdjacencyList(const drwnFactorGraph& graph);

    drwnFactorGraph createJunctionTree(const drwnFactorGraph& graph);

    double removeUniformFactors(drwnFactorGraph& graph);

    void absorbSmallFactors(drwnFactorGraph& graph, bool bIncludeUnary = true);

    void mergeDuplicateFactors(drwnFactorGraph& graph);
};