Re: [Boost-users] [BGL] AT&T Graphviz adaptor

From: Dmitry (dmitry_at_[hidden])
Date: 2008-06-24 05:06:52

I have attached a draft version. I wrote it strictly following to the
instructions from boost::graph documentation
http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/leda_conversion.html
What was really exciting is that after this I was able to call graph
algorithms (currently I have succided in calling Bellman Ford shortes
path, strongly connected components and minimal cycle ratio) without
data copying.
boost::bundle_property_map<> is quite suitable for creating boost
property maps from graphviz properties. In my current implementation its
usage is not completly generic. I think with enough motivation it would
take one day to make it 100% generic.

Waiting somebody motivates me,
Regards,

Dmitry

Max escribi¨®:
> Please give more details ...
> :-)
> 
> Cheers
> Max
> 
>> Hi there,
>>
>> I have a very nice BGL adaptor for AT&T graphviz
>> graph representation.
>> Is it worthy  to add it to the boost library ?
>>
>> Thanks in advance,
>>
>> Sr. Dmitry
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users


#ifndef GRAPHVIZ_BGL_ADAPTOR_HPP
#define GRAPHVIZ_BGL_ADAPTOR_HPP

#include <stdexcept>
//#include <iostream>
#include <boost/config.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <agraph.h>

namespace boost {
  typedef Agraph_t* bgl_graphviz_t;
  struct graphviz_traversal_category : 
    public virtual edge_list_graph_tag,
    public virtual bidirectional_graph_tag,
    public virtual adjacency_graph_tag,
    public virtual vertex_list_graph_tag { };

  template <>  struct graph_traits<bgl_graphviz_t> 
  {
    typedef Agnode_t* vertex_descriptor;
    typedef Agedge_t* edge_descriptor;

    struct vertex_iterator : public iterator_facade<vertex_iterator,
                             vertex_descriptor,
                             forward_traversal_tag,
                             const vertex_descriptor&>
    {
      explicit vertex_iterator(vertex_descriptor v = 0) :  m_v(v) { }

      const vertex_descriptor& dereference() const { return m_v; }

      bool equal(const vertex_iterator& other) const
      {
        if (m_v == other.m_v) return true;
        if (other.m_v == 0 || m_v == 0) return false;
        return AGID(m_v) == AGID(other.m_v); 
      }

      void increment()
      {
        m_v = agnxtnode(m_v);
      }
    private:
      vertex_descriptor m_v;
    };
                  
    struct edge_iterator : public iterator_facade<edge_iterator,
                           edge_descriptor,
                           forward_traversal_tag,
                           const edge_descriptor&>
    {
      explicit edge_iterator(vertex_descriptor v = 0, edge_descriptor e = 0) :  m_v(v), m_base(e)
      { }
      virtual ~edge_iterator() {}
    
    protected:
      virtual void increment() 
      { 
        if (m_base == 0) throw std::runtime_error("Out of range\n");
        m_base = agnxtout(m_base);
        if (m_base == 0)
          { 
            m_v = agnxtnode(m_v);
            if (m_v) m_base = agfstout(m_v);
          }
        
      }

      const edge_descriptor& dereference() const { return m_base; }

      bool equal(const edge_iterator& other) const
      { 
        if (m_base == other.m_base) return true;
        if (other.m_base == 0 || m_base == 0) return false;
        return AGID(m_base) == AGID(other.m_base); 
      }

      vertex_descriptor	m_v;
      edge_descriptor	m_base;
     
      friend class iterator_core_access;
    };

    struct out_edge_iterator : public iterator_facade<out_edge_iterator,
                           edge_descriptor,
                           forward_traversal_tag,
                           const edge_descriptor&>
    {
      explicit out_edge_iterator(vertex_descriptor v = 0, edge_descriptor e = 0) : m_v(v), m_base(e)
      {}

    protected:
      const edge_descriptor& dereference() const { return m_base; }
      void increment() 
      { 
            if (m_base == 0) throw std::runtime_error("Out of range\n");
            m_base = agnxtout(m_base);
      }
      bool equal(const out_edge_iterator& other) const
          { 
                if (m_base == other.m_base) return true;
                if (other.m_base == 0 || m_base == 0) return false;
                return AGID(m_base) == AGID(other.m_base); 
          }

      vertex_descriptor	m_v;
      edge_descriptor	m_base;
      friend class iterator_core_access;
    };
    
    struct in_edge_iterator : public edge_iterator
    {
      explicit in_edge_iterator(vertex_descriptor v = 0, edge_descriptor e = 0) : edge_iterator(v, e) 
      {  }

      void increment() 
      { 
        if (m_base == 0) throw std::runtime_error("Out of range\n");
        m_base = agnxtin(m_base);
      }
      
    };

    typedef boost::directed_tag directed_category;
    typedef allow_parallel_edge_tag edge_parallel_category;
    typedef graphviz_traversal_category traversal_category;
    typedef unsigned vertices_size_type;
    typedef int edges_size_type;
    typedef int degree_size_type;
    vertex_descriptor null_vertex() { return vertex_descriptor(0); }
  };

