mlGraphToBoostGraph.h

Go to the documentation of this file.

/*************************************************************************************
**
** Copyright 2012, MeVis Medical Solutions AG
**
** The user may use this file in accordance with the license agreement provided with
** the Software or, alternatively, in accordance with the terms contained in a
** written agreement between the user and MeVis Medical Solutions AG.
**
** For further information use the contact form at https://www.mevislab.de/contact
**
**************************************************************************************/
 
#ifndef ML_GRAPH_TO_BOOST_GRAPH_H
#define ML_GRAPH_TO_BOOST_GRAPH_H
 
 
 
#include <iterator>
#include <boost/operators.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/property_map/property_map.hpp>
 
#include "mlGraphComponents.h"
#include "mlGraph.h"
#include <mlVesselEdge.h>
 
//
// Functions and traits for the plain ml::Graph class
//
 
class ml_out_edge_iterator;
class ml_vertex_iterator;
 
typedef ml::Graph* ml_graph_ptr;
 
namespace boost {
 
 // typedef const UndirectedVesselGraph* ml_const_uv_graph_ptr;
 
  struct ml_graph_traversal_tag :
    public virtual incidence_graph_tag,     // Graph is of type IncidenceGraph
  //  public virtual adjacency_graph_tag,
    public virtual vertex_list_graph_tag    // Graph is of type IncidenceGraph
    { };
 
 
  template <> struct graph_traits<ml_graph_ptr> {
 
    // --- typedefs for boost::Graph ---
 
    typedef ml::VesselNode* vertex_descriptor;
 
    typedef ml::VesselEdge* edge_descriptor;
 
    typedef directed_tag directed_category;
 
    typedef allow_parallel_edge_tag edge_parallel_category;
 
    typedef ml_graph_traversal_tag traversal_category;
 
    // --- typedefs for boost::IncidenceGraph  ---
 
    typedef long degree_size_type;
 
    // An out-edge iterator for a vertex v provides access to the out-edges of the vertex. As such,
    // the value type of an out-edge iterator is the edge descriptor type of its graph.
    typedef  ml_out_edge_iterator out_edge_iterator;
 
    // --- typedefs for boost::VertexListGraph  ---
 
    typedef ml::Graph::NodeIterator vertex_iterator;
 
    typedef long vertices_size_type;
 
    // to do: add missing functions/traits for other boost graph models
    /*
    typedef void in_edge_iterator;
    typedef sgb_adj_iterator adjacency_iterator;
    typedef void edge_iterator;
    typedef long edge_size_type;
    */
  };
 
 
 
} // namespace boost
 
 
// Iterator class to iterate over all out edges of a vertex (out_edge_iterator)
 
// ml::VesselNode stores all edges in a std::vector but has no information which edges are
// directed from this node to another; this must be looked up in the edges itself
// see comment at out_edges
class ml_out_edge_iterator : public boost::forward_iterator_helper<
                                            ml_out_edge_iterator,  // operand type
                                            ml::VesselEdge*,        // value type
                                            std::ptrdiff_t,        // difference type
                                            ml::VesselEdge**,       // pointer type
                                            ml::VesselEdge*>        // reference type
{
 
typedef ml_out_edge_iterator self;
 
public:
 
  ml_out_edge_iterator() : _vertex(nullptr) {}
 
  ml_out_edge_iterator(ml::VesselNode* vertex,
                       std::vector<ml::VesselEdge*>::iterator edgeIter,
                       std::vector<ml::VesselEdge*>::iterator edgeIterEnd)
  :_vertex(vertex)
  ,_edgeIter(edgeIter),
   _edgeIterEnd(edgeIterEnd)
  {
    // set edgeIter to first out edge, skip all edges which predecessor is
    // not the vertex
    while ( (_edgeIter!=_edgeIterEnd)  &&
            !((*_edgeIter)->isPred(_vertex)) )
    {
      ++_edgeIter;
    }
  }
 
  ml::VesselEdge* operator*() { return *_edgeIter; }
 
  self& operator++()
  {
    do // skip in-edges
    {
      // must check if iterator is already at the end, otherwise loop might become endless
      if (_edgeIter != _edgeIterEnd) { ++_edgeIter; };
    }
    while ( (_edgeIter != _edgeIterEnd) && !((*_edgeIter)->isPred(_vertex)) );
    return *this;
  }
 
  friend bool operator==(const self& x, const self& y) {
    return x._edgeIter == y._edgeIter; }
 
protected:
  ml::VesselNode* _vertex;
  std::vector<ml::VesselEdge*>::iterator _edgeIter;
  std::vector<ml::VesselEdge*>::iterator _edgeIterEnd;
};
 
 
namespace boost {
 
