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

Revision 857, 14.1 KB checked in by igarcia, 19 years ago (diff)
Line 
1//
2//=======================================================================
3// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5//
6// Distributed under the Boost Software License, Version 1.0. (See
7// accompanying file LICENSE_1_0.txt or copy at
8// http://www.boost.org/LICENSE_1_0.txt)
9//=======================================================================
10//
11#ifndef BOOST_GRAPH_UTILITY_HPP
12#define BOOST_GRAPH_UTILITY_HPP
13
14#include <stdlib.h>
15#include <iostream>
16#include <algorithm>
17#include <assert.h>
18#include <boost/config.hpp>
19#include <boost/tuple/tuple.hpp>
20#ifndef BOOST_NO_SLIST
21#  include <slist> // shouldn't have to include this... -JGS
22#endif
23#include <boost/graph/graph_traits.hpp>
24#include <boost/graph/properties.hpp>
25#include <boost/pending/container_traits.hpp>
26#include <boost/graph/depth_first_search.hpp>
27// iota moved to detail/algorithm.hpp
28#include <boost/detail/algorithm.hpp>
29
30namespace boost {
31
32  // Provide an undirected graph interface alternative to the
33  // the source() and target() edge functions.
34  template <class UndirectedGraph>
35  inline
36  std::pair<typename graph_traits<UndirectedGraph>::vertex_descriptor,
37            typename graph_traits<UndirectedGraph>::vertex_descriptor>
38  incident(typename graph_traits<UndirectedGraph>::edge_descriptor e,
39           UndirectedGraph& g)
40  {
41    return std::make_pair(source(e,g), target(e,g));
42  }
43
44  // Provide an undirected graph interface alternative
45  // to the out_edges() function.
46  template <class Graph>
47  inline
48  std::pair<typename graph_traits<Graph>::out_edge_iterator,
49            typename graph_traits<Graph>::out_edge_iterator>
50  incident_edges(typename graph_traits<Graph>::vertex_descriptor u,
51                 Graph& g)
52  {
53    return out_edges(u, g);
54  }
55
56  template <class Graph>
57  inline typename graph_traits<Graph>::vertex_descriptor
58  opposite(typename graph_traits<Graph>::edge_descriptor e,
59           typename graph_traits<Graph>::vertex_descriptor v,
60           const Graph& g)
61  {
62    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
63    if (v == source(e, g))
64      return target(e, g);
65    else if (v == target(e, g))
66      return source(e, g);
67    else
68      return vertex_descriptor();
69  }
70
71  //===========================================================================
72  // Some handy predicates
73
74  template <typename Vertex, typename Graph>
75  struct incident_from_predicate {
76    incident_from_predicate(Vertex u, const Graph& g)
77      : m_u(u), m_g(g) { }
78    template <class Edge>
79    bool operator()(const Edge& e) const {
80      return source(e, m_g) == m_u;
81    }
82    Vertex m_u;
83    const Graph& m_g;
84  };
85  template <typename Vertex, typename Graph>
86  inline incident_from_predicate<Vertex, Graph>
87  incident_from(Vertex u, const Graph& g) {
88    return incident_from_predicate<Vertex, Graph>(u, g);
89  }
90 
91  template <typename Vertex, typename Graph>
92  struct incident_to_predicate {
93    incident_to_predicate(Vertex u, const Graph& g)
94      : m_u(u), m_g(g) { }
95    template <class Edge>
96    bool operator()(const Edge& e) const {
97      return target(e, m_g) == m_u;
98    }
99    Vertex m_u;
100    const Graph& m_g;
101  };
102  template <typename Vertex, typename Graph>
103  inline incident_to_predicate<Vertex, Graph>
104  incident_to(Vertex u, const Graph& g) {
105    return incident_to_predicate<Vertex, Graph>(u, g);
106  }
107
108  template <typename Vertex, typename Graph>
109  struct incident_on_predicate {
110    incident_on_predicate(Vertex u, const Graph& g)
111      : m_u(u), m_g(g) { }
112    template <class Edge>
113    bool operator()(const Edge& e) const {
114      return source(e, m_g) == m_u || target(e, m_g) == m_u;
115    }
116    Vertex m_u;
117    const Graph& m_g;
118  };
119  template <typename Vertex, typename Graph>
120  inline incident_on_predicate<Vertex, Graph>
121  incident_on(Vertex u, const Graph& g) {
122    return incident_on_predicate<Vertex, Graph>(u, g);
123  }
124 
125  template <typename Vertex, typename Graph>
126  struct connects_predicate {
127    connects_predicate(Vertex u, Vertex v, const Graph& g)
128      : m_u(u), m_v(v), m_g(g) { }
129    template <class Edge>
130    bool operator()(const Edge& e) const {
131      if (is_directed(m_g))
132        return source(e, m_g) == m_u && target(e, m_g) == m_v;
133      else
134        return (source(e, m_g) == m_u && target(e, m_g) == m_v)
135          || (source(e, m_g) == m_v && target(e, m_g) == m_u);
136    }
137    Vertex m_u, m_v;
138    const Graph& m_g;
139  };
140  template <typename Vertex, typename Graph>
141  inline connects_predicate<Vertex, Graph>
142  connects(Vertex u, Vertex v, const Graph& g) {
143          return connects_predicate<Vertex, Graph>(u, v, g);
144  }
145
146
147  // Need to convert all of these printing functions to take an ostream object
148  // -JGS
149
150  template <class IncidenceGraph, class Name>
151  void print_in_edges(const IncidenceGraph& G, Name name)
152  {
153    typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
154    for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
155      std::cout << get(name,*ui) << " <-- ";
156      typename graph_traits<IncidenceGraph>
157        ::in_edge_iterator ei, ei_end;
158      for(tie(ei,ei_end) = in_edges(*ui,G); ei != ei_end; ++ei)
159        std::cout << get(name,source(*ei,G)) << " ";
160      std::cout << std::endl;
161    }
162  }
163
164  template <class IncidenceGraph, class Name>
165  void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag)
166  {
167    typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
168    for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
169      std::cout << get(name,*ui) << " --> ";
170      typename graph_traits<IncidenceGraph>
171        ::out_edge_iterator ei, ei_end;
172      for(tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)
173        std::cout << get(name,target(*ei,G)) << " ";
174      std::cout << std::endl;
175    }
176  }
177  template <class IncidenceGraph, class Name>
178  void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag)
179  {
180    typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
181    for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
182      std::cout << get(name,*ui) << " <--> ";
183      typename graph_traits<IncidenceGraph>
184        ::out_edge_iterator ei, ei_end;
185      for(tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)
186        std::cout << get(name,target(*ei,G)) << " ";
187      std::cout << std::endl;
188    }
189  }
190  template <class IncidenceGraph, class Name>
191  void print_graph(const IncidenceGraph& G, Name name)
192  {
193    typedef typename graph_traits<IncidenceGraph>
194      ::directed_category Cat;
195    print_graph_dispatch(G, name, Cat());
196  }
197  template <class IncidenceGraph>
198  void print_graph(const IncidenceGraph& G) {
199    print_graph(G, get(vertex_index, G));
200  }
201
202  template <class EdgeListGraph, class Name>
203  void print_edges(const EdgeListGraph& G, Name name)
204  {
205    typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;
206    for (tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
207      std::cout << "(" << get(name, source(*ei, G))
208                << "," << get(name, target(*ei, G)) << ") ";
209    std::cout << std::endl;
210  }
211
212  template <class EdgeListGraph, class VertexName, class EdgeName>
213  void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename)
214  {
215    typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;
216    for (tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
217      std::cout << get(ename, *ei) << "(" << get(vname, source(*ei, G))
218                << "," << get(vname, target(*ei, G)) << ") ";
219    std::cout << std::endl;
220  }
221
222  template <class VertexListGraph, class Name>
223  void print_vertices(const VertexListGraph& G, Name name)
224  {
225    typename graph_traits<VertexListGraph>::vertex_iterator vi,vi_end;
226    for (tie(vi,vi_end) = vertices(G); vi != vi_end; ++vi)
227      std::cout << get(name,*vi) << " ";
228    std::cout << std::endl;
229  }
230
231  template <class Graph, class Vertex>
232  bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag)
233  {
234    typedef typename graph_traits<Graph>::edge_descriptor
235      edge_descriptor;
236    typename graph_traits<Graph>::adjacency_iterator vi, viend,
237      adj_found;
238    tie(vi, viend) = adjacent_vertices(a, g);
239    adj_found = std::find(vi, viend, b);
240    if (adj_found == viend)
241      return false; 
242
243    typename graph_traits<Graph>::out_edge_iterator oi, oiend,
244      out_found;
245    tie(oi, oiend) = out_edges(a, g);
246    out_found = std::find_if(oi, oiend, incident_to(b, g));
247    if (out_found == oiend)
248      return false;
249
250    typename graph_traits<Graph>::in_edge_iterator ii, iiend,
251      in_found;
252    tie(ii, iiend) = in_edges(b, g);
253    in_found = std::find_if(ii, iiend, incident_from(a, g));
254    if (in_found == iiend)
255      return false;
256
257    return true;
258  }
259  template <class Graph, class Vertex>
260  bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag)
261  {
262    typedef typename graph_traits<Graph>::edge_descriptor
263      edge_descriptor;
264    typename graph_traits<Graph>::adjacency_iterator vi, viend, found;
265    tie(vi, viend) = adjacent_vertices(a, g);
266#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT)
267    // Getting internal compiler error with std::find()
268    found = viend;
269    for (; vi != viend; ++vi)
270      if (*vi == b) {
271        found = vi;
272        break;
273      }
274#else
275    found = std::find(vi, viend, b);
276#endif
277    if ( found == viend )
278      return false;
279
280    typename graph_traits<Graph>::out_edge_iterator oi, oiend,
281      out_found;
282    tie(oi, oiend) = out_edges(a, g);
283
284#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT)
285    // Getting internal compiler error with std::find()
286    out_found = oiend;
287    for (; oi != oiend; ++oi)
288      if (target(*oi, g) == b) {
289        out_found = oi;
290        break;
291      }
292#else
293    out_found = std::find_if(oi, oiend, incident_to(b, g));
294#endif
295    if (out_found == oiend)
296      return false;
297    return true;
298  }
299  template <class Graph, class Vertex>
300  bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag)
301  {
302    return is_adj_dispatch(g, a, b, directed_tag());
303  }
304
305  template <class Graph, class Vertex>
306  bool is_adjacent(Graph& g, Vertex a, Vertex b) {
307    typedef typename graph_traits<Graph>::directed_category Cat;
308    return is_adj_dispatch(g, a, b, Cat());
309  }
310
311  template <class Graph, class Edge>
312  bool in_edge_set(Graph& g, Edge e)
313  {
314    typename Graph::edge_iterator ei, ei_end, found;
315    tie(ei, ei_end) = edges(g);
316    found = std::find(ei, ei_end, e);
317    return found != ei_end;
318  }
319
320  template <class Graph, class Vertex>
321  bool in_vertex_set(Graph& g, Vertex v)
322  {
323    typename Graph::vertex_iterator vi, vi_end, found;
324    tie(vi, vi_end) = vertices(g);
325    found = std::find(vi, vi_end, v);
326    return found != vi_end;
327  }
328
329  template <class Graph, class Vertex>
330  bool in_edge_set(Graph& g, Vertex u, Vertex v)
331  {
332    typename Graph::edge_iterator ei, ei_end;
333    for (tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
334      if (source(*ei,g) == u && target(*ei,g) == v)
335        return true;
336    return false;
337  }
338
339  // is x a descendant of y?
340  template <typename ParentMap>
341  inline bool is_descendant
342  (typename property_traits<ParentMap>::value_type x,
343   typename property_traits<ParentMap>::value_type y,
344   ParentMap parent)
345  {
346    if (get(parent, x) == x) // x is the root of the tree
347      return false;
348    else if (get(parent, x) == y)
349      return true;
350    else
351      return is_descendant(get(parent, x), y, parent);
352  }
353
354  // is y reachable from x?
355  template <typename IncidenceGraph, typename VertexColorMap>
356  inline bool is_reachable
357    (typename graph_traits<IncidenceGraph>::vertex_descriptor x,
358     typename graph_traits<IncidenceGraph>::vertex_descriptor y,
359     const IncidenceGraph& g,
360     VertexColorMap color) // should start out white for every vertex
361  {
362    typedef typename property_traits<VertexColorMap>::value_type ColorValue;
363    dfs_visitor<> vis;
364    depth_first_visit(g, x, vis, color);
365    return get(color, y) != color_traits<ColorValue>::white();
366  }
367
368  // Is the undirected graph connected?
369  // Is the directed graph strongly connected?
370  template <typename VertexListGraph, typename VertexColorMap>
371  inline bool is_connected(const VertexListGraph& g, VertexColorMap color)
372  {
373    typedef typename property_traits<VertexColorMap>::value_type ColorValue;
374    typedef color_traits<ColorValue> Color;
375    typename graph_traits<VertexListGraph>::vertex_iterator
376      ui, ui_end, vi, vi_end, ci, ci_end;
377    for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
378      for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
379        if (*ui != *vi) {
380          for (tie(ci, ci_end) = vertices(g); ci != ci_end; ++ci)
381            put(color, *ci, Color::white());
382          if (! is_reachable(*ui, *vi, color))
383            return false;
384        }
385    return true;
386  }
387
388  template <typename Graph>
389  bool is_self_loop
390    (typename graph_traits<Graph>::edge_descriptor e,
391     const Graph& g)
392  {
393    return source(e, g) == target(e, g);
394  }
395
396
397  template <class T1, class T2>
398  std::pair<T1,T2>
399  make_list(const T1& t1, const T2& t2)
400    { return std::make_pair(t1, t2); }
401
402  template <class T1, class T2, class T3>
403  std::pair<T1,std::pair<T2,T3> >
404  make_list(const T1& t1, const T2& t2, const T3& t3)
405    { return std::make_pair(t1, std::make_pair(t2, t3)); }
406
407  template <class T1, class T2, class T3, class T4>
408  std::pair<T1,std::pair<T2,std::pair<T3,T4> > >
409  make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4)
410    { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, t4))); }
411
412  template <class T1, class T2, class T3, class T4, class T5>
413  std::pair<T1,std::pair<T2,std::pair<T3,std::pair<T4,T5> > > >
414  make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5)
415    { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5)))); }
416
417} /* namespace boost */
418
419#endif /* BOOST_GRAPH_UTILITY_HPP*/
Note: See TracBrowser for help on using the repository browser.