epoc32/include/stdapis/boost/graph/subgraph.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
williamr@2
     1
//=======================================================================
williamr@2
     2
// Copyright 2001 University of Notre Dame.
williamr@2
     3
// Authors: Jeremy G. Siek and Lie-Quan Lee
williamr@2
     4
//
williamr@2
     5
// Distributed under the Boost Software License, Version 1.0. (See
williamr@2
     6
// accompanying file LICENSE_1_0.txt or copy at
williamr@2
     7
// http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     8
//=======================================================================
williamr@2
     9
williamr@2
    10
#ifndef BOOST_SUBGRAPH_HPP
williamr@2
    11
#define BOOST_SUBGRAPH_HPP
williamr@2
    12
williamr@2
    13
// UNDER CONSTRUCTION
williamr@2
    14
williamr@2
    15
#include <boost/config.hpp>
williamr@2
    16
#include <list>
williamr@2
    17
#include <vector>
williamr@2
    18
#include <map>
williamr@2
    19
#include <cassert>
williamr@2
    20
#include <boost/graph/graph_traits.hpp>
williamr@2
    21
#include <boost/graph/properties.hpp>
williamr@2
    22
#include <boost/iterator/indirect_iterator.hpp>
williamr@2
    23
williamr@2
    24
#include <boost/static_assert.hpp>
williamr@2
    25
#include <boost/type_traits/is_same.hpp>
williamr@2
    26
williamr@2
    27
