base_undirected_graph.hpp

Go to the documentation of this file.

#ifndef BASE_UNDIRECTED_GRAPH_HPP_INCLUDED
#define BASE_UNDIRECTED_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_undirected_graph : public gcl::base_graph<VertexType>
  {
    // ============================================================================================
    // *** Objects related to the graph.
    private:
      const unsigned int id_degree;                                   
    // ============================================================================================
    // *** Information about the graph.
    private:
      unsigned int nb_wedges;                                         
      unsigned int nb_triangles;                                      
      double       global_clustering_coefficient;                     
      double       avg_local_clustering_coefficient;                  
      std::list< std::vector<unsigned int> > triangles;               
    // ============================================================================================
    // *** Member functions.
    public:
      base_undirected_graph();                                        
      virtual ~base_undirected_graph() {}                             
      unsigned int get_min_degree();                                  
      unsigned int get_max_degree();                                  
      double       get_avg_degree();                                  
      unsigned int get_nb_triangles();                                
      unsigned int get_nb_wedges();                                   
      double       get_global_clustering_coefficient();               
      double       get_avg_local_clustering_coefficient();            
      void write_edgelist(std::string _name);                         
      // void analyse_structural_properties();                           ///< Computes a set of structural properties.
      void survey_triangles();                                        
      void compute_clustering_coefficients();                         
      virtual void write_graph_properties(std::string _name) = 0;     
      virtual void write_vertices_properties(std::string _name) = 0;  
    protected:
      void base_undirected_graph_clear();                             
  };

} // End of namespace gcl.

// Il faudrait faire un wrap up de survey_degrees_distribution pour avoir une forme au singulier.


// ================================================================================================
// ================================================================================================
template <class VertexType>
gcl::base_undirected_graph<VertexType>::base_undirected_graph() : id_degree(0) {};

// ================================================================================================
// ================================================================================================
template <class VertexType>
unsigned int gcl::base_undirected_graph<VertexType>::get_min_degree()
{
  return this->get_base_graph_min_degrees(id_degree);
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
unsigned int gcl::base_undirected_graph<VertexType>::get_max_degree()
{
  return this->get_base_graph_max_degrees(id_degree);
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
double gcl::base_undirected_graph<VertexType>::get_avg_degree()
{
  return this->get_base_graph_avg_degrees(id_degree);
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
unsigned int gcl::base_undirected_graph<VertexType>::get_nb_triangles()
{
  return nb_triangles;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
unsigned int gcl::base_undirected_graph<VertexType>::get_nb_wedges()
{
  return nb_wedges;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
double gcl::base_undirected_graph<VertexType>::get_global_clustering_coefficient()
{
  return global_clustering_coefficient;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
double gcl::base_undirected_graph<VertexType>::get_avg_local_clustering_coefficient()
{
  return avg_local_clustering_coefficient;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
void gcl::base_undirected_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 neighbours of node1.
    it  = (*this)(node1)->neighbour_begin();
    end = (*this)(node1)->neighbour_end();
    node1_str = (*this)(node1)->get_name();
    for(; it!=end; ++it)
    {
      node2 = it->id;
      if(node1 < node2) // Ensures that undirected edges appear only once (excludes self-edges).
      {
        edgelist_file << node1_str << "  " << (*this)(node2)->get_name() << std::endl;
      }
    }
  }
  // Closes the stream.
  edgelist_file.close();
}

// // ================================================================================================
// // ================================================================================================
// template <class VertexType>
// void gcl::base_undirected_graph<VertexType>::analyse_structural_properties()
// {
//   // Degree distributions.
//   this->survey_degrees_distribution();
//   // Identifies the triangles.
//   survey_triangles();
//   // Computes the clustering coefficients.
//   compute_clustering_coefficients();
// }

// ================================================================================================
// ================================================================================================
template <class VertexType>
void gcl::base_undirected_graph<VertexType>::survey_triangles()
{
  // 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;
  // 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)
  {
    // Degree of vertex v1.
    d1 = (*this)(v1)->get_degree();
    // Performs the calculation only if d1>1.
    if( d1 > 1 )
    {
      // Builds an ordered list of the neighbourhood of v1
      it1  = (*this)(v1)->neighbour_begin();
      end1 = (*this)(v1)->neighbour_end();
      neighbours_v1.clear();
      for(; it1 != end1; ++it1)
      {
        neighbours_v1.insert(it1->id);
      }
      it1 = (*this)(v1)->neighbour_begin();
      // Loops over the neighbours of vertex v1.
      for(; it1!=end1; ++it1)
      {
        // Identity and degree of vertex 2.
        v2 = it1->id;
        d2 = (*this)(v2)->get_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
          it2  = (*this)(v2)->neighbour_begin();
          end2 = (*this)(v2)->neighbour_end();
          neighbours_v2.clear();
          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});
            }
          }
        }
      }
    }
  }
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
void gcl::base_undirected_graph<VertexType>::compute_clustering_coefficients()
{
  // 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)
  {
    // Loops over the three vertices in the triangle.
    for(unsigned int i(0); i<3; ++i)
    {
      v = (*it)[i];
      (*this)(v)->set_nb_triangles((*this)(v)->get_nb_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_degree();
    nb_wedges += d * ( d - 1. ) / 2.;
    // Local clustering coefficient.
    avg_local_clustering_coefficient += (*this)(n)->get_local_clustering_coefficient();
  }
  avg_local_clustering_coefficient /= this->get_nb_vertices();
  // Counts the number of triangles.
  nb_triangles = triangles.size();
  // Sets the global clustering coefficient.
  global_clustering_coefficient = 3. * nb_triangles / nb_wedges;
}

// ================================================================================================
// ================================================================================================
template <class VertexType>
void gcl::base_undirected_graph<VertexType>::base_undirected_graph_clear()
{
  // Resets the number of types of vertices.
  this->set_nb_of_types_of_degrees(1);
  // Resets the variables inherited from base_graph.
  this->base_graph_clear();
  // Resets the quatities related to the clustering.
  nb_wedges = 0;
  nb_triangles = 0;
  global_clustering_coefficient = 0;
  avg_local_clustering_coefficient = 0;
  triangles.clear();
}



#endif // BASE_UNDIRECTED_GRAPH_HPP_INCLUDED