subgraph.hpp

support vector clustering for vc++

  add_vertex(typename subgraph<G>::vertex_descriptor u_global,
             subgraph<G>& g)
  {
    assert(!g.is_root());
    typename subgraph<G>::vertex_descriptor u_local, v_global, uu_global;
    typename subgraph<G>::edge_descriptor e_global;

    u_local = add_vertex(g.m_graph);
    g.m_global_vertex.push_back(u_global);
    g.m_local_vertex[u_global] = u_local;

    subgraph<G>& r = g.root();

    // remember edge global and local maps
    {
      typename subgraph<G>::out_edge_iterator ei, ei_end;
      for (tie(ei, ei_end) = out_edges(u_global, r);
           ei != ei_end; ++ei) {
        e_global = *ei;
        v_global = target(e_global, r);
        if (g.find_vertex(v_global).second == true)
          g.local_add_edge(u_local, g.global_to_local(v_global), e_global);
      }
    }
    if (is_directed(g)) { // not necessary for undirected graph
      typename subgraph<G>::vertex_iterator vi, vi_end;
      typename subgraph<G>::out_edge_iterator ei, ei_end;
      for (tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) {
        v_global = *vi;
        if (g.find_vertex(v_global).second)
          for (tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) {
            e_global = *ei;
            uu_global = target(e_global, r);
            if (uu_global == u_global && g.find_vertex(v_global).second)
              g.local_add_edge(g.global_to_local(v_global), u_local, e_global);
          }
      }
    }

    return u_local;
  }

  //===========================================================================
  // Functions required by the IncidenceGraph concept

  template <typename G>
  std::pair<typename graph_traits<G>::out_edge_iterator,
            typename graph_traits<G>::out_edge_iterator>
  out_edges(typename graph_traits<G>::vertex_descriptor u_local,
            const subgraph<G>& g)
    { return out_edges(u_local, g.m_graph); }

  template <typename G>
  typename graph_traits<G>::degree_size_type
  out_degree(typename graph_traits<G>::vertex_descriptor u_local,
             const subgraph<G>& g)
    { return out_degree(u_local, g.m_graph); }

  template <typename G>
  typename graph_traits<G>::vertex_descriptor
  source(typename graph_traits<G>::edge_descriptor e_local,
         const subgraph<G>& g)
    { return source(e_local, g.m_graph); }

  template <typename G>
  typename graph_traits<G>::vertex_descriptor
  target(typename graph_traits<G>::edge_descriptor e_local,
         const subgraph<G>& g)
    { return target(e_local, g.m_graph); }

  //===========================================================================
  // Functions required by the BidirectionalGraph concept

  template <typename G>
  std::pair<typename graph_traits<G>::in_edge_iterator,
            typename graph_traits<G>::in_edge_iterator>
  in_edges(typename graph_traits<G>::vertex_descriptor u_local,
            const subgraph<G>& g)
    { return in_edges(u_local, g.m_graph); }

  template <typename G>
  typename graph_traits<G>::degree_size_type
  in_degree(typename graph_traits<G>::vertex_descriptor u_local,
             const subgraph<G>& g)
    { return in_degree(u_local, g.m_graph); }

  template <typename G>
  typename graph_traits<G>::degree_size_type
  degree(typename graph_traits<G>::vertex_descriptor u_local,
             const subgraph<G>& g)
    { return degree(u_local, g.m_graph); }

  //===========================================================================
  // Functions required by the AdjacencyGraph concept

  template <typename G>
  std::pair<typename subgraph<G>::adjacency_iterator,
            typename subgraph<G>::adjacency_iterator>
  adjacent_vertices(typename subgraph<G>::vertex_descriptor u_local,
                    const subgraph<G>& g)
    { return adjacent_vertices(u_local, g.m_graph); }

  //===========================================================================
  // Functions required by the VertexListGraph concept

  template <typename G>
  std::pair<typename subgraph<G>::vertex_iterator,
            typename subgraph<G>::vertex_iterator>
  vertices(const subgraph<G>& g)
    { return vertices(g.m_graph); }

  template <typename G>
  typename subgraph<G>::vertices_size_type
  num_vertices(const subgraph<G>& g)
    { return num_vertices(g.m_graph); }

  //===========================================================================
  // Functions required by the EdgeListGraph concept

  template <typename G>
  std::pair<typename subgraph<G>::edge_iterator,
            typename subgraph<G>::edge_iterator>
  edges(const subgraph<G>& g)
    { return edges(g.m_graph); }

  template <typename G>
  typename subgraph<G>::edges_size_type
  num_edges(const subgraph<G>& g)
    { return num_edges(g.m_graph); }

  //===========================================================================
  // Functions required by the AdjacencyMatrix concept

  template <typename G>
  std::pair<typename subgraph<G>::edge_descriptor, bool>
  edge(typename subgraph<G>::vertex_descriptor u_local,
       typename subgraph<G>::vertex_descriptor v_local,
       const subgraph<G>& g)
  {
    return edge(u_local, v_local, g.m_graph);
  }

  //===========================================================================
  // Functions required by the MutableGraph concept

  namespace detail {

    template <typename Vertex, typename Edge, typename Graph>
    void add_edge_recur_down
    (Vertex u_global, Vertex v_global, Edge e_global, subgraph<Graph>& g);

    template <typename Vertex, typename Edge, typename Children, typename G>
    void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global,
                           Children& c, subgraph<G>* orig)
    {
      for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
        if ((*i)->find_vertex(u_global).second
            && (*i)->find_vertex(v_global).second)
          add_edge_recur_down(u_global, v_global, e_global, **i, orig);
    }

    template <typename Vertex, typename Edge, typename Graph>
    void add_edge_recur_down
      (Vertex u_global, Vertex v_global, Edge e_global, subgraph<Graph>& g,
       subgraph<Graph>* orig)
    {
      if (&g != orig ) {
        // add local edge only if u_global and v_global are in subgraph g
        Vertex u_local, v_local;
        bool u_in_subgraph, v_in_subgraph;
        tie(u_local, u_in_subgraph) = g.find_vertex(u_global);
        tie(v_local, v_in_subgraph) = g.find_vertex(v_global);
        if (u_in_subgraph && v_in_subgraph)
          g.local_add_edge(u_local, v_local, e_global);
      }
      children_add_edge(u_global, v_global, e_global, g.m_children, orig);
    }

    template <typename Vertex, typename Graph>
    std::pair<typename subgraph<Graph>::edge_descriptor, bool>
    add_edge_recur_up(Vertex u_global, Vertex v_global,
                      const typename Graph::edge_property_type& ep,
                      subgraph<Graph>& g, subgraph<Graph>* orig)
    {
      if (g.is_root()) {
        typename subgraph<Graph>::edge_descriptor e_global;
        bool inserted;
        tie(e_global, inserted) = add_edge(u_global, v_global, ep, g.m_graph);
        put(edge_index, g.m_graph, e_global, g.m_edge_counter++);
        g.m_global_edge.push_back(e_global);
        children_add_edge(u_global, v_global, e_global, g.m_children, orig);
        return std::make_pair(e_global, inserted);
      } else
        return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig);
    }

  } // namespace detail

  // Add an edge to the subgraph g, specified by the local vertex
  // descriptors u and v. In addition, the edge will be added to any
  // other subgraphs which contain vertex descriptors u and v.

  template <typename G>
  std::pair<typename subgraph<G>::edge_descriptor, bool>
  add_edge(typename subgraph<G>::vertex_descriptor u_local,
           typename subgraph<G>::vertex_descriptor v_local,
           const typename G::edge_property_type& ep,
           subgraph<G>& g)
  {
    if (g.is_root()) // u_local and v_local are really global
      return detail::add_edge_recur_up(u_local, v_local, ep, g, &g);
    else {
      typename subgraph<G>::edge_descriptor e_local, e_global;
      bool inserted;
      tie(e_global, inserted) = detail::add_edge_recur_up
        (g.local_to_global(u_local), g.local_to_global(v_local), ep, g, &g);
      e_local = g.local_add_edge(u_local, v_local, e_global);
      return std::make_pair(e_local, inserted);
    }
  }

  template <typename G>
  std::pair<typename subgraph<G>::edge_descriptor, bool>
  add_edge(typename subgraph<G>::vertex_descriptor u,
           typename subgraph<G>::vertex_descriptor v,
           subgraph<G>& g)
  {
    typename G::edge_property_type ep;
    return add_edge(u, v, ep, g);
  }

  namespace detail {

    //-------------------------------------------------------------------------
    // implementation of remove_edge(u,v,g)

    template <typename Vertex, typename Graph>
    void remove_edge_recur_down(Vertex u_global, Vertex v_global,
                                subgraph<Graph>& g);

    template <typename Vertex, typename Children>
    void children_remove_edge(Vertex u_global, Vertex v_global,
                              Children& c)
    {
      for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
        if ((*i)->find_vertex(u_global).second
            && (*i)->find_vertex(v_global).second)
          remove_edge_recur_down(u_global, v_global, **i);
    }

    template <typename Vertex, typename Graph>
    void remove_edge_recur_down(Vertex u_global, Vertex v_global,
                                subgraph<Graph>& g)
    {
      Vertex u_local, v_local;
      u_local = g.m_local_vertex[u_global];
      v_local = g.m_local_vertex[v_global];
      remove_edge(u_local, v_local, g.m_graph);
      children_remove_edge(u_global, v_global, g.m_children);
    }

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

    //-------------------------------------------------------------------------
    // implementation of remove_edge(e,g)

    template <typename Edge, typename Graph>
    void remove_edge_recur_down(Edge e_global, subgraph<Graph>& g);

    template <typename Edge, typename Children>
    void children_remove_edge(Edge e_global, Children& c)
    {
      for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
        if ((*i)->find_vertex(source(e_global, **i)).second
            && (*i)->find_vertex(target(e_global, **i)).second)
          remove_edge_recur_down(source(e_global, **i),
                                 target(e_global, **i), **i);
    }

    template <typename Edge, typename Graph>
    void remove_edge_recur_down(Edge e_global, subgraph<Graph>& g)
    {