source: NonGTP/Boost/boost/graph/transitive_closure.hpp @ 857

Revision 857, 13.7 KB checked in by igarcia, 19 years ago (diff)
RevLine 
[857]1// Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su>
2// Copyright (C) 2001 Jeremy Siek <jsiek@cs.indiana.edu>
3// Distributed under the Boost Software License, Version 1.0. (See
4// accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6
7// NOTE: this final is generated by libs/graph/doc/transitive_closure.w
8
9#ifndef BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
10#define BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
11
12#include <vector>
13#include <algorithm> // for std::min and std::max
14#include <functional>
15#include <boost/config.hpp>
16#include <boost/bind.hpp>
17#include <boost/graph/vector_as_graph.hpp>
18#include <boost/graph/strong_components.hpp>
19#include <boost/graph/topological_sort.hpp>
20#include <boost/graph/graph_concepts.hpp>
21#include <boost/graph/named_function_params.hpp>
22
23namespace boost
24{
25
26  namespace detail
27  {
28    inline void
29      union_successor_sets(const std::vector < std::size_t > &s1,
30                           const std::vector < std::size_t > &s2,
31                           std::vector < std::size_t > &s3)
32    {
33      BOOST_USING_STD_MIN();
34      for (std::size_t k = 0; k < s1.size(); ++k)
35        s3[k] = min BOOST_PREVENT_MACRO_SUBSTITUTION(s1[k], s2[k]);
36    }
37  }                             // namespace detail
38
39  namespace detail
40  {
41    template < typename Container, typename ST = std::size_t,
42      typename VT = typename Container::value_type >
43      struct subscript_t:public std::unary_function < ST, VT >
44    {
45      typedef VT& result_type;
46
47      subscript_t(Container & c):container(&c)
48      {
49      }
50      VT & operator() (const ST & i) const
51      {
52        return (*container)[i];
53      }
54    protected:
55        Container * container;
56    };
57    template < typename Container >
58      subscript_t < Container > subscript(Container & c) {
59      return subscript_t < Container > (c);
60    }
61  }                             // namespace detail
62
63  template < typename Graph, typename GraphTC,
64    typename G_to_TC_VertexMap,
65    typename VertexIndexMap >
66    void transitive_closure(const Graph & g, GraphTC & tc,
67                            G_to_TC_VertexMap g_to_tc_map,
68                            VertexIndexMap index_map)
69  {
70    if (num_vertices(g) == 0)
71      return;
72    typedef typename graph_traits < Graph >::vertex_descriptor vertex;
73    typedef typename graph_traits < Graph >::edge_descriptor edge;
74    typedef typename graph_traits < Graph >::vertex_iterator vertex_iterator;
75    typedef typename property_traits < VertexIndexMap >::value_type size_type;
76    typedef typename graph_traits <
77      Graph >::adjacency_iterator adjacency_iterator;
78
79    function_requires < VertexListGraphConcept < Graph > >();
80    function_requires < AdjacencyGraphConcept < Graph > >();
81    function_requires < VertexMutableGraphConcept < GraphTC > >();
82    function_requires < EdgeMutableGraphConcept < GraphTC > >();
83    function_requires < ReadablePropertyMapConcept < VertexIndexMap,
84      vertex > >();
85
86    typedef size_type cg_vertex;
87    std::vector < cg_vertex > component_number_vec(num_vertices(g));
88    iterator_property_map < cg_vertex *, VertexIndexMap, cg_vertex, cg_vertex& >
89      component_number(&component_number_vec[0], index_map);
90
91    int num_scc = strong_components(g, component_number,
92                                    vertex_index_map(index_map));
93
94    std::vector < std::vector < vertex > >components;
95    build_component_lists(g, num_scc, component_number, components);
96
97    typedef std::vector<std::vector<cg_vertex> > CG_t;
98    CG_t CG(num_scc);
99    for (cg_vertex s = 0; s < components.size(); ++s) {
100      std::vector < cg_vertex > adj;
101      for (size_type i = 0; i < components[s].size(); ++i) {
102        vertex u = components[s][i];
103        adjacency_iterator v, v_end;
104        for (tie(v, v_end) = adjacent_vertices(u, g); v != v_end; ++v) {
105          cg_vertex t = component_number[*v];
106          if (s != t)           // Avoid loops in the condensation graph
107            adj.push_back(t);
108        }
109      }
110      std::sort(adj.begin(), adj.end());
111      typename std::vector<cg_vertex>::iterator di =
112        std::unique(adj.begin(), adj.end());
113      if (di != adj.end())
114        adj.erase(di, adj.end());
115      CG[s] = adj;
116    }
117
118    std::vector<cg_vertex> topo_order;
119    std::vector<cg_vertex> topo_number(num_vertices(CG));
120    topological_sort(CG, std::back_inserter(topo_order),
121                     vertex_index_map(identity_property_map()));
122    std::reverse(topo_order.begin(), topo_order.end());
123    size_type n = 0;
124    for (typename std::vector<cg_vertex>::iterator iter = topo_order.begin();
125         iter != topo_order.end(); ++iter)
126      topo_number[*iter] = n++;
127
128    for (size_type i = 0; i < num_vertices(CG); ++i)
129      std::sort(CG[i].begin(), CG[i].end(),
130                boost::bind(std::less<cg_vertex>(),
131                            boost::bind(detail::subscript(topo_number), _1),
132                            boost::bind(detail::subscript(topo_number), _2)));
133
134    std::vector<std::vector<cg_vertex> > chains;
135    {
136      std::vector<cg_vertex> in_a_chain(num_vertices(CG));
137      for (typename std::vector<cg_vertex>::iterator i = topo_order.begin();
138           i != topo_order.end(); ++i) {
139        cg_vertex v = *i;
140        if (!in_a_chain[v]) {
141          chains.resize(chains.size() + 1);
142          std::vector<cg_vertex>& chain = chains.back();
143          for (;;) {
144            chain.push_back(v);
145            in_a_chain[v] = true;
146            typename graph_traits<CG_t>::adjacency_iterator adj_first, adj_last;
147            tie(adj_first, adj_last) = adjacent_vertices(v, CG);
148            typename graph_traits<CG_t>::adjacency_iterator next
149              = std::find_if(adj_first, adj_last,
150                             std::not1(detail::subscript(in_a_chain)));
151            if (next != adj_last)
152              v = *next;
153            else
154              break;            // end of chain, dead-end
155
156          }
157        }
158      }
159    }
160    std::vector<size_type> chain_number(num_vertices(CG));
161    std::vector<size_type> pos_in_chain(num_vertices(CG));
162    for (size_type i = 0; i < chains.size(); ++i)
163      for (size_type j = 0; j < chains[i].size(); ++j) {
164        cg_vertex v = chains[i][j];
165        chain_number[v] = i;
166        pos_in_chain[v] = j;
167      }
168
169    cg_vertex inf = (std::numeric_limits< cg_vertex >::max)();
170    std::vector<std::vector<cg_vertex> > successors(num_vertices(CG),
171                                                    std::vector<cg_vertex>
172                                                    (chains.size(), inf));
173    for (typename std::vector<cg_vertex>::reverse_iterator
174           i = topo_order.rbegin(); i != topo_order.rend(); ++i) {
175      cg_vertex u = *i;
176      typename graph_traits<CG_t>::adjacency_iterator adj, adj_last;
177      for (tie(adj, adj_last) = adjacent_vertices(u, CG);
178           adj != adj_last; ++adj) {
179        cg_vertex v = *adj;
180        if (topo_number[v] < successors[u][chain_number[v]]) {
181          // Succ(u) = Succ(u) U Succ(v)
182          detail::union_successor_sets(successors[u], successors[v],
183                                       successors[u]);
184          // Succ(u) = Succ(u) U {v}
185          successors[u][chain_number[v]] = topo_number[v];
186        }
187      }
188    }
189
190    for (size_type i = 0; i < CG.size(); ++i)
191      CG[i].clear();
192    for (size_type i = 0; i < CG.size(); ++i)
193      for (size_type j = 0; j < chains.size(); ++j) {
194        size_type topo_num = successors[i][j];
195        if (topo_num < inf) {
196          cg_vertex v = topo_order[topo_num];
197          for (size_type k = pos_in_chain[v]; k < chains[j].size(); ++k)
198            CG[i].push_back(chains[j][k]);
199        }
200      }
201
202
203    // Add vertices to the transitive closure graph
204    typedef typename graph_traits < GraphTC >::vertex_descriptor tc_vertex;
205    {
206      vertex_iterator i, i_end;
207      for (tie(i, i_end) = vertices(g); i != i_end; ++i)
208        g_to_tc_map[*i] = add_vertex(tc);
209    }
210    // Add edges between all the vertices in two adjacent SCCs
211    typename graph_traits<CG_t>::vertex_iterator si, si_end;
212    for (tie(si, si_end) = vertices(CG); si != si_end; ++si) {
213      cg_vertex s = *si;
214      typename graph_traits<CG_t>::adjacency_iterator i, i_end;
215      for (tie(i, i_end) = adjacent_vertices(s, CG); i != i_end; ++i) {
216        cg_vertex t = *i;
217        for (size_type k = 0; k < components[s].size(); ++k)
218          for (size_type l = 0; l < components[t].size(); ++l)
219            add_edge(g_to_tc_map[components[s][k]],
220                     g_to_tc_map[components[t][l]], tc);
221      }
222    }
223    // Add edges connecting all vertices in a SCC
224    for (size_type i = 0; i < components.size(); ++i)
225      if (components[i].size() > 1)
226        for (size_type k = 0; k < components[i].size(); ++k)
227          for (size_type l = 0; l < components[i].size(); ++l) {
228            vertex u = components[i][k], v = components[i][l];
229            add_edge(g_to_tc_map[u], g_to_tc_map[v], tc);
230          }
231
232    // Find loopbacks in the original graph.
233    // Need to add it to transitive closure.
234    {
235      vertex_iterator i, i_end;
236      for (tie(i, i_end) = vertices(g); i != i_end; ++i)
237        {
238          adjacency_iterator ab, ae;
239          for (boost::tie(ab, ae) = adjacent_vertices(*i, g); ab != ae; ++ab)
240            {
241              if (*ab == *i)
242                if (components[component_number[*i]].size() == 1)
243                  add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc);
244            }
245        }
246    }
247  }
248
249  template <typename Graph, typename GraphTC>
250  void transitive_closure(const Graph & g, GraphTC & tc)
251  {
252    if (num_vertices(g) == 0)
253      return;
254    typedef typename property_map<Graph, vertex_index_t>::const_type
255      VertexIndexMap;
256    VertexIndexMap index_map = get(vertex_index, g);
257
258    typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex;
259    std::vector<tc_vertex> to_tc_vec(num_vertices(g));
260    iterator_property_map < tc_vertex *, VertexIndexMap, tc_vertex, tc_vertex&>
261      g_to_tc_map(&to_tc_vec[0], index_map);
262
263    transitive_closure(g, tc, g_to_tc_map, index_map);
264  }
265
266  namespace detail
267  {
268    template < typename Graph, typename GraphTC, typename G_to_TC_VertexMap,
269      typename VertexIndexMap>
270    void transitive_closure_dispatch
271      (const Graph & g, GraphTC & tc,
272       G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map)
273    {
274      typedef typename graph_traits < GraphTC >::vertex_descriptor tc_vertex;
275      typename std::vector < tc_vertex >::size_type
276        n = is_default_param(g_to_tc_map) ? num_vertices(g) : 1;
277      std::vector < tc_vertex > to_tc_vec(n);
278
279      transitive_closure
280        (g, tc,
281         choose_param(g_to_tc_map, make_iterator_property_map
282                      (to_tc_vec.begin(), index_map, to_tc_vec[0])),
283         index_map);
284    }
285  }                             // namespace detail
286
287  template < typename Graph, typename GraphTC,
288    typename P, typename T, typename R >
289    void transitive_closure(const Graph & g, GraphTC & tc,
290                            const bgl_named_params < P, T, R > &params)
291  {
292    if (num_vertices(g) == 0)
293      return;
294    detail::transitive_closure_dispatch
295      (g, tc, get_param(params, orig_to_copy_t()),
296       choose_const_pmap(get_param(params, vertex_index), g, vertex_index) );
297  }
298
299
300  template < typename G > void warshall_transitive_closure(G & g)
301  {
302    typedef typename graph_traits < G >::vertex_descriptor vertex;
303    typedef typename graph_traits < G >::vertex_iterator vertex_iterator;
304
305    function_requires < AdjacencyMatrixConcept < G > >();
306    function_requires < EdgeMutableGraphConcept < G > >();
307
308    // Matrix form:
309    // for k
310    //  for i
311    //    if A[i,k]
312    //      for j
313    //        A[i,j] = A[i,j] | A[k,j]
314    vertex_iterator ki, ke, ii, ie, ji, je;
315    for (tie(ki, ke) = vertices(g); ki != ke; ++ki)
316      for (tie(ii, ie) = vertices(g); ii != ie; ++ii)
317        if (edge(*ii, *ki, g).second)
318          for (tie(ji, je) = vertices(g); ji != je; ++ji)
319            if (!edge(*ii, *ji, g).second && edge(*ki, *ji, g).second) {
320              add_edge(*ii, *ji, g);
321            }
322  }
323
324
325  template < typename G > void warren_transitive_closure(G & g)
326  {
327    using namespace boost;
328    typedef typename graph_traits < G >::vertex_descriptor vertex;
329    typedef typename graph_traits < G >::vertex_iterator vertex_iterator;
330
331    function_requires < AdjacencyMatrixConcept < G > >();
332    function_requires < EdgeMutableGraphConcept < G > >();
333
334    // Make sure second loop will work
335    if (num_vertices(g) == 0)
336      return;
337
338    // for i = 2 to n
339    //    for k = 1 to i - 1
340    //      if A[i,k]
341    //        for j = 1 to n
342    //          A[i,j] = A[i,j] | A[k,j]
343
344    vertex_iterator ic, ie, jc, je, kc, ke;
345    for (tie(ic, ie) = vertices(g), ++ic; ic != ie; ++ic)
346      for (tie(kc, ke) = vertices(g); *kc != *ic; ++kc)
347        if (edge(*ic, *kc, g).second)
348          for (tie(jc, je) = vertices(g); jc != je; ++jc)
349            if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second) {
350              add_edge(*ic, *jc, g);
351            }
352    //  for i = 1 to n - 1
353    //    for k = i + 1 to n
354    //      if A[i,k]
355    //        for j = 1 to n
356    //          A[i,j] = A[i,j] | A[k,j]
357
358    for (tie(ic, ie) = vertices(g), --ie; ic != ie; ++ic)
359      for (kc = ic, ke = ie, ++kc; kc != ke; ++kc)
360        if (edge(*ic, *kc, g).second)
361          for (tie(jc, je) = vertices(g); jc != je; ++jc)
362            if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second) {
363              add_edge(*ic, *jc, g);
364            }
365  }
366
367
368}                               // namespace boost
369
370#endif // BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP
Note: See TracBrowser for help on using the repository browser.