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
45using namespace std;
46using boost::default_color_type;
47
48namespace ue2 {
49
50static
51void 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. */
69static
70void 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. */
111static
112void 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). */
120static
121u64a 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. */
168vector<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