graph.hpp

Go to the documentation of this file.

/*
 *
 *                   _/_/_/    _/_/   _/    _/ _/_/_/    _/_/
 *                  _/   _/ _/    _/ _/_/  _/ _/   _/ _/    _/
 *                 _/_/_/  _/_/_/_/ _/  _/_/ _/   _/ _/_/_/_/
 *                _/      _/    _/ _/    _/ _/   _/ _/    _/
 *               _/      _/    _/ _/    _/ _/_/_/  _/    _/
 *
 *             ***********************************************
 *                              PandA Project
 *                     URL: http://panda.dei.polimi.it
 *                       Politecnico di Milano - DEIB
 *                        System Architectures Group
 *             ***********************************************
 *              Copyright (C) 2004-2024 Politecnico di Milano
 *
 *   This file is part of the PandA framework.
 *
 *   The PandA framework 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.
 *
 *   This program 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 General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
#ifndef GRAPH_HPP
#define GRAPH_HPP

#include "edge_info.hpp"
#include "graph_info.hpp"
#include "node_info.hpp"

#include <fstream>
#include <ostream>

#include "custom_set.hpp"
#include <deque>
#include <list>

#include "exceptions.hpp"
#include "refcount.hpp"
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/version.hpp>
#include <utility>

CONSTREF_FORWARD_DECL(EdgeInfo);
CONSTREF_FORWARD_DECL(EdgeWriter);
CONSTREF_FORWARD_DECL(GraphWriter);
CONSTREF_FORWARD_DECL(NodeInfo);
REF_FORWARD_DECL(NodeInfo);
CONSTREF_FORWARD_DECL(Parameter);
CONSTREF_FORWARD_DECL(UEdgeWriter);
CONSTREF_FORWARD_DECL(UVertexWriter);
CONSTREF_FORWARD_DECL(VertexWriter);

using boost_raw_graph =
    boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS,
                          boost::property<boost::vertex_index_t, std::size_t, NodeInfoRef>, EdgeInfoRef, GraphInfoRef>;

struct RawGraph : public boost_raw_graph
{
 public:
   explicit RawGraph(GraphInfoRef g_info)
   {
      (*this)[boost::graph_bundle] = g_info;
   }

   ~RawGraph() = default;

   inline boost::graph_traits<boost_raw_graph>::vertex_descriptor AddVertex(const NodeInfoRef v_info)
   {
      size_t index = boost::num_vertices(*this);
      boost::graph_traits<boost_raw_graph>::vertex_descriptor new_v = boost::add_vertex(*this);
      (*this)[new_v] = v_info;
      boost::get(boost::vertex_index_t(), *this)[new_v] = index;
      return new_v;
   };

   inline void RemoveVertex(boost::graph_traits<boost_raw_graph>::vertex_descriptor v)
   {
      boost::remove_vertex(v, *this);
      boost::property_map<boost_raw_graph, boost::vertex_index_t>::type index_map =
          boost::get(boost::vertex_index_t(), *this);
      boost::graph_traits<boost_raw_graph>::vertex_iterator v_it, v_it_end;
      size_t index = 0;
      for(boost::tie(v_it, v_it_end) = boost::vertices(*this); v_it != v_it_end; v_it++, index++)
      {
         index_map[*v_it] = index;
      }
   }

   inline boost::graph_traits<boost_raw_graph>::edge_descriptor
   AddEdge(boost::graph_traits<boost_raw_graph>::vertex_descriptor src,
           boost::graph_traits<boost_raw_graph>::vertex_descriptor tgt, const EdgeInfoRef e_info)
   {
      boost::graph_traits<boost_raw_graph>::edge_descriptor e;
      bool found;
      boost::tie(e, found) = boost::edge(src, tgt, *this);
      THROW_ASSERT(not found, "Trying to insert an already existing edge");
      boost::tie(e, found) = boost::add_edge(src, tgt, e_info, *this);
      (*this)[e] = e_info;
      return e;
   }

   inline void RemoveEdge(boost::graph_traits<boost_raw_graph>::edge_descriptor e)
   {
      boost::remove_edge(boost::source(e, *this), boost::target(e, *this), *this);
   }

   inline void RemoveEdge(boost::graph_traits<boost_raw_graph>::vertex_descriptor src,
                          boost::graph_traits<boost_raw_graph>::vertex_descriptor tgt)
   {
      boost::graph_traits<boost_raw_graph>::edge_descriptor e;
      bool found;
      boost::tie(e, found) = boost::edge(src, tgt, *this);
      THROW_ASSERT(found, "Edge not found");
      boost::remove_edge(boost::source(e, *this), boost::target(e, *this), *this);
   }
};

template <class info_object, class Graph>
info_object* get_raw_edge_info(typename boost::graph_traits<Graph>::edge_descriptor e, Graph& g)
{
   EdgeInfoRef& info = g[e];
   if(!info)
   {
      info = EdgeInfoRef(new info_object);
   }
   THROW_ASSERT(GetPointer<info_object>(info) != nullptr,
                "Function get_raw_edge_info: the edges associated with the graph used are not derived from "
                "info_object\n\tCheck the actual type of info_object and the type of the edge of Graph");
   return GetPointer<info_object>(info);
}
template <class info_object, class Graph>
const info_object* Cget_raw_edge_info(typename boost::graph_traits<Graph>::edge_descriptor e, const Graph& g)
{
   const EdgeInfo* info = g[e].get();
   THROW_ASSERT(!info || dynamic_cast<const info_object*>(info) != nullptr,
                "Function Cget_raw_edge_info: the edges associated with the graph used are not derived from "
                "info_object\n\tCheck the actual type of info_object and the type of the edge of Graph");
   return info ? dynamic_cast<const info_object*>(info) : nullptr;
}

#define GET_RAW_EDGE_INFO(data, edge_info, edge_index) get_edge_info<edge_info>(edge_index, *(data))

#define CGET_RAW_EDGE_INFO(data, edge_info, edge_index) Cget_edge_info<edge_info>(edge_index, *(data))

struct EdgeProperty
{
 public:
   int selector;

   EdgeInfoRef info;

   EdgeProperty() : selector(0)
   {
   }

   explicit EdgeProperty(int _selector) : selector(_selector)
   {
   }

   EdgeProperty(const int _selector, EdgeInfoRef _info) : selector(_selector), info(_info)
   {
   }
};
#if BOOST_VERSION >= 104600
using boost_graphs_collection = boost::adjacency_list<
    boost::listS, boost::listS, boost::bidirectionalS,
    boost::property<boost::vertex_index_t, std::size_t,
                    boost::property<boost::vertex_color_t, boost::default_color_type, NodeInfoRef>>,
    EdgeProperty, GraphInfoRef>;

using undirected_boost_graphs_collection = boost::adjacency_list<
    boost::listS, boost::listS, boost::undirectedS,
    boost::property<boost::vertex_index_t, std::size_t,
                    boost::property<boost::vertex_color_t, boost::default_color_type, NodeInfoRef>>,
    EdgeProperty, GraphInfoRef>;

#define boost_CGetOpGraph_property(graph_arg) (graph_arg)[boost::graph_bundle]

#else

struct graph_info_t
{
   typedef boost::graph_property_tag kind;
};

typedef boost::property<graph_info_t, GraphInfoRef> GraphProperty;

typedef boost::adjacency_list<
    boost::listS, boost::listS, boost::bidirectionalS,
    boost::property<boost::vertex_index_t, std::size_t,
                    boost::property<boost::vertex_color_t, boost::default_color_type, NodeInfoRef>>,
    EdgeProperty, GraphProperty>
    boost_graphs_collection;

typedef boost::adjacency_list<
    boost::listS, boost::listS, boost::undirectedS,
    boost::property<boost::vertex_index_t, std::size_t,
                    boost::property<boost::vertex_color_t, boost::default_color_type, NodeInfoRef>>,
    EdgeProperty, GraphProperty>
    undirected_boost_graphs_collection;

#define boost_CGetOpGraph_property(graph_arg) boost::get_property(graph_arg, graph_info_t())

#endif

struct graphs_collection : public boost_graphs_collection
{
 public:
   const ParameterConstRef parameters;

   graphs_collection(GraphInfoRef info, const ParameterConstRef _parameters) : parameters(_parameters)
   {
      boost_CGetOpGraph_property(*this) = info;
   }

   virtual ~graphs_collection() = default;

   inline boost::graph_traits<graphs_collection>::edge_descriptor
   AddSelector(const boost::graph_traits<graphs_collection>::edge_descriptor edge, const int selector)
   {
      (*this)[edge].selector |= selector;
      return edge;
   }

   inline boost::graph_traits<graphs_collection>::edge_descriptor
   AddSelector(const boost::graph_traits<graphs_collection>::vertex_descriptor source,
               const boost::graph_traits<graphs_collection>::vertex_descriptor target, const int selector)
   {
      boost::graph_traits<graphs_collection>::edge_descriptor edge;
      bool inserted;
      boost::tie(edge, inserted) = boost::edge(source, target, *this);
      THROW_ASSERT(inserted, "Edge not found");
      AddSelector(edge, selector);
      return edge;
   }

   inline void RemoveSelector(boost::graph_traits<graphs_collection>::edge_descriptor edge)
   {
      (*this)[edge].selector = 0;
   }

   inline void RemoveSelector(boost::graph_traits<graphs_collection>::edge_descriptor edge, const int selector)
   {
      (*this)[edge].selector = (*this)[edge].selector & ~selector;
   }

   inline void RemoveSelector(boost::graph_traits<graphs_collection>::vertex_descriptor source,
                              boost::graph_traits<graphs_collection>::vertex_descriptor target, const int selector)
   {
      boost::graph_traits<graphs_collection>::edge_descriptor edge;
      bool inserted;
      boost::tie(edge, inserted) = boost::edge(source, target, *this);
      THROW_ASSERT(inserted, "Edge not found");
      RemoveSelector(edge, selector);
   }

   inline int GetSelector(const edge_descriptor e) const
   {
      return (*this)[e].selector;
   }

   virtual boost::graph_traits<boost_graphs_collection>::vertex_descriptor AddVertex(const NodeInfoRef info);

   inline boost::graph_traits<graphs_collection>::edge_descriptor
   AddEdge(boost::graph_traits<graphs_collection>::vertex_descriptor,
           boost::graph_traits<graphs_collection>::vertex_descriptor, const int)
   {
      THROW_UNREACHABLE("This function should be overriden by derived classes");
      return boost::graph_traits<graphs_collection>::edge_descriptor();
   }

   inline boost::graph_traits<graphs_collection>::edge_descriptor
   InternalAddEdge(boost::graph_traits<graphs_collection>::vertex_descriptor source,
                   boost::graph_traits<graphs_collection>::vertex_descriptor target, const int selector,
                   const EdgeInfoRef info)
   {
      boost::graph_traits<graphs_collection>::edge_descriptor edge;
      bool inserted;
      boost::tie(edge, inserted) = boost::edge(source, target, *this);
      THROW_ASSERT(not inserted, "Trying to add an already existing edge");
      boost::add_edge(source, target, EdgeProperty(selector), *this);
      boost::tie(edge, inserted) = boost::edge(source, target, *this);
      AddSelector(source, target, selector);
      (*this)[edge].info = info;
      return edge;
   }

   virtual void RemoveVertex(boost::graph_traits<boost_graphs_collection>::vertex_descriptor v);

   inline bool ExistsEdge(const boost::graph_traits<graphs_collection>::vertex_descriptor source,
                          const boost::graph_traits<graphs_collection>::vertex_descriptor target) const
   {
      boost::graph_traits<graphs_collection>::edge_descriptor edge;
      bool inserted;
      boost::tie(edge, inserted) = boost::edge(source, target, *this);
      return inserted;
   }

   inline void CompressEdges()
   {
      std::deque<boost::graph_traits<graphs_collection>::edge_descriptor> toBeRemoved;
      boost::graph_traits<graphs_collection>::edge_iterator ei0, ei0_end;
      for(boost::tie(ei0, ei0_end) = boost::edges(*this); ei0 != ei0_end; ++ei0)
      {
         if((*this)[*ei0].selector == 0)
         {
            toBeRemoved.push_back(*ei0);
         }
      }
      for(auto e0 : toBeRemoved)
      {
         boost::remove_edge(e0, *this);
      }
   }
};

using graphs_collectionRef = refcount<graphs_collection>;

struct undirected_graphs_collection : public undirected_boost_graphs_collection
{
   undirected_graphs_collection() = default;

   ~undirected_graphs_collection() = default;

   inline boost::graph_traits<undirected_boost_graphs_collection>::vertex_descriptor AddVertex()
   {
      size_t index = boost::num_vertices(*this);
      boost::graph_traits<undirected_boost_graphs_collection>::vertex_descriptor v = boost::add_vertex(*this);
      boost::get(boost::vertex_index_t(), *this)[v] = index;
      return v;
   }

   inline void RemoveVertex(boost::graph_traits<undirected_boost_graphs_collection>::vertex_descriptor v)
   {
      boost::remove_vertex(v, *this);
      boost::property_map<undirected_boost_graphs_collection, boost::vertex_index_t>::type index_map =
          boost::get(boost::vertex_index_t(), *this);
      boost::graph_traits<undirected_boost_graphs_collection>::vertex_iterator v_it, v_it_end;
      size_t index = 0;
      for(boost::tie(v_it, v_it_end) = boost::vertices(*this); v_it != v_it_end; v_it++, index++)
      {
         index_map[*v_it] = index;
      }
   }

   inline int GetSelector(const edge_descriptor e) const
   {
      return (*this)[e].selector;
   }

   inline void SetSelector(edge_descriptor e, const int selector)
   {
      (*this)[e].selector = selector;
   }
};

using undirected_graphs_collectionRef = refcount<undirected_graphs_collection>;

template <class info_object, class Graph>
NodeInfoRef& Cget_node_infoRef(typename boost::graph_traits<Graph>::vertex_descriptor v, Graph& g)
{
   NodeInfoRef& info = g[v];
   if(!info)
   {
      info = NodeInfoRef(new info_object);
   }
   return info;
}

template <class info_object, class Graph>
void set_node_info(typename boost::graph_traits<Graph>::vertex_descriptor v, const refcount<info_object>& obj, Graph& g)
{
   NodeInfoRef& info = g[v];
   info = obj;
}

#define SET_NODE_INFO_REF(data, NodeInfo, obj, vertex_index) set_node_info<NodeInfo>(vertex_index, obj, *(data))

#define GET_NODE_INFO_REF(data, NodeInfo, vertex_index) Cget_node_infoRef<NodeInfo>(vertex_index, *(data))

template <class info_object, class Graph>
info_object* get_node_info(typename boost::graph_traits<Graph>::vertex_descriptor v, Graph& g)
{
   NodeInfoRef& info = g[v];
   if(!info)
   {
      info = NodeInfoRef(new info_object);
   }
   THROW_ASSERT(GetPointer<info_object>(info) != nullptr,
                "Function get_node_info: the vertices associated with the graph used are not derived from "
                "info_object\n\tCheck the actual type of info_object and the type of the node of Graph");
   return GetPointer<info_object>(info);
}

template <class info_object, class Graph>
const info_object* Cget_node_info(typename boost::graph_traits<Graph>::vertex_descriptor v, const Graph& g)
{
   const NodeInfo* info = g[v].get();
   THROW_ASSERT(!info || dynamic_cast<const info_object*>(info) != nullptr,
                "Function Cget_node_info: the nodes associated with the graph used are not derived from "
                "info_object\n\tCheck the actual type of info_object and the type of the node of Graph");
   return info ? dynamic_cast<const info_object*>(info) : nullptr;
}

#define GET_NODE_INFO(data, NodeInfo, vertex_index) get_node_info<NodeInfo>(vertex_index, *(data))

#define CGET_NODE_INFO(data, NodeInfo, vertex_index) Cget_node_info<NodeInfo>(vertex_index, *(data))

template <class info_object, class Graph>
info_object* get_edge_info(typename boost::graph_traits<Graph>::edge_descriptor e, Graph& g)
{
   EdgeInfoRef& info = g[e].info;
   if(!info)
   {
      info = EdgeInfoRef(new info_object);
   }
   THROW_ASSERT(GetPointer<info_object>(info) != nullptr,
                "Function get_edge_info: the edges associated with the graph used are not derived from "
                "info_object\n\tCheck the actual type of info_object and the type of the edge of Graph");
   return GetPointer<info_object>(info);
}
template <class info_object, class Graph>
const info_object* Cget_edge_info(typename boost::graph_traits<Graph>::edge_descriptor e, const Graph& g)
{
   const EdgeInfo* info = g[e].info.get();
   THROW_ASSERT(!info || dynamic_cast<const info_object*>(info) != nullptr,
                "Function Cget_edge_info: the edges associated with the graph used are not derived from "
                "info_object\n\tCheck the actual type of info_object and the type of the edge of Graph");
   return info ? dynamic_cast<const info_object*>(info) : nullptr;
}

#define GET_EDGE_INFO(data, edge_info, edge_index) get_edge_info<edge_info>(edge_index, *(data))

#define CGET_EDGE_INFO(data, edge_info, edge_index) Cget_edge_info<edge_info>(edge_index, *(data))

template <typename Graph>
struct SelectVertex
{
 private:
   bool all;

   CustomUnorderedSet<typename boost::graph_traits<Graph>::vertex_descriptor> subset;

 public:
   SelectVertex() : all(true), subset()
   {
   }

   explicit SelectVertex(const CustomUnorderedSet<typename boost::graph_traits<Graph>::vertex_descriptor>& _subset)
       : all(false), subset(_subset)
   {
   }

   bool operator()(const typename boost::graph_traits<Graph>::vertex_descriptor& v) const
   {
      if(all)
      {
         return true;
      }
      else
      {
         return (subset.find(v) != subset.end());
      }
   }
};

template <typename Graph>
struct SelectEdge
{
 private:
   int selector;

   Graph* g;

   CustomUnorderedSet<typename boost::graph_traits<Graph>::vertex_descriptor> subgraph_vertices;

   bool empty;

 public:
   SelectEdge() : selector(0), g(nullptr), subgraph_vertices(), empty(true)
   {
   }

   SelectEdge(const int _selector, Graph* _g) : selector(_selector), g(_g), subgraph_vertices(), empty(true)
   {
   }

   SelectEdge(const int _selector, Graph* _g,
              const CustomUnorderedSet<typename boost::graph_traits<Graph>::vertex_descriptor>& _subgraph_vertices)
       : selector(_selector), g(_g), subgraph_vertices(_subgraph_vertices), empty(false)
   {
   }

   template <typename Edge>
   bool operator()(const Edge& e) const
   {
      if(empty)
      {
         return selector & (*g)[e].selector;
      }
      else
      {
         typename boost::graph_traits<Graph>::vertex_descriptor u, v;
         u = boost::source(e, *g);
         v = boost::target(e, *g);
         if((selector & (*g)[e].selector) && subgraph_vertices.find(v) != subgraph_vertices.end() &&
            subgraph_vertices.find(u) != subgraph_vertices.end())
         {
            return true;
         }
         else
         {
            return false;
         }
      }
   }
};

struct graph : public boost::filtered_graph<boost_graphs_collection, SelectEdge<boost_graphs_collection>,
                                            SelectVertex<boost_graphs_collection>>
{
 protected:
   inline const NodeInfoConstRef
   CGetNodeInfo(typename boost::graph_traits<graphs_collection>::vertex_descriptor node) const
   {
      const NodeInfoRef info = (*this)[node];
      THROW_ASSERT(info, "Node without associate info");
      return info;
   }

   inline EdgeInfoRef GetEdgeInfo(typename boost::graph_traits<graphs_collection>::vertex_descriptor source,
                                  typename boost::graph_traits<graphs_collection>::vertex_descriptor target)
   {
      bool found;
      typename boost::graph_traits<graphs_collection>::edge_descriptor edge;
      boost::tie(edge, found) = boost::edge(source, target, *this);
      THROW_ASSERT(found, "Edge not present in the graph");
      return GetEdgeInfo(edge);
   }

   inline const EdgeInfoConstRef
   CGetEdgeInfo(typename boost::graph_traits<graphs_collection>::vertex_descriptor source,
                typename boost::graph_traits<graphs_collection>::vertex_descriptor target) const
   {
      bool found;
      typename boost::graph_traits<graphs_collection>::edge_descriptor edge;
      boost::tie(edge, found) = boost::edge(source, target, *this);
      THROW_ASSERT(found, "Edge not present in the graph");
      return CGetEdgeInfo(edge);
   }

   inline EdgeInfoRef GetEdgeInfo(typename boost::graph_traits<graphs_collection>::edge_descriptor edge) const
   {
      const EdgeInfoRef info = (*this)[edge].info;
      THROW_ASSERT(info, "Info not associated with the edge");
      return info;
   }

   inline EdgeInfoConstRef CGetEdgeInfo(typename boost::graph_traits<graphs_collection>::edge_descriptor edge) const
   {
      const EdgeInfoConstRef info = (*this)[edge].info;
      THROW_ASSERT(info, "Info not associated with the edge");
      return info;
   }

   graphs_collection* collection;

   const int selector;

   template <typename VertexWriterTemplate, typename EdgeWriterTemplate, typename GraphWriterTemplate>
   void InternalWriteDot(const std::string& file_name, const VertexWriterConstRef vertex_writer,
                         const EdgeWriterConstRef edge_writer, const GraphWriterConstRef graph_writer) const
   {
      std::ofstream file_stream(file_name.c_str());
      boost::write_graphviz(file_stream, *this, *(GetPointer<VertexWriterTemplate>(vertex_writer)),
                            *(GetPointer<EdgeWriterTemplate>(edge_writer)),
                            *(GetPointer<GraphWriterTemplate>(graph_writer)));
   }

 public:


   graph(graphs_collection* g, const int _selector)
       : boost::filtered_graph<boost_graphs_collection, SelectEdge<boost_graphs_collection>,
                               SelectVertex<boost_graphs_collection>>(
             *g, SelectEdge<boost_graphs_collection>(_selector, g), SelectVertex<boost_graphs_collection>()),
         collection(g),
         selector(_selector)
   {
   }

   graph(graphs_collection* g, const int _selector,
         const CustomUnorderedSet<boost::graph_traits<graphs_collection>::vertex_descriptor>& vertices)
       : boost::filtered_graph<boost_graphs_collection, SelectEdge<boost_graphs_collection>,
                               SelectVertex<boost_graphs_collection>>(
             *g, SelectEdge<boost_graphs_collection>(_selector, g, vertices),
             SelectVertex<boost_graphs_collection>(vertices)),
         collection(g),
         selector(_selector)
   {
   }

   friend boost::graph_traits<graph>::vertex_descriptor VERTEX(const boost::graph_traits<graph>::vertices_size_type,
                                                               const graph&);

   virtual ~graph() = default;

   bool is_in_subset(const boost::graph_traits<graph>::vertex_descriptor v) const
   {
      return m_vertex_pred(v);
   }

   inline int GetSelector() const
   {
      return selector;
   }

   inline int GetSelector(const edge_descriptor e) const
   {
      return collection->GetSelector(e) & GetSelector();
   }

   inline int GetSelector(const boost::graph_traits<graphs_collection>::vertex_descriptor source,
                          const boost::graph_traits<graphs_collection>::vertex_descriptor target) const
   {
      bool found;
      typename boost::graph_traits<graphs_collection>::edge_descriptor edge;
      boost::tie(edge, found) = boost::edge(source, target, *this);
      return collection->GetSelector(edge);
   }

   void GetStronglyConnectedComponents(
       std::map<size_t, UnorderedSetStdStable<boost::graph_traits<graphs_collection>::vertex_descriptor>>&
           strongly_connected_components) const
   {
      std::map<boost::graph_traits<graphs_collection>::vertex_descriptor, size_t> temp_vertex_to_component;
      boost::associative_property_map<std::map<boost::graph_traits<graphs_collection>::vertex_descriptor, size_t>>
          vertex_to_component(temp_vertex_to_component);
      boost::strong_components(*this, vertex_to_component);
      boost::graph_traits<graph>::vertex_iterator vertex_it, vertex_end;
      for(boost::tie(vertex_it, vertex_end) = boost::vertices(*this); vertex_it != vertex_end; vertex_it++)
      {
         const size_t strongly_connected_component = vertex_to_component[*vertex_it];
         strongly_connected_components[strongly_connected_component].insert(*vertex_it);
      }
   }

   void BreadthFirstSearch(const boost::graph_traits<graphs_collection>::vertex_descriptor node,
                           boost::bfs_visitor<>* vis) const
   {
      boost::breadth_first_search(*this, node, visitor(*vis));
   }

   void
   ReverseTopologicalSort(std::deque<boost::graph_traits<graphs_collection>::vertex_descriptor>& sorted_vertices) const
   {
      boost::topological_sort(*this, std::back_inserter(sorted_vertices));
   }

   void TopologicalSort(std::list<boost::graph_traits<graphs_collection>::vertex_descriptor>& sorted_vertices) const
   {
      boost::topological_sort(*this, std::front_inserter(sorted_vertices));
   }

   bool IsReachable(const boost::graph_traits<graphs_collection>::vertex_descriptor x,
                    const boost::graph_traits<graphs_collection>::vertex_descriptor y) const
   {
      std::list<boost::graph_traits<graphs_collection>::vertex_descriptor> running_vertices;
      CustomUnorderedSet<boost::graph_traits<graphs_collection>::vertex_descriptor> encountered_vertices;
      running_vertices.push_back(x);
      encountered_vertices.insert(x);
      while(not running_vertices.empty())
      {
         const boost::graph_traits<graphs_collection>::vertex_descriptor current = running_vertices.front();
         running_vertices.pop_front();
         boost::graph_traits<graph>::out_edge_iterator oe, oe_end;
         for(boost::tie(oe, oe_end) = boost::out_edges(current, *this); oe != oe_end; oe++)
         {
            const boost::graph_traits<graphs_collection>::vertex_descriptor target = boost::target(*oe, *this);
            if(target == y)
            {
               return true;
            }
            if(encountered_vertices.find(target) == encountered_vertices.end())
            {
               encountered_vertices.insert(target);
               running_vertices.push_back(target);
            }
         }
      }
      return false;
   }

   inline NodeInfoRef GetNodeInfo(typename boost::graph_traits<graphs_collection>::vertex_descriptor node)
   {
      NodeInfoRef info = (*this)[node];
      THROW_ASSERT(info, "Node without associate info");
      return info;
   }

   inline GraphInfoRef GetGraphInfo()
   {
      GraphInfoRef info = boost_CGetOpGraph_property(*this);
      return info;
   }

   inline const GraphInfoConstRef CGetGraphInfo() const
   {
      GraphInfoRef info = boost_CGetOpGraph_property(*this);
      return info;
   }

   template <typename VertexWriterTemplate, typename EdgeWriterTemplate>
   void InternalWriteDot(const std::string& file_name, const VertexWriterConstRef vertex_writer,
                         const EdgeWriterConstRef edge_writer) const
   {
      std::ofstream file_stream(file_name.c_str());
      boost::write_graphviz(file_stream, *this, *(GetPointer<VertexWriterTemplate>(vertex_writer)),
                            *(GetPointer<EdgeWriterTemplate>(edge_writer)));
   }

   inline bool ExistsEdge(const boost::graph_traits<graphs_collection>::vertex_descriptor source,
                          const boost::graph_traits<graphs_collection>::vertex_descriptor target) const
   {
      boost::graph_traits<graphs_collection>::edge_descriptor edge;
      bool inserted;
      boost::tie(edge, inserted) = boost::edge(source, target, *this);
      return inserted;
   }

   inline boost::graph_traits<graphs_collection>::edge_descriptor
   CGetEdge(const boost::graph_traits<graphs_collection>::vertex_descriptor source,
            const boost::graph_traits<graphs_collection>::vertex_descriptor target) const
   {
      boost::graph_traits<graphs_collection>::edge_descriptor edge;
      bool inserted;
      boost::tie(edge, inserted) = boost::edge(source, target, *this);
      THROW_ASSERT(inserted, "Edge does not exist in this graph");
      return edge;
   }

#if BOOST_VERSION >= 104200
   using edge_property_type = boost::edge_property_type<graphs_collection>::type;
   using vertex_property_type = boost::vertex_property_type<graphs_collection>::type;
   using graph_property_type = boost::graph_property_type<graphs_collection>::type;
#endif
};
using graphRef = refcount<graph>;
using graphConstRef = refcount<const graph>;

#if BOOST_VERSION >= 104600
namespace boost
{
   namespace detail
   {
      struct filtered_graph_property_selector
      {
         template <class FilteredGraph, class Property, class Tag>
         struct bind_
         {
            using Graph = typename FilteredGraph::graph_type;
            using Map = property_map<Graph, Tag>;
            using type = typename Map::type;
            using const_type = typename Map::const_type;
         };
      };
   } // namespace detail
   template <>
   struct vertex_property_selector<filtered_graph_tag>
   {
      using type = detail::filtered_graph_property_selector;
   };
   template <>
   struct edge_property_selector<filtered_graph_tag>
   {
      using type = detail::filtered_graph_property_selector;
   };

} // namespace boost
#endif

struct ugraph
    : public boost::filtered_graph<undirected_boost_graphs_collection, SelectEdge<undirected_boost_graphs_collection>,
                                   SelectVertex<undirected_boost_graphs_collection>>
{
 protected:
   undirected_graphs_collection* collection;

   const int selector;

   template <typename UVertexWriterTemplate, typename UEdgeWriterTemplate>
   void InternalWriteDot(const std::string& file_name, const UVertexWriterConstRef uvertex_writer,
                         const UEdgeWriterConstRef uedge_writer) const
   {
      std::ofstream file_stream(file_name.c_str());
      boost::write_graphviz(file_stream, *this, *(GetPointer<UVertexWriterTemplate>(uvertex_writer)),
                            *(GetPointer<UEdgeWriterTemplate>(uedge_writer)));
   }

 public:


   ugraph(undirected_graphs_collection* g, const int _selector)
       : boost::filtered_graph<undirected_boost_graphs_collection, SelectEdge<undirected_boost_graphs_collection>,
                               SelectVertex<undirected_boost_graphs_collection>>(
             *g, SelectEdge<undirected_boost_graphs_collection>(_selector, g),
             SelectVertex<undirected_boost_graphs_collection>()),
         collection(g),
         selector(_selector)
   {
   }

   ugraph(
       undirected_graphs_collection* g, const int _selector,
       const CustomUnorderedSet<boost::graph_traits<undirected_boost_graphs_collection>::vertex_descriptor>& vertices)
       : boost::filtered_graph<undirected_boost_graphs_collection, SelectEdge<undirected_boost_graphs_collection>,
                               SelectVertex<undirected_boost_graphs_collection>>(
             *g, SelectEdge<undirected_boost_graphs_collection>(_selector, g, vertices),
             SelectVertex<undirected_boost_graphs_collection>(vertices)),
         collection(g),
         selector(_selector)

   {
   }

   friend boost::graph_traits<ugraph>::vertex_descriptor VERTEX(const boost::graph_traits<ugraph>::vertices_size_type,
                                                                const ugraph&);

   ~ugraph() = default;

   bool is_in_subset(const boost::graph_traits<ugraph>::vertex_descriptor v) const
   {
      return m_vertex_pred(v);
   }

   inline int GetSelector() const
   {
      return selector;
   }

   inline int GetSelector(const edge_descriptor e) const
   {
      return collection->GetSelector(e);
   }

#if BOOST_VERSION >= 104200
   using edge_property_type = boost::edge_property_type<undirected_graphs_collection>::type;
   using vertex_property_type = boost::vertex_property_type<undirected_graphs_collection>::type;
   using graph_property_type = boost::graph_property_type<undirected_graphs_collection>::type;
#endif
};

using ugraphRef = refcount<ugraph>;

template <typename Graph>
struct ltedge
{
 private:
   const Graph* g;

 public:
   explicit ltedge(const Graph* _g) : g(_g)
   {
   }

   bool operator()(const typename boost::graph_traits<Graph>::edge_descriptor first,
                   const typename boost::graph_traits<Graph>::edge_descriptor second) const
   {
      if(boost::source(first, *g) < boost::source(second, *g))
      {
         return true;
      }
      if(boost::source(first, *g) > boost::source(second, *g))
      {
         return false;
      }
      return boost::target(first, *g) < boost::target(second, *g);
   }
};

using vertex = boost::graph_traits<graph>::vertex_descriptor;
#define NULL_VERTEX boost::graph_traits<graph>::null_vertex()
using VertexIterator = boost::graph_traits<graph>::vertex_iterator;

using InEdgeIterator = boost::graph_traits<graph>::in_edge_iterator;
using OutEdgeIterator = boost::graph_traits<graph>::out_edge_iterator;
using EdgeIterator = boost::graph_traits<graph>::edge_iterator;
using EdgeDescriptor = boost::graph_traits<graph>::edge_descriptor;

namespace std
{
   template <>
   struct hash<EdgeDescriptor> : public unary_function<EdgeDescriptor, size_t>
   {
      size_t operator()(EdgeDescriptor edge) const
      {
         size_t hash_value = 0;
         boost::hash_combine(hash_value, edge.m_source);
         boost::hash_combine(hash_value, edge.m_target);
         return hash_value;
      }
   };
} // namespace std

template <typename H>
H AbslHashValue(const H& h, const EdgeDescriptor& m)
{
   return H::combine(h, m.m_source, m.m_target);
}
using uvertex = boost::graph_traits<ugraph>::vertex_descriptor;
#define NULL_UVERTEX boost::graph_traits<ugraph>::null_vertex()

using UGCvertex = boost::graph_traits<undirected_graphs_collection>::vertex_descriptor;
#define NULL_UGCVERTEX boost::graph_traits<undirected_graphs_collection>::null_vertex()

using UVertexIterator = boost::graph_traits<ugraph>::vertex_iterator;

using UInEdgeIterator = boost::graph_traits<ugraph>::in_edge_iterator;
using UOutEdgeIterator = boost::graph_traits<ugraph>::out_edge_iterator;
using UEdgeIterator = boost::graph_traits<ugraph>::edge_iterator;
using UEdgeDescriptor = boost::graph_traits<ugraph>::edge_descriptor;

inline boost::graph_traits<graph>::vertex_descriptor VERTEX(const boost::graph_traits<graph>::vertices_size_type i,
                                                            const graph& g)
{
   return boost::vertex(i, (g.m_g));
}

inline boost::graph_traits<ugraph>::vertex_descriptor VERTEX(const boost::graph_traits<ugraph>::vertices_size_type i,
                                                             const ugraph& g)
{
   return boost::vertex(i, (g.m_g));
}

template <class Graph>
void ADD_UEDGE(typename boost::graph_traits<Graph>::vertex_descriptor A,
               typename boost::graph_traits<Graph>::vertex_descriptor B, int selector, Graph& g)
{
   UEdgeDescriptor e;
   bool inserted;
   boost::tie(e, inserted) = boost::edge(A, B, g);
   if(inserted)
   {
      g[e].selector = g[e].selector | selector;
   }
   else
   {
      boost::add_edge(A, B, selector, g);
   }
}

class VertexWriter
{
 protected:
   const graph* printing_graph;

   const int detail_level;

 public:
   VertexWriter(const graph* _graph, const int _detail_level) : printing_graph(_graph), detail_level(_detail_level)
   {
   }

   virtual ~VertexWriter() = default;

   virtual void operator()(std::ostream& out, const vertex& v) const = 0;
};

class EdgeWriter
{
 protected:
   const graph* printing_graph;

   const int selector;

   const int detail_level;

 public:
   EdgeWriter(const graph* _printing_graph, const int _detail_level)
       : printing_graph(_printing_graph), selector(printing_graph->GetSelector()), detail_level(_detail_level)
   {
   }

   virtual ~EdgeWriter() = default;

   virtual void operator()(std::ostream& out, const EdgeDescriptor& edge) const = 0;
};

class GraphWriter
{
 protected:
   const graph* printing_graph;

   const int detail_level;

 public:
   GraphWriter(const graph* _printing_graph, const int _detail_level)
       : printing_graph(_printing_graph), detail_level(_detail_level)
   {
   }

   virtual ~GraphWriter() = default;

   virtual void operator()(std::ostream& out) const = 0;
};

class UVertexWriter
{
 protected:
   const ugraph* printing_ugraph;

   const int detail_level;

 public:
   UVertexWriter(const ugraph* _printing_ugraph, const int _detail_level)
       : printing_ugraph(_printing_ugraph), detail_level(_detail_level)
   {
   }

   virtual ~UVertexWriter() = default;

   virtual void operator()(std::ostream& out, const uvertex& v) const = 0;
};

class UEdgeWriter
{
 protected:
   const ugraph* printing_ugraph;

   const int selector;

   const int detail_level;

 public:
   UEdgeWriter(const ugraph* _printing_ugraph, const int _detail_level)
       : printing_ugraph(_printing_ugraph), selector(printing_ugraph->GetSelector()), detail_level(_detail_level)
   {
   }

   virtual ~UEdgeWriter() = default;

   virtual void operator()(std::ostream& out, const UEdgeDescriptor& edge) const = 0;
};
#endif