Back to home page

EIC code displayed by LXR
 
 

    

Warning, file /include/boost/graph/graph_utility.hpp was not indexed or was modified since last indexation (in which case cross-reference links may be missing, inaccurate or erroneous).

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #ifndef BOOST_GRAPH_UTILITY_HPP
0012 #define BOOST_GRAPH_UTILITY_HPP
0013 
0014 #include <stdlib.h>
0015 #include <iostream>
0016 #include <algorithm>
0017 #include <assert.h>
0018 #include <boost/config.hpp>
0019 #include <boost/tuple/tuple.hpp>
0020 
0021 #include <boost/graph/graph_traits.hpp>
0022 #include <boost/graph/iteration_macros.hpp>
0023 #include <boost/graph/properties.hpp>
0024 #include <boost/pending/container_traits.hpp>
0025 #include <boost/graph/depth_first_search.hpp>
0026 // iota moved to detail/algorithm.hpp
0027 #include <boost/detail/algorithm.hpp>
0028 
0029 namespace boost
0030 {
0031 
0032 // Provide an undirected graph interface alternative to the
0033 // the source() and target() edge functions.
0034 template < class UndirectedGraph >
0035 inline std::pair< typename graph_traits< UndirectedGraph >::vertex_descriptor,
0036     typename graph_traits< UndirectedGraph >::vertex_descriptor >
0037 incident(typename graph_traits< UndirectedGraph >::edge_descriptor e,
0038     UndirectedGraph& g)
0039 {
0040     return std::make_pair(source(e, g), target(e, g));
0041 }
0042 
0043 // Provide an undirected graph interface alternative
0044 // to the out_edges() function.
0045 template < class Graph >
0046 inline std::pair< typename graph_traits< Graph >::out_edge_iterator,
0047     typename graph_traits< Graph >::out_edge_iterator >
0048 incident_edges(typename graph_traits< Graph >::vertex_descriptor u, Graph& g)
0049 {
0050     return out_edges(u, g);
0051 }
0052 
0053 template < class Graph >
0054 inline typename graph_traits< Graph >::vertex_descriptor opposite(
0055     typename graph_traits< Graph >::edge_descriptor e,
0056     typename graph_traits< Graph >::vertex_descriptor v, const Graph& g)
0057 {
0058     typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
0059     if (v == source(e, g))
0060         return target(e, g);
0061     else if (v == target(e, g))
0062         return source(e, g);
0063     else
0064         return vertex_descriptor();
0065 }
0066 
0067 //===========================================================================
0068 // Some handy predicates
0069 
0070 template < typename Vertex, typename Graph > struct incident_from_predicate
0071 {
0072     incident_from_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {}
0073     template < class Edge > bool operator()(const Edge& e) const
0074     {
0075         return source(e, m_g) == m_u;
0076     }
0077     Vertex m_u;
0078     const Graph& m_g;
0079 };
0080 template < typename Vertex, typename Graph >
0081 inline incident_from_predicate< Vertex, Graph > incident_from(
0082     Vertex u, const Graph& g)
0083 {
0084     return incident_from_predicate< Vertex, Graph >(u, g);
0085 }
0086 
0087 template < typename Vertex, typename Graph > struct incident_to_predicate
0088 {
0089     incident_to_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {}
0090     template < class Edge > bool operator()(const Edge& e) const
0091     {
0092         return target(e, m_g) == m_u;
0093     }
0094     Vertex m_u;
0095     const Graph& m_g;
0096 };
0097 template < typename Vertex, typename Graph >
0098 inline incident_to_predicate< Vertex, Graph > incident_to(
0099     Vertex u, const Graph& g)
0100 {
0101     return incident_to_predicate< Vertex, Graph >(u, g);
0102 }
0103 
0104 template < typename Vertex, typename Graph > struct incident_on_predicate
0105 {
0106     incident_on_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {}
0107     template < class Edge > bool operator()(const Edge& e) const
0108     {
0109         return source(e, m_g) == m_u || target(e, m_g) == m_u;
0110     }
0111     Vertex m_u;
0112     const Graph& m_g;
0113 };
0114 template < typename Vertex, typename Graph >
0115 inline incident_on_predicate< Vertex, Graph > incident_on(
0116     Vertex u, const Graph& g)
0117 {
0118     return incident_on_predicate< Vertex, Graph >(u, g);
0119 }
0120 
0121 template < typename Vertex, typename Graph > struct connects_predicate
0122 {
0123     connects_predicate(Vertex u, Vertex v, const Graph& g)
0124     : m_u(u), m_v(v), m_g(g)
0125     {
0126     }
0127     template < class Edge > bool operator()(const Edge& e) const
0128     {
0129         if (is_directed(m_g))
0130             return source(e, m_g) == m_u && target(e, m_g) == m_v;
0131         else
0132             return (source(e, m_g) == m_u && target(e, m_g) == m_v)
0133                 || (source(e, m_g) == m_v && target(e, m_g) == m_u);
0134     }
0135     Vertex m_u, m_v;
0136     const Graph& m_g;
0137 };
0138 template < typename Vertex, typename Graph >
0139 inline connects_predicate< Vertex, Graph > connects(
0140     Vertex u, Vertex v, const Graph& g)
0141 {
0142     return connects_predicate< Vertex, Graph >(u, v, g);
0143 }
0144 
0145 // Need to convert all of these printing functions to take an ostream object
0146 // -JGS
0147 
0148 template < class IncidenceGraph, class Name >
0149 void print_in_edges(
0150     const IncidenceGraph& G, Name name, std::ostream& os = std::cout)
0151 {
0152     typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end;
0153     for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
0154     {
0155         os << get(name, *ui) << " <-- ";
0156         typename graph_traits< IncidenceGraph >::in_edge_iterator ei, ei_end;
0157         for (boost::tie(ei, ei_end) = in_edges(*ui, G); ei != ei_end; ++ei)
0158             os << get(name, source(*ei, G)) << " ";
0159         os << '\n';
0160     }
0161 }
0162 
0163 template < class IncidenceGraph, class Name >
0164 void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag,
0165     std::ostream& os = std::cout)
0166 {
0167     typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end;
0168     for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
0169     {
0170         os << get(name, *ui) << " --> ";
0171         typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end;
0172         for (boost::tie(ei, ei_end) = out_edges(*ui, G); ei != ei_end; ++ei)
0173             os << get(name, target(*ei, G)) << " ";
0174         os << '\n';
0175     }
0176 }
0177 template < class IncidenceGraph, class Name >
0178 void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag,
0179     std::ostream& os = std::cout)
0180 {
0181     typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end;
0182     for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
0183     {
0184         os << get(name, *ui) << " <--> ";
0185         typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end;
0186         for (boost::tie(ei, ei_end) = out_edges(*ui, G); ei != ei_end; ++ei)
0187             os << get(name, target(*ei, G)) << " ";
0188         os << '\n';
0189     }
0190 }
0191 template < class IncidenceGraph, class Name >
0192 void print_graph(
0193     const IncidenceGraph& G, Name name, std::ostream& os = std::cout)
0194 {
0195     typedef typename graph_traits< IncidenceGraph >::directed_category Cat;
0196     print_graph_dispatch(G, name, Cat(), os);
0197 }
0198 template < class IncidenceGraph >
0199 void print_graph(const IncidenceGraph& G, std::ostream& os = std::cout)
0200 {
0201     print_graph(G, get(vertex_index, G), os);
0202 }
0203 
0204 template < class EdgeListGraph, class Name >
0205 void print_edges(
0206     const EdgeListGraph& G, Name name, std::ostream& os = std::cout)
0207 {
0208     typename graph_traits< EdgeListGraph >::edge_iterator ei, ei_end;
0209     for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
0210         os << "(" << get(name, source(*ei, G)) << ","
0211            << get(name, target(*ei, G)) << ") ";
0212     os << '\n';
0213 }
0214 
0215 template < class EdgeListGraph, class VertexName, class EdgeName >
0216 void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename,
0217     std::ostream& os = std::cout)
0218 {
0219     typename graph_traits< EdgeListGraph >::edge_iterator ei, ei_end;
0220     for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
0221         os << get(ename, *ei) << "(" << get(vname, source(*ei, G)) << ","
0222            << get(vname, target(*ei, G)) << ") ";
0223     os << '\n';
0224 }
0225 
0226 template < class VertexListGraph, class Name >
0227 void print_vertices(
0228     const VertexListGraph& G, Name name, std::ostream& os = std::cout)
0229 {
0230     typename graph_traits< VertexListGraph >::vertex_iterator vi, vi_end;
0231     for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
0232         os << get(name, *vi) << " ";
0233     os << '\n';
0234 }
0235 
0236 template < class Graph, class Vertex >
0237 bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag)
0238 {
0239     typename graph_traits< Graph >::adjacency_iterator vi, viend, adj_found;
0240     boost::tie(vi, viend) = adjacent_vertices(a, g);
0241     adj_found = std::find(vi, viend, b);
0242     if (adj_found == viend)
0243         return false;
0244 
0245     typename graph_traits< Graph >::out_edge_iterator oi, oiend, out_found;
0246     boost::tie(oi, oiend) = out_edges(a, g);
0247     out_found = std::find_if(oi, oiend, incident_to(b, g));
0248     if (out_found == oiend)
0249         return false;
0250 
0251     typename graph_traits< Graph >::in_edge_iterator ii, iiend, in_found;
0252     boost::tie(ii, iiend) = in_edges(b, g);
0253     in_found = std::find_if(ii, iiend, incident_from(a, g));
0254     if (in_found == iiend)
0255         return false;
0256 
0257     return true;
0258 }
0259 template < class Graph, class Vertex >
0260 bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag)
0261 {
0262     typename graph_traits< Graph >::adjacency_iterator vi, viend, found;
0263     boost::tie(vi, viend) = adjacent_vertices(a, g);
0264     found = std::find(vi, viend, b);
0265     if (found == viend)
0266         return false;
0267 
0268     typename graph_traits< Graph >::out_edge_iterator oi, oiend, out_found;
0269     boost::tie(oi, oiend) = out_edges(a, g);
0270 
0271     out_found = std::find_if(oi, oiend, incident_to(b, g));
0272     if (out_found == oiend)
0273         return false;
0274     return true;
0275 }
0276 template < class Graph, class Vertex >
0277 bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag)
0278 {
0279     return is_adj_dispatch(g, a, b, directed_tag());
0280 }
0281 
0282 template < class Graph, class Vertex >
0283 bool is_adjacent(Graph& g, Vertex a, Vertex b)
0284 {
0285     typedef typename graph_traits< Graph >::directed_category Cat;
0286     return is_adj_dispatch(g, a, b, Cat());
0287 }
0288 
0289 template < class Graph, class Edge > bool in_edge_set(Graph& g, Edge e)
0290 {
0291     typename Graph::edge_iterator ei, ei_end, found;
0292     boost::tie(ei, ei_end) = edges(g);
0293     found = std::find(ei, ei_end, e);
0294     return found != ei_end;
0295 }
0296 
0297 template < class Graph, class Vertex > bool in_vertex_set(Graph& g, Vertex v)
0298 {
0299     typename Graph::vertex_iterator vi, vi_end, found;
0300     boost::tie(vi, vi_end) = vertices(g);
0301     found = std::find(vi, vi_end, v);
0302     return found != vi_end;
0303 }
0304 
0305 template < class Graph, class Vertex >
0306 bool in_edge_set(Graph& g, Vertex u, Vertex v)
0307 {
0308     typename Graph::edge_iterator ei, ei_end;
0309     for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
0310         if (source(*ei, g) == u && target(*ei, g) == v)
0311             return true;
0312     return false;
0313 }
0314 
0315 // is x a descendant of y?
0316 template < typename ParentMap >
0317 inline bool is_descendant(typename property_traits< ParentMap >::value_type x,
0318     typename property_traits< ParentMap >::value_type y, ParentMap parent)
0319 {
0320     if (get(parent, x) == x) // x is the root of the tree
0321         return false;
0322     else if (get(parent, x) == y)
0323         return true;
0324     else
0325         return is_descendant(get(parent, x), y, parent);
0326 }
0327 
0328 // is y reachable from x?
0329 template < typename IncidenceGraph, typename VertexColorMap >
0330 inline bool is_reachable(
0331     typename graph_traits< IncidenceGraph >::vertex_descriptor x,
0332     typename graph_traits< IncidenceGraph >::vertex_descriptor y,
0333     const IncidenceGraph& g,
0334     VertexColorMap color) // should start out white for every vertex
0335 {
0336     typedef typename property_traits< VertexColorMap >::value_type ColorValue;
0337     dfs_visitor<> vis;
0338     depth_first_visit(g, x, vis, color);
0339     return get(color, y) != color_traits< ColorValue >::white();
0340 }
0341 
0342 // Is the undirected graph connected?
0343 // Is the directed graph strongly connected?
0344 template < typename VertexListGraph, typename VertexColorMap >
0345 inline bool is_connected(const VertexListGraph& g, VertexColorMap color)
0346 {
0347     typedef typename property_traits< VertexColorMap >::value_type ColorValue;
0348     typedef color_traits< ColorValue > Color;
0349     typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end, vi,
0350         vi_end, ci, ci_end;
0351     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0352         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0353             if (*ui != *vi)
0354             {
0355                 for (boost::tie(ci, ci_end) = vertices(g); ci != ci_end; ++ci)
0356                     put(color, *ci, Color::white());
0357                 if (!is_reachable(*ui, *vi, g, color))
0358                     return false;
0359             }
0360     return true;
0361 }
0362 
0363 template < typename Graph >
0364 bool is_self_loop(
0365     typename graph_traits< Graph >::edge_descriptor e, const Graph& g)
0366 {
0367     return source(e, g) == target(e, g);
0368 }
0369 
0370 template < class T1, class T2 >
0371 std::pair< T1, T2 > make_list(const T1& t1, const T2& t2)
0372 {
0373     return std::make_pair(t1, t2);
0374 }
0375 
0376 template < class T1, class T2, class T3 >
0377 std::pair< T1, std::pair< T2, T3 > > make_list(
0378     const T1& t1, const T2& t2, const T3& t3)
0379 {
0380     return std::make_pair(t1, std::make_pair(t2, t3));
0381 }
0382 
0383 template < class T1, class T2, class T3, class T4 >
0384 std::pair< T1, std::pair< T2, std::pair< T3, T4 > > > make_list(
0385     const T1& t1, const T2& t2, const T3& t3, const T4& t4)
0386 {
0387     return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, t4)));
0388 }
0389 
0390 template < class T1, class T2, class T3, class T4, class T5 >
0391 std::pair< T1, std::pair< T2, std::pair< T3, std::pair< T4, T5 > > > >
0392 make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5)
0393 {
0394     return std::make_pair(
0395         t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5))));
0396 }
0397 
0398 namespace graph
0399 {
0400 
0401     // Functor for remove_parallel_edges: edge property of the removed edge is
0402     // added to the remaining
0403     template < typename EdgeProperty > struct add_removed_edge_property
0404     {
0405         add_removed_edge_property(EdgeProperty ep) : ep(ep) {}
0406 
0407         template < typename Edge > void operator()(Edge stay, Edge away)
0408         {
0409             put(ep, stay, get(ep, stay) + get(ep, away));
0410         }
0411         EdgeProperty ep;
0412     };
0413 
0414     // Same as above: edge property is capacity here
0415     template < typename Graph >
0416     struct add_removed_edge_capacity
0417     : add_removed_edge_property<
0418           typename property_map< Graph, edge_capacity_t >::type >
0419     {
0420         typedef add_removed_edge_property<
0421             typename property_map< Graph, edge_capacity_t >::type >
0422             base;
0423         add_removed_edge_capacity(Graph& g) : base(get(edge_capacity, g)) {}
0424     };
0425 
0426     template < typename Graph > bool has_no_vertices(const Graph& g)
0427     {
0428         typedef typename boost::graph_traits< Graph >::vertex_iterator vi;
0429         std::pair< vi, vi > p = vertices(g);
0430         return (p.first == p.second);
0431     }
0432 
0433     template < typename Graph > bool has_no_edges(const Graph& g)
0434     {
0435         typedef typename boost::graph_traits< Graph >::edge_iterator ei;
0436         std::pair< ei, ei > p = edges(g);
0437         return (p.first == p.second);
0438     }
0439 
0440     template < typename Graph >
0441     bool has_no_out_edges(
0442         const typename boost::graph_traits< Graph >::vertex_descriptor& v,
0443         const Graph& g)
0444     {
0445         typedef typename boost::graph_traits< Graph >::out_edge_iterator ei;
0446         std::pair< ei, ei > p = out_edges(v, g);
0447         return (p.first == p.second);
0448     }
0449 
0450 } // namespace graph
0451 
0452 template < class PropertyIn, class PropertyOut, class Graph >
0453 void copy_vertex_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
0454 {
0455     BGL_FORALL_VERTICES_T(u, g, Graph)
0456     put(p_out, u, get(p_in, g));
0457 }
0458 
0459 template < class PropertyIn, class PropertyOut, class Graph >
0460 void copy_edge_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
0461 {
0462     BGL_FORALL_EDGES_T(e, g, Graph)
0463     put(p_out, e, get(p_in, g));
0464 }
0465 
0466 // Return true if property_map1 and property_map2 differ
0467 // for any of the vertices in graph.
0468 template < typename PropertyMapFirst, typename PropertyMapSecond,
0469     typename Graph >
0470 bool are_property_maps_different(const PropertyMapFirst property_map1,
0471     const PropertyMapSecond property_map2, const Graph& graph)
0472 {
0473 
0474     BGL_FORALL_VERTICES_T(vertex, graph, Graph)
0475     {
0476         if (get(property_map1, vertex) != get(property_map2, vertex))
0477         {
0478 
0479             return (true);
0480         }
0481     }
0482 
0483     return (false);
0484 }
0485 
0486 } /* namespace boost */
0487 
0488 #endif /* BOOST_GRAPH_UTILITY_HPP*/
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!