filtered_graph.hpp

support vector clustering for vc++

  inline filtered_graph<const Graph, EdgePredicate, VertexPredicate>
  make_filtered_graph(const Graph& g, EdgePredicate ep, VertexPredicate vp) {
    return filtered_graph<const Graph, EdgePredicate, VertexPredicate>(g, ep, vp);
  }

  template <typename G, typename EP, typename VP>
  std::pair<typename filtered_graph<G, EP, VP>::vertex_iterator,
            typename filtered_graph<G, EP, VP>::vertex_iterator>
  vertices(const filtered_graph<G, EP, VP>& g)
  {
    typedef filtered_graph<G, EP, VP> Graph;    
    typename graph_traits<G>::vertex_iterator f, l;
    tie(f, l) = vertices(g.m_g);
    typedef typename Graph::vertex_iterator iter;
    return std::make_pair(iter(g.m_vertex_pred, f, l), 
                          iter(g.m_vertex_pred, l, l));
  }

  template <typename G, typename EP, typename VP>
  std::pair<typename filtered_graph<G, EP, VP>::edge_iterator,
            typename filtered_graph<G, EP, VP>::edge_iterator>
  edges(const filtered_graph<G, EP, VP>& g)
  {
    typedef filtered_graph<G, EP, VP> Graph;
    typename Graph::EdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
    typename graph_traits<G>::edge_iterator f, l;
    tie(f, l) = edges(g.m_g);
    typedef typename Graph::edge_iterator iter;
    return std::make_pair(iter(pred, f, l), iter(pred, l, l));
  }

  // An alternative for num_vertices() and num_edges() would be to
  // count the number in the filtered graph. This is problematic
  // because of the interaction with the vertex indices...  they would
  // no longer go from 0 to num_vertices(), which would cause trouble
  // for algorithms allocating property storage in an array. We could
  // try to create a mapping to new recalibrated indices, but I don't
  // see an efficient way to do this.
  //
  // However, the current solution is still unsatisfactory because
  // the following semantic constraints no longer hold:
  // tie(vi, viend) = vertices(g);
  // assert(std::distance(vi, viend) == num_vertices(g));

  template <typename G, typename EP, typename VP>  
  typename filtered_graph<G, EP, VP>::vertices_size_type
  num_vertices(const filtered_graph<G, EP, VP>& g) {
    return num_vertices(g.m_g);
  }

  template <typename G, typename EP, typename VP>  
  typename filtered_graph<G, EP, VP>::edges_size_type
  num_edges(const filtered_graph<G, EP, VP>& g) {
    return num_edges(g.m_g);
  }
  
  template <typename G>
  typename filtered_graph_base<G>::vertex_descriptor
  source(typename filtered_graph_base<G>::edge_descriptor e,
         const filtered_graph_base<G>& g)
  {
    return source(e, g.m_g);
  }

  template <typename G>
  typename filtered_graph_base<G>::vertex_descriptor
  target(typename filtered_graph_base<G>::edge_descriptor e,
         const filtered_graph_base<G>& g)
  {
    return target(e, g.m_g);
  }

  template <typename G, typename EP, typename VP>
  std::pair<typename filtered_graph<G, EP, VP>::out_edge_iterator,
            typename filtered_graph<G, EP, VP>::out_edge_iterator>
  out_edges(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
            const filtered_graph<G, EP, VP>& g)
  {
    typedef filtered_graph<G, EP, VP> Graph;
    typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
    typedef typename Graph::out_edge_iterator iter;
    typename graph_traits<G>::out_edge_iterator f, l;
    tie(f, l) = out_edges(u, g.m_g);
    return std::make_pair(iter(pred, f, l), iter(pred, l, l));
  }

  template <typename G, typename EP, typename VP>
  typename filtered_graph<G, EP, VP>::degree_size_type
  out_degree(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
             const filtered_graph<G, EP, VP>& g)
  {
    typename filtered_graph<G, EP, VP>::degree_size_type n = 0;
    typename filtered_graph<G, EP, VP>::out_edge_iterator f, l;
    for (tie(f, l) = out_edges(u, g); f != l; ++f)
      ++n;
    return n;
  }

  template <typename G, typename EP, typename VP>
  std::pair<typename filtered_graph<G, EP, VP>::adjacency_iterator,
            typename filtered_graph<G, EP, VP>::adjacency_iterator>
  adjacent_vertices(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
                    const filtered_graph<G, EP, VP>& g)
  {
    typedef filtered_graph<G, EP, VP> Graph;
    typedef typename Graph::adjacency_iterator adjacency_iterator;
    typename Graph::out_edge_iterator f, l;
    tie(f, l) = out_edges(u, g);
    return std::make_pair(adjacency_iterator(f, const_cast<Graph*>(&g)),
                          adjacency_iterator(l, const_cast<Graph*>(&g)));
  }
  
  template <typename G, typename EP, typename VP>
  std::pair<typename filtered_graph<G, EP, VP>::in_edge_iterator,
            typename filtered_graph<G, EP, VP>::in_edge_iterator>
  in_edges(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
            const filtered_graph<G, EP, VP>& g)
  {
    typedef filtered_graph<G, EP, VP> Graph;
    typename Graph::InEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
    typedef typename Graph::in_edge_iterator iter;
    typename graph_traits<G>::in_edge_iterator f, l;
    tie(f, l) = in_edges(u, g.m_g);
    return std::make_pair(iter(pred, f, l), iter(pred, l, l));
  }

  template <typename G, typename EP, typename VP>
  typename filtered_graph<G, EP, VP>::degree_size_type
  in_degree(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
             const filtered_graph<G, EP, VP>& g)
  {
    typename filtered_graph<G, EP, VP>::degree_size_type n = 0;
    typename filtered_graph<G, EP, VP>::in_edge_iterator f, l;
    for (tie(f, l) = in_edges(u, g); f != l; ++f)
      ++n;
    return n;
  }

  template <typename G, typename EP, typename VP>
  std::pair<typename filtered_graph<G, EP, VP>::edge_descriptor, bool>
  edge(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
       typename filtered_graph<G, EP, VP>::vertex_descriptor v,
       const filtered_graph<G, EP, VP>& g)
  {
    typename graph_traits<G>::edge_descriptor e;
    bool exists;
    tie(e, exists) = edge(u, v, g.m_g);
    return std::make_pair(e, exists && g.m_edge_pred(e));
  }

  template <typename G, typename EP, typename VP>
  std::pair<typename filtered_graph<G, EP, VP>::out_edge_iterator,
            typename filtered_graph<G, EP, VP>::out_edge_iterator>
  edge_range(typename filtered_graph<G, EP, VP>::vertex_descriptor u,
             typename filtered_graph<G, EP, VP>::vertex_descriptor v,
             const filtered_graph<G, EP, VP>& g)
  {
    typedef filtered_graph<G, EP, VP> Graph;
    typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g);
    typedef typename Graph::out_edge_iterator iter;
    typename graph_traits<G>::out_edge_iterator f, l;
    tie(f, l) = edge_range(u, v, g.m_g);
    return std::make_pair(iter(pred, f, l), iter(pred, l, l));
  }


  //===========================================================================
  // Property map

  namespace detail {
    struct filtered_graph_property_selector {
      template <class FilteredGraph, class Property, class Tag>
      struct bind_ {
        typedef typename FilteredGraph::graph_type Graph;
        typedef property_map<Graph, Tag> Map;
        typedef typename Map::type type;
        typedef typename Map::const_type const_type;
      };
    };    
  } // namespace detail

  template <>  
  struct vertex_property_selector<filtered_graph_tag> {
    typedef detail::filtered_graph_property_selector type;
  };
  template <>  
  struct edge_property_selector<filtered_graph_tag> {
    typedef detail::filtered_graph_property_selector type;
  };

  template <typename G, typename EP, typename VP, typename Property>
  typename property_map<G, Property>::type
  get(Property p, filtered_graph<G, EP, VP>& g)
  {
    return get(p, const_cast<G&>(g.m_g));
  }

  template <typename G, typename EP, typename VP,typename Property>
  typename property_map<G, Property>::const_type
  get(Property p, const filtered_graph<G, EP, VP>& g)
  {
    return get(p, (const G&)g.m_g);
  }

  template <typename G, typename EP, typename VP, typename Property,
            typename Key>
  typename property_map_value<G, Property>::type
  get(Property p, const filtered_graph<G, EP, VP>& g, const Key& k)
  {
    return get(p, (const G&)g.m_g, k);
  }

  template <typename G, typename EP, typename VP, typename Property, 
            typename Key, typename Value>
  void
  put(Property p, const filtered_graph<G, EP, VP>& g, const Key& k,
      const Value& val)
  {
    put(p, const_cast<G&>(g.m_g), k, val);
  }

  //===========================================================================
  // Some filtered subgraph specializations

  template <typename Graph, typename Set>
  struct vertex_subset_filter {
    typedef filtered_graph<Graph, keep_all, is_in_subset<Set> > type;
  };
  template <typename Graph, typename Set>
  inline typename vertex_subset_filter<Graph, Set>::type
  make_vertex_subset_filter(Graph& g, const Set& s) {
    typedef typename vertex_subset_filter<Graph, Set>::type Filter;
    is_in_subset<Set> p(s);
    return Filter(g, keep_all(), p);
  }

  template <typename Graph, typename Set>
  struct vertex_subset_compliment_filter {
    typedef filtered_graph<Graph, keep_all, is_not_in_subset<Set> > type;
  };
  template <typename Graph, typename Set>
  inline typename vertex_subset_compliment_filter<Graph, Set>::type
  make_vertex_subset_compliment_filter(Graph& g, const Set& s) {
    typedef typename vertex_subset_compliment_filter<Graph, Set>::type Filter;
    is_not_in_subset<Set> p(s);
    return Filter(g, keep_all(), p);
  }


} // namespace boost


#endif // BOOST_FILTERED_GRAPH_HPP