subgraph.hpp

support vector clustering for vc++

      remove_edge(g.global_to_local(e_global), g.m_graph);
      children_remove_edge(e_global, g.m_children);
    }

    template <typename Edge, typename Graph>
    void remove_edge_recur_up(Edge e_global, subgraph<Graph>& g)
    {
      if (g.is_root()) {
        remove_edge(e_global, g.m_graph);
        children_remove_edge(e_global, g.m_children);
      } else
        remove_edge_recur_up(e_global, *g.m_parent);
    }

  } // namespace detail

  template <typename G>
  void
  remove_edge(typename subgraph<G>::vertex_descriptor u_local,
              typename subgraph<G>::vertex_descriptor v_local,
              subgraph<G>& g)
  {
    if (g.is_root())
      detail::remove_edge_recur_up(u_local, v_local, g);
    else
      detail::remove_edge_recur_up(g.local_to_global(u_local),
                                   g.local_to_global(v_local), g);
  }

  template <typename G>
  void
  remove_edge(typename subgraph<G>::edge_descriptor e_local,
              subgraph<G>& g)
  {
    if (g.is_root())
      detail::remove_edge_recur_up(e_local, g);
    else
      detail::remove_edge_recur_up(g.local_to_global(e_local), g);
  }

  template <typename Predicate, typename G>
  void
  remove_edge_if(Predicate p, subgraph<G>& g)
  {
    // This is wrong...
    remove_edge_if(p, g.m_graph);
  }

  template <typename G>
  void
  clear_vertex(typename subgraph<G>::vertex_descriptor v_local,
               subgraph<G>& g)
  {
    // this is wrong...
    clear_vertex(v_local, g.m_graph);
  }

  namespace detail {

    template <typename G>
    typename subgraph<G>::vertex_descriptor
    add_vertex_recur_up(subgraph<G>& g)
    {
      typename subgraph<G>::vertex_descriptor u_local, u_global;
      if (g.is_root()) {
        u_global = add_vertex(g.m_graph);
        g.m_global_vertex.push_back(u_global);
      } else {
        u_global = add_vertex_recur_up(*g.m_parent);
        u_local = add_vertex(g.m_graph);
        g.m_global_vertex.push_back(u_global);
        g.m_local_vertex[u_global] = u_local;
      }
      return u_global;
    }

  } // namespace detail

  template <typename G>
  typename subgraph<G>::vertex_descriptor
  add_vertex(subgraph<G>& g)
  {
    typename subgraph<G>::vertex_descriptor  u_local, u_global;
    if (g.is_root()) {
      u_global = add_vertex(g.m_graph);
      g.m_global_vertex.push_back(u_global);
      u_local = u_global;
    } else {
      u_global = detail::add_vertex_recur_up(g.parent());
      u_local = add_vertex(g.m_graph);
      g.m_global_vertex.push_back(u_global);
      g.m_local_vertex[u_global] = u_local;
    }
    return u_local;
  }

  template <typename G>
  void remove_vertex(typename subgraph<G>::vertex_descriptor u,
                     subgraph<G>& g)
  {
    // UNDER CONSTRUCTION
    assert(false);
  }


  //===========================================================================
  // Functions required by the PropertyGraph concept

  template <typename GraphPtr, typename PropertyMap, typename Tag>
  class subgraph_global_property_map
    : public put_get_helper<
        typename property_traits<PropertyMap>::reference,
        subgraph_global_property_map<GraphPtr, PropertyMap, Tag> >
  {
    typedef property_traits<PropertyMap> Traits;
  public:
    typedef typename Traits::category category;
    typedef typename Traits::value_type value_type;
    typedef typename Traits::key_type key_type;
    typedef typename Traits::reference reference;

    subgraph_global_property_map() { }

    subgraph_global_property_map(GraphPtr g)
      : m_g(g) { }

    inline reference operator[](key_type e_local) const {
      PropertyMap pmap = get(Tag(), m_g->root().m_graph);
      if (m_g->m_parent == 0)
        return pmap[e_local];
      else
        return pmap[m_g->local_to_global(e_local)];
    }
    GraphPtr m_g;
  };

  template <typename GraphPtr, typename PropertyMap, typename Tag>
  class subgraph_local_property_map
    : public put_get_helper<
        typename property_traits<PropertyMap>::reference,
        subgraph_local_property_map<GraphPtr, PropertyMap, Tag> >
  {
    typedef property_traits<PropertyMap> Traits;
  public:
    typedef typename Traits::category category;
    typedef typename Traits::value_type value_type;
    typedef typename Traits::key_type key_type;
    typedef typename Traits::reference reference;

    subgraph_local_property_map() { }

    subgraph_local_property_map(GraphPtr g)
      : m_g(g) { }

    inline reference operator[](key_type e_local) const {
      PropertyMap pmap = get(Tag(), *m_g);
      return pmap[e_local];
    }
    GraphPtr m_g;
  };

  namespace detail {

    struct subgraph_any_pmap {
      template <class Tag, class SubGraph, class Property>
      class bind_ {
        typedef typename SubGraph::graph_type Graph;
        typedef SubGraph* SubGraphPtr;
        typedef const SubGraph* const_SubGraphPtr;
        typedef typename property_map<Graph, Tag>::type PMap;
        typedef typename property_map<Graph, Tag>::const_type const_PMap;
      public:
        typedef subgraph_global_property_map<SubGraphPtr, PMap, Tag> type;
        typedef subgraph_global_property_map<const_SubGraphPtr, const_PMap, Tag>
          const_type;
      };
    };
    struct subgraph_id_pmap {
      template <class Tag, class SubGraph, class Property>
      struct bind_ {
        typedef typename SubGraph::graph_type Graph;
        typedef SubGraph* SubGraphPtr;
        typedef const SubGraph* const_SubGraphPtr;
        typedef typename property_map<Graph, Tag>::type PMap;
        typedef typename property_map<Graph, Tag>::const_type const_PMap;
      public:
        typedef subgraph_local_property_map<SubGraphPtr, PMap, Tag> type;
        typedef subgraph_local_property_map<const_SubGraphPtr, const_PMap, Tag>
          const_type;
      };
    };
    template <class Tag>
    struct subgraph_choose_pmap_helper {
      typedef subgraph_any_pmap type;
    };
    template <>
    struct subgraph_choose_pmap_helper<vertex_index_t> {
      typedef subgraph_id_pmap type;
    };
    template <class Tag, class Graph, class Property>
    struct subgraph_choose_pmap {
      typedef typename subgraph_choose_pmap_helper<Tag>::type Helper;
      typedef typename Helper::template bind_<Tag, Graph, Property> Bind;
      typedef typename Bind::type type;
      typedef typename Bind::const_type const_type;
    };
    struct subgraph_property_generator {
      template <class SubGraph, class Property, class Tag>
      struct bind_ {
        typedef subgraph_choose_pmap<Tag, SubGraph, Property> Choice;
        typedef typename Choice::type type;
        typedef typename Choice::const_type const_type;
      };
    };

  } // namespace detail

  template <>
  struct vertex_property_selector<subgraph_tag> {
    typedef detail::subgraph_property_generator type;
  };

  template <>
  struct edge_property_selector<subgraph_tag> {
    typedef detail::subgraph_property_generator type;
  };

  template <typename G, typename Property>
  typename property_map< subgraph<G>, Property>::type
  get(Property, subgraph<G>& g)
  {
    typedef typename property_map< subgraph<G>, Property>::type PMap;
    return PMap(&g);
  }

  template <typename G, typename Property>
  typename property_map< subgraph<G>, Property>::const_type
  get(Property, const subgraph<G>& g)
  {
    typedef typename property_map< subgraph<G>, Property>::const_type PMap;
    return PMap(&g);
  }

  template <typename G, typename Property, typename Key>
  typename property_traits<
    typename property_map< subgraph<G>, Property>::const_type
  >::value_type
  get(Property, const subgraph<G>& g, const Key& k)
  {
    typedef typename property_map< subgraph<G>, Property>::const_type PMap;
    PMap pmap(&g);
    return pmap[k];
  }

  template <typename G, typename Property, typename Key, typename Value>
  void
  put(Property, subgraph<G>& g, const Key& k, const Value& val)
  {
    typedef typename property_map< subgraph<G>, Property>::type PMap;
    PMap pmap(&g);
    pmap[k] = val;
  }

  template <typename G, typename Tag>
  inline
  typename graph_property<G, Tag>::type&
  get_property(subgraph<G>& g, Tag tag) {
    return get_property(g.m_graph, tag);
  }

  template <typename G, typename Tag>
  inline
  const typename graph_property<G, Tag>::type&
  get_property(const subgraph<G>& g, Tag tag) {
    return get_property(g.m_graph, tag);
  }

  //===========================================================================
  // Miscellaneous Functions

  template <typename G>
  typename subgraph<G>::vertex_descriptor
  vertex(typename subgraph<G>::vertices_size_type n, const subgraph<G>& g)
  {
    return vertex(n, g.m_graph);
  }

} // namespace boost

#endif // BOOST_SUBGRAPH_HPP