// -*- c++ -*- //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= #include <boost/config.hpp> #include <iostream> #include <boost/graph/adjacency_list.hpp> /* Thanks to Dale Gerdemann for this example, which inspired some changes to adjacency_list to make this work properly. */ /* Sample output: 0 --c--> 1 --j--> 1 --c--> 2 --x--> 2 1 --c--> 2 --d--> 3 2 --t--> 4 3 --h--> 4 4 merging vertex 1 into vertex 0 0 --c--> 0 --j--> 0 --c--> 1 --x--> 1 --d--> 2 1 --t--> 3 2 --h--> 3 3 */ // merge_vertex(u,v,g): // incoming/outgoing edges for v become incoming/outgoing edges for u // v is deleted template <class Graph, class GetEdgeProperties> void merge_vertex (typename boost::graph_traits<Graph>::vertex_descriptor u, typename boost::graph_traits<Graph>::vertex_descriptor v, Graph& g, GetEdgeProperties getp) { typedef boost::graph_traits<Graph> Traits; typename Traits::edge_descriptor e; typename Traits::out_edge_iterator out_i, out_end; for (tie(out_i, out_end) = out_edges(v, g); out_i != out_end; ++out_i) { e = *out_i; typename Traits::vertex_descriptor targ = target(e, g); add_edge(u, targ, getp(e), g); } typename Traits::in_edge_iterator in_i, in_end; for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i) { e = *in_i; typename Traits::vertex_descriptor src = source(e, g); add_edge(src, u, getp(e), g); } clear_vertex(v, g); remove_vertex(v, g); } template <class StoredEdge> struct order_by_name : public std::binary_function<StoredEdge,StoredEdge,bool> { bool operator()(const StoredEdge& e1, const StoredEdge& e2) const { // Using std::pair operator< as an easy way to get lexicographical // compare over tuples. return std::make_pair(e1.get_target(), boost::get(boost::edge_name, e1)) < std::make_pair(e2.get_target(), boost::get(boost::edge_name, e2)); } }; struct ordered_set_by_nameS { }; #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION namespace boost { template <class ValueType> struct container_gen<ordered_set_by_nameS, ValueType> { typedef std::set<ValueType, order_by_name<ValueType> > type; }; template <> struct parallel_edge_traits<ordered_set_by_nameS> { typedef allow_parallel_edge_tag type; }; } #endif template <class Graph> struct get_edge_name { get_edge_name(const Graph& g_) : g(g_) { } template <class Edge> boost::property<boost::edge_name_t, char> operator()(Edge e) const { return boost::property<boost::edge_name_t, char>(boost::get(boost::edge_name, g, e)); } const Graph& g; }; int main() { #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION std::cout << "This program requires partial specialization." << std::endl; #else using namespace boost; typedef property<edge_name_t, char> EdgeProperty; typedef adjacency_list<ordered_set_by_nameS, vecS, bidirectionalS, no_property, EdgeProperty> graph_type; graph_type g; add_edge(0, 1, EdgeProperty('j'), g); add_edge(0, 2, EdgeProperty('c'), g); add_edge(0, 2, EdgeProperty('x'), g); add_edge(1, 3, EdgeProperty('d'), g); add_edge(1, 2, EdgeProperty('c'), g); add_edge(1, 3, EdgeProperty('d'), g); add_edge(2, 4, EdgeProperty('t'), g); add_edge(3, 4, EdgeProperty('h'), g); add_edge(0, 1, EdgeProperty('c'), g); property_map<graph_type, vertex_index_t>::type id = get(vertex_index, g); property_map<graph_type, edge_name_t>::type name = get(edge_name, g); graph_traits<graph_type>::vertex_iterator i, end; graph_traits<graph_type>::out_edge_iterator ei, edge_end; for (boost::tie(i, end) = vertices(g); i != end; ++i) { std::cout << id[*i] << " "; for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei) std::cout << " --" << name[*ei] << "--> " << id[target(*ei, g)] << " "; std::cout << std::endl; } std::cout << std::endl; std::cout << "merging vertex 1 into vertex 0" << std::endl << std::endl; merge_vertex(0, 1, g, get_edge_name<graph_type>(g)); for (boost::tie(i, end) = vertices(g); i != end; ++i) { std::cout << id[*i] << " "; for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei) std::cout << " --" << name[*ei] << "--> " << id[target(*ei, g)] << " "; std::cout << std::endl; } std::cout << std::endl; #endif return 0; }