File: transitive_reduction.h

package info (click to toggle)
cufflinks 1.3.0-2
  • links: PTS, VCS
  • area: non-free
  • in suites: wheezy
  • size: 3,864 kB
  • sloc: cpp: 48,999; ansic: 12,297; sh: 3,381; python: 432; makefile: 209
file content (129 lines) | stat: -rw-r--r-- 5,755 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// (C) Copyright 2009 Eric Bose-Wolf
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GRAPH_TRANSITIVE_REDUCTION_HPP
#define BOOST_GRAPH_TRANSITIVE_REDUCTION_HPP

#include <vector>
#include <algorithm> //std::find
#include <boost/concept/requires.hpp>
#include <boost/concept_check.hpp>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/topological_sort.hpp>

// also I didn't got all of the concepts thin. Am I suppose to check
// for all concepts, which are needed for functions I call? (As if I
// wouldn't do that, the users would see the functions called by
// complaining about missings concepts, which would be clearly an error
// message revealing internal implementation and should therefore be avoided?)

// the pseudocode which I followed implementing this algorithmn was taken
// from the german book Algorithmische Graphentheorie by Volker Turau
// it is proposed to be of O(n + nm_red ) where n is the number
// of vertices and m_red is the number of edges in the transitive
// reduction, but I think my implementation spoiled this up at some point
// indicated below.

namespace boost {
    
    template <
    typename Graph, typename GraphTR, typename G_to_TR_VertexMap,
    typename VertexIndexMap
    >
    BOOST_CONCEPT_REQUIRES(
                           ((VertexListGraphConcept< Graph >))
                           ((IncidenceGraphConcept< Graph >))
                           ((MutableGraphConcept< GraphTR >))
                           ((ReadablePropertyMapConcept< VertexIndexMap,
                             typename graph_traits<Graph>::vertex_descriptor >))
                           ((Integer< typename
                             property_traits< VertexIndexMap >::value_type >))
                           ((LvaluePropertyMapConcept< G_to_TR_VertexMap,
                             typename graph_traits<Graph>::vertex_descriptor >)),
                           (void))
    transitive_reduction(const Graph& g, GraphTR& tr,
                         G_to_TR_VertexMap g_to_tr_map,
                         VertexIndexMap g_index_map )
    {
        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
        typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
        typedef typename std::vector<Vertex>::size_type size_type;
        
        std::vector<Vertex> topo_order;
        topological_sort(g, std::back_inserter(topo_order));
        
        std::vector<size_type> topo_number_storage(num_vertices(g));
        
        iterator_property_map<size_type*, VertexIndexMap,
        size_type, size_type&> topo_number( &topo_number_storage[0], g_index_map );
        
        {
            typename std::vector<Vertex>::reverse_iterator it = topo_order.rbegin();
            size_type n = 0;
            for(; it != topo_order.rend(); ++it,++n ) {
                topo_number[ *it ] = n;
            }
        }
        
        std::vector< std::vector< bool > > edge_in_closure(num_vertices(g),
                                                           std::vector<bool>( num_vertices(g), false));
        {
            typename std::vector<Vertex>::reverse_iterator it = topo_order.rbegin();
            for( ; it != topo_order.rend(); ++it ) {
                g_to_tr_map[*it] = add_vertex(tr);
            }
        }
        
        typename std::vector<Vertex>::iterator
        it = topo_order.begin(),
        end = topo_order.end();
        for( ; it != end; ++it ) {
            size_type i = topo_number[ *it ];
            edge_in_closure[i][i] = true;
            std::vector<Vertex> neighbors;
            
            //I have to collect the successors of *it and traverse them in
            //ascending topological order. I didn't know a better way, how to
            //do that. So what I'm doint is, collection the successors of *it here
            {
                typename Graph::out_edge_iterator oi,oi_end;
                for( tie(oi, oi_end) = out_edges( *it, g ); oi != oi_end; ++oi ) {
                    neighbors.push_back( target( *oi, g ) );
                }
            }
            
            {
                //and run through all vertices in topological order
                typename std::vector<Vertex>::reverse_iterator rit = topo_order.rbegin();
                typename std::vector<Vertex>::reverse_iterator rend = topo_order.rend();
                for(; rit != rend; ++rit ) {
                    //looking if they are successors of *it
                    if( std::find( neighbors.begin(), neighbors.end(), *rit) != neighbors.end() ) {
                        size_type j = topo_number[ *rit ];
                        if( not edge_in_closure[i][j] ) {
                            for(size_type k = j; k < num_vertices(g); ++k) {
                                if( not edge_in_closure[i][k] ) {
                                    //here we need edge_in_closure to be in topological order,
                                    edge_in_closure[i][k] = edge_in_closure[j][k];
                                }
                            }
                            //therefore we only access edge_in_closure only through
                            //topo_number property_map
                            add_edge(g_to_tr_map[*it], g_to_tr_map[*rit], tr);
                        } //if ( not edge_in_
                    } //if (find (
                } //for( typename vector<Vertex>::reverse_iterator
            } // {
            
        } //for( typename vector<Vertex>::iterator
        
    } //void transitive_reduction
    
} // namespace boost

#endif