1 // -*- c++ -*-
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 #include <boost/config.hpp>
11 #include <iostream>
12
13 #include <boost/graph/adjacency_list.hpp>
14
15 /*
16 Thanks to Dale Gerdemann for this example, which inspired some
17 changes to adjacency_list to make this work properly.
18 */
19
20 /*
21 Sample output:
22
23 0 --c--> 1 --j--> 1 --c--> 2 --x--> 2
24 1 --c--> 2 --d--> 3
25 2 --t--> 4
26 3 --h--> 4
27 4
28
29 merging vertex 1 into vertex 0
30
31 0 --c--> 0 --j--> 0 --c--> 1 --x--> 1 --d--> 2
32 1 --t--> 3
33 2 --h--> 3
34 3
35 */
36
37 // merge_vertex(u,v,g):
38 // incoming/outgoing edges for v become incoming/outgoing edges for u
39 // v is deleted
40 template < class Graph, class GetEdgeProperties >
merge_vertex(typename boost::graph_traits<Graph>::vertex_descriptor u,typename boost::graph_traits<Graph>::vertex_descriptor v,Graph & g,GetEdgeProperties getp)41 void merge_vertex(typename boost::graph_traits< Graph >::vertex_descriptor u,
42 typename boost::graph_traits< Graph >::vertex_descriptor v, Graph& g,
43 GetEdgeProperties getp)
44 {
45 typedef boost::graph_traits< Graph > Traits;
46 typename Traits::edge_descriptor e;
47 typename Traits::out_edge_iterator out_i, out_end;
48 for (boost::tie(out_i, out_end) = out_edges(v, g); out_i != out_end;
49 ++out_i)
50 {
51 e = *out_i;
52 typename Traits::vertex_descriptor targ = target(e, g);
53 add_edge(u, targ, getp(e), g);
54 }
55 typename Traits::in_edge_iterator in_i, in_end;
56 for (boost::tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
57 {
58 e = *in_i;
59 typename Traits::vertex_descriptor src = source(e, g);
60 add_edge(src, u, getp(e), g);
61 }
62 clear_vertex(v, g);
63 remove_vertex(v, g);
64 }
65
66 template < class StoredEdge > struct order_by_name
67 {
68 typedef StoredEdge first_argument_type;
69 typedef StoredEdge second_argument_type;
70 typedef bool result_type;
operator ()order_by_name71 bool operator()(const StoredEdge& e1, const StoredEdge& e2) const
72 {
73 // Using std::pair operator< as an easy way to get lexicographical
74 // compare over tuples.
75 return std::make_pair(e1.get_target(), boost::get(boost::edge_name, e1))
76 < std::make_pair(e2.get_target(), boost::get(boost::edge_name, e2));
77 }
78 };
79 struct ordered_set_by_nameS
80 {
81 };
82
83 #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
84 namespace boost
85 {
86 template < class ValueType >
87 struct container_gen< ordered_set_by_nameS, ValueType >
88 {
89 typedef std::set< ValueType, order_by_name< ValueType > > type;
90 };
91 template <> struct parallel_edge_traits< ordered_set_by_nameS >
92 {
93 typedef allow_parallel_edge_tag type;
94 };
95 }
96 #endif
97
98 template < class Graph > struct get_edge_name
99 {
get_edge_nameget_edge_name100 get_edge_name(const Graph& g_) : g(g_) {}
101
102 template < class Edge >
operator ()get_edge_name103 boost::property< boost::edge_name_t, char > operator()(Edge e) const
104 {
105 return boost::property< boost::edge_name_t, char >(
106 boost::get(boost::edge_name, g, e));
107 }
108 const Graph& g;
109 };
110
main()111 int main()
112 {
113 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
114 std::cout << "This program requires partial specialization." << std::endl;
115 #else
116 using namespace boost;
117 typedef property< edge_name_t, char > EdgeProperty;
118 typedef adjacency_list< ordered_set_by_nameS, vecS, bidirectionalS,
119 no_property, EdgeProperty >
120 graph_type;
121
122 graph_type g;
123
124 add_edge(0, 1, EdgeProperty('j'), g);
125 add_edge(0, 2, EdgeProperty('c'), g);
126 add_edge(0, 2, EdgeProperty('x'), g);
127 add_edge(1, 3, EdgeProperty('d'), g);
128 add_edge(1, 2, EdgeProperty('c'), g);
129 add_edge(1, 3, EdgeProperty('d'), g);
130 add_edge(2, 4, EdgeProperty('t'), g);
131 add_edge(3, 4, EdgeProperty('h'), g);
132 add_edge(0, 1, EdgeProperty('c'), g);
133
134 property_map< graph_type, vertex_index_t >::type id = get(vertex_index, g);
135 property_map< graph_type, edge_name_t >::type name = get(edge_name, g);
136
137 graph_traits< graph_type >::vertex_iterator i, end;
138 graph_traits< graph_type >::out_edge_iterator ei, edge_end;
139
140 for (boost::tie(i, end) = vertices(g); i != end; ++i)
141 {
142 std::cout << id[*i] << " ";
143 for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei)
144 std::cout << " --" << name[*ei] << "--> " << id[target(*ei, g)]
145 << " ";
146 std::cout << std::endl;
147 }
148 std::cout << std::endl;
149
150 std::cout << "merging vertex 1 into vertex 0" << std::endl << std::endl;
151 merge_vertex(0, 1, g, get_edge_name< graph_type >(g));
152
153 for (boost::tie(i, end) = vertices(g); i != end; ++i)
154 {
155 std::cout << id[*i] << " ";
156 for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei)
157 std::cout << " --" << name[*ei] << "--> " << id[target(*ei, g)]
158 << " ";
159 std::cout << std::endl;
160 }
161 std::cout << std::endl;
162 #endif
163 return 0;
164 }
165