  // --- functions required by boost::IncidenceGraph  ---
 
 
  inline boost::graph_traits<ml_graph_ptr>::vertex_descriptor
  source(graph_traits<ml_graph_ptr>::edge_descriptor e,
         const ml_graph_ptr)
  {
    return e->predNode();
  }
 
  inline boost::graph_traits<ml_graph_ptr>::vertex_descriptor
  target(graph_traits<ml_graph_ptr>::edge_descriptor e,
         const ml_graph_ptr)
  {
    return e->succNode();
  }
 
  inline std::pair<boost::graph_traits<ml_graph_ptr>::out_edge_iterator,
                   boost::graph_traits<ml_graph_ptr>::out_edge_iterator>
  out_edges(boost::graph_traits<ml_graph_ptr>::vertex_descriptor vertex,
            const ml_graph_ptr)
  {
    return std::make_pair(
      ml_out_edge_iterator(vertex, vertex->edges()->begin(), vertex->edges()->end()),
      ml_out_edge_iterator(vertex, vertex->edges()->end(),   vertex->edges()->end()) );
  }
 
 
  inline boost::graph_traits<ml_graph_ptr>::degree_size_type
  out_degree(boost::graph_traits<ml_graph_ptr>::vertex_descriptor vertex,
             const ml_graph_ptr )
  {
    boost::graph_traits<ml_graph_ptr>::degree_size_type count = 0;
 
    std::vector<ml::VesselEdge*>::iterator edgeIter = vertex->edges()->begin();
    std::vector<ml::VesselEdge*>::iterator edgeIterEnd = vertex->edges()->end();
 
    while (edgeIter != edgeIterEnd)
    {
      if ((*edgeIter)->isPred(vertex))
      {
        ++count;
      }
      ++edgeIter;
    }
    return count;
  }
 
 
  // --- functions required by boost::VertexListGraph ---
 
  inline std::pair<boost::graph_traits<ml_graph_ptr>::vertex_iterator,
                   boost::graph_traits<ml_graph_ptr>::vertex_iterator>
  vertices(ml_graph_ptr g)
  {
    return std::make_pair( g->beginNode(),
                           g->endNode() );
  }
 
  inline boost::graph_traits<ml_graph_ptr>::vertices_size_type
  num_vertices(const ml_graph_ptr g)
  {
    return static_cast<long> (g->numNodes());
  }
 
 
  inline boost::graph_traits<ml_graph_ptr>::vertex_descriptor
  vertex(boost::graph_traits<ml_graph_ptr>::degree_size_type arrayIndex, const ml_graph_ptr g)
  {
    return g->getNode(arrayIndex);
  }
 
  // --- Property maps ---
  // put_get_helper<class Reference, class LvaluePropertyMap> is a helper template which
  // automatically generates the put() and get() functions for a property map
 
  class ml_vertex_id_map : public boost::put_get_helper<unsigned int, ml_vertex_id_map>
  {
    public:
      // readonly property
      typedef boost::readable_property_map_tag category;
 
      // vertex index is of type long
      typedef unsigned int value_type;
      typedef unsigned int reference;
 
