base_directed_graph.hpp

Go to the documentation of this file.

#ifndef BASE_DIRECTED_GRAPH_HPP_INCLUDED
#define BASE_DIRECTED_GRAPH_HPP_INCLUDED

// Standard Library
#include <algorithm> // set_intersection
#include <cstdlib>   // abort
#include <iostream>
#include <list>
#include <set>
#include <string>
#include <vector>
// Graph C++ Library
#include "base_graph.hpp"

namespace gcl
{

  template <class VertexType>
  class base_directed_graph : public gcl::base_graph<VertexType>
  {
    // ============================================================================================
    // *** Objects related to the graph.
    protected:
      // const unsigned int nb_degree_types;                              ///< Numbers of different degree types (in this case 2)
      const unsigned int id_out_degree;                                
      const unsigned int id_in_degree;                                 
    // ============================================================================================
    // *** Information about the graph.
    private:
      double reciprocity;                                                   
      unsigned int nb_reciprocal_edges;                                     
      std::list< std::vector<unsigned int> > triangles;                     
      // Quantities related to the undirected projection of the graph (regardless of the direction of the edges).
      unsigned int nb_undirected_projection_wedges;                         
      unsigned int nb_undirected_projection_triangles;                      
      double       global_undirected_projection_clustering_coefficient;     
      double       avg_local_undirected_projection_clustering_coefficient;  
    // ============================================================================================
    // *** Status of the properties computed.
    private:
      bool has_triangles_been_surveyed;
      bool has_nb_reciprocal_edges_been_computed;
      bool have_undirected_projection_clustering_coefficients_been_computed;
    // ============================================================================================
    // *** Member functions.
    public:
      base_directed_graph();                                                      
      virtual ~base_directed_graph() {}                                           
      unsigned int get_nb_reciprocal_edges();                                     
      double       get_reciprocity();                                             
      unsigned int get_nb_undirected_projection_triangles();                      
      unsigned int get_nb_undirected_projection_wedges();                         
      double       get_global_undirected_projection_clustering_coefficient();     
      double       get_avg_local_undirected_projection_clustering_coefficient();  
      unsigned int get_min_in_degree();                                           
      unsigned int get_max_in_degree();                                           
      double       get_avg_in_degree();                                           
      unsigned int get_min_out_degree();                                          
      unsigned int get_max_out_degree();                                          
      double       get_avg_out_degree();                                          
      void         survey_triangles();                                            
      void write_edgelist(std::string _name);                                     
      // void analyse_structural_properties();                                    ///< Computes a set of structural properties.
      void compute_nb_reciprocal_edges();                                         
      void compute_undirected_projection_clustering_coefficients();               
      virtual void write_graph_properties(std::string _name) = 0;                 
      virtual void write_vertices_properties(std::string _name) = 0;              
    protected:
      void base_directed_graph_clear();                                           
  };

} // End of namespace gcl.



// ================================================================================================
// ================================================================================================
template <class VertexType>
gcl::base_directed_graph<VertexType>::base_directed_graph()
: /*nb_degree_types(2),*/ id_out_degree(0), id_in_degree(1) { }

