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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
#ifndef GRAPHALGORITHMS_H
#define GRAPHALGORITHMS_H 1
#include "Graph/Properties.h"
#include "ConstrainedSearch.h" // for constrainedSearch
#include <boost/graph/graph_traits.hpp>
#include <cassert>
#include <vector>
#include <boost/tuple/tuple.hpp>
using boost::graph_traits;
/**
* Return the transitive edges.
* Find the subset of edges (u,w) in E for which there exists a vertex
* v such that the edges (u,v) and (v,w) exist in E.
* This algorithm is not a general-purpose transitive reduction
* algorithm. It is able to find transitive edges with exactly one
* intermediate vertex.
*/
template <typename Graph, typename OutIt>
void find_transitive_edges(const Graph& g, OutIt out)
{
typedef graph_traits<Graph> GTraits;
typedef typename GTraits::adjacency_iterator adjacency_iterator;
typedef typename GTraits::edge_descriptor edge_descriptor;
typedef typename GTraits::out_edge_iterator out_edge_iterator;
typedef typename GTraits::vertex_descriptor vertex_descriptor;
typedef typename GTraits::vertex_iterator vertex_iterator;
std::vector<bool> seen(num_vertices(g));
std::pair<vertex_iterator, vertex_iterator> urange = vertices(g);
for (vertex_iterator uit = urange.first;
uit != urange.second; ++uit) {
vertex_descriptor u = *uit;
if (get(vertex_removed, g, u))
continue;
// Clear the colour of the adjacent vertices.
std::pair<adjacency_iterator, adjacency_iterator>
vrange = adjacent_vertices(u, g);
for (adjacency_iterator vit = vrange.first;
vit != vrange.second; ++vit)
seen[get(vertex_index, g, *vit)] = false;
// Set the colour of all vertices reachable in two hops.
for (adjacency_iterator vit = vrange.first;
vit != vrange.second; ++vit) {
vertex_descriptor v = *vit;
if (u == v) // ignore self loops
continue;
std::pair<adjacency_iterator, adjacency_iterator>
wrange = adjacent_vertices(v, g);
for (adjacency_iterator wit = wrange.first;
wit != wrange.second; ++wit) {
vertex_descriptor w = *wit;
if (v == w) // ignore self loops
continue;
seen[get(vertex_index, g, w)] = true;
}
}
// Find the transitive edges.
std::pair<out_edge_iterator, out_edge_iterator>
uvrange = out_edges(u, g);
for (out_edge_iterator uvit = uvrange.first;
uvit != uvrange.second; ++uvit) {
edge_descriptor uv = *uvit;
vertex_descriptor v = target(uv, g);
if (seen[get(vertex_index, g, v)]) {
// The edge (u,v) is transitive. Mark it for removal.
*out++ = uv;
}
}
}
}
/** Remove edges from the graph that satisfy the predicate.
* @return the number of edges removed
*/
template <typename Graph, typename Predicate>
size_t
removeEdgeIf(Predicate predicate, Graph& g)
{
typedef graph_traits<Graph> GTraits;
typedef typename GTraits::edge_descriptor edge_descriptor;
typedef typename GTraits::edge_iterator edge_iterator;
size_t n = 0;
std::pair<edge_iterator, edge_iterator> erange = edges(g);
for (edge_iterator eit = erange.first; eit != erange.second; ++eit) {
edge_descriptor e = *eit;
if (predicate(e)) {
remove_edge(e, g);
++n;
}
}
return n;
}
/** Remove the edges [first,last) from g.
* @return the number of removed edges
*/
template <typename Graph, typename It>
void remove_edges(Graph& g, It first, It last)
{
for (It it = first; it != last; ++it)
remove_edge(*it, g);
}
/**
* Remove transitive edges from the specified graph.
* Find and remove the subset of edges (u,w) in E for which there
* exists a vertex v such that the edges (u,v) and (v,w) exist in E.
* This algorithm is not a general-purpose transitive reduction
* algorithm. It is able to find transitive edges with exactly one
* intermediate vertex.
* @return the number of transitive edges removed from g
*/
template <typename Graph>
unsigned remove_transitive_edges(Graph& g)
{
typedef typename graph_traits<Graph>::edge_descriptor
edge_descriptor;
std::vector<edge_descriptor> transitive;
find_transitive_edges(g, back_inserter(transitive));
remove_edges(g, transitive.begin(), transitive.end());
return transitive.size();
}
/**
* Find transitive edges when more than one intermediate vertex exists
* between u and w.
*/
template <typename Graph, typename OutIt>
void find_complex_transitive_edges(Graph& g, OutIt out)
{
typedef graph_traits<Graph> GTraits;
typedef typename GTraits::vertex_descriptor vertex_descriptor;
typedef typename GTraits::edge_iterator edge_iterator;
//ConstrainedSearch<Graph> anyPath(100000, 2, false);
edge_iterator efirst, elast;
for (boost::tie(efirst, elast) = edges(g); efirst != elast;
efirst++) {
vertex_descriptor u = source(*efirst, g);
Constraint c = std::make_pair(target(*efirst, g), 100000);
Constraints cs;
cs.push_back(c);
ContigPaths cp;
unsigned numVisited = 0;
constrainedSearch(g, u, cs, cp, numVisited);
if (cp.size() > 1)
*out++ = *efirst;
}
}
/**
* Remove transitive edges from the specified graph.
* Find and remove the subset of edges (u,w) in E for which there
* exists a vertex path v such that the edges (u,v) and (v,w) exist in E.
* @return the number of transitive edges removed from g
*/
template <typename Graph>
unsigned remove_complex_transitive_edges(Graph& g)
{
typedef typename graph_traits<Graph>::edge_descriptor
edge_descriptor;
std::vector<edge_descriptor> transitive;
find_complex_transitive_edges(g, back_inserter(transitive));
remove_edges(g, transitive.begin(), transitive.end());
return transitive.size();
}
#endif
|
