1 // (C) Copyright 2009 Eric Bose-Wolf
2 //
3 // Use, modification and distribution are subject to the
4 // Boost Software License, Version 1.0 (See accompanying file
5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
6
7 #ifndef BOOST_GRAPH_TRANSITIVE_REDUCTION_HPP
8 #define BOOST_GRAPH_TRANSITIVE_REDUCTION_HPP
9
10 #include <vector>
11 #include <algorithm> //std::find
12 #include <boost/concept/requires.hpp>
13 #include <boost/concept_check.hpp>
14
15 #include <boost/graph/graph_traits.hpp>
16 #include <boost/graph/topological_sort.hpp>
17
18 // also I didn't got all of the concepts thin. Am I suppose to check
19 // for all concepts, which are needed for functions I call? (As if I
20 // wouldn't do that, the users would see the functions called by
21 // complaining about missings concepts, which would be clearly an error
22 // message revealing internal implementation and should therefore be avoided?)
23
24 // the pseudocode which I followed implementing this algorithmn was taken
25 // from the german book Algorithmische Graphentheorie by Volker Turau
26 // it is proposed to be of O(n + nm_red ) where n is the number
27 // of vertices and m_red is the number of edges in the transitive
28 // reduction, but I think my implementation spoiled this up at some point
29 // indicated below.
30
31 namespace boost
32 {
33
34 template < typename Graph, typename GraphTR, typename G_to_TR_VertexMap,
35 typename VertexIndexMap >
36 BOOST_CONCEPT_REQUIRES(
37 ((VertexListGraphConcept< Graph >))((IncidenceGraphConcept< Graph >))(
38 (MutableGraphConcept< GraphTR >))(
39 (ReadablePropertyMapConcept< VertexIndexMap,
40 typename graph_traits< Graph >::vertex_descriptor >))(
41 (Integer< typename property_traits< VertexIndexMap >::value_type >))(
42 (LvaluePropertyMapConcept< G_to_TR_VertexMap,
43 typename graph_traits< Graph >::vertex_descriptor >)),
44 (void))
transitive_reduction(const Graph & g,GraphTR & tr,G_to_TR_VertexMap g_to_tr_map,VertexIndexMap g_index_map)45 transitive_reduction(const Graph& g, GraphTR& tr, G_to_TR_VertexMap g_to_tr_map,
46 VertexIndexMap g_index_map)
47 {
48 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
49 typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
50 typedef typename std::vector< Vertex >::size_type size_type;
51
52 std::vector< Vertex > topo_order;
53 topological_sort(g, std::back_inserter(topo_order));
54
55 std::vector< size_type > topo_number_storage(num_vertices(g));
56
57 iterator_property_map< size_type*, VertexIndexMap, size_type, size_type& >
58 topo_number(&topo_number_storage[0], g_index_map);
59
60 {
61 typename std::vector< Vertex >::reverse_iterator it
62 = topo_order.rbegin();
63 size_type n = 0;
64 for (; it != topo_order.rend(); ++it, ++n)
65 {
66 topo_number[*it] = n;
67 }
68 }
69
70 std::vector< std::vector< bool > > edge_in_closure(
71 num_vertices(g), std::vector< bool >(num_vertices(g), false));
72 {
73 typename std::vector< Vertex >::reverse_iterator it
74 = topo_order.rbegin();
75 for (; it != topo_order.rend(); ++it)
76 {
77 g_to_tr_map[*it] = add_vertex(tr);
78 }
79 }
80
81 typename std::vector< Vertex >::iterator it = topo_order.begin(),
82 end = topo_order.end();
83 for (; it != end; ++it)
84 {
85 size_type i = topo_number[*it];
86 edge_in_closure[i][i] = true;
87 std::vector< Vertex > neighbors;
88
89 // I have to collect the successors of *it and traverse them in
90 // ascending topological order. I didn't know a better way, how to
91 // do that. So what I'm doint is, collection the successors of *it here
92 {
93 typename Graph::out_edge_iterator oi, oi_end;
94 for (boost::tie(oi, oi_end) = out_edges(*it, g); oi != oi_end; ++oi)
95 {
96 neighbors.push_back(target(*oi, g));
97 }
98 }
99
100 {
101 // and run through all vertices in topological order
102 typename std::vector< Vertex >::reverse_iterator rit
103 = topo_order.rbegin(),
104 rend = topo_order.rend();
105 for (; rit != rend; ++rit)
106 {
107 // looking if they are successors of *it
108 if (std::find(neighbors.begin(), neighbors.end(), *rit)
109 != neighbors.end())
110 {
111 size_type j = topo_number[*rit];
112 if (not edge_in_closure[i][j])
113 {
114 for (size_type k = j; k < num_vertices(g); ++k)
115 {
116 if (not edge_in_closure[i][k])
117 {
118 // here we need edge_in_closure to be in
119 // topological order,
120 edge_in_closure[i][k] = edge_in_closure[j][k];
121 }
122 }
123 // therefore we only access edge_in_closure only through
124 // topo_number property_map
125 add_edge(g_to_tr_map[*it], g_to_tr_map[*rit], tr);
126 } // if ( not edge_in_
127 } // if (find (
128 } // for( typename vector<Vertex>::reverse_iterator
129 } // {
130
131 } // for( typename vector<Vertex>::iterator
132
133 } // void transitive_reduction
134
135 } // namespace boost
136
137 #endif
138