1 | /* |
2 | * Copyright (c) 2015-2017, Intel Corporation |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions are met: |
6 | * |
7 | * * Redistributions of source code must retain the above copyright notice, |
8 | * this list of conditions and the following disclaimer. |
9 | * * Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * * Neither the name of Intel Corporation nor the names of its contributors |
13 | * may be used to endorse or promote products derived from this software |
14 | * without specific prior written permission. |
15 | * |
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
26 | * POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
28 | |
29 | /** \file |
30 | * \brief Network flow (min flow, max cut) algorithms. |
31 | */ |
32 | #include "ng_netflow.h" |
33 | |
34 | #include "ng_holder.h" |
35 | #include "ng_literal_analysis.h" |
36 | #include "ng_util.h" |
37 | #include "ue2common.h" |
38 | #include "util/container.h" |
39 | #include "util/graph_range.h" |
40 | #include "util/graph_small_color_map.h" |
41 | |
42 | #include <algorithm> |
43 | #include <boost/graph/boykov_kolmogorov_max_flow.hpp> |
44 | |
45 | using namespace std; |
46 | using boost::default_color_type; |
47 | |
48 | namespace ue2 { |
49 | |
50 | static |
51 | void addReverseEdge(const NGHolder &g, vector<NFAEdge> &reverseEdge, |
52 | NFAEdge fwd, NFAEdge rev) { |
53 | u32 fwdIndex = g[fwd].index; |
54 | u32 revIndex = g[rev].index; |
55 | |
56 | // Make sure our vector is big enough. |
57 | size_t sz = max(fwdIndex, revIndex) + 1; |
58 | if (reverseEdge.size() < sz) { |
59 | reverseEdge.resize(sz); |
60 | } |
61 | |
62 | // Add entries to list. |
63 | reverseEdge[fwdIndex] = rev; |
64 | reverseEdge[revIndex] = fwd; |
65 | } |
66 | |
67 | /** Add temporary reverse edges to the graph \p g, as they are required by the |
68 | * BGL's boykov_kolmogorov_max_flow algorithm. */ |
69 | static |
70 | void addReverseEdges(NGHolder &g, vector<NFAEdge> &reverseEdge, |
71 | vector<u64a> &capacityMap) { |
72 | // We're probably going to need space for 2x edge count. |
73 | const size_t numEdges = num_edges(g); |
74 | reverseEdge.reserve(numEdges * 2); |
75 | capacityMap.reserve(numEdges * 2); |
76 | |
77 | // To avoid walking the graph for _ages_, we build a temporary map of all |
78 | // edges indexed by vertex pair for existence checks. |
79 | map<pair<size_t, size_t>, NFAEdge> allEdges; |
80 | for (const auto &e : edges_range(g)) { |
81 | NFAVertex u = source(e, g), v = target(e, g); |
82 | size_t uidx = g[u].index, vidx = g[v].index; |
83 | allEdges[make_pair(uidx, vidx)] = e; |
84 | } |
85 | |
86 | // Now we walk over all edges and add their reverse edges to the reverseEdge |
87 | // vector, also adding them to the graph when they don't already exist. |
88 | for (const auto &m : allEdges) { |
89 | const NFAEdge &fwd = m.second; |
90 | const size_t uidx = m.first.first, vidx = m.first.second; |
91 | |
92 | auto it = allEdges.find(make_pair(vidx, uidx)); |
93 | if (it == allEdges.end()) { |
94 | // No reverse edge, add one. |
95 | NFAVertex u = source(fwd, g), v = target(fwd, g); |
96 | NFAEdge rev = add_edge(v, u, g); |
97 | it = allEdges.insert(make_pair(make_pair(vidx, uidx), rev)).first; |
98 | // Add to capacity map. |
99 | u32 revIndex = g[rev].index; |
100 | if (capacityMap.size() < revIndex + 1) { |
101 | capacityMap.resize(revIndex + 1); |
102 | } |
103 | capacityMap[revIndex] = 0; |
104 | } |
105 | |
106 | addReverseEdge(g, reverseEdge, fwd, it->second); |
107 | } |
108 | } |
109 | |
110 | /** Remove all edges with indices >= \p idx. */ |
111 | static |
112 | void removeEdgesFromIndex(NGHolder &g, vector<u64a> &capacityMap, u32 idx) { |
113 | remove_edge_if([&](const NFAEdge &e) { return g[e].index >= idx; }, g); |
114 | capacityMap.resize(idx); |
115 | renumber_edges(g); |
116 | } |
117 | |
118 | /** A wrapper around boykov_kolmogorov_max_flow, returns the max flow and |
119 | * colour map (from which we can find the min cut). */ |
120 | static |
121 | u64a getMaxFlow(NGHolder &h, const vector<u64a> &capacityMap_in, |
122 | decltype(make_small_color_map(NGHolder())) &colorMap) { |
123 | vector<u64a> capacityMap = capacityMap_in; |
124 | NFAVertex src = h.start; |
125 | NFAVertex sink = h.acceptEod; |
126 | |
127 | // netflow relies on these stylised edges, as all starts should be covered |
128 | // by our source and all accepts by our sink. |
129 | assert(edge(h.start, h.startDs, h).second); |
130 | assert(edge(h.accept, h.acceptEod, h).second); |
131 | |
132 | // The boykov_kolmogorov_max_flow algorithm requires us to have reverse |
133 | // edges for all edges in the graph, so we create them here (and remove |
134 | // them after the call). |
135 | const unsigned int numRealEdges = num_edges(h); |
136 | vector<NFAEdge> reverseEdges; |
137 | addReverseEdges(h, reverseEdges, capacityMap); |
138 | |
139 | const unsigned int numTotalEdges = num_edges(h); |
140 | const unsigned int numVertices = num_vertices(h); |
141 | |
142 | vector<u64a> edgeResiduals(numTotalEdges); |
143 | vector<NFAEdge> predecessors(numVertices); |
144 | vector<s32> distances(numVertices); |
145 | |
146 | auto v_index_map = get(vertex_index, h); |
147 | auto e_index_map = get(edge_index, h); |
148 | |
149 | u64a flow = boykov_kolmogorov_max_flow(h, |
150 | make_iterator_property_map(capacityMap.begin(), e_index_map), |
151 | make_iterator_property_map(edgeResiduals.begin(), e_index_map), |
152 | make_iterator_property_map(reverseEdges.begin(), e_index_map), |
153 | make_iterator_property_map(predecessors.begin(), v_index_map), |
154 | colorMap, |
155 | make_iterator_property_map(distances.begin(), v_index_map), |
156 | v_index_map, |
157 | src, sink); |
158 | |
159 | // Remove reverse edges from graph. |
160 | removeEdgesFromIndex(h, capacityMap, numRealEdges); |
161 | assert(num_edges(h) == numRealEdges); |
162 | |
163 | DEBUG_PRINTF("flow = %llu\n" , flow); |
164 | return flow; |
165 | } |
166 | |
167 | /** Returns a min cut (in \p cutset) for the graph in \p h. */ |
168 | vector<NFAEdge> findMinCut(NGHolder &h, const vector<u64a> &scores) { |
169 | assert(hasCorrectlyNumberedEdges(h)); |
170 | assert(hasCorrectlyNumberedVertices(h)); |
171 | |
172 | auto colors = make_small_color_map(h); |
173 | u64a flow = getMaxFlow(h, scores, colors); |
174 | |
175 | vector<NFAEdge> picked_white; |
176 | vector<NFAEdge> picked_black; |
177 | u64a observed_black_flow = 0; |
178 | u64a observed_white_flow = 0; |
179 | |
180 | for (const auto &e : edges_range(h)) { |
181 | NFAVertex from = source(e, h); |
182 | NFAVertex to = target(e, h); |
183 | u64a ec = scores[h[e].index]; |
184 | if (ec == 0) { |
185 | continue; // skips, among other things, reverse edges |
186 | } |
187 | |
188 | auto fromColor = get(colors, from); |
189 | auto toColor = get(colors, to); |
190 | |
191 | if (fromColor != small_color::white && toColor == small_color::white) { |
192 | assert(ec <= INVALID_EDGE_CAP); |
193 | DEBUG_PRINTF("found white cut edge %zu->%zu cap %llu\n" , |
194 | h[from].index, h[to].index, ec); |
195 | observed_white_flow += ec; |
196 | picked_white.push_back(e); |
197 | } |
198 | if (fromColor == small_color::black && toColor != small_color::black) { |
199 | assert(ec <= INVALID_EDGE_CAP); |
200 | DEBUG_PRINTF("found black cut edge %zu->%zu cap %llu\n" , |
201 | h[from].index, h[to].index, ec); |
202 | observed_black_flow += ec; |
203 | picked_black.push_back(e); |
204 | } |
205 | } |
206 | |
207 | DEBUG_PRINTF("min flow = %llu b flow = %llu w flow %llu\n" , flow, |
208 | observed_black_flow, observed_white_flow); |
209 | if (min(observed_white_flow, observed_black_flow) != flow) { |
210 | DEBUG_PRINTF("bad cut\n" ); |
211 | } |
212 | |
213 | if (observed_white_flow < observed_black_flow) { |
214 | return picked_white; |
215 | } else { |
216 | return picked_black; |
217 | } |
218 | } |
219 | |
220 | } // namespace ue2 |
221 | |