common_types.hpp

Go to the documentation of this file.

/***************************************************************************
 *                                                                          *
 *   Copyright (C) 2018 by David B. Blumenthal                              *
 *                                                                          *
 *   This file is part of GEDLIB.                                           *
 *                                                                          *
 *   GEDLIB is free software: you can redistribute it and/or modify it      *
 *   under the terms of the GNU Lesser General Public License as published  *
 *   by the Free Software Foundation, either version 3 of the License, or   *
 *   (at your option) any later version.                                    *
 *                                                                          *
 *   GEDLIB is distributed in the hope that it will be useful,              *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of         *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the           *
 *   GNU Lesser General Public License for more details.                    *
 *                                                                          *
 *   You should have received a copy of the GNU Lesser General Public       *
 *   License along with GEDLIB. If not, see <http://www.gnu.org/licenses/>. *
 *                                                                          *
 ***************************************************************************/

#ifndef SRC_ENV_COMMON_TYPES_HPP_
#define SRC_ENV_COMMON_TYPES_HPP_

// Include standard libraries.
#include <cstddef>
#include <functional>
#include <limits>
#include <vector>
#include <list>
#include <initializer_list>
#include <map>
#include <queue>
#include <string>
#include <unordered_set>
#include <chrono>
#include <cmath>
#include <iostream>
#include <ios>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <random>
#include <stdexcept>
#include <sstream>
#include <typeinfo>
#ifdef _OPENMP
#include <omp.h>
#endif

// Include Boost libraries.
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/copy.hpp>
#include <boost/graph/max_cardinality_matching.hpp>
#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/xml_parser.hpp>

// Include Gurobi.
#ifdef GUROBI
#include <gurobi_c++.h>
#endif

// Include external non-standard libraries.
#ifndef LSAPE_IndexType
#define LSAPE_IndexType std::size_t
#endif
#include <lsap.h>
#include <lsape.h>
#include <svm.h>
#include <doublefann.h>
#include <fann_cpp.h>
#include <Dense>
#include <nomad.hpp>

// Include helper classes.
#include "timer.hpp"
#include "error.hpp"
#include "progress_bar.hpp"


namespace ged {

typedef std::chrono::duration<double> Seconds;

typedef std::map<std::string, std::string> GXLLabel;

template<class Key, class Value>
std::ostream & operator<<(std::ostream & os, const std::map<Key, Value> & map) {
    os << "{ ";
    for (const auto & key_val : map) {
        os << "(" << key_val.first << "," << key_val.second << ") ";
    }
    os << "}";
    return os;
}

typedef std::string GXLNodeID;

typedef std::size_t LabelID;

struct NoLabel {};

constexpr bool operator==(NoLabel const &, NoLabel const &) {return true;}

constexpr LabelID invalid_label() {return std::numeric_limits<LabelID>::max();}

constexpr LabelID dummy_label() {return 0;}


constexpr std::size_t undefined() {return std::numeric_limits<std::size_t>::max();}

constexpr double pi() {return 3.141592653589793238463;}

struct Options {


    enum class GEDMethod {
#ifdef GUROBI
        F1,                  
        F2,                  
        COMPACT_MIP,         
        BLP_NO_EDGE_LABELS,  
#endif /* GUROBI */
        BRANCH,              
        BRANCH_FAST,         
        BRANCH_TIGHT,        
        BRANCH_UNIFORM,      
        BRANCH_COMPACT,      
        PARTITION,           
        HYBRID,              
        RING,                
        ANCHOR_AWARE_GED,    
        WALKS,               
        IPFP,                
        BIPARTITE,           
        SUBGRAPH,            
        NODE,                
        RING_ML,             
        BIPARTITE_ML,        
        REFINE,              
        BP_BEAM,             
        SIMULATED_ANNEALING, 
        HED,                 
        STAR                 
    };

    enum class EditCosts {
        CHEM_1,      
        CHEM_2,      
        CMU,         
        GREC_1,      
        GREC_2,      
        PROTEIN,     
        FINGERPRINT, 
        LETTER,      
        CONSTANT     
    };

    enum class GXLNodeEdgeType {
        LABELED,  
        UNLABELED 
    };