      // key = Vertex
      typedef ml::VesselNode* key_type;
 
      ml_vertex_id_map() : _g(nullptr) {}
      ml_vertex_id_map(ml_graph_ptr g) : _g(g) {}
      unsigned int operator[](ml::VesselNode* vertex) const {  return static_cast<unsigned int>(_g->getIndex(vertex)); }
 
    protected:
      ml_graph_ptr _g;
  };
 
  inline ml_vertex_id_map get(vertex_index_t, ml_graph_ptr g)
  {
    return ml_vertex_id_map(g);
  }
 
  // --- Property Map Traits classes ---
  template<>
  struct property_map<ml_graph_ptr, vertex_index_t>
  {
    typedef ml_vertex_id_map type;
    typedef ml_vertex_id_map const_type;
  };
 
 
  class ml_edge_weight_map : public boost::put_get_helper<double, ml_edge_weight_map>
  {
    public:
       // readonly property
      typedef boost::lvalue_property_map_tag category;
 
      // vertex index is of type long
      typedef double value_type;
      using reference = double const&;
 
      // key = edge
      typedef ml::VesselEdge* key_type;
 
      value_type operator[](ml::VesselEdge* edge) const {
        std::cout << "edge.getWeight() = " << edge->getWeight() << std::endl;
        return edge->getWeight();
      }
  };
 
  inline ml_edge_weight_map get(edge_weight_t, ml_graph_ptr)
  {
    return ml_edge_weight_map();
  }
 
  // --- Property Map Traits classes ---
  template<>
  struct property_map<ml_graph_ptr, edge_weight_t>
  {
    typedef ml_edge_weight_map type;
    typedef ml_edge_weight_map const_type;
  };
 
 
} // namespace boost
 
 
 
template<class T, class ValueType>
struct broken_VC_ptr_traits
{
  typedef T iterator_type;
  typedef std::random_access_iterator_tag iterator_category;
  typedef ValueType value_type;
  typedef ptrdiff_t difference_type;
  typedef ValueType* pointer;
  typedef ValueType& reference;
};
 
 
namespace boost {
 
template <class IteratorTraits, class IDMap>
class ml_iterator_map
{
public:
 
  typedef typename property_traits<IDMap>::key_type key_type;
  typedef typename IteratorTraits::value_type value_type;
  typedef typename IteratorTraits::value_type& reference;
  typedef lvalue_property_map_tag category;
 
  ml_iterator_map(typename IteratorTraits::iterator_type i = IteratorTraits::iterator_type(),
              const IDMap& id = IDMap())
    : m_iter(i), m_id(id) { }
  typename IteratorTraits::iterator_type m_iter;
  IDMap m_id;
};
 
// Next we implement the three property map functions, get(), put(), and at(). In each of the
// functions, the key object is converted to an integer offset using the m_id property map, and
// then that is used as an offset to the random access iterator m_iter.
 
template <class IteratorTraits, class IDMap>
typename IteratorTraits::value_type
get(const ml_iterator_map<IteratorTraits,IDMap>& i,
    typename property_traits<IDMap>::key_type key)
{
  return i.m_iter[i.m_id[key]];
}
template <class IteratorTraits, class IDMap>
void
put(const ml_iterator_map<IteratorTraits,IDMap>& i,
    typename property_traits<IDMap>::key_type key,
    const typename IteratorTraits::value_type& value)
{
 // std::cout << "put(" << key <<", " << value <<" )" << std::endl;
  i.m_iter[i.m_id[key]] = value;
}
 
template <class IteratorTraits, class IDMap>
typename IteratorTraits::value_type&
at(const ml_iterator_map<IteratorTraits,IDMap>& i,
    typename property_traits<IDMap>::key_type key)
{
  return i.m_iter[i.m_id[key]];
}
 
 
 
} // namespace boost
 
 
#endif