namespace boost {
williamr@2
    28
williamr@2
    29
  struct subgraph_tag { };
williamr@2
    30
williamr@2
    31
  // Invariants of an induced subgraph:
williamr@2
    32
  //   - If vertex u is in subgraph g, then u must be in g.parent().
williamr@2
    33
  //   - If edge e is in subgraph g, then e must be in g.parent().
williamr@2
    34
  //   - If edge e=(u,v) is in the root graph, then edge e
williamr@2
    35
  //     is also in any subgraph that contains both vertex u and v.
williamr@2
    36
williamr@2
    37
  // The Graph template parameter must have a vertex_index
williamr@2
    38
  // and edge_index internal property. It is assumed that
williamr@2
    39
  // the vertex indices are assigned automatically by the
williamr@2
    40
  // graph during a call to add_vertex(). It is not
williamr@2
    41
  // assumed that the edge vertices are assigned automatically,
williamr@2
    42
  // they are explicitly assigned here.
williamr@2
    43
williamr@2
    44
  template <typename Graph>
williamr@2
    45
  class subgraph {
williamr@2
    46
    typedef graph_traits<Graph> Traits;
williamr@2
    47
    typedef std::list<subgraph<Graph>*> ChildrenList;
williamr@2
    48
  public:
williamr@2
    49
    // Graph requirements
williamr@2
    50
    typedef typename Traits::vertex_descriptor         vertex_descriptor;
williamr@2
    51
    typedef typename Traits::edge_descriptor           edge_descriptor;
williamr@2
    52
    typedef typename Traits::directed_category         directed_category;
williamr@2
    53
    typedef typename Traits::edge_parallel_category    edge_parallel_category;
williamr@2
    54
    typedef typename Traits::traversal_category        traversal_category;
williamr@2
    55
williamr@2
    56
    static vertex_descriptor null_vertex()
williamr@2
    57
    {
williamr@2
    58
      return Traits::null_vertex();
williamr@2
    59
    }
williamr@2
    60
williamr@2
    61
williamr@2
    62
    // IncidenceGraph requirements
williamr@2
    63
    typedef typename Traits::out_edge_iterator         out_edge_iterator;
williamr@2
    64
    typedef typename Traits::degree_size_type          degree_size_type;
williamr@2
    65
williamr@2
    66
    // AdjacencyGraph requirements
williamr@2
    67
    typedef typename Traits::adjacency_iterator        adjacency_iterator;
williamr@2
    68
williamr@2
    69
    // VertexListGraph requirements
williamr@2
    70
    typedef typename Traits::vertex_iterator           vertex_iterator;
williamr@2
    71
    typedef typename Traits::vertices_size_type        vertices_size_type;
williamr@2
    72
williamr@2
    73
    // EdgeListGraph requirements
williamr@2
    74
    typedef typename Traits::edge_iterator             edge_iterator;
williamr@2
    75
    typedef typename Traits::edges_size_type           edges_size_type;
williamr@2
    76
williamr@2
    77
    typedef typename Traits::in_edge_iterator          in_edge_iterator;
williamr@2
    78
williamr@2
    79
    typedef typename Graph::edge_property_type         edge_property_type;
williamr@2
    80
    typedef typename Graph::vertex_property_type       vertex_property_type;
williamr@2
    81
    typedef subgraph_tag                               graph_tag;
williamr@2
    82
    typedef Graph                                      graph_type;
williamr@2
    83
    typedef typename Graph::graph_property_type        graph_property_type;
williamr@2
    84
williamr@2
    85
    // Constructors
williamr@2
    86
williamr@2
    87
    // Create the main graph, the root of the subgraph tree
williamr@2
    88
    subgraph()
williamr@2
    89
      : m_parent(0), m_edge_counter(0)
williamr@2
    90
    { }
williamr@2
    91
    subgraph(const graph_property_type& p)
williamr@2
    92
      : m_graph(p), m_parent(0), m_edge_counter(0)
williamr@2
    93
    { }
williamr@2
    94
    subgraph(vertices_size_type n,
williamr@2
    95
             const graph_property_type& p = graph_property_type())
williamr@2
    96
      : m_graph(n, p), m_parent(0), m_edge_counter(0), m_global_vertex(n)
williamr@2
    97
    {
williamr@2
    98
      typename Graph::vertex_iterator v, v_end;
williamr@2
    99
      vertices_size_type i = 0;
williamr@2
   100
      for (tie(v, v_end) = vertices(m_graph); v != v_end; ++v)
williamr@2
   101
        m_global_vertex[i++] = *v;
williamr@2
   102
    }
williamr@2
   103
williamr@2
   104
    // copy constructor
williamr@2
   105
    subgraph(const subgraph& x)
williamr@2
   106
      : m_graph(x.m_graph), m_parent(x.m_parent),
williamr@2
   107
      m_edge_counter(x.m_edge_counter),
williamr@2
   108
      m_global_vertex(x.m_global_vertex),
williamr@2
   109
      m_global_edge(x.m_global_edge)
williamr@2
   110
    {
williamr@2
   111
      // Do a deep copy
williamr@2
   112
      for (typename ChildrenList::const_iterator i = x.m_children.begin();
williamr@2
   113
           i != x.m_children.end(); ++i)
williamr@2
   114
        m_children.push_back(new subgraph<Graph>( **i ));
williamr@2
   115
    }
williamr@2
   116
williamr@2
   117
williamr@2
   118
    ~subgraph() {
williamr@2
   119
      for (typename ChildrenList::iterator i = m_children.begin();
williamr@2
   120
           i != m_children.end(); ++i)
williamr@2
   121
        delete *i;
williamr@2
   122
    }
williamr@2
   123
williamr@2
   124
williamr@2
   125
    // Create a subgraph
williamr@2
   126
    subgraph<Graph>& create_subgraph() {
williamr@2
   127
      m_children.push_back(new subgraph<Graph>());
williamr@2
   128
      m_children.back()->m_parent = this;
williamr@2
   129
      return *m_children.back();
williamr@2
   130
    }
williamr@2
   131
williamr@2
   132
    // Create a subgraph with the specified vertex set.
williamr@2
   133
    template <typename VertexIterator>
williamr@2
   134
    subgraph<Graph>& create_subgraph(VertexIterator first,
williamr@2
   135
                                     VertexIterator last)
williamr@2
   136
    {
williamr@2
   137
      m_children.push_back(new subgraph<Graph>());
williamr@2
   138
      m_children.back()->m_parent = this;
williamr@2
   139
      for (; first != last; ++first)
williamr@2
   140
        add_vertex(*first, *m_children.back());
williamr@2
   141
      return *m_children.back();
williamr@2
   142
    }
williamr@2
   143
williamr@2
   144
    // local <-> global descriptor conversion functions
williamr@2
   145
    vertex_descriptor local_to_global(vertex_descriptor u_local) const
williamr@2
   146
    {
williamr@2
   147
      return m_global_vertex[u_local];
williamr@2
   148
    }
williamr@2
   149
    vertex_descriptor global_to_local(vertex_descriptor u_global) const
williamr@2
   150
    {
williamr@2
   151
      vertex_descriptor u_local; bool in_subgraph;
williamr@2
   152
      tie(u_local, in_subgraph) = this->find_vertex(u_global);
williamr@2
   153
      assert(in_subgraph == true);
williamr@2
   154
      return u_local;
williamr@2
   155
    }
williamr@2
   156
    edge_descriptor local_to_global(edge_descriptor e_local) const
williamr@2
   157
    {
williamr@2
   158
      return m_global_edge[get(get(edge_index, m_graph), e_local)];
williamr@2
   159
    }
williamr@2
   160
    edge_descriptor global_to_local(edge_descriptor e_global) const
williamr@2
   161
    {
williamr@2
   162
      return
williamr@2
   163
        (*m_local_edge.find(get(get(edge_index, root().m_graph), e_global))).second;
williamr@2
   164
    }
williamr@2
   165
williamr@2
   166
    // Is vertex u (of the root graph) contained in this subgraph?
williamr@2
   167
    // If so, return the matching local vertex.
williamr@2
   168
    std::pair<vertex_descriptor, bool>
williamr@2
   169
    find_vertex(vertex_descriptor u_global) const
williamr@2
   170
    {
williamr@2
   171
      typename std::map<vertex_descriptor, vertex_descriptor>::const_iterator
williamr@2
   172
        i = m_local_vertex.find(u_global);
williamr@2
   173
      bool valid = i != m_local_vertex.end();
williamr@2
   174
      return std::make_pair((valid ? (*i).second : null_vertex()), valid);
williamr@2
   175
    }
williamr@2
   176
williamr@2
   177
    // Return the parent graph.
williamr@2
   178
    subgraph& parent() { return *m_parent; }
williamr@2
   179
    const subgraph& parent() const { return *m_parent; }
williamr@2
   180
williamr@2
   181
    bool is_root() const { return m_parent == 0; }
williamr@2
   182
williamr@2
   183
    // Return the root graph of the subgraph tree.
williamr@2
   184
    subgraph& root() {
williamr@2
   185
      if (this->is_root())
williamr@2
   186
        return *this;
williamr@2
   187
      else
williamr@2
   188
        return m_parent->root();
williamr@2
   189
    }
williamr@2
   190
    const subgraph& root() const {
williamr@2
   191
      if (this->is_root())
williamr@2
   192
        return *this;
williamr@2
   193
      else
williamr@2
   194
        return m_parent->root();
williamr@2
   195
    }
williamr@2
   196
williamr@2
   197
    // Return the children subgraphs of this graph/subgraph.
williamr@2
   198
    // Use a list of pointers because the VC++ std::list doesn't like
williamr@2
   199
    // storing incomplete type.
williamr@2
   200
    typedef indirect_iterator<
williamr@2
   201
        typename ChildrenList::const_iterator
williamr@2
   202
      , subgraph<Graph>
williamr@2
   203
      , std::bidirectional_iterator_tag
williamr@2
   204
    >
williamr@2
   205
    children_iterator;
williamr@2
   206
williamr@2
   207
    typedef indirect_iterator<
williamr@2
   208
        typename ChildrenList::const_iterator
williamr@2
   209
      , subgraph<Graph> const
williamr@2
   210
      , std::bidirectional_iterator_tag
williamr@2
   211
    >
williamr@2
   212
    const_children_iterator;
williamr@2
   213
williamr@2
   214
    std::pair<const_children_iterator, const_children_iterator>
williamr@2
   215
    children() const
williamr@2
   216
    {
williamr@2
   217
      return std::make_pair(const_children_iterator(m_children.begin()),
williamr@2
   218
                            const_children_iterator(m_children.end()));
williamr@2
   219
    }
williamr@2
   220
williamr@2
   221
    std::pair<children_iterator, children_iterator>
williamr@2
   222
    children()
williamr@2
   223
    {
williamr@2
   224
      return std::make_pair(children_iterator(m_children.begin()),
williamr@2
   225
                            children_iterator(m_children.end()));
williamr@2
   226
    }
williamr@2
   227
williamr@2
   228
    std::size_t num_children() const { return m_children.size(); }
williamr@2
   229
williamr@2
   230
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
williamr@2
   231
    // Bundled properties support
williamr@2
   232
    template<typename Descriptor>
williamr@2
   233
    typename graph::detail::bundled_result<Graph, Descriptor>::type&
williamr@2
   234
    operator[](Descriptor x)
williamr@2
   235
    { 
williamr@2
   236
      if (m_parent == 0) return m_graph[x];
williamr@2
   237
      else return root().m_graph[local_to_global(x)];
williamr@2
   238
    }
williamr@2
   239
williamr@2
   240
    template<typename Descriptor>
williamr@2
   241
    typename graph::detail::bundled_result<Graph, Descriptor>::type const&
williamr@2
   242
    operator[](Descriptor x) const
williamr@2
   243
    { 
williamr@2
   244
      if (m_parent == 0) return m_graph[x];
williamr@2
   245
      else return root().m_graph[local_to_global(x)];
williamr@2
   246
    }
williamr@2
   247
#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
williamr@2
   248
williamr@2
   249
    //  private:
williamr@2
   250
    typedef typename property_map<Graph, edge_index_t>::type EdgeIndexMap;
williamr@2
   251
    typedef typename property_traits<EdgeIndexMap>::value_type edge_index_type;
williamr@2
   252
    BOOST_STATIC_ASSERT((!is_same<edge_index_type, 
williamr@2
   253
                        boost::detail::error_property_not_found>::value));
williamr@2
   254
williamr@2
   255
    Graph m_graph;
williamr@2
   256
    subgraph<Graph>* m_parent;
williamr@2
   257
    edge_index_type m_edge_counter; // for generating unique edge indices
williamr@2
   258
    ChildrenList m_children;
williamr@2
   259
    std::vector<vertex_descriptor> m_global_vertex; // local -> global
williamr@2
   260
    std::map<vertex_descriptor, vertex_descriptor> m_local_vertex;  // global -> local
williamr@2
   261
    std::vector<edge_descriptor> m_global_edge;              // local -> global
williamr@2
   262
    std::map<edge_index_type, edge_descriptor> m_local_edge; // global -> local
williamr@2
   263
williamr@2
   264
    edge_descriptor
williamr@2
   265
    local_add_edge(vertex_descriptor u_local, vertex_descriptor v_local,
williamr@2
   266
                   edge_descriptor e_global)
williamr@2
   267
    {
williamr@2
   268
      edge_descriptor e_local;
williamr@2
   269
      bool inserted;
williamr@2
   270
      tie(e_local, inserted) = add_edge(u_local, v_local, m_graph);
williamr@2
   271
      put(edge_index, m_graph, e_local, m_edge_counter++);
williamr@2
   272
      m_global_edge.push_back(e_global);
williamr@2
   273
      m_local_edge[get(get(edge_index, this->root()), e_global)] = e_local;
williamr@2
   274
      return e_local;
williamr@2
   275
    }
williamr@2
   276
williamr@2
   277
  };
williamr@2
   278
williamr@2
   279
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
williamr@2
   280
  template<typename Graph>
williamr@2
   281
  struct vertex_bundle_type<subgraph<Graph> > : vertex_bundle_type<Graph> { };
williamr@2
   282
williamr@2
   283
  template<typename Graph>
williamr@2
   284
  struct edge_bundle_type<subgraph<Graph> > : edge_bundle_type<Graph> { };
williamr@2
   285
#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
williamr@2
   286
williamr@2
   287
  //===========================================================================
williamr@2
   288
  // Functions special to the Subgraph Class
williamr@2
   289
williamr@2
   290
  template <typename G>
williamr@2
   291
  typename subgraph<G>::vertex_descriptor
williamr@2
   292
  add_vertex(typename subgraph<G>::vertex_descriptor u_global,
williamr@2
   293
             subgraph<G>& g)
williamr@2
   294
  {
williamr@2
   295
    assert(!g.is_root());
williamr@2
   296
    typename subgraph<G>::vertex_descriptor u_local, v_global, uu_global;
williamr@2
   297
    typename subgraph<G>::edge_descriptor e_global;
williamr@2
   298
williamr@2
   299
    u_local = add_vertex(g.m_graph);
williamr@2
   300
    g.m_global_vertex.push_back(u_global);
williamr@2
   301
    g.m_local_vertex[u_global] = u_local;
williamr@2
   302
williamr@2
   303
    subgraph<G>& r = g.root();
williamr@2
   304
williamr@2
   305
    // remember edge global and local maps
williamr@2
   306
    {
williamr@2
   307
      typename subgraph<G>::out_edge_iterator ei, ei_end;
williamr@2
   308
      for (tie(ei, ei_end) = out_edges(u_global, r);
williamr@2
   309
           ei != ei_end; ++ei) {
williamr@2
   310
        e_global = *ei;
williamr@2
   311
        v_global = target(e_global, r);
williamr@2
   312
        if (g.find_vertex(v_global).second == true)
williamr@2
   313
          g.local_add_edge(u_local, g.global_to_local(v_global), e_global);
williamr@2
   314
      }
williamr@2
   315
    }
williamr@2
   316
    if (is_directed(g)) { // not necessary for undirected graph
williamr@2
   317
      typename subgraph<G>::vertex_iterator vi, vi_end;
williamr@2
   318
      typename subgraph<G>::out_edge_iterator ei, ei_end;
williamr@2
   319
      for (tie(vi, vi_end) = vertices(r); vi != vi_end; ++vi) {
williamr@2
   320
        v_global = *vi;
williamr@2
   321
        if (g.find_vertex(v_global).second)
williamr@2
   322
          for (tie(ei, ei_end) = out_edges(*vi, r); ei != ei_end; ++ei) {
williamr@2
   323
            e_global = *ei;
williamr@2
   324
            uu_global = target(e_global, r);
williamr@2
   325
            if (uu_global == u_global && g.find_vertex(v_global).second)
williamr@2
   326
              g.local_add_edge(g.global_to_local(v_global), u_local, e_global);
williamr@2
   327
          }
williamr@2
   328
      }
williamr@2
   329
    }
williamr@2
   330
williamr@2
   331
    return u_local;
williamr@2
   332
  }
williamr@2
   333
williamr@2
   334
  //===========================================================================
williamr@2
   335
  // Functions required by the IncidenceGraph concept
williamr@2
   336
williamr@2
   337
  template <typename G>
williamr@2
   338
  std::pair<typename graph_traits<G>::out_edge_iterator,
williamr@2
   339
            typename graph_traits<G>::out_edge_iterator>
williamr@2
   340
  out_edges(typename graph_traits<G>::vertex_descriptor u_local,
williamr@2
   341
            const subgraph<G>& g)
williamr@2
   342
    { return out_edges(u_local, g.m_graph); }
williamr@2
   343
williamr@2
   344
  template <typename G>
williamr@2
   345
  typename graph_traits<G>::degree_size_type
williamr@2
   346
  out_degree(typename graph_traits<G>::vertex_descriptor u_local,
williamr@2
   347
             const subgraph<G>& g)
williamr@2
   348
    { return out_degree(u_local, g.m_graph); }
williamr@2
   349
williamr@2
   350
  template <typename G>
williamr@2
   351
  typename graph_traits<G>::vertex_descriptor
williamr@2
   352
  source(typename graph_traits<G>::edge_descriptor e_local,
williamr@2
   353
         const subgraph<G>& g)
williamr@2
   354
    { return source(e_local, g.m_graph); }
williamr@2
   355
williamr@2
   356
  template <typename G>
williamr@2
   357
  typename graph_traits<G>::vertex_descriptor
williamr@2
   358
  target(typename graph_traits<G>::edge_descriptor e_local,
williamr@2
   359
         const subgraph<G>& g)
williamr@2
   360
    { return target(e_local, g.m_graph); }
williamr@2
   361
williamr@2
   362
  //===========================================================================
williamr@2
   363
  // Functions required by the BidirectionalGraph concept
williamr@2
   364
williamr@2
   365
  template <typename G>
williamr@2
   366
  std::pair<typename graph_traits<G>::in_edge_iterator,
williamr@2
   367
            typename graph_traits<G>::in_edge_iterator>
williamr@2
   368
  in_edges(typename graph_traits<G>::vertex_descriptor u_local,
williamr@2
   369
            const subgraph<G>& g)
williamr@2
   370
    { return in_edges(u_local, g.m_graph); }
williamr@2
   371
williamr@2
   372
  template <typename G>
williamr@2
   373
  typename graph_traits<G>::degree_size_type
williamr@2
   374
  in_degree(typename graph_traits<G>::vertex_descriptor u_local,
williamr@2
   375
             const subgraph<G>& g)
williamr@2
   376
    { return in_degree(u_local, g.m_graph); }
williamr@2
   377
williamr@2
   378
  template <typename G>
williamr@2
   379
  typename graph_traits<G>::degree_size_type
williamr@2
   380
  degree(typename graph_traits<G>::vertex_descriptor u_local,
williamr@2
   381
             const subgraph<G>& g)
williamr@2
   382
    { return degree(u_local, g.m_graph); }
williamr@2
   383
williamr@2
   384
  //===========================================================================
williamr@2
   385
  // Functions required by the AdjacencyGraph concept
williamr@2
   386
williamr@2
   387
  template <typename G>
williamr@2
   388
  std::pair<typename subgraph<G>::adjacency_iterator,
williamr@2
   389
            typename subgraph<G>::adjacency_iterator>
williamr@2
   390
  adjacent_vertices(typename subgraph<G>::vertex_descriptor u_local,
williamr@2
   391
                    const subgraph<G>& g)
williamr@2
   392
    { return adjacent_vertices(u_local, g.m_graph); }
williamr@2
   393
williamr@2
   394
  //===========================================================================
williamr@2
   395
  // Functions required by the VertexListGraph concept
williamr@2
   396
williamr@2
   397
  template <typename G>
williamr@2
   398
  std::pair<typename subgraph<G>::vertex_iterator,
williamr@2
   399
            typename subgraph<G>::vertex_iterator>
williamr@2
   400
  vertices(const subgraph<G>& g)
williamr@2
   401
    { return vertices(g.m_graph); }
williamr@2
   402
williamr@2
   403
  template <typename G>
williamr@2
   404
  typename subgraph<G>::vertices_size_type
williamr@2
   405
  num_vertices(const subgraph<G>& g)
williamr@2
   406
    { return num_vertices(g.m_graph); }
williamr@2
   407
williamr@2
   408
  //===========================================================================
williamr@2
   409
  // Functions required by the EdgeListGraph concept
williamr@2
   410
williamr@2
   411
  template <typename G>
williamr@2
   412
  std::pair<typename subgraph<G>::edge_iterator,
williamr@2
   413
            typename subgraph<G>::edge_iterator>
williamr@2
   414
  edges(const subgraph<G>& g)
williamr@2
   415
    { return edges(g.m_graph); }
williamr@2
   416
williamr@2
   417
  template <typename G>
williamr@2
   418
  typename subgraph<G>::edges_size_type
williamr@2
   419
  num_edges(const subgraph<G>& g)
williamr@2
   420
    { return num_edges(g.m_graph); }
williamr@2
   421
williamr@2
   422
  //===========================================================================
williamr@2
   423
  // Functions required by the AdjacencyMatrix concept
williamr@2
   424
williamr@2
   425
  template <typename G>
williamr@2
   426
  std::pair<typename subgraph<G>::edge_descriptor, bool>
williamr@2
   427
  edge(typename subgraph<G>::vertex_descriptor u_local,
williamr@2
   428
       typename subgraph<G>::vertex_descriptor v_local,
williamr@2
   429
       const subgraph<G>& g)
williamr@2
   430
  {
williamr@2
   431
    return edge(u_local, v_local, g.m_graph);
williamr@2
   432
  }
williamr@2
   433
williamr@2
   434
  //===========================================================================
williamr@2
   435
  // Functions required by the MutableGraph concept
williamr@2
   436
williamr@2
   437
  namespace detail {
williamr@2
   438
williamr@2
   439
    template <typename Vertex, typename Edge, typename Graph>
williamr@2
   440
    void add_edge_recur_down
williamr@2
   441
    (Vertex u_global, Vertex v_global, Edge e_global, subgraph<Graph>& g);
williamr@2
   442
williamr@2
   443
    template <typename Vertex, typename Edge, typename Children, typename G>
williamr@2
   444
    void children_add_edge(Vertex u_global, Vertex v_global, Edge e_global,
williamr@2
   445
                           Children& c, subgraph<G>* orig)
williamr@2
   446
    {
williamr@2
   447
      for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
williamr@2
   448
        if ((*i)->find_vertex(u_global).second
williamr@2
   449
            && (*i)->find_vertex(v_global).second)
williamr@2
   450
          add_edge_recur_down(u_global, v_global, e_global, **i, orig);
williamr@2
   451
    }
williamr@2
   452
williamr@2
   453
    template <typename Vertex, typename Edge, typename Graph>
williamr@2
   454
    void add_edge_recur_down
williamr@2
   455
      (Vertex u_global, Vertex v_global, Edge e_global, subgraph<Graph>& g,
williamr@2
   456
       subgraph<Graph>* orig)
williamr@2
   457
    {
williamr@2
   458
      if (&g != orig ) {
williamr@2
   459
        // add local edge only if u_global and v_global are in subgraph g
williamr@2
   460
        Vertex u_local, v_local;
williamr@2
   461
        bool u_in_subgraph, v_in_subgraph;
williamr@2
   462
        tie(u_local, u_in_subgraph) = g.find_vertex(u_global);
williamr@2
   463
        tie(v_local, v_in_subgraph) = g.find_vertex(v_global);
williamr@2
   464
        if (u_in_subgraph && v_in_subgraph)
williamr@2
   465
          g.local_add_edge(u_local, v_local, e_global);
williamr@2
   466
      }
williamr@2
   467
      children_add_edge(u_global, v_global, e_global, g.m_children, orig);
williamr@2
   468
    }
williamr@2
   469
williamr@2
   470
    template <typename Vertex, typename Graph>
williamr@2
   471
    std::pair<typename subgraph<Graph>::edge_descriptor, bool>
williamr@2
   472
    add_edge_recur_up(Vertex u_global, Vertex v_global,
williamr@2
   473
                      const typename Graph::edge_property_type& ep,
williamr@2
   474
                      subgraph<Graph>& g, subgraph<Graph>* orig)
williamr@2
   475
    {
williamr@2
   476
      if (g.is_root()) {
williamr@2
   477
        typename subgraph<Graph>::edge_descriptor e_global;
williamr@2
   478
        bool inserted;
williamr@2
   479
        tie(e_global, inserted) = add_edge(u_global, v_global, ep, g.m_graph);
williamr@2
   480
        put(edge_index, g.m_graph, e_global, g.m_edge_counter++);
williamr@2
   481
        g.m_global_edge.push_back(e_global);
williamr@2
   482
        children_add_edge(u_global, v_global, e_global, g.m_children, orig);
williamr@2
   483
        return std::make_pair(e_global, inserted);
williamr@2
   484
      } else
williamr@2
   485
        return add_edge_recur_up(u_global, v_global, ep, *g.m_parent, orig);
williamr@2
   486
    }
williamr@2
   487
williamr@2
   488
  } // namespace detail
williamr@2
   489
williamr@2
   490
  // Add an edge to the subgraph g, specified by the local vertex
williamr@2
   491
  // descriptors u and v. In addition, the edge will be added to any
williamr@2
   492
  // other subgraphs which contain vertex descriptors u and v.
williamr@2
   493
williamr@2
   494
  template <typename G>
williamr@2
   495
  std::pair<typename subgraph<G>::edge_descriptor, bool>
williamr@2
   496
  add_edge(typename subgraph<G>::vertex_descriptor u_local,
williamr@2
   497
           typename subgraph<G>::vertex_descriptor v_local,
williamr@2
   498
           const typename G::edge_property_type& ep,
williamr@2
   499
           subgraph<G>& g)
williamr@2
   500
  {
williamr@2
   501
    if (g.is_root()) // u_local and v_local are really global
williamr@2
   502
      return detail::add_edge_recur_up(u_local, v_local, ep, g, &g);
williamr@2
   503
    else {
williamr@2
   504
      typename subgraph<G>::edge_descriptor e_local, e_global;
williamr@2
   505
      bool inserted;
williamr@2
   506
      tie(e_global, inserted) = detail::add_edge_recur_up
williamr@2
   507
        (g.local_to_global(u_local), g.local_to_global(v_local), ep, g, &g);
williamr@2
   508
      e_local = g.local_add_edge(u_local, v_local, e_global);
williamr@2
   509
      return std::make_pair(e_local, inserted);
williamr@2
   510
    }
williamr@2
   511
  }
williamr@2
   512
williamr@2
   513
  template <typename G>
williamr@2
   514
  std::pair<typename subgraph<G>::edge_descriptor, bool>
williamr@2
   515
  add_edge(typename subgraph<G>::vertex_descriptor u,
williamr@2
   516
           typename subgraph<G>::vertex_descriptor v,
williamr@2
   517
           subgraph<G>& g)
williamr@2
   518
  {
williamr@2
   519
    typename G::edge_property_type ep;
williamr@2
   520
    return add_edge(u, v, ep, g);
williamr@2
   521
  }
williamr@2
   522
williamr@2
   523
  namespace detail {
williamr@2
   524
williamr@2
   525
    //-------------------------------------------------------------------------
williamr@2
   526
    // implementation of remove_edge(u,v,g)
williamr@2
   527
williamr@2
   528
    template <typename Vertex, typename Graph>
williamr@2
   529
    void remove_edge_recur_down(Vertex u_global, Vertex v_global,
williamr@2
   530
                                subgraph<Graph>& g);
williamr@2
   531
williamr@2
   532
    template <typename Vertex, typename Children>
williamr@2
   533
    void children_remove_edge(Vertex u_global, Vertex v_global,
williamr@2
   534
                              Children& c)
williamr@2
   535
    {
williamr@2
   536
      for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
williamr@2
   537
        if ((*i)->find_vertex(u_global).second
williamr@2
   538
            && (*i)->find_vertex(v_global).second)
williamr@2
   539
          remove_edge_recur_down(u_global, v_global, **i);
williamr@2
   540
    }
williamr@2
   541
williamr@2
   542
    template <typename Vertex, typename Graph>
williamr@2
   543
    void remove_edge_recur_down(Vertex u_global, Vertex v_global,
williamr@2
   544
                                subgraph<Graph>& g)
williamr@2
   545
    {
williamr@2
   546
      Vertex u_local, v_local;
williamr@2
   547
      u_local = g.m_local_vertex[u_global];
williamr@2
   548
      v_local = g.m_local_vertex[v_global];
williamr@2
   549
      remove_edge(u_local, v_local, g.m_graph);
williamr@2
   550
      children_remove_edge(u_global, v_global, g.m_children);
williamr@2
   551
    }
williamr@2
   552
williamr@2
   553
    template <typename Vertex, typename Graph>
williamr@2
   554
    void remove_edge_recur_up(Vertex u_global, Vertex v_global,
williamr@2
   555
                              subgraph<Graph>& g)
williamr@2
   556
    {
williamr@2
   557
      if (g.is_root()) {
williamr@2
   558
        remove_edge(u_global, v_global, g.m_graph);
williamr@2
   559
        children_remove_edge(u_global, v_global, g.m_children);
williamr@2
   560
      } else
williamr@2
   561
        remove_edge_recur_up(u_global, v_global, *g.m_parent);
williamr@2
   562
    }
williamr@2
   563
williamr@2
   564
    //-------------------------------------------------------------------------
williamr@2
   565
    // implementation of remove_edge(e,g)
williamr@2
   566
williamr@2
   567
    template <typename Edge, typename Graph>
williamr@2
   568
    void remove_edge_recur_down(Edge e_global, subgraph<Graph>& g);
williamr@2
   569
williamr@2
   570
    template <typename Edge, typename Children>
williamr@2
   571
    void children_remove_edge(Edge e_global, Children& c)
williamr@2
   572
    {
williamr@2
   573
      for (typename Children::iterator i = c.begin(); i != c.end(); ++i)
williamr@2
   574
        if ((*i)->find_vertex(source(e_global, **i)).second
williamr@2
   575
            && (*i)->find_vertex(target(e_global, **i)).second)
williamr@2
   576
          remove_edge_recur_down(source(e_global, **i),
williamr@2
   577
                                 target(e_global, **i), **i);
williamr@2
   578
    }
williamr@2
   579
williamr@2
   580
    template <typename Edge, typename Graph>
williamr@2
   581
    void remove_edge_recur_down(Edge e_global, subgraph<Graph>& g)
williamr@2
   582
    {
williamr@2
   583
      remove_edge(g.global_to_local(e_global), g.m_graph);
williamr@2
   584
      children_remove_edge(e_global, g.m_children);
williamr@2
   585
    }
williamr@2
   586
williamr@2
   587
    template <typename Edge, typename Graph>
williamr@2
   588
    void remove_edge_recur_up(Edge e_global, subgraph<Graph>& g)
williamr@2
   589
    {
williamr@2
   590
      if (g.is_root()) {
williamr@2
   591
        remove_edge(e_global, g.m_graph);
williamr@2
   592
        children_remove_edge(e_global, g.m_children);
williamr@2
   593
      } else
williamr@2
   594
        remove_edge_recur_up(e_global, *g.m_parent);
williamr@2
   595
    }
williamr@2
   596
williamr@2
   597
  } // namespace detail
williamr@2
   598
williamr@2
   599
  template <typename G>
williamr@2
   600
  void
williamr@2
   601
  remove_edge(typename subgraph<G>::vertex_descriptor u_local,
williamr@2
   602
              typename subgraph<G>::vertex_descriptor v_local,
williamr@2
   603
              subgraph<G>& g)
williamr@2
   604
  {
williamr@2
   605
    if (g.is_root())
williamr@2
   606
      detail::remove_edge_recur_up(u_local, v_local, g);
williamr@2
   607
    else
williamr@2
   608
      detail::remove_edge_recur_up(g.local_to_global(u_local),
williamr@2
   609
                                   g.local_to_global(v_local), g);
williamr@2
   610
  }
williamr@2
   611
williamr@2
   612
  template <typename G>
williamr@2
   613
  void
williamr@2
   614
  remove_edge(typename subgraph<G>::edge_descriptor e_local,
williamr@2
   615
              subgraph<G>& g)
williamr@2
   616
  {
williamr@2
   617
    if (g.is_root())
williamr@2
   618
      detail::remove_edge_recur_up(e_local, g);
williamr@2
   619
    else
williamr@2
   620
      detail::remove_edge_recur_up(g.local_to_global(e_local), g);
williamr@2
   621
  }
williamr@2
   622
williamr@2
   623
  template <typename Predicate, typename G>
williamr@2
   624
  void
williamr@2
   625
  remove_edge_if(Predicate p, subgraph<G>& g)
williamr@2
   626
  {
williamr@2
   627
    // This is wrong...
williamr@2
   628
    remove_edge_if(p, g.m_graph);
williamr@2
   629
  }
williamr@2
   630
williamr@2
   631
  template <typename G>
williamr@2
   632
  void
williamr@2
   633
  clear_vertex(typename subgraph<G>::vertex_descriptor v_local,
williamr@2
   634
               subgraph<G>& g)
williamr@2
   635
  {
williamr@2
   636
    // this is wrong...
williamr@2
   637
    clear_vertex(v_local, g.m_graph);
williamr@2
   638
  }
williamr@2
   639
williamr@2
   640
  namespace detail {
williamr@2
   641
williamr@2
   642
    template <typename G>
williamr@2
   643
    typename subgraph<G>::vertex_descriptor
williamr@2
   644
    add_vertex_recur_up(subgraph<G>& g)
williamr@2
   645
    {
williamr@2
   646
      typename subgraph<G>::vertex_descriptor u_local, u_global;
williamr@2
   647
      if (g.is_root()) {
williamr@2
   648
        u_global = add_vertex(g.m_graph);
williamr@2
   649
        g.m_global_vertex.push_back(u_global);
williamr@2
   650
      } else {
williamr@2
   651
        u_global = add_vertex_recur_up(*g.m_parent);
williamr@2
   652
        u_local = add_vertex(g.m_graph);
williamr@2
   653
        g.m_global_vertex.push_back(u_global);
williamr@2
   654
        g.m_local_vertex[u_global] = u_local;
williamr@2
   655
      }
williamr@2
   656
      return u_global;
williamr@2
   657
    }
williamr@2
   658
williamr@2
   659
  } // namespace detail
williamr@2
   660
williamr@2
   661
  template <typename G>
williamr@2
   662
  typename subgraph<G>::vertex_descriptor
williamr@2
   663
  add_vertex(subgraph<G>& g)
williamr@2
   664
  {
williamr@2
   665
    typename subgraph<G>::vertex_descriptor  u_local, u_global;
williamr@2
   666
    if (g.is_root()) {
williamr@2
   667
      u_global = add_vertex(g.m_graph);
williamr@2
   668
      g.m_global_vertex.push_back(u_global);
williamr@2
   669
      u_local = u_global;
williamr@2
   670
    } else {
williamr@2
   671
      u_global = detail::add_vertex_recur_up(g.parent());
williamr@2
   672
      u_local = add_vertex(g.m_graph);
williamr@2
   673
      g.m_global_vertex.push_back(u_global);
williamr@2
   674
      g.m_local_vertex[u_global] = u_local;
williamr@2
   675
    }
williamr@2
   676
    return u_local;
williamr@2
   677
  }
williamr@2
   678
williamr@2
   679
  template <typename G>
williamr@2
   680
  void remove_vertex(typename subgraph<G>::vertex_descriptor u,
williamr@2
   681
                     subgraph<G>& g)
williamr@2
   682
  {
williamr@2
   683
    // UNDER CONSTRUCTION
williamr@2
   684
    assert(false);
williamr@2
   685
  }
williamr@2
   686
williamr@2
   687
williamr@2
   688
  //===========================================================================
williamr@2
   689
  // Functions required by the PropertyGraph concept
williamr@2
   690
williamr@2
   691
  template <typename GraphPtr, typename PropertyMap, typename Tag>
williamr@2
   692
  class subgraph_global_property_map
williamr@2
   693
    : public put_get_helper<
williamr@2
   694
        typename property_traits<PropertyMap>::reference,
williamr@2
   695
        subgraph_global_property_map<GraphPtr, PropertyMap, Tag> >
williamr@2
   696
  {
williamr@2
   697
    typedef property_traits<PropertyMap> Traits;
williamr@2
   698
  public:
williamr@2
   699
    typedef typename Traits::category category;
williamr@2
   700
    typedef typename Traits::value_type value_type;
williamr@2
   701
    typedef typename Traits::key_type key_type;
williamr@2
   702
    typedef typename Traits::reference reference;
williamr@2
   703
williamr@2
   704
    subgraph_global_property_map() { }
williamr@2
   705
williamr@2
   706
    subgraph_global_property_map(GraphPtr g)
williamr@2
   707
      : m_g(g) { }
williamr@2
   708
williamr@2
   709
    inline reference operator[](key_type e_local) const {
williamr@2
   710
      PropertyMap pmap = get(Tag(), m_g->root().m_graph);
williamr@2
   711
      if (m_g->m_parent == 0)
williamr@2
   712
        return pmap[e_local];
williamr@2
   713
      else
williamr@2
   714
        return pmap[m_g->local_to_global(e_local)];
williamr@2
   715
    }
williamr@2
   716
    GraphPtr m_g;
williamr@2
   717
  };
williamr@2
   718
williamr@2
   719
  template <typename GraphPtr, typename PropertyMap, typename Tag>
williamr@2
   720
  class subgraph_local_property_map
williamr@2
   721
    : public put_get_helper<
williamr@2
   722
        typename property_traits<PropertyMap>::reference,
williamr@2
   723
        subgraph_local_property_map<GraphPtr, PropertyMap, Tag> >
williamr@2
   724
  {
williamr@2
   725
    typedef property_traits<PropertyMap> Traits;
williamr@2
   726
  public:
williamr@2
   727
    typedef typename Traits::category category;
williamr@2
   728
    typedef typename Traits::value_type value_type;
williamr@2
   729
    typedef typename Traits::key_type key_type;
williamr@2
   730
    typedef typename Traits::reference reference;
williamr@2
   731
williamr@2
   732
    subgraph_local_property_map() { }
williamr@2
   733
williamr@2
   734
    subgraph_local_property_map(GraphPtr g)
williamr@2
   735
      : m_g(g) { }
williamr@2
   736
williamr@2
   737
    inline reference operator[](key_type e_local) const {
williamr@2
   738
      PropertyMap pmap = get(Tag(), *m_g);
williamr@2
   739
      return pmap[e_local];
williamr@2
   740
    }
williamr@2
   741
    GraphPtr m_g;
williamr@2
   742
  };
williamr@2
   743
williamr@2
   744
  namespace detail {
williamr@2
   745
williamr@2
   746
    struct subgraph_any_pmap {
williamr@2
   747
      template <class Tag, class SubGraph, class Property>
williamr@2
   748
      class bind_ {
williamr@2
   749
        typedef typename SubGraph::graph_type Graph;
williamr@2
   750
        typedef SubGraph* SubGraphPtr;
williamr@2
   751
        typedef const SubGraph* const_SubGraphPtr;
williamr@2
   752
        typedef typename property_map<Graph, Tag>::type PMap;
williamr@2
   753
        typedef typename property_map<Graph, Tag>::const_type const_PMap;
williamr@2
   754
      public:
williamr@2
   755
        typedef subgraph_global_property_map<SubGraphPtr, PMap, Tag> type;
williamr@2
   756
        typedef subgraph_global_property_map<const_SubGraphPtr, const_PMap, Tag>
williamr@2
   757
          const_type;
williamr@2
   758
      };
williamr@2
   759
    };
williamr@2
   760
    struct subgraph_id_pmap {
williamr@2
   761
      template <class Tag, class SubGraph, class Property>
williamr@2
   762
      struct bind_ {
williamr@2
   763
        typedef typename SubGraph::graph_type Graph;
williamr@2
   764
        typedef SubGraph* SubGraphPtr;
williamr@2
   765
        typedef const SubGraph* const_SubGraphPtr;
williamr@2
   766
        typedef typename property_map<Graph, Tag>::type PMap;
williamr@2
   767
        typedef typename property_map<Graph, Tag>::const_type const_PMap;
williamr@2
   768
      public:
williamr@2
   769
        typedef subgraph_local_property_map<SubGraphPtr, PMap, Tag> type;
williamr@2
   770
        typedef subgraph_local_property_map<const_SubGraphPtr, const_PMap, Tag>
williamr@2
   771
          const_type;
williamr@2
   772
      };
williamr@2
   773
    };
williamr@2
   774
    template <class Tag>
williamr@2
   775
    struct subgraph_choose_pmap_helper {
williamr@2
   776
      typedef subgraph_any_pmap type;
williamr@2
   777
    };
williamr@2
   778
    template <>
williamr@2
   779
    struct subgraph_choose_pmap_helper<vertex_index_t> {
williamr@2
   780
      typedef subgraph_id_pmap type;
williamr@2
   781
    };
williamr@2
   782
    template <class Tag, class Graph, class Property>
williamr@2
   783
    struct subgraph_choose_pmap {
williamr@2
   784
      typedef typename subgraph_choose_pmap_helper<Tag>::type Helper;
williamr@2
   785
      typedef typename Helper::template bind_<Tag, Graph, Property> Bind;
williamr@2
   786
      typedef typename Bind::type type;
williamr@2
   787
      typedef typename Bind::const_type const_type;
williamr@2
   788
    };
williamr@2
   789
    struct subgraph_property_generator {
williamr@2
   790
      template <class SubGraph, class Property, class Tag>
williamr@2
   791
      struct bind_ {
williamr@2
   792
        typedef subgraph_choose_pmap<Tag, SubGraph, Property> Choice;
williamr@2
   793
        typedef typename Choice::type type;
williamr@2
   794
        typedef typename Choice::const_type const_type;
williamr@2
   795
      };
williamr@2
   796
    };
williamr@2
   797
williamr@2
   798
  } // namespace detail
williamr@2
   799
williamr@2
   800
  template <>
williamr@2
   801
  struct vertex_property_selector<subgraph_tag> {
williamr@2
   802
    typedef detail::subgraph_property_generator type;
williamr@2
   803
  };
williamr@2
   804
williamr@2
   805
  template <>
williamr@2
   806
  struct edge_property_selector<subgraph_tag> {
williamr@2
   807
    typedef detail::subgraph_property_generator type;
williamr@2
   808
  };
williamr@2
   809
williamr@2
   810
  template <typename G, typename Property>
williamr@2
   811
  typename property_map< subgraph<G>, Property>::type
williamr@2
   812
  get(Property, subgraph<G>& g)
williamr@2
   813
  {
williamr@2
   814
    typedef typename property_map< subgraph<G>, Property>::type PMap;
williamr@2
   815
    return PMap(&g);
williamr@2
   816
  }
williamr@2
   817
williamr@2
   818
  template <typename G, typename Property>
williamr@2
   819
  typename property_map< subgraph<G>, Property>::const_type
williamr@2
   820
  get(Property, const subgraph<G>& g)
williamr@2
   821
  {
williamr@2
   822
    typedef typename property_map< subgraph<G>, Property>::const_type PMap;
williamr@2
   823
    return PMap(&g);
williamr@2
   824
  }
williamr@2
   825
williamr@2
   826
  template <typename G, typename Property, typename Key>
williamr@2
   827
  typename property_traits<
williamr@2
   828
    typename property_map< subgraph<G>, Property>::const_type
williamr@2
   829
  >::value_type
williamr@2
   830
  get(Property, const subgraph<G>& g, const Key& k)
williamr@2
   831
  {
williamr@2
   832
    typedef typename property_map< subgraph<G>, Property>::const_type PMap;
williamr@2
   833
    PMap pmap(&g);
williamr@2
   834
    return pmap[k];
williamr@2
   835
  }
williamr@2
   836
williamr@2
   837
  template <typename G, typename Property, typename Key, typename Value>
williamr@2
   838
  void
williamr@2
   839
  put(Property, subgraph<G>& g, const Key& k, const Value& val)
williamr@2
   840
  {
williamr@2
   841
    typedef typename property_map< subgraph<G>, Property>::type PMap;
williamr@2
   842
    PMap pmap(&g);
williamr@2
   843
    pmap[k] = val;
williamr@2
   844
  }
williamr@2
   845
williamr@2
   846
  template <typename G, typename Tag>
williamr@2
   847
  inline
williamr@2
   848
  typename graph_property<G, Tag>::type&
williamr@2
   849
  get_property(subgraph<G>& g, Tag tag) {
williamr@2
   850
    return get_property(g.m_graph, tag);
williamr@2
   851
  }
williamr@2
   852
williamr@2
   853
  template <typename G, typename Tag>
williamr@2
   854
  inline
williamr@2
   855
  const typename graph_property<G, Tag>::type&
williamr@2
   856
  get_property(const subgraph<G>& g, Tag tag) {
williamr@2
   857
    return get_property(g.m_graph, tag);
williamr@2
   858
  }
williamr@2
   859
williamr@2
   860
  //===========================================================================
williamr@2
   861
  // Miscellaneous Functions
williamr@2
   862
williamr@2
   863
  template <typename G>
williamr@2
   864
  typename subgraph<G>::vertex_descriptor
williamr@2
   865
  vertex(typename subgraph<G>::vertices_size_type n, const subgraph<G>& g)
williamr@2
   866
  {
williamr@2
   867
    return vertex(n, g.m_graph);
williamr@2
   868
  }
williamr@2
   869
williamr@2
   870
} // namespace boost
williamr@2
   871
williamr@2
   872
#endif // BOOST_SUBGRAPH_HPP