  inline std::pair<
    graph_traits< bgl_graphviz_t >::edge_iterator,
    graph_traits< bgl_graphviz_t >::edge_iterator >  
  edges(const bgl_graphviz_t& g)
  {
    typedef graph_traits< bgl_graphviz_t>::edge_iterator   myIter;
     bgl_graphviz_t &ncg = const_cast< bgl_graphviz_t&>(g);
    return std::make_pair( myIter(agfstnode(ncg), agfstout(agfstnode(ncg))), myIter() );
  }
  
   inline std::pair<
    graph_traits< bgl_graphviz_t >::vertex_iterator,
    graph_traits< bgl_graphviz_t >::vertex_iterator >  
   vertices(const bgl_graphviz_t& g)
  {
    typedef graph_traits<bgl_graphviz_t >::vertex_iterator   myIter;
    Agraph_t* ncg = const_cast<bgl_graphviz_t>(g);
    return std::make_pair( myIter(agfstnode(ncg)), myIter() );
  }

 inline graph_traits<bgl_graphviz_t>::vertex_descriptor  
 source(graph_traits<bgl_graphviz_t>::edge_descriptor e, const bgl_graphviz_t  &g)
 {
   return agtail(e);
 }

  inline graph_traits<bgl_graphviz_t>::vertex_descriptor  
  target(graph_traits<bgl_graphviz_t>::edge_descriptor e, const bgl_graphviz_t  &g)
  {
   return aghead(e);
  }

   inline std::pair<
    graph_traits<bgl_graphviz_t>::out_edge_iterator,
    graph_traits<bgl_graphviz_t >::out_edge_iterator >  
  out_edges( graph_traits< bgl_graphviz_t>::vertex_descriptor v, const  bgl_graphviz_t &g)
  {
    typedef graph_traits< bgl_graphviz_t >::out_edge_iterator   myIter;
    return std::make_pair( myIter(v, agfstout(v)), myIter(v) );
  }

  inline graph_traits<Agraph_t*>::degree_size_type	
  out_degree(graph_traits<Agraph_t*>::vertex_descriptor v, const  bgl_graphviz_t &g)
  {
    return agdegree(v, FALSE, TRUE);
  }

  inline graph_traits< bgl_graphviz_t >::vertices_size_type
  num_vertices(const bgl_graphviz_t&  g)
  {
    return agnnodes(const_cast<bgl_graphviz_t>(g));
  }  
  
  inline graph_traits<bgl_graphviz_t>::edges_size_type
  num_edges(const bgl_graphviz_t&  g)
  {
    return agnedges(const_cast<bgl_graphviz_t>(g));
  } 

   inline graph_traits<bgl_graphviz_t>::degree_size_type	
   in_degree(graph_traits<bgl_graphviz_t>::vertex_descriptor v, const bgl_graphviz_t& g)
   {
     return agdegree(v, TRUE, FALSE);
   }

  inline std::pair<
     graph_traits<bgl_graphviz_t>::in_edge_iterator,
     graph_traits<bgl_graphviz_t >::in_edge_iterator >  
   in_edges( graph_traits<bgl_graphviz_t>::vertex_descriptor v, const bgl_graphviz_t& g)
   {
    typedef graph_traits<bgl_graphviz_t>::in_edge_iterator   myIter;
    return std::make_pair( myIter(v, agfstin(v)), myIter(v) );
  }
  
  template <typename OBJ> struct graphviz_id_map
    : public put_get_helper<int, graphviz_id_map<OBJ> >
  {
    typedef readable_property_map_tag category;
    typedef int value_type;
    typedef int reference;
    typedef OBJ key_type; //Node or edge
    graphviz_id_map() { }
    int operator[](const OBJ& o) const { return AGID(o); }
  };

  /* inline graphviz_id_map
  get(vertex_index_t, const bgl_graphviz_t& g) 
  {
    return graphviz_id_map();
    }*/
    template <typename OBJ>
    struct ltgraphviz {
        bool operator()(const OBJ& o1, const OBJ& o2) const
        {
            return AGID(o1) < AGID(o2);
        }
    };
} // namespace boost

typedef boost::graphviz_id_map<Agnode_t*> vim1_t;
typedef boost::graphviz_id_map<Agedge_t*> eim1_t;

#endif //GRAPHVIZ_BGL_ADAPTOR_HPP