Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / graph_utility.hpp
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
30 namespace 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*/