GraphCut.h

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Written (W) 2014 Jiaolong Xu
 * Copyright (C) 2014 Jiaolong Xu
 */

#ifndef __GRAPH_CUT_H__
#define __GRAPH_CUT_H__

#include <shogun/lib/config.h>

#include <shogun/lib/SGVector.h>
#include <shogun/lib/List.h>
#include <shogun/base/DynArray.h>
#include <shogun/structure/FactorGraph.h>
#include <shogun/structure/Factor.h>
#include <shogun/structure/MAPInference.h>

/* special constants for node->parent. */
#define TERMINAL_EDGE ( (GCEdge *) 1 ) // to terminal
#define ORPHAN_EDGE   ( (GCEdge *) 2 ) // orphan

#define INFINITE_D 1000000000 // infinite distance to the terminal

namespace shogun
{
enum ETerminalType
{
    SOURCE = 0,
    SINK = 1
};

struct GCNode;
struct GCEdge
{
    int32_t id;
    GCNode* head;
    GCEdge* next;
    GCEdge* reverse;
    float64_t residual_capacity;
};

struct GCNode
{
    int32_t id;
    GCEdge* first;
    GCEdge* parent;
    GCNode* next;
    int32_t timestamp;
    int32_t dist_terminal;
    ETerminalType type_tree;
    float64_t tree_cap;
};

struct GCNodePtr
{
    GCNode* ptr;
    GCNodePtr* next;
};

class CGraphCut : public CMAPInferImpl
{
public:
    CGraphCut();

    CGraphCut(CFactorGraph* fg);

    CGraphCut(int32_t num_nodes, int32_t num_edges);

    virtual ~CGraphCut();

    virtual const char* get_name() const
    {
        return "GraphCut";
    }

    virtual float64_t inference(SGVector<int32_t> assignment);

    float64_t get_flow()
    {
        return m_flow;
    }

    void build_st_graph(int32_t num_nodes, int32_t num_edges);

    void add_edge(int32_t i, int32_t j, float64_t capacity, float64_t reverse_capacity);

    void add_tweights(int32_t i, float64_t cap_source, float64_t cap_sink);

    void init_maxflow();

    float64_t compute_maxflow();

    ETerminalType get_assignment(int32_t i, ETerminalType default_terminal = SOURCE);

    void print_graph();

    void print_assignment();

private:
    void init();

    void add_factor(CFactor* factor);

    int32_t get_tripleId(SGVector<int32_t> triple);

    void set_active(GCNode* node_i);

    GCNode* next_active();

    void set_orphan_front(GCNode* node_i);

    void set_orphan_rear(GCNode* node_i);

    void process_orphan(GCNode* node_i, ETerminalType terminalType_tree);

    bool grow(GCEdge* &edge, GCNode* &current_node);

    void augment_path(GCEdge* connecting_edge);

    void adopt();

    void test_consistency(GCNode* current_node = NULL);
protected:
    float64_t m_map_energy;

private:
    int32_t m_num_variables;
    SGVector<int32_t> m_num_factors_at_order;
    DynArray< SGVector<int32_t> > m_triple_list;

    GCNode*     m_nodes;
    int32_t     m_num_nodes;
    GCEdge*     m_edges;
    GCEdge*     m_edges_last;
    int32_t     m_num_edges;

    float64_t   m_flow;
    int32_t     m_timestamp;

    GCNode*     m_active_first[2];
    GCNode*     m_active_last[2];

    GCNodePtr*  m_orphan_first;
    GCNodePtr*  m_orphan_last;
};

}
#endif