// ================================================================================================
// ================================================================================================
template <class VertexType>
unsigned int gcl::base_directed_graph<VertexType>::get_nb_reciprocal_edges()
{
  return nb_reciprocal_edges;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
double gcl::base_directed_graph<VertexType>::get_reciprocity()
{
  return reciprocity;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
unsigned int gcl::base_directed_graph<VertexType>::get_min_in_degree()
{
  return this->get_base_graph_min_degrees(id_in_degree);
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
unsigned int gcl::base_directed_graph<VertexType>::get_max_in_degree()
{
  return this->get_base_graph_max_degrees(id_in_degree);
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
double gcl::base_directed_graph<VertexType>::get_avg_in_degree()
{
  return this->get_base_graph_avg_degrees(id_in_degree);
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
unsigned int gcl::base_directed_graph<VertexType>::get_min_out_degree()
{
  return this->get_base_graph_min_degrees(id_out_degree);
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
unsigned int gcl::base_directed_graph<VertexType>::get_max_out_degree()
{
  return this->get_base_graph_max_degrees(id_out_degree);
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
double gcl::base_directed_graph<VertexType>::get_avg_out_degree()
{
  return this->get_base_graph_avg_degrees(id_out_degree);
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
unsigned int gcl::base_directed_graph<VertexType>::get_nb_undirected_projection_triangles()
{
  return nb_undirected_projection_triangles;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
unsigned int gcl::base_directed_graph<VertexType>::get_nb_undirected_projection_wedges()
{
  return nb_undirected_projection_wedges;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
double gcl::base_directed_graph<VertexType>::get_global_undirected_projection_clustering_coefficient()
{
  return global_undirected_projection_clustering_coefficient;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
double gcl::base_directed_graph<VertexType>::get_avg_local_undirected_projection_clustering_coefficient()
{
  return avg_local_undirected_projection_clustering_coefficient;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
void gcl::base_directed_graph<VertexType>::write_edgelist(std::string _name)
{
  // Stream objects.
  std::ofstream edgelist_file;
  // String objects.
  std::string edgelist_filename = _name + "_edgelist.dat";
  std::string node1_str;
  // Operator objects.
  typename VertexType::iterator it, end;
  // Opens the stream and aborts if the operation did not succeed.
  edgelist_file.open(edgelist_filename.c_str(), std::ios_base::out);
  if( !edgelist_file.is_open() )
  {
    std::cout << "Could not open file: " << edgelist_filename << "." << std::endl;
    abort();
  }
  // Writes each edges in the format "node1 node2". Each edge appears once.
  for(unsigned int node1(0), node2, nn(this->get_nb_vertices()); node1<nn; ++node1)
  {
    // Browses the out neighbours of node1.
    it  = (*this)(node1)->out_neighbour_begin();
    end = (*this)(node1)->out_neighbour_end();
    node1_str = (*this)(node1)->get_name();
    for(; it!=end; ++it)
    {
      node2 = it->id;
      edgelist_file << node1_str << "  " << (*this)(node2)->get_name() << std::endl;
    }
  }
  // Closes the stream.
  edgelist_file.close();
}

// // ================================================================================================
// // ================================================================================================
// template <class VertexType>
// void gcl::base_directed_graph<VertexType>::analyse_structural_properties()
// {
//   // Degree distributions.
//   this->survey_degrees_distribution();
//   // Number of reciprocal edges.
//   compute_nb_reciprocal_edges();
// }

// ================================================================================================
// ================================================================================================
template <class VertexType>
void gcl::base_directed_graph<VertexType>::compute_nb_reciprocal_edges()
{
  // Vector objects.
  std::vector<unsigned int> intersection;
  // Set objects.
  std::set<unsigned int> in_neighbours, out_neighbours;
  // Iterator objects.
  std::vector<unsigned int>::iterator it;
  typename VertexType::iterator it_in, end_in, it_out, end_out;
  // Computes the intersection for the in- and out- neighbourhoods of each node.
  for(unsigned int n(0), nn(this->get_nb_vertices()); n<nn; ++n)
  {
    // Sets the iterators.
    it_in   = (*this)(n)->in_neighbour_begin();
    end_in  = (*this)(n)->in_neighbour_end();
    it_out  = (*this)(n)->out_neighbour_begin();
    end_out = (*this)(n)->out_neighbour_end();
    // Fills the ordered sets.
    in_neighbours.clear();
    for(; it_in!=end_in; ++it_in)
    {
      in_neighbours.insert(it_in->id);
    }
    out_neighbours.clear();
    for(; it_out!=end_out; ++it_out)
    {
      out_neighbours.insert(it_out->id);
    }
    // Counts the number of edges that are reciprocal.
    intersection.clear();
    intersection.resize(std::min((*this)(n)->get_in_degree(), (*this)(n)->get_out_degree()));
    it = std::set_intersection(in_neighbours.begin(), in_neighbours.end(), out_neighbours.begin(), out_neighbours.end(), intersection.begin());
    intersection.resize(it-intersection.begin());
    nb_reciprocal_edges += intersection.size();
    (*this)(n)->set_nb_reciprocal_edges(2 * intersection.size());
  }
  // // Divides the number of intersections found since every reciprocal edge is counted twice.
  // nb_reciprocal_edges /= 2;
  // Computes the reciprocity.
  reciprocity = static_cast<double>(this->get_nb_reciprocal_edges()) / this->get_nb_edges();
  // Indicates that the calculations has been done.
  has_nb_reciprocal_edges_been_computed = true;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
void gcl::base_directed_graph<VertexType>::survey_triangles()
{
  // Ensures that required quantities have previously been calculated.
  if(!has_nb_reciprocal_edges_been_computed)
  {
    compute_nb_reciprocal_edges();
  }
  // Vector objects.
  std::vector<unsigned int> intersection;
  // Set objects.
  std::set<unsigned int> neighbours_v1, neighbours_v2;
  // Iterator objects.
  std::vector<unsigned int>::iterator it;
  typename VertexType::iterator it1, end1, it2, end2;
  std::set<unsigned int>::iterator it3, end3;
  // Computes the intersection for the in- and out- neighbourhoods of each node.
  for(unsigned int v1(0), v2, v3, d1, d2, nn(this->get_nb_vertices()); v1<nn; ++v1)
  {
    // Projected undirected degree of vertex v1.
    d1 = (*this)(v1)->get_undirected_projection_degree();
    // Performs the calculation only if d1>1.
    if( d1 > 1 )
    {
      // Builds an ordered list of the neighbourhood of v1 (neighbors appear only once).
      neighbours_v1.clear();
      it1  = (*this)(v1)->out_neighbour_begin();
      end1 = (*this)(v1)->out_neighbour_end();
      for(; it1 != end1; ++it1)
      {
        neighbours_v1.insert(it1->id);
      }
      it1  = (*this)(v1)->in_neighbour_begin();
      end1 = (*this)(v1)->in_neighbour_end();
      for(; it1 != end1; ++it1)
      {
        neighbours_v1.insert(it1->id);
      }
      // it1 = (*this)(v1)->neighbour_begin();
      // Loops over the neighbours of vertex v1.
      it3  = neighbours_v1.begin();
      end3 = neighbours_v1.end();
      for(; it3!=end3; ++it3)
      {
        // Identity and degree of vertex 2.
        v2 = *it3;
        d2 = (*this)(v2)->get_undirected_projection_degree();
        // Performs the calculation only if d1>1 and if v2>v1 (ensures that each triangle is counted once).
        if( v2 > v1 && d2 > 1 )
        {
          // Builds an ordered list of the neighbourhood of v2 (neighbors appear only once).
          neighbours_v2.clear();
          it2  = (*this)(v2)->out_neighbour_begin();
          end2 = (*this)(v2)->out_neighbour_end();
          for(; it2 != end2; ++it2)
          {
            v3 = it2->id;
            if(v3 > v2) // Ensures that triangles will be counted only once.
            {
              neighbours_v2.insert(v3);
            }
          }
          it2  = (*this)(v2)->in_neighbour_begin();
          end2 = (*this)(v2)->in_neighbour_end();
          for(; it2 != end2; ++it2)
          {
            v3 = it2->id;
            if(v3 > v2) // Ensures that triangles will be counted only once.
            {
              neighbours_v2.insert(v3);
            }
          }
          d2 = neighbours_v2.size();
          // Identifies the triangles.
          intersection.clear();
          intersection.resize(std::min(d1,d2));
          it = std::set_intersection(neighbours_v1.begin(), neighbours_v1.end(), neighbours_v2.begin(), neighbours_v2.end(), intersection.begin());
          intersection.resize(it-intersection.begin());
          // Loops over the common neighbours of vertices v1 and v2.
          for(unsigned int n(0), nn(intersection.size()); n<nn; ++n)
          {
            // Identity and degree of vertex 2.
            v3 = intersection[n];
            // Considers the triangle only if v1 is the lowest index (ensures that each triangle is counted once).
            // if(v3 > v1)
            {
              // Adds the triangle to the list.
              triangles.push_back({v1,v2,v3});
            }
          }
        }
      }
    }
  }
  // Counts the number of triangles.
  nb_undirected_projection_triangles = triangles.size();
  // Indicates that the calculations has been done.
  has_triangles_been_surveyed = true;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
void gcl::base_directed_graph<VertexType>::compute_undirected_projection_clustering_coefficients()
{
  // Ensures that required quantities have previously been calculated.
  if(!has_triangles_been_surveyed)
  {
    survey_triangles();
  }
  // Sets the local clustering coefficients.
  unsigned int v1, v2, v3;
  std::list< std::vector<unsigned int> >::iterator it  = triangles.begin();
  std::list< std::vector<unsigned int> >::iterator end = triangles.end();
  for(unsigned int v; it != end; ++it)
  {
    // std::cout << (*it)[0] << "  " << (*it)[1] << "  " << (*it)[2] << std::endl;
    // Loops over the three vertices in the triangle.
    for(unsigned int i(0); i<3; ++i)
    {
      v = (*it)[i];
      (*this)(v)->set_nb_undirected_projection_triangles((*this)(v)->get_nb_undirected_projection_triangles() + 1);
    }
  }
  // Counts the number of wedges and computes the average local clustering coefficient.
  for(unsigned int n(0), d, nn(this->get_nb_vertices()); n<nn; ++n)
  {
    // Number of wedges.
    d = (*this)(n)->get_undirected_projection_degree();
    nb_undirected_projection_wedges += d * ( d - 1. ) / 2.;
    // Local clustering coefficient.
    avg_local_undirected_projection_clustering_coefficient += (*this)(n)->get_local_undirected_projection_clustering_coefficient();
  }
  avg_local_undirected_projection_clustering_coefficient /= this->get_nb_vertices();
  // Sets the global clustering coefficient.
  global_undirected_projection_clustering_coefficient = 3. * this->get_nb_undirected_projection_triangles() / nb_undirected_projection_wedges;
  // Indicates that the calculations has been done.
  have_undirected_projection_clustering_coefficients_been_computed = true;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
void gcl::base_directed_graph<VertexType>::base_directed_graph_clear()
{
  // Resets the number of types of vertices.
  this->set_nb_of_types_of_degrees(2);
  // Resets the variables inherited from base_graph.
  this->base_graph_clear();
  // Resets various objects.
  reciprocity = 0;
  nb_reciprocal_edges = 0;
  nb_undirected_projection_wedges = 0;
  nb_undirected_projection_triangles = 0;
  global_undirected_projection_clustering_coefficient = 0;
  avg_local_undirected_projection_clustering_coefficient = 0;
  has_triangles_been_surveyed = false;
  triangles.clear();
  // Resets boolean indicators.
  has_triangles_been_surveyed = false;
  has_nb_reciprocal_edges_been_computed = false;
  have_undirected_projection_clustering_coefficients_been_computed = false;
}



#endif // BASE_DIRECTED_GRAPH_HPP_INCLUDED