// iota moved to detail/algorithm.hpp
#include <boost/detail/algorithm.hpp>
-namespace boost {
-
- // Provide an undirected graph interface alternative to the
- // the source() and target() edge functions.
- template <class UndirectedGraph>
- inline
- std::pair<typename graph_traits<UndirectedGraph>::vertex_descriptor,
- typename graph_traits<UndirectedGraph>::vertex_descriptor>
- incident(typename graph_traits<UndirectedGraph>::edge_descriptor e,
- UndirectedGraph& g)
- {
- return std::make_pair(source(e,g), target(e,g));
- }
-
- // Provide an undirected graph interface alternative
- // to the out_edges() function.
- template <class Graph>
- inline
- std::pair<typename graph_traits<Graph>::out_edge_iterator,
- typename graph_traits<Graph>::out_edge_iterator>
- incident_edges(typename graph_traits<Graph>::vertex_descriptor u,
- Graph& g)
- {
+namespace boost
+{
+
+// Provide an undirected graph interface alternative to the
+// the source() and target() edge functions.
+template < class UndirectedGraph >
+inline std::pair< typename graph_traits< UndirectedGraph >::vertex_descriptor,
+ typename graph_traits< UndirectedGraph >::vertex_descriptor >
+incident(typename graph_traits< UndirectedGraph >::edge_descriptor e,
+ UndirectedGraph& g)
+{
+ return std::make_pair(source(e, g), target(e, g));
+}
+
+// Provide an undirected graph interface alternative
+// to the out_edges() function.
+template < class Graph >
+inline std::pair< typename graph_traits< Graph >::out_edge_iterator,
+ typename graph_traits< Graph >::out_edge_iterator >
+incident_edges(typename graph_traits< Graph >::vertex_descriptor u, Graph& g)
+{
return out_edges(u, g);
- }
-
- template <class Graph>
- inline typename graph_traits<Graph>::vertex_descriptor
- opposite(typename graph_traits<Graph>::edge_descriptor e,
- typename graph_traits<Graph>::vertex_descriptor v,
- const Graph& g)
- {
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+}
+
+template < class Graph >
+inline typename graph_traits< Graph >::vertex_descriptor opposite(
+ typename graph_traits< Graph >::edge_descriptor e,
+ typename graph_traits< Graph >::vertex_descriptor v, const Graph& g)
+{
+ typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
if (v == source(e, g))
- return target(e, g);
+ return target(e, g);
else if (v == target(e, g))
- return source(e, g);
+ return source(e, g);
else
- return vertex_descriptor();
- }
-
- //===========================================================================
- // Some handy predicates
-
- template <typename Vertex, typename Graph>
- struct incident_from_predicate {
- incident_from_predicate(Vertex u, const Graph& g)
- : m_u(u), m_g(g) { }
- template <class Edge>
- bool operator()(const Edge& e) const {
- return source(e, m_g) == m_u;
+ return vertex_descriptor();
+}
+
+//===========================================================================
+// Some handy predicates
+
+template < typename Vertex, typename Graph > struct incident_from_predicate
+{
+ incident_from_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {}
+ template < class Edge > bool operator()(const Edge& e) const
+ {
+ return source(e, m_g) == m_u;
}
Vertex m_u;
const Graph& m_g;
- };
- template <typename Vertex, typename Graph>
- inline incident_from_predicate<Vertex, Graph>
- incident_from(Vertex u, const Graph& g) {
- return incident_from_predicate<Vertex, Graph>(u, g);
- }
-
- template <typename Vertex, typename Graph>
- struct incident_to_predicate {
- incident_to_predicate(Vertex u, const Graph& g)
- : m_u(u), m_g(g) { }
- template <class Edge>
- bool operator()(const Edge& e) const {
- return target(e, m_g) == m_u;
+};
+template < typename Vertex, typename Graph >
+inline incident_from_predicate< Vertex, Graph > incident_from(
+ Vertex u, const Graph& g)
+{
+ return incident_from_predicate< Vertex, Graph >(u, g);
+}
+
+template < typename Vertex, typename Graph > struct incident_to_predicate
+{
+ incident_to_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {}
+ template < class Edge > bool operator()(const Edge& e) const
+ {
+ return target(e, m_g) == m_u;
}
Vertex m_u;
const Graph& m_g;
- };
- template <typename Vertex, typename Graph>
- inline incident_to_predicate<Vertex, Graph>
- incident_to(Vertex u, const Graph& g) {
- return incident_to_predicate<Vertex, Graph>(u, g);
- }
-
- template <typename Vertex, typename Graph>
- struct incident_on_predicate {
- incident_on_predicate(Vertex u, const Graph& g)
- : m_u(u), m_g(g) { }
- template <class Edge>
- bool operator()(const Edge& e) const {
- return source(e, m_g) == m_u || target(e, m_g) == m_u;
+};
+template < typename Vertex, typename Graph >
+inline incident_to_predicate< Vertex, Graph > incident_to(
+ Vertex u, const Graph& g)
+{
+ return incident_to_predicate< Vertex, Graph >(u, g);
+}
+
+template < typename Vertex, typename Graph > struct incident_on_predicate
+{
+ incident_on_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {}
+ template < class Edge > bool operator()(const Edge& e) const
+ {
+ return source(e, m_g) == m_u || target(e, m_g) == m_u;
}
Vertex m_u;
const Graph& m_g;
- };
- template <typename Vertex, typename Graph>
- inline incident_on_predicate<Vertex, Graph>
- incident_on(Vertex u, const Graph& g) {
- return incident_on_predicate<Vertex, Graph>(u, g);
- }
-
- template <typename Vertex, typename Graph>
- struct connects_predicate {
+};
+template < typename Vertex, typename Graph >
+inline incident_on_predicate< Vertex, Graph > incident_on(
+ Vertex u, const Graph& g)
+{
+ return incident_on_predicate< Vertex, Graph >(u, g);
+}
+
+template < typename Vertex, typename Graph > struct connects_predicate
+{
connects_predicate(Vertex u, Vertex v, const Graph& g)
- : m_u(u), m_v(v), m_g(g) { }
- template <class Edge>
- bool operator()(const Edge& e) const {
- if (is_directed(m_g))
- return source(e, m_g) == m_u && target(e, m_g) == m_v;
- else
- return (source(e, m_g) == m_u && target(e, m_g) == m_v)
- || (source(e, m_g) == m_v && target(e, m_g) == m_u);
+ : m_u(u), m_v(v), m_g(g)
+ {
+ }
+ template < class Edge > bool operator()(const Edge& e) const
+ {
+ if (is_directed(m_g))
+ return source(e, m_g) == m_u && target(e, m_g) == m_v;
+ else
+ return (source(e, m_g) == m_u && target(e, m_g) == m_v)
+ || (source(e, m_g) == m_v && target(e, m_g) == m_u);
}
Vertex m_u, m_v;
const Graph& m_g;
- };
- template <typename Vertex, typename Graph>
- inline connects_predicate<Vertex, Graph>
- connects(Vertex u, Vertex v, const Graph& g) {
- return connects_predicate<Vertex, Graph>(u, v, g);
- }
-
-
- // Need to convert all of these printing functions to take an ostream object
- // -JGS
-
- template <class IncidenceGraph, class Name>
- void print_in_edges(const IncidenceGraph& G, Name name, std::ostream& os = std::cout)
- {
- typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
- for (boost::tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
- os << get(name,*ui) << " <-- ";
- typename graph_traits<IncidenceGraph>
- ::in_edge_iterator ei, ei_end;
- for(boost::tie(ei,ei_end) = in_edges(*ui,G); ei != ei_end; ++ei)
- os << get(name,source(*ei,G)) << " ";
- os << '\n';
+};
+template < typename Vertex, typename Graph >
+inline connects_predicate< Vertex, Graph > connects(
+ Vertex u, Vertex v, const Graph& g)
+{
+ return connects_predicate< Vertex, Graph >(u, v, g);
+}
+
+// Need to convert all of these printing functions to take an ostream object
+// -JGS
+
+template < class IncidenceGraph, class Name >
+void print_in_edges(
+ const IncidenceGraph& G, Name name, std::ostream& os = std::cout)
+{
+ typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end;
+ for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
+ {
+ os << get(name, *ui) << " <-- ";
+ typename graph_traits< IncidenceGraph >::in_edge_iterator ei, ei_end;
+ for (boost::tie(ei, ei_end) = in_edges(*ui, G); ei != ei_end; ++ei)
+ os << get(name, source(*ei, G)) << " ";
+ os << '\n';
}
- }
-
- template <class IncidenceGraph, class Name>
- void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag, std::ostream& os = std::cout)
- {
- typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
- for (boost::tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
- os << get(name,*ui) << " --> ";
- typename graph_traits<IncidenceGraph>
- ::out_edge_iterator ei, ei_end;
- for(boost::tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)
- os << get(name,target(*ei,G)) << " ";
- os << '\n';
+}
+
+template < class IncidenceGraph, class Name >
+void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag,
+ std::ostream& os = std::cout)
+{
+ typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end;
+ for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
+ {
+ os << get(name, *ui) << " --> ";
+ typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end;
+ for (boost::tie(ei, ei_end) = out_edges(*ui, G); ei != ei_end; ++ei)
+ os << get(name, target(*ei, G)) << " ";
+ os << '\n';
}
- }
- template <class IncidenceGraph, class Name>
- void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag, std::ostream& os = std::cout)
- {
- typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
- for (boost::tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
- os << get(name,*ui) << " <--> ";
- typename graph_traits<IncidenceGraph>
- ::out_edge_iterator ei, ei_end;
- for(boost::tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)
- os << get(name,target(*ei,G)) << " ";
- os << '\n';
+}
+template < class IncidenceGraph, class Name >
+void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag,
+ std::ostream& os = std::cout)
+{
+ typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end;
+ for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
+ {
+ os << get(name, *ui) << " <--> ";
+ typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end;
+ for (boost::tie(ei, ei_end) = out_edges(*ui, G); ei != ei_end; ++ei)
+ os << get(name, target(*ei, G)) << " ";
+ os << '\n';
}
- }
- template <class IncidenceGraph, class Name>
- void print_graph(const IncidenceGraph& G, Name name, std::ostream& os = std::cout)
- {
- typedef typename graph_traits<IncidenceGraph>
- ::directed_category Cat;
+}
+template < class IncidenceGraph, class Name >
+void print_graph(
+ const IncidenceGraph& G, Name name, std::ostream& os = std::cout)
+{
+ typedef typename graph_traits< IncidenceGraph >::directed_category Cat;
print_graph_dispatch(G, name, Cat(), os);
- }
- template <class IncidenceGraph>
- void print_graph(const IncidenceGraph& G, std::ostream& os = std::cout) {
+}
+template < class IncidenceGraph >
+void print_graph(const IncidenceGraph& G, std::ostream& os = std::cout)
+{
print_graph(G, get(vertex_index, G), os);
- }
+}
- template <class EdgeListGraph, class Name>
- void print_edges(const EdgeListGraph& G, Name name, std::ostream& os = std::cout)
- {
- typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;
+template < class EdgeListGraph, class Name >
+void print_edges(
+ const EdgeListGraph& G, Name name, std::ostream& os = std::cout)
+{
+ typename graph_traits< EdgeListGraph >::edge_iterator ei, ei_end;
for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
- os << "(" << get(name, source(*ei, G))
- << "," << get(name, target(*ei, G)) << ") ";
+ os << "(" << get(name, source(*ei, G)) << ","
+ << get(name, target(*ei, G)) << ") ";
os << '\n';
- }
+}
- template <class EdgeListGraph, class VertexName, class EdgeName>
- void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename, std::ostream& os = std::cout)
- {
- typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;
+template < class EdgeListGraph, class VertexName, class EdgeName >
+void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename,
+ std::ostream& os = std::cout)
+{
+ typename graph_traits< EdgeListGraph >::edge_iterator ei, ei_end;
for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
- os << get(ename, *ei) << "(" << get(vname, source(*ei, G))
- << "," << get(vname, target(*ei, G)) << ") ";
+ os << get(ename, *ei) << "(" << get(vname, source(*ei, G)) << ","
+ << get(vname, target(*ei, G)) << ") ";
os << '\n';
- }
-
- template <class VertexListGraph, class Name>
- void print_vertices(const VertexListGraph& G, Name name, std::ostream& os = std::cout)
- {
- typename graph_traits<VertexListGraph>::vertex_iterator vi,vi_end;
- for (boost::tie(vi,vi_end) = vertices(G); vi != vi_end; ++vi)
- os << get(name,*vi) << " ";
+}
+
+template < class VertexListGraph, class Name >
+void print_vertices(
+ const VertexListGraph& G, Name name, std::ostream& os = std::cout)
+{
+ typename graph_traits< VertexListGraph >::vertex_iterator vi, vi_end;
+ for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
+ os << get(name, *vi) << " ";
os << '\n';
- }
+}
- template <class Graph, class Vertex>
- bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag)
- {
- typename graph_traits<Graph>::adjacency_iterator vi, viend,
- adj_found;
+template < class Graph, class Vertex >
+bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag)
+{
+ typename graph_traits< Graph >::adjacency_iterator vi, viend, adj_found;
boost::tie(vi, viend) = adjacent_vertices(a, g);
adj_found = std::find(vi, viend, b);
if (adj_found == viend)
- return false;
+ return false;
- typename graph_traits<Graph>::out_edge_iterator oi, oiend,
- out_found;
+ typename graph_traits< Graph >::out_edge_iterator oi, oiend, out_found;
boost::tie(oi, oiend) = out_edges(a, g);
out_found = std::find_if(oi, oiend, incident_to(b, g));
if (out_found == oiend)
- return false;
+ return false;
- typename graph_traits<Graph>::in_edge_iterator ii, iiend,
- in_found;
+ typename graph_traits< Graph >::in_edge_iterator ii, iiend, in_found;
boost::tie(ii, iiend) = in_edges(b, g);
in_found = std::find_if(ii, iiend, incident_from(a, g));
if (in_found == iiend)
- return false;
+ return false;
return true;
- }
- template <class Graph, class Vertex>
- bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag)
- {
- typename graph_traits<Graph>::adjacency_iterator vi, viend, found;
+}
+template < class Graph, class Vertex >
+bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag)
+{
+ typename graph_traits< Graph >::adjacency_iterator vi, viend, found;
boost::tie(vi, viend) = adjacent_vertices(a, g);
found = std::find(vi, viend, b);
- if ( found == viend )
- return false;
+ if (found == viend)
+ return false;
- typename graph_traits<Graph>::out_edge_iterator oi, oiend,
- out_found;
+ typename graph_traits< Graph >::out_edge_iterator oi, oiend, out_found;
boost::tie(oi, oiend) = out_edges(a, g);
out_found = std::find_if(oi, oiend, incident_to(b, g));
if (out_found == oiend)
- return false;
+ return false;
return true;
- }
- template <class Graph, class Vertex>
- bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag)
- {
+}
+template < class Graph, class Vertex >
+bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag)
+{
return is_adj_dispatch(g, a, b, directed_tag());
- }
+}
- template <class Graph, class Vertex>
- bool is_adjacent(Graph& g, Vertex a, Vertex b) {
- typedef typename graph_traits<Graph>::directed_category Cat;
+template < class Graph, class Vertex >
+bool is_adjacent(Graph& g, Vertex a, Vertex b)
+{
+ typedef typename graph_traits< Graph >::directed_category Cat;
return is_adj_dispatch(g, a, b, Cat());
- }
+}
- template <class Graph, class Edge>
- bool in_edge_set(Graph& g, Edge e)
- {
+template < class Graph, class Edge > bool in_edge_set(Graph& g, Edge e)
+{
typename Graph::edge_iterator ei, ei_end, found;
boost::tie(ei, ei_end) = edges(g);
found = std::find(ei, ei_end, e);
return found != ei_end;
- }
+}
- template <class Graph, class Vertex>
- bool in_vertex_set(Graph& g, Vertex v)
- {
+template < class Graph, class Vertex > bool in_vertex_set(Graph& g, Vertex v)
+{
typename Graph::vertex_iterator vi, vi_end, found;
boost::tie(vi, vi_end) = vertices(g);
found = std::find(vi, vi_end, v);
return found != vi_end;
- }
+}
- template <class Graph, class Vertex>
- bool in_edge_set(Graph& g, Vertex u, Vertex v)
- {
+template < class Graph, class Vertex >
+bool in_edge_set(Graph& g, Vertex u, Vertex v)
+{
typename Graph::edge_iterator ei, ei_end;
- for (boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
- if (source(*ei,g) == u && target(*ei,g) == v)
- return true;
+ for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
+ if (source(*ei, g) == u && target(*ei, g) == v)
+ return true;
return false;
- }
-
- // is x a descendant of y?
- template <typename ParentMap>
- inline bool is_descendant
- (typename property_traits<ParentMap>::value_type x,
- typename property_traits<ParentMap>::value_type y,
- ParentMap parent)
- {
+}
+
+// is x a descendant of y?
+template < typename ParentMap >
+inline bool is_descendant(typename property_traits< ParentMap >::value_type x,
+ typename property_traits< ParentMap >::value_type y, ParentMap parent)
+{
if (get(parent, x) == x) // x is the root of the tree
- return false;
+ return false;
else if (get(parent, x) == y)
- return true;
+ return true;
else
- return is_descendant(get(parent, x), y, parent);
- }
-
- // is y reachable from x?
- template <typename IncidenceGraph, typename VertexColorMap>
- inline bool is_reachable
- (typename graph_traits<IncidenceGraph>::vertex_descriptor x,
- typename graph_traits<IncidenceGraph>::vertex_descriptor y,
- const IncidenceGraph& g,
- VertexColorMap color) // should start out white for every vertex
- {
- typedef typename property_traits<VertexColorMap>::value_type ColorValue;
+ return is_descendant(get(parent, x), y, parent);
+}
+
+// is y reachable from x?
+template < typename IncidenceGraph, typename VertexColorMap >
+inline bool is_reachable(
+ typename graph_traits< IncidenceGraph >::vertex_descriptor x,
+ typename graph_traits< IncidenceGraph >::vertex_descriptor y,
+ const IncidenceGraph& g,
+ VertexColorMap color) // should start out white for every vertex
+{
+ typedef typename property_traits< VertexColorMap >::value_type ColorValue;
dfs_visitor<> vis;
depth_first_visit(g, x, vis, color);
- return get(color, y) != color_traits<ColorValue>::white();
- }
-
- // Is the undirected graph connected?
- // Is the directed graph strongly connected?
- template <typename VertexListGraph, typename VertexColorMap>
- inline bool is_connected(const VertexListGraph& g, VertexColorMap color)
- {
- typedef typename property_traits<VertexColorMap>::value_type ColorValue;
- typedef color_traits<ColorValue> Color;
- typename graph_traits<VertexListGraph>::vertex_iterator
- ui, ui_end, vi, vi_end, ci, ci_end;
+ return get(color, y) != color_traits< ColorValue >::white();
+}
+
+// Is the undirected graph connected?
+// Is the directed graph strongly connected?
+template < typename VertexListGraph, typename VertexColorMap >
+inline bool is_connected(const VertexListGraph& g, VertexColorMap color)
+{
+ typedef typename property_traits< VertexColorMap >::value_type ColorValue;
+ typedef color_traits< ColorValue > Color;
+ typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end, vi,
+ vi_end, ci, ci_end;
for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
- if (*ui != *vi) {
- for (boost::tie(ci, ci_end) = vertices(g); ci != ci_end; ++ci)
- put(color, *ci, Color::white());
- if (! is_reachable(*ui, *vi, g, color))
- return false;
- }
+ for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
+ if (*ui != *vi)
+ {
+ for (boost::tie(ci, ci_end) = vertices(g); ci != ci_end; ++ci)
+ put(color, *ci, Color::white());
+ if (!is_reachable(*ui, *vi, g, color))
+ return false;
+ }
return true;
- }
+}
- template <typename Graph>
- bool is_self_loop
- (typename graph_traits<Graph>::edge_descriptor e,
- const Graph& g)
- {
+template < typename Graph >
+bool is_self_loop(
+ typename graph_traits< Graph >::edge_descriptor e, const Graph& g)
+{
return source(e, g) == target(e, g);
- }
-
-
- template <class T1, class T2>
- std::pair<T1,T2>
- make_list(const T1& t1, const T2& t2)
- { return std::make_pair(t1, t2); }
-
- template <class T1, class T2, class T3>
- std::pair<T1,std::pair<T2,T3> >
- make_list(const T1& t1, const T2& t2, const T3& t3)
- { return std::make_pair(t1, std::make_pair(t2, t3)); }
-
- template <class T1, class T2, class T3, class T4>
- std::pair<T1,std::pair<T2,std::pair<T3,T4> > >
- make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4)
- { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, t4))); }
-
- template <class T1, class T2, class T3, class T4, class T5>
- std::pair<T1,std::pair<T2,std::pair<T3,std::pair<T4,T5> > > >
- make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5)
- { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5)))); }
-
- namespace graph {
-
- // Functor for remove_parallel_edges: edge property of the removed edge is added to the remaining
- template <typename EdgeProperty>
- struct add_removed_edge_property
+}
+
+template < class T1, class T2 >
+std::pair< T1, T2 > make_list(const T1& t1, const T2& t2)
+{
+ return std::make_pair(t1, t2);
+}
+
+template < class T1, class T2, class T3 >
+std::pair< T1, std::pair< T2, T3 > > make_list(
+ const T1& t1, const T2& t2, const T3& t3)
+{
+ return std::make_pair(t1, std::make_pair(t2, t3));
+}
+
+template < class T1, class T2, class T3, class T4 >
+std::pair< T1, std::pair< T2, std::pair< T3, T4 > > > make_list(
+ const T1& t1, const T2& t2, const T3& t3, const T4& t4)
+{
+ return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, t4)));
+}
+
+template < class T1, class T2, class T3, class T4, class T5 >
+std::pair< T1, std::pair< T2, std::pair< T3, std::pair< T4, T5 > > > >
+make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5)
+{
+ return std::make_pair(
+ t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5))));
+}
+
+namespace graph
+{
+
+ // Functor for remove_parallel_edges: edge property of the removed edge is
+ // added to the remaining
+ template < typename EdgeProperty > struct add_removed_edge_property
{
- add_removed_edge_property(EdgeProperty ep) : ep(ep) {}
-
- template <typename Edge>
- void operator() (Edge stay, Edge away)
- {
- put(ep, stay, get(ep, stay) + get(ep, away));
- }
- EdgeProperty ep;
+ add_removed_edge_property(EdgeProperty ep) : ep(ep) {}
+
+ template < typename Edge > void operator()(Edge stay, Edge away)
+ {
+ put(ep, stay, get(ep, stay) + get(ep, away));
+ }
+ EdgeProperty ep;
};
// Same as above: edge property is capacity here
- template <typename Graph>
+ template < typename Graph >
struct add_removed_edge_capacity
- : add_removed_edge_property<typename property_map<Graph, edge_capacity_t>::type>
+ : add_removed_edge_property<
+ typename property_map< Graph, edge_capacity_t >::type >
+ {
+ typedef add_removed_edge_property<
+ typename property_map< Graph, edge_capacity_t >::type >
+ base;
+ add_removed_edge_capacity(Graph& g) : base(get(edge_capacity, g)) {}
+ };
+
+ template < typename Graph > bool has_no_vertices(const Graph& g)
{
- typedef add_removed_edge_property<typename property_map<Graph, edge_capacity_t>::type> base;
- add_removed_edge_capacity(Graph& g) : base(get(edge_capacity, g)) {}
- };
-
- template <typename Graph>
- bool has_no_vertices(const Graph& g) {
- typedef typename boost::graph_traits<Graph>::vertex_iterator vi;
- std::pair<vi, vi> p = vertices(g);
- return (p.first == p.second);
+ typedef typename boost::graph_traits< Graph >::vertex_iterator vi;
+ std::pair< vi, vi > p = vertices(g);
+ return (p.first == p.second);
}
- template <typename Graph>
- bool has_no_edges(const Graph& g) {
- typedef typename boost::graph_traits<Graph>::edge_iterator ei;
- std::pair<ei, ei> p = edges(g);
- return (p.first == p.second);
+ template < typename Graph > bool has_no_edges(const Graph& g)
+ {
+ typedef typename boost::graph_traits< Graph >::edge_iterator ei;
+ std::pair< ei, ei > p = edges(g);
+ return (p.first == p.second);
}
- template <typename Graph>
- bool has_no_out_edges(const typename boost::graph_traits<Graph>::vertex_descriptor& v, const Graph& g) {
- typedef typename boost::graph_traits<Graph>::out_edge_iterator ei;
- std::pair<ei, ei> p = out_edges(v, g);
- return (p.first == p.second);
+ template < typename Graph >
+ bool has_no_out_edges(
+ const typename boost::graph_traits< Graph >::vertex_descriptor& v,
+ const Graph& g)
+ {
+ typedef typename boost::graph_traits< Graph >::out_edge_iterator ei;
+ std::pair< ei, ei > p = out_edges(v, g);
+ return (p.first == p.second);
}
- } // namespace graph
+} // namespace graph
- #include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/iteration_macros.hpp>
- template <class PropertyIn, class PropertyOut, class Graph>
- void copy_vertex_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
- {
+template < class PropertyIn, class PropertyOut, class Graph >
+void copy_vertex_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
+{
BGL_FORALL_VERTICES_T(u, g, Graph)
- put(p_out, u, get(p_in, g));
- }
+ put(p_out, u, get(p_in, g));
+}
- template <class PropertyIn, class PropertyOut, class Graph>
- void copy_edge_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
- {
+template < class PropertyIn, class PropertyOut, class Graph >
+void copy_edge_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
+{
BGL_FORALL_EDGES_T(e, g, Graph)
- put(p_out, e, get(p_in, g));
- }
-
- // Return true if property_map1 and property_map2 differ
- // for any of the vertices in graph.
- template <typename PropertyMapFirst,
- typename PropertyMapSecond,
- typename Graph>
- bool are_property_maps_different
- (const PropertyMapFirst property_map1,
- const PropertyMapSecond property_map2,
- const Graph& graph) {
-
- BGL_FORALL_VERTICES_T(vertex, graph, Graph) {
- if (get(property_map1, vertex) !=
- get(property_map2, vertex)) {
-
- return (true);
- }
+ put(p_out, e, get(p_in, g));
+}
+
+// Return true if property_map1 and property_map2 differ
+// for any of the vertices in graph.
+template < typename PropertyMapFirst, typename PropertyMapSecond,
+ typename Graph >
+bool are_property_maps_different(const PropertyMapFirst property_map1,
+ const PropertyMapSecond property_map2, const Graph& graph)
+{
+
+ BGL_FORALL_VERTICES_T(vertex, graph, Graph)
+ {
+ if (get(property_map1, vertex) != get(property_map2, vertex))
+ {
+
+ return (true);
+ }
}
return (false);
- }
+}
} /* namespace boost */
projects / ceph.git / blobdiff