1/*
2 * Copyright (c) 2016-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 An algorithm to find cliques.
31 */
32
33#include "clique.h"
34#include "container.h"
35#include "graph_range.h"
36#include "make_unique.h"
37
38#include <map>
39#include <set>
40#include <stack>
41
42using namespace std;
43
44namespace ue2 {
45
46static
47vector<u32> getNeighborInfo(const CliqueGraph &g,
48 const CliqueVertex &cv, const set<u32> &group) {
49 u32 id = g[cv].stateId;
50 vector<u32> neighbor;
51 // find neighbors for cv
52 for (const auto &v : adjacent_vertices_range(cv, g)) {
53 if (g[v].stateId != id && contains(group, g[v].stateId)){
54 neighbor.push_back(g[v].stateId);
55 DEBUG_PRINTF("Neighbor:%u\n", g[v].stateId);
56 }
57 }
58
59 return neighbor;
60}
61
62static
63vector<u32> findCliqueGroup(CliqueGraph &cg) {
64 stack<vector<u32>> gStack;
65
66 // Create mapping between vertex and id
67 map<u32, CliqueVertex> vertexMap;
68 vector<u32> init;
69 for (const auto &v : vertices_range(cg)) {
70 vertexMap[cg[v].stateId] = v;
71 init.push_back(cg[v].stateId);
72 }
73 gStack.push(init);
74
75 // Get the vertex to start from
76 vector<u32> clique;
77 while (!gStack.empty()) {
78 vector<u32> g = move(gStack.top());
79 gStack.pop();
80
81 // Choose a vertex from the graph
82 u32 id = g[0];
83 CliqueVertex &n = vertexMap.at(id);
84 clique.push_back(id);
85 // Corresponding vertex in the original graph
86 set<u32> subgraphId(g.begin(), g.end());
87 auto neighbor = getNeighborInfo(cg, n, subgraphId);
88 // Get graph consisting of neighbors for left branch
89 if (!neighbor.empty()) {
90 gStack.push(neighbor);
91 }
92 }
93
94 return clique;
95}
96
97template<typename Graph>
98bool graph_empty(const Graph &g) {
99 typename Graph::vertex_iterator vi, ve;
100 tie(vi, ve) = vertices(g);
101 return vi == ve;
102}
103
104vector<vector<u32>> removeClique(CliqueGraph &cg) {
105 DEBUG_PRINTF("graph size:%zu\n", num_vertices(cg));
106 vector<vector<u32>> cliquesVec = {findCliqueGroup(cg)};
107 while (!graph_empty(cg)) {
108 const vector<u32> &c = cliquesVec.back();
109 vector<CliqueVertex> dead;
110 for (const auto &v : vertices_range(cg)) {
111 u32 id = cg[v].stateId;
112 if (find(c.begin(), c.end(), id) != c.end()) {
113 dead.push_back(v);
114 }
115 }
116 for (const auto &v : dead) {
117 clear_vertex(v, cg);
118 remove_vertex(v, cg);
119 }
120 if (graph_empty(cg)) {
121 break;
122 }
123 auto clique = findCliqueGroup(cg);
124 cliquesVec.push_back(clique);
125 }
126
127 return cliquesVec;
128}
129
130} // namespace ue2
131