    enum class InitType {
        LAZY_WITHOUT_SHUFFLED_COPIES, 
        EAGER_WITHOUT_SHUFFLED_COPIES, 
        LAZY_WITH_SHUFFLED_COPIES, 
        EAGER_WITH_SHUFFLED_COPIES 
    };

};

std::ostream & operator<<(std::ostream & os, const Options::GEDMethod & ged_method) {
    switch (ged_method) {
    case Options::GEDMethod::BRANCH:
        os << "BRANCH";
        break;
    case Options::GEDMethod::BRANCH_FAST:
        os << "BRANCH_FAST";
        break;
    case Options::GEDMethod::BRANCH_TIGHT:
        os << "BRANCH_TIGHT";
        break;
    case Options::GEDMethod::BRANCH_UNIFORM:
        os << "BRANCH_UNIFORM";
        break;
    case Options::GEDMethod::BRANCH_COMPACT:
        os << "BRANCH_COMPACT";
        break;
    case Options::GEDMethod::PARTITION:
        os << "PARTITION";
        break;
    case Options::GEDMethod::HYBRID:
        os << "HYBRID";
        break;
    case Options::GEDMethod::RING:
        os << "RING";
        break;
    case Options::GEDMethod::ANCHOR_AWARE_GED:
        os << "ANCHOR_AWARE_GED";
        break;
    case Options::GEDMethod::WALKS:
        os << "WALKS";
        break;
    case Options::GEDMethod::IPFP:
        os << "IPFP";
        break;
    case Options::GEDMethod::BIPARTITE:
        os << "BIPARTITE";
        break;
    case Options::GEDMethod::SUBGRAPH:
        os << "SUBGRAPH";
        break;
    case Options::GEDMethod::NODE:
        os << "NODE";
        break;
    case Options::GEDMethod::RING_ML:
        os << "RING_ML";
        break;
    case Options::GEDMethod::BIPARTITE_ML:
        os << "BIPARTITE_ML";
        break;
    case Options::GEDMethod::REFINE:
        os << "REFINE";
        break;
    case Options::GEDMethod::BP_BEAM:
        os << "BP_BEAM";
        break;
    case Options::GEDMethod::SIMULATED_ANNEALING:
        os << "SIMULATED_ANNEALING";
        break;
    case Options::GEDMethod::HED:
        os << "HED";
        break;
    case Options::GEDMethod::STAR:
        os << "STAR";
        break;
#ifdef GUROBI
    case Options::GEDMethod::F1:
        os << "F1";
        break;
    case Options::GEDMethod::F2:
        os << "F2";
        break;
    case Options::GEDMethod::COMPACT_MIP:
        os << "COMPACT_MIP";
        break;
    case Options::GEDMethod::BLP_NO_EDGE_LABELS:
        os << "BLP_NO_EDGE_LABELS";
        break;
#endif
    }
    return os;
}

template<class UserNodeID, class UserNodeLabel, class UserEdgeLabel> struct ExchangeGraph {

    std::size_t id;                                                                   

    std::size_t num_nodes;                                                            

    std::size_t num_edges;                                                            

    std::vector<UserNodeID> original_node_ids;                                        

    std::vector<UserNodeLabel> node_labels;                                           

    std::vector<std::vector<std::size_t>> adj_matrix;                                 

    std::map<std::pair<std::size_t, std::size_t>, UserEdgeLabel> edge_labels;         

    bool operator==(const ExchangeGraph<UserNodeID, UserNodeLabel, UserEdgeLabel> & rhs) const {
        return ((original_node_ids == rhs.original_node_ids) and (node_labels == rhs.node_labels) and (adj_matrix == rhs.adj_matrix) and (edge_labels == rhs.edge_labels));
    };
};

#ifdef ENABLE_GRAPH_STREAMING

template<class UserNodeID, class UserNodeLabel, class UserEdgeLabel>
std::ostream & operator<<(std::ostream & os, const ExchangeGraph<UserNodeID, UserNodeLabel, UserEdgeLabel> & graph) {
    os << "graph [\n";
    os << "\tid = " << graph.id << "\n";
    os << "\tdirected = 0\n";
    os << "\tnum_nodes = " << graph.num_nodes << "\n";
    os << "\tnum_edges = " << graph.num_edges << "\n";
    for (std::size_t node_id{0}; node_id < graph.num_nodes; node_id++) {
        os << "\tnode [\n";
        os << "\t\tinternal_id = " << node_id << "\n";
        os << "\t\toriginal_id = \"" << graph.original_node_ids.at(node_id) << "\"\n";
        os << "\t\tlabel = \"" << graph.node_labels.at(node_id) << "\"\n";
        os << "\t]\n";
    }
    for (std::size_t tail_id{0}; tail_id < graph.num_nodes; tail_id++) {
        for (std::size_t head_id{tail_id + 1}; head_id < graph.num_nodes; head_id++) {
            if (graph.adj_matrix[node_id][head_id] == 1) {
                os << "\tedge [\n";
                os << "\t\tinternal_id_tail = " << tail_id << "\n";
                os << "\t\tinternal_id_head = " << head_id << "\n";
                os << "\t\tlabel = \"" << graph.edge_labels[std::make_pair(tail_id, head_id)] << "\"\n";
                os << "\t]\n";
            }
        }
    }
    os << "]\n";
    return os;
}
#endif /* ENABLE_GRAPH_STREAMING */

}

#endif /* SRC_ENV_COMMON_TYPES_HPP_ */