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
addReverseEdge(const NGHolder & g,vector<NFAEdge> & reverseEdge,NFAEdge fwd,NFAEdge rev)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
addReverseEdges(NGHolder & g,vector<NFAEdge> & reverseEdge,vector<u64a> & capacityMap)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
removeEdgesFromIndex(NGHolder & g,vector<u64a> & capacityMap,u32 idx)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
getMaxFlow(NGHolder & h,const vector<u64a> & capacityMap_in,decltype(make_small_color_map (NGHolder ()))& colorMap)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. */
findMinCut(NGHolder & h,const vector<u64a> & scores)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