graph.h

Go to the documentation of this file.

#ifndef GRAPH_H_
#define GRAPH_H_

#include "MyTools.h"
#include <iostream>
#include <map>
#include <vector>

#include <boost/graph/adjacency_list.hpp>

#include "types.h"

struct undirected_t
{
    typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS,
            boost::property<boost::vertex_name_t, double>,
            boost::property<boost::edge_name_t, double> > graph; 
    typedef boost::graph_traits<graph>::vertex_descriptor vertex; 
    typedef boost::graph_traits<graph>::edge_descriptor edge; 
    typedef boost::graph_traits<graph>::edge_iterator edge_iterator; 
    typedef std::map<lui, vertex> map; 
    typedef double edge_name_t; 
    typedef lui vertex_name_t; 
};


struct directed_t
{
    typedef boost::adjacency_list<boost::setS, boost::listS, boost::directedS,
            boost::property<boost::vertex_name_t, lui>,
            boost::property<boost::edge_name_t, lui> > graph; 
    typedef boost::graph_traits<graph>::vertex_descriptor vertex; 
    typedef boost::graph_traits<graph>::edge_descriptor edge; 
    typedef boost::graph_traits<graph>::edge_iterator edge_iterator;
    typedef std::map<lui, vertex> map;
    typedef double edge_name_t; 
    typedef lui vertex_name_t; 
};


struct bidirected_t
{
    typedef boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS,
            boost::property<boost::vertex_name_t, lui>,
            boost::property<boost::edge_name_t, double> > graph; 
    typedef boost::graph_traits<graph>::vertex_descriptor vertex; 
    typedef boost::graph_traits<graph>::edge_descriptor edge; 
    typedef boost::graph_traits<graph>::edge_iterator edge_iterator; 
    typedef std::map<lui, vertex> map;
    typedef double edge_name_t; 
    typedef lui vertex_name_t; 
};


template <typename graph_t>
typename graph_t::vertex add_or_get_vertex(typename graph_t::graph &g,
        typename graph_t::map &vertices, lui id)
{
    typename graph_t::map::iterator pos;
    bool inserted;
    typename graph_t::vertex v;

    boost::tie(pos, inserted) = vertices.insert(
            std::make_pair(id, typename graph_t::vertex()));

    if (inserted)
    {
        v = add_vertex(g);
        boost::put(boost::vertex_name, g, v, id);
        pos->second = v;
    }
    else
    {
        v = pos->second;
    }
    return v;
}


template <typename graph_t>
void bump_edge(typename graph_t::graph &g, typename graph_t::map &vertices,
        typename graph_t::vertex_name_t fr, typename graph_t::vertex_name_t to)
{
    typename graph_t::vertex u, v;
    typename graph_t::edge_name_t weight;
    u = add_or_get_vertex<graph_t>(g, vertices, fr);
    v = add_or_get_vertex<graph_t>(g, vertices, to);

    typename graph_t::edge e;
    bool inserted;
    boost::tie(e, inserted) = boost::add_edge(u, v, g);
    if (inserted)
    {
        boost::put(boost::edge_name, g, e, 1);
    }
    else
    {
        weight = boost::get(boost::edge_name, g, e);
        boost::put(boost::edge_name, g, e, weight + 1);
    }
}

template <typename graph_t>
void read_from_stream(typename graph_t::graph& g, typename graph_t::map& vertices, map <string, lui>& id,
        std::ifstream& in, double alpha, double beta, double weightThresh, string delimiter)
{
    typename graph_t::vertex_name_t fr;
    typename graph_t::vertex_name_t to;
    typename graph_t::edge_name_t wt;

    vector <string> fields;
    map <string, lui>::iterator mit;
    lui NextId = 0;
    
    for (mit = id.begin(); mit != id.end(); mit++)
    {
      if (mit->second > NextId)
        NextId = mit->second;
    }
    
    NextId++;

    double maxWeight = 0;

    while (fline_tr(&in, &fields, delimiter.c_str()))
      {
        if (fields.size() != 3)
          continue;

        double dw = boost::lexical_cast<double>(fields[2]);
        if (abs(dw) > maxWeight)
          maxWeight = abs(dw);
      }

    beta = beta / maxWeight;
    alpha = alpha / maxWeight;

    in.clear();
    in.seekg(0, ios::beg);

    ofstream gout("TrueNetwork.dat");
    while (fline_tr(&in, &fields, delimiter.c_str()) )
    {
      if (fields.size() != 3)
        continue;

      double dw = boost::lexical_cast<double>(fields[2]);
      if (dw < 0)
        dw *= beta;
      else
        dw *= alpha;
      
      if (abs(dw) < weightThresh)
        continue;
      
      wt = boost::lexical_cast<typename graph_t::edge_name_t>(dw);
      
      if ((mit = id.find(fields[0])) != id.end())
        fr = mit->second;
      else
      {
        id.insert(make_pair<string, int>(fields[0], NextId));
        fr = NextId++;
      }
      
      if ((mit = id.find(fields[1])) != id.end())
        to = mit->second;
      else
      {
        id.insert(make_pair<string, int>(fields[1], NextId));
        to = NextId++;
      }
      
      gout << fr << ", " << to << ", " << dw << endl;
      
      typename graph_t::vertex u, v;
      u = add_or_get_vertex<graph_t>(g, vertices, fr);
      v = add_or_get_vertex<graph_t>(g, vertices, to);

      if (u == v)
      {
          // Disallow self-edges.
          continue;
      }

      typename graph_t::edge e;
      bool inserted;
      boost::tie(e, inserted) = boost::add_edge(u, v, g);
      if (inserted)
      {
          boost::put(boost::edge_name, g, e, wt);
      }
      else
      {
        typename graph_t::vertex_name_t a, b;
        a = boost::get(boost::vertex_name, g, u);
        b = boost::get(boost::vertex_name, g, v);
        cerr << a << " " << b << endl;
          throw "Duplicate edge not allowed. ";
      }
    }
}

template <typename graph_t>
void print_set(const typename graph_t::graph& g,
               const std::set<typename graph_t::vertex>& v, std::ostream& out, float density)
{
  if (density <= 0)
    return;
  
  string outString = "";
  if (v.size() > 2)
  {
    outString += boost::lexical_cast<string>(density) + " " + boost::lexical_cast<string>(v.size()) + " ";
    typename std::set<typename graph_t::vertex>::const_iterator i;
    for (i = v.begin(); i != v.end(); ++i)
    {
        typename graph_t::vertex_name_t u;
        u = boost::get(boost::vertex_name, g, *i);
        outString += boost::lexical_cast<string>(u) + " ";
    }
    outString += "\n";
    out << outString;
    out.flush();
  }
}
template <typename graph_t>
void print_set_trans(const typename graph_t::graph& g,
                     const std::set<typename graph_t::vertex>& v, std::ostream& out, float density, map<string, lui> ID, char delim)
{
  if (density <= 0){
    return;
  }
  map <lui, string> rID;
    map <lui, string>::iterator it_r;
    map <string, lui>::iterator it_id;
    set <lui>::iterator it_sl; 
    
    for (it_id = ID.begin(); it_id != ID.end(); it_id++){
      rID.insert(make_pair<lui, string>(it_id->second, it_id->first));
    }
    
  string outString = "";
  if (v.size() > 2)
  {
    outString += boost::lexical_cast<string>(density) + boost::lexical_cast<string>(delim) + " " + boost::lexical_cast<string>(v.size()) + boost::lexical_cast<string>(delim) + " ";
    typename std::set<typename graph_t::vertex>::const_iterator i;
    for (i = v.begin(); i != v.end(); ++i)
    {
        typename graph_t::vertex_name_t u;
        u = boost::get(boost::vertex_name, g, *i);
        outString += (rID.find(boost::lexical_cast<lui>(u)))->second + boost::lexical_cast<string>(delim) + " ";
    }
    outString = outString.substr(0, outString.size()-2) + "\n";
    out << outString;
    out.flush();
  }
}
#endif