#include <bits/stdc++.h>
#include "testlib.h"
using namespace std;
using namespace std::chrono;
const int DEBUG_MODE = 0;
const int MODE = DEBUG_MODE;
const string LOG_FILE = "log.txt";
const double eps = 1e-9;
const double INF = 1e15;
struct Graph {
int n;
vector<vector<pair<int, double>>> adj;
vector<vector<bool>> adj_matrix;
vector<vector<double>> weight_matrix;
void init(int _n) {
assert(_n > 0);
n = _n;
adj = vector<vector<pair<int, double>>>(n, vector<pair<int, double>>());
adj_matrix = vector<vector<bool>>(n, vector<bool>(n, false));
weight_matrix = vector<vector<double>>(n, vector<double>(n, 0.0));
}
Graph() {
n = 0;
adj.clear();
}
Graph(int _n) {
assert(_n > 0);
init(_n);
}
void add_edge(int u, int v, double weight) {
assert((0 <= min(u, v)) && (max(u, v) < n));
adj[u].push_back(make_pair(v, weight));
adj[v].push_back(make_pair(u, weight));
weight_matrix[u][v] = weight_matrix[v][u] = weight;
adj_matrix[u][v] = adj_matrix[v][u] = true;
}
int get_deg(int u) {
assert((0 <= u) && (u < n));
return adj[u].size();
}
bool have_edge(int u, int v) {
assert((0 <= min(u, v)) && (max(u, v) < n));
return adj_matrix[u][v];
}
double get_weight(int u, int v) {
assert((0 <= min(u, v)) && (max(u, v) < n));
return weight_matrix[u][v];
}
};
struct Tree {
int n, root;
vector<int> par, subtree;
vector<vector<int>> child;
vector<vector<bool>> adj_matrix;
void init(int _n, int _root) {
assert(_n > 0);
assert((0 <= _root) && (_root < _n));
n = _n; root = _root;
assert((root >= 0) && (root < n));
par = vector<int>(n, -1); subtree = vector<int>(n, 0);
child = vector<vector<int>>(n, vector<int>());
adj_matrix = vector<vector<bool>>(n, vector<bool>(n, false));
}
void append_child(int u, int v) {
assert((0 <= min(u, v)) && (max(u, v) < n));
child[u].push_back(v);
par[v] = u;
adj_matrix[u][v] = adj_matrix[v][u] = true;
}
void DFS(int u, int par, Graph &g) {
subtree[u] = 1;
for(pair<int, double> &e : g.adj[u]) {
int v = e.first;
if (v != par) {
append_child(u, v);
DFS(v, u, g);
subtree[u] += subtree[v];
}
}
}
void init(Graph &g, int root) {
assert((0 <= root) && (root < g.n));
init(g.n, root);
DFS(root, -1, g);
}
Tree() {}
Tree(Graph &g, int root) {
init(g, root);
}
int get_num_child(int u) {
assert((0 <= u) && (u < n));
return child[u].size();
}
int get_deg(int u) {
assert((0 <= u) && (u < n));
return child[u].size() + (par[u] != -1);
}
bool have_edge(int u, int v) {
assert((0 <= min(u, v)) && (max(u, v) < n));
return adj_matrix[u][v];
}
};
const int MAXQ = 100 + 10;
const int MAXG = 100 + 10;
//input data
Graph G, Q_graph;
Tree Q_tree;
int n_ins; double per_ins;
int n_del; double per_del;
double similar_score[MAXQ][MAXG];
double threshold = 0.0;
//variables for algorithm
int n_duplications;
int n_colors;
int color[MAXG];
//match result
double best_match_score;
vector<int> inserted_nodes;
vector<int> map_to;
void init_log() {
ofstream lf(LOG_FILE);
lf.close();
}
inline void write_log(string message) {
ofstream lf(LOG_FILE, std::ofstream::app);
lf << message;
lf.close();
}
bool homologous(int q, int v) {
return similar_score[q][v] >= threshold;
}
int get_bit(int x, int n) {
return ((x >> n) & 1);
}
namespace feedback_vertex_set {
bool DFS(Graph &g, int u, int par, int removed_vertices, vector<bool> &visited) {
if (visited[u])
return true;
visited[u] = true;
for(pair<int, double> &p : g.adj[u]) {
int v = p.first;
if ((v != par) && (get_bit(removed_vertices, v) == 0)) {
if (DFS(g, v, u, removed_vertices, visited))
return true;
}
}
return false;
}
bool is_feedback_vertex_set(Graph &g, int vertex_set) {
vector<bool> visited(g.n, false);
for(int v = 0; v < g.n; ++v)
if ((!visited[v]) && (get_bit(vertex_set, v) == 0)) {
bool cycle_found = DFS(g, v, -1, vertex_set, visited);
if (cycle_found) return false;
}
return true;
}
vector<int> run(Graph &g) {
for(int vertex_set = 0; vertex_set < (1 << g.n); ++vertex_set) {
if (is_feedback_vertex_set(g, vertex_set)) {
vector<int> feedback_vertex_set;
for(int v = 0; v < g.n; ++v)
if (get_bit(vertex_set, v))
feedback_vertex_set.push_back(v);
return feedback_vertex_set;
}
}
}
}
int choose_root(Graph &g) {
for(int i = 0; i < g.n; ++i)
if (g.adj[i].size() == 1)
return i;
return -1;
}
namespace graph_to_tree {
vector<int> dup_ver;
vector<vector<int>> dup;
vector<vector<bool>> existing_edges;
vector<pair<int, int>> add_edges;
vector<int> origin;
int n_dup;
int DFS(Graph &g, vector<vector<bool>> &existing_edges, int u, vector<int> &par, vector<bool> &visited) {
if (visited[u])
return u;
visited[u] = true;
for(pair<int, double> &p : g.adj[u]) {
int v = p.first;
if ((v != par[u]) && (existing_edges[u][v])) {
par[v] = u;
int x = DFS(g, existing_edges, v, par, visited);
if (x >= 0) return x;
}
}
return -1;
}
vector<int> find_a_cycle(Graph &g, vector<vector<bool>> &existing_edges) {
vector<int> par(g.n, -1);
vector<bool> visited(g.n, false);
for(int v = 0; v < g.n; ++v)
if (!visited[v]) {
int u = DFS(g, existing_edges, v, par, visited);
if (u >= 0) {
vector<int> c;
int x = par[u];
while (x != u) {
c.push_back(x);
x = par[x];
}
c.push_back(u);
return c;
}
}
return vector<int>();
}
int choose_duplicated_vertex(vector<int> &feedback_vertex_set, vector<int> &cycle) {
for(int u : feedback_vertex_set)
for(int v : cycle)
if (u == v)
return u;
return -1;
}
int choose_neighbor_of_duplicated_node(Graph &g, int dup_ver, vector<int> &cycle, vector<vector<bool>> &existing_edges) {
for(pair<int, double> &p : g.adj[dup_ver]) {
int u = p.first;
if (existing_edges[dup_ver][u]) {
for(int v : cycle)
if (u == v)
return u;
}
}
return -1;
}
Tree create_tree(Graph &g) {
Graph g_tree(g.n + n_dup);
for(int u = 0; u < g.n; ++u)
for(int v = u + 1; v < g.n; ++v)
if (existing_edges[u][v])
g_tree.add_edge(u, v, 0.0);
for(pair<int, int> &e : add_edges)
g_tree.add_edge(e.first, e.second, 0.0);
int root = choose_root(g_tree);
Tree tree(g_tree, root);
for(int i = 0; i < g_tree.n; ++i)
for(int j = i + 1; j < g_tree.n; ++j)
if (g_tree.have_edge(i, j))
cout << "edge = " << i << " " << j << endl;
return tree;
}
Tree run(Graph &g, vector<int> feedback_vertex_set) {
dup = vector<vector<int>>(g.n, vector<int>());
existing_edges = g.adj_matrix;
add_edges.clear();
n_dup = 0;
origin.resize(g.n);
for(int v = 0; v < g.n; ++v) origin[v] = v;
while (true) {
vector<int> cycle = find_a_cycle(g, existing_edges);
if (cycle.size() == 0) break;
cout << "cycle = "; for(int c : cycle) cout << c << " "; cout << "\n";
int dup_ver = choose_duplicated_vertex(feedback_vertex_set, cycle);
cout << "dup_ver = " << dup_ver << endl;
assert(dup_ver >= 0);
int nei = choose_neighbor_of_duplicated_node(g, dup_ver, cycle, existing_edges);
cout << "nei = " << nei << "\n";
assert(nei >= 0);
cout << "index of new vertex = " << g.n + n_dup << endl;
existing_edges[dup_ver][nei] = existing_edges[nei][dup_ver] = false;
dup[dup_ver].push_back(g.n + n_dup);
add_edges.push_back(make_pair(nei, g.n + n_dup));
origin.push_back(dup_ver);
++n_dup;
}
dup_ver.resize(0);
for(int v = 0; v < g.n; ++v)
if (dup[v].size() > 0)
dup_ver.push_back(v);
return create_tree(g);
}
}
bool can_delete_general(int q) {
return Q_graph.get_deg(q) == 2;
}
bool can_insert_general(int v) {
return true;
//return G.get_deg(v) == 2;
}
bool maximize(double &a, double b) {
if (a < b) {
a = b;
return true;
}
else return false;
}
string my_to_string(int x) {
if (x == 0) return "0";
string s = "";
bool neg = false;
if (x < 0) {
neg = true;
x = -x;
}
while (x > 0) {
s.push_back(char(int('0') + x % 10));
x /= 10;
}
if (neg) s.push_back('-');
reverse(s.begin(), s.end());
return s;
}
string my_double_to_string(double x) {
std::ostringstream strs;
strs << x;
std::string str = strs.str();
return str;
}
bool equals(double x, double y) {
return abs(x - y) <= eps;
}
namespace tree_match_graph {
Graph G;
vector<int> match;
double best_match_score;
int best_root_map_to, best_color_set, best_n_del_left;
vector<int> best_coloring;
vector<vector<vector<vector<double>>>> fm, fi, fd; //f(u, v, color_set_use, num_deletion_left)
vector<vector<vector<double>>> fm_temp;
vector<vector<vector<vector<vector<int>>>>> trace_fm_color, trace_fm_n_del_left, trace_fm_nxt_vertex;
vector<vector<vector<vector<int>>>> trace_fi_nxt_vertex, trace_fd_nxt_vertex;
vector<int> choosed, best_choosed;
vector<bool> can_use_color_set;
double pre_assign_score;
//variables stored result
vector<int> inserted_nodes;
vector<int> map_to; //map_to[q] = v => q is map to v; map_to[q] = -1 => q is deleted node
double get_similar_score(int q, int v) {
return similar_score[graph_to_tree::origin[q]][v];
}
bool can_map(int color_set_use, int v) {
if (!can_use_color_set[color_set_use]) return false;
if (choosed[v] != -1) return true;
return (get_bit(color_set_use, color[v]) == 1);
}
bool can_map(int u, int color_set_use, int v) {
int ou = graph_to_tree::origin[u];
if (match[ou] == -1)
return (can_map(color_set_use, v) && homologous(ou, v));
else return (match[ou] == v);
}
bool can_delete(int q) {
int oq = graph_to_tree::origin[q];
if (match[oq] != -1) return false;
return (Q_graph.get_deg(oq) == 2);
}
bool can_insert(int v) {
return ((G.get_deg(v) == 2) && (choosed[v] == -1));
}
int add_vertex(int color_set, int vertex) {
return (choosed[vertex] == -1) ? (color_set + (1 << color[vertex])) : color_set;
}
int remove_vertex(int color_set, int vertex) {
return (choosed[vertex] == -1) ? (color_set - (1 << color[vertex])) : color_set;
}
void update_fm(int q, int v, int color_set_prev, int n_del_left_prev, int k_th_child, int color_set_on_child, int n_del_left_on_child) {
if (!can_use_color_set[color_set_prev] || !can_use_color_set[color_set_on_child]) return;
if (equals(fm[q][v][color_set_prev][n_del_left_prev], -INF)) return;
if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_prev = "
+ my_to_string(color_set_prev) + ", n_del_left_prev = " + my_to_string(n_del_left_prev)
+ ", k_th_child = " + my_to_string(k_th_child) + ", color_set_on_child = "
+ my_to_string(color_set_on_child) + ", n_del_left_on_child = " + my_to_string(n_del_left_on_child) + ")...\n");
int color_set_use = color_set_prev | color_set_on_child;
int n_del_left = n_del_left_prev + n_del_left_on_child;
int child = Q_tree.child[q][k_th_child];
for(pair<int, double> &neighbor : G.adj[v]) {
int u = neighbor.first; double w = neighbor.second;
if (can_map(child, color_set_on_child, u)) {
//map child -> u
if (!equals(fm[child][u][color_set_on_child][n_del_left_on_child], -INF))
if (maximize(fm_temp[v][color_set_use][n_del_left], fm[q][v][color_set_prev][n_del_left_prev]
+ fm[child][u][color_set_on_child][n_del_left_on_child] + w))
{
trace_fm_color[q][k_th_child][v][color_set_use][n_del_left] = color_set_on_child;
trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left] = n_del_left_on_child;
trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left] = u;
};
//insert child
if (can_insert(u) && (!equals(fi[child][u][color_set_on_child][n_del_left_on_child], -INF))) {
if (maximize(fm_temp[v][color_set_use][n_del_left], fm[q][v][color_set_prev][n_del_left_prev]
+ fi[child][u][color_set_on_child][n_del_left_on_child] + w))
{
trace_fm_color[q][k_th_child][v][color_set_use][n_del_left] = color_set_on_child;
trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left] = n_del_left_on_child;
trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left] = - u - 1;
};
}
}
}
if (can_delete(child) && (!equals(fd[child][v][color_set_on_child][n_del_left_on_child], -INF))) {
//delete child
if (maximize(fm_temp[v][color_set_use][n_del_left], fm[q][v][color_set_prev][n_del_left_prev]
+ fd[child][v][color_set_on_child][n_del_left_on_child]))
{
trace_fm_color[q][k_th_child][v][color_set_use][n_del_left] = color_set_on_child;
trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left] = n_del_left_on_child;
trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left] = v; //keep
};
}
if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_prev = "
+ my_to_string(color_set_prev) + ", n_del_left_prev = " + my_to_string(n_del_left_prev)
+ ", k_th_child = " + my_to_string(k_th_child) + ", color_set_on_child = "
+ my_to_string(color_set_on_child) + ", n_del_left_on_child = " + my_to_string(n_del_left_on_child) + ") done\n");
}
void update_fm(int q, int k_th_child) {
if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", k_th_child = " + my_to_string(k_th_child) + ")....\n");
for(int v = 0; v < G.n; ++v)
for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
fm_temp[v][color_set][n_del_left] = -INF;
for(int color_set_prev = (1 << n_colors) - 1; color_set_prev >= 0; --color_set_prev)
if (can_use_color_set[color_set_prev])
for(int n_del_left_prev = 0; n_del_left_prev <= n_del; ++n_del_left_prev) {
for(int color_set_on_child = 0; color_set_on_child < (1 << n_colors); ++color_set_on_child)
if ((can_use_color_set[color_set_on_child]) &&((color_set_prev + color_set_on_child) == (color_set_prev | color_set_on_child)))
for(int n_del_left_on_child = 0; n_del_left_on_child <= n_del - n_del_left_prev; ++n_del_left_on_child)
for(int v = 0; v < G.n; ++v) {
if (can_map(q, color_set_prev, v))
update_fm(q, v, color_set_prev, n_del_left_prev, k_th_child, color_set_on_child, n_del_left_on_child);
}
}
for(int v = 0; v < G.n; ++v)
for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
fm[q][v][color_set][n_del_left] = fm_temp[v][color_set][n_del_left];
if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", k_th_child = " + my_to_string(k_th_child) + ") done\n");
}
// color[v] belongs to color_set_use
void update_fi(int q, int v, int color_set_use, int n_del_left) {
if (!can_use_color_set[color_set_use]) return;
if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
int new_color_set = color_set_use - (1 << color[v]);
for(pair<int, double> &neighbor : G.adj[v]) {
int u = neighbor.first; double w = neighbor.second;
if (can_map(new_color_set, u)) {
if (can_map(q, new_color_set, u) && (!equals(fm[q][u][new_color_set][n_del_left], -INF)))
if (maximize(fi[q][v][color_set_use][n_del_left], per_ins + fm[q][u][new_color_set][n_del_left] + w)) {
trace_fi_nxt_vertex[q][v][color_set_use][n_del_left] = u;
};
if (can_insert(u) && (!equals(fi[q][u][new_color_set][n_del_left], -INF))) {
maximize(fi[q][v][color_set_use][n_del_left], per_ins + fi[q][u][new_color_set][n_del_left] + w);
trace_fi_nxt_vertex[q][v][color_set_use][n_del_left] = - u - 1;
}
}
}
if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
}
void update_fi(int q) {
if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ")....\n");
for(int v = 0; v < G.n; ++v)
if (can_insert(v))
for(int color_set_use = 0; color_set_use < (1 << n_colors); ++color_set_use)
if (can_use_color_set[color_set_use])
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
if (can_map(color_set_use, v))
update_fi(q, v, color_set_use, n_del_left);
if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ") done\n");
}
void update_fd(int q, int v, int color_set_use, int n_del_left) {
if (!can_use_color_set[color_set_use]) return;
if (n_del_left < 1) return;
if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = " + my_to_string(color_set_use)
+ ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
int q_nxt = Q_tree.child[q][0];
for(pair<int, double> &neighbor : G.adj[v]) {
int u = neighbor.first; double w = neighbor.second;
if (can_map(color_set_use, u)) {
if (can_map(q_nxt, color_set_use, u) && (!equals(fm[q_nxt][u][color_set_use][n_del_left - 1], -INF))) {
if (maximize(fd[q][v][color_set_use][n_del_left], per_del + fm[q_nxt][u][color_set_use][n_del_left - 1] + w)) {
trace_fd_nxt_vertex[q][v][color_set_use][n_del_left] = u;
};
}
if (!equals(fi[q_nxt][u][color_set_use][n_del_left - 1], -INF)) {
if (maximize(fd[q][v][color_set_use][n_del_left], per_del + fi[q_nxt][u][color_set_use][n_del_left - 1] + w)) {
trace_fd_nxt_vertex[q][v][color_set_use][n_del_left] = - u - 1;
};
}
}
}
if (can_delete(q_nxt) && (n_del_left > 0) && (!equals(fd[q_nxt][v][color_set_use][n_del_left - 1], -INF))) {
if (maximize(fd[q][v][color_set_use][n_del_left], per_del + fd[q_nxt][v][color_set_use][n_del_left - 1])) {
}
trace_fd_nxt_vertex[q][v][color_set_use][n_del_left] = v;
};
}
if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = " + my_to_string(color_set_use)
+ ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
}
void update_fd(int q) {
if (!can_delete(q)) return;
if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ")....\n");
for(int v = 0; v < G.n; ++v)
for(int color_set_use = 0; color_set_use < (1 << n_colors); ++color_set_use)
if (can_use_color_set[color_set_use])
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
update_fd(q, v, color_set_use, n_del_left);
if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ") done\n");
}
void init_dp(int q) {
if (MODE == DEBUG_MODE) write_log("init_dp(q = " + my_to_string(q) + ")...\n");
for(int v = 0; v < G.n; ++v)
for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
fm[q][v][color_set][n_del_left] = -INF;
fi[q][v][color_set][n_del_left] = -INF;
fd[q][v][color_set][n_del_left] = -INF;
}
for(int v = 0; v < G.n; ++v)
if (can_map(q, (1 << color[v]), v)) {
fm[q][v][add_vertex(0, v)][0] = (match[q] == -1) ? get_similar_score(q, v) : 0.0;
}
if (MODE == DEBUG_MODE) write_log("init_dp(q = " + my_to_string(q) + ") done\n");
}
void write_log_dp_values(int q) {
write_log("get dp values at node " + my_to_string(q) + "...\n");
write_log("get fm(q = " + my_to_string(q) + ")\n");
for(int v = 0; v < G.n; ++v)
for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
if (!equals(fm[q][v][color_set][n_del_left], -INF))
write_log("fm(" + my_to_string(q) + "," + my_to_string(v) + "," + my_to_string(color_set) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fm[q][v][color_set][n_del_left]) + "\n");
}
write_log("get fi(q = " + my_to_string(q) + ")\n");
for(int v = 0; v < G.n; ++v)
for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
if (!equals(fi[q][v][color_set][n_del_left], -INF))
write_log("fi(" + my_to_string(q) + "," + my_to_string(v) + "," + my_to_string(color_set) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fi[q][v][color_set][n_del_left]) + "\n");
}
write_log("get fd(q = " + my_to_string(q) + ")\n");
for(int v = 0; v < G.n; ++v)
for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
if (!equals(fd[q][v][color_set][n_del_left], -INF))
write_log("fd(" + my_to_string(q) + "," + my_to_string(v) + "," + my_to_string(color_set) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fd[q][v][color_set][n_del_left]) + "\n");
}
write_log("get dp values at node " + my_to_string(q) + " done\n");
}
void DFS(int u) {
if (MODE == DEBUG_MODE) write_log("DFS have just enter node " + my_to_string(u) + "\n");
init_dp(u);
for(int k = 0; k < Q_tree.child[u].size(); ++k) {
if (MODE == DEBUG_MODE) write_log("start DFS child " + my_to_string(Q_tree.child[u][k]) + " of " + my_to_string(u) + "\n");
DFS(Q_tree.child[u][k]);
update_fm(u, k);
}
update_fi(u);
update_fd(u);
if (MODE == DEBUG_MODE) write_log("DFS subtree rooted at " + my_to_string(u) + " done\n");
if (MODE == DEBUG_MODE) write_log_dp_values(u);
}
//forward declaration
void trace_result_matching_fm(int q, int v, int color_set_use, int n_del_left);
void trace_result_matching_fi(int q, int v, int color_set_use, int n_del_left);
void trace_result_matching_fd(int q, int v, int color_set_use, int n_del_left);
void trace_result_matching_fm(int q, int v, int color_set_use, int n_del_left) {
if (MODE == DEBUG_MODE) write_log("trace_result_matching_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
if (MODE == DEBUG_MODE) write_log("with fm = " + my_double_to_string(fm[q][v][color_set_use][n_del_left]));
if (MODE == DEBUG_MODE) write_log("cost match mode " + my_to_string(q) + "->"
+ my_to_string(v) + " = " + my_double_to_string(get_similar_score(q, v)) + "\n");
map_to[q] = v;
for(int k_th_child = (int)(Q_tree.child[q].size()) - 1; k_th_child >= 0; --k_th_child) {
int child = Q_tree.child[q][k_th_child];
int u = trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left];
if (MODE == DEBUG_MODE) write_log("k_th_child = " + my_to_string(k_th_child)
+ ", child = " + my_to_string(child) + ", u = " + my_to_string(u) + "\n");
if (u == v) {
trace_result_matching_fd(child, v, trace_fm_color[q][k_th_child][v][color_set_use][n_del_left],
trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left]);
}
else if (u >= 0) {
if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(u)
+ "=" + my_double_to_string(G.get_weight(v, u)));
trace_result_matching_fm(child, u, trace_fm_color[q][k_th_child][v][color_set_use][n_del_left],
trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left]);
}
else { // u < 0
if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(-u-1)
+ "=" + my_double_to_string(G.get_weight(v, -u-1)));
trace_result_matching_fi(child, -u - 1, trace_fm_color[q][k_th_child][v][color_set_use][n_del_left],
trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left]);
}
int nxt_color_set = color_set_use - trace_fm_color[q][k_th_child][v][color_set_use][n_del_left];
int nxt_n_del_left = n_del_left - trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left];
color_set_use = nxt_color_set;
n_del_left = nxt_n_del_left;
}
if (MODE == DEBUG_MODE) write_log("trace_result_matching_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
}
void trace_result_matching_fi(int q, int v, int color_set_use, int n_del_left) {
if (MODE == DEBUG_MODE) write_log("trace_result_matching_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
if (MODE == DEBUG_MODE) write_log("with fi = " + my_double_to_string(fi[q][v][color_set_use][n_del_left]));
inserted_nodes.push_back(v);
int u = trace_fi_nxt_vertex[q][v][color_set_use][n_del_left];
if (MODE == DEBUG_MODE) write_log("u = " + my_to_string(u) + "\n");
if (u >= 0) {
if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(u)
+ "=" + my_double_to_string(G.get_weight(v, u)));
trace_result_matching_fm(q, u, color_set_use - (1 << color[v]), n_del_left);
}
else { //u < 0
if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(-u-1)
+ "=" + my_double_to_string(G.get_weight(v, -u-1)));
trace_result_matching_fi(q, -u - 1, color_set_use - (1 << color[v]), n_del_left);
}
if (MODE == DEBUG_MODE) write_log("trace_result_matching_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
}
void trace_result_matching_fd(int q, int v, int color_set_use, int n_del_left) {
if (MODE == DEBUG_MODE) write_log("trace_result_matching_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
if (MODE == DEBUG_MODE) write_log("with fd = " + my_double_to_string(fd[q][v][color_set_use][n_del_left]));
int u = trace_fd_nxt_vertex[q][v][color_set_use][n_del_left];
if (MODE == DEBUG_MODE) write_log("u = " + my_to_string(u) + "\n");
int q_nxt = Q_tree.child[q][0];
if (u == v) {
trace_result_matching_fd(q_nxt, v, color_set_use, n_del_left - 1);
}
else if (u >= 0) {
if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(u)
+ "=" + my_double_to_string(G.get_weight(v, u)));
trace_result_matching_fm(q_nxt, u, color_set_use, n_del_left - 1);
}
else { // u < 0
if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(-u-1)
+ "=" + my_double_to_string(G.get_weight(v, -u-1)));
trace_result_matching_fi(q_nxt, -u - 1, color_set_use, n_del_left - 1);
}
if (MODE == DEBUG_MODE) write_log("trace_result_matching_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
}
void get_result() {
if (MODE == DEBUG_MODE) write_log("get_result()...\n");
double this_best_score = -INF;
int root_map_to = -1, start_color_set = -1, start_n_del_left = -1;
for(int v = 0; v < G.n; ++v)
//map Q.root -> v
for(int color_set_use = 0; color_set_use < (1 << n_colors); ++color_set_use)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
if ((MODE == DEBUG_MODE) && (!equals(fm[Q_tree.root][v][color_set_use][n_del_left], -INF)))
write_log("fm(" + my_to_string(Q_tree.root) + "," + my_to_string(v) + "," + my_to_string(color_set_use) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fm[Q_tree.root][v][color_set_use][n_del_left]) + "\n");
if (maximize(this_best_score, fm[Q_tree.root][v][color_set_use][n_del_left])) {
root_map_to = v;
start_color_set = color_set_use;
start_n_del_left = n_del_left;
};
}
if (!equals(this_best_score, -INF)) this_best_score += pre_assign_score;
if (maximize(best_match_score, this_best_score)) {
best_root_map_to = root_map_to;
best_color_set = start_color_set;
best_n_del_left = start_n_del_left;
for(int v = 0; v < G.n; ++v) {
best_coloring[v] = color[v];
best_choosed[v] = choosed[v];
}
};
//cout << "this_best_score = " << this_best_score << endl;
if (MODE == DEBUG_MODE) write_log("this_best_score = " + my_double_to_string(this_best_score) + "\n");
if (MODE == DEBUG_MODE) write_log("best_match_score = " + my_double_to_string(best_match_score) + "\n");
if (MODE == DEBUG_MODE) write_log("get_result() done\n");
}
void random_coloring() {
if (MODE == DEBUG_MODE) write_log("start random coloring...\n");
for(int v = 0; v < G.n; ++v) {
color[v] = v % n_colors; //rnd.next(0, n_colors - 1); //rand() % n_colors;
if (MODE == DEBUG_MODE) write_log("color(" + my_to_string(v) + ") = " + my_to_string(color[v]) + "\n");
}
if (MODE == DEBUG_MODE) write_log("random coloring done\n");
}
void init_before_dp_on_tree() {
can_use_color_set.resize((1 << n_colors));
for(int color_set = 0; color_set < (1 << n_colors); ++color_set) {
bool ok = true;
for(int v = 0; v < G.n; ++v)
if (choosed[v] != -1)
if (get_bit(color_set, color[v]) == 1)
ok = false;
can_use_color_set[color_set] = ok;
}
pre_assign_score = 0.0;
for(int q = 0; q < Q_graph.n; ++q)
if (match[q] != -1)
pre_assign_score += get_similar_score(q, match[q]);
cout << "pre_assign_score = " << pre_assign_score << endl;
}
void dp_on_tree() {
for(int i = 0; i < G.n; ++i) cout << "color(" << i << ") = " << color[i] << endl;
for(int i = 0; i < Q_graph.n; ++i)
if (match[i] != -1) cout << i << "->" << match[i] << endl;
init_before_dp_on_tree();
if (MODE == DEBUG_MODE) write_log("start DFS from Q_tree.root = " + my_to_string(Q_tree.root) + "\n");
DFS(Q_tree.root);
if (MODE == DEBUG_MODE) write_log("DFS done\n");
get_result();
cout << "1 phase dp done\n";
}
void backtrack_assign(int qi, int set_choosed) {
if (qi >= graph_to_tree::dup_ver.size()) {
dp_on_tree();
return;
}
int q = graph_to_tree::dup_ver[qi];
for(int v = 0; v < G.n; ++v)
if ((choosed[v] == -1) && (get_bit(set_choosed, color[v]) == 0) && (G.get_deg(v) >= Q_graph.get_deg(qi) - n_del)) {
choosed[v] = q;
match[q] = v;
backtrack_assign(qi + 1, set_choosed + (1 << color[v]));
choosed[v] = -1;
match[q] = -1;
}
}
void pre_assignment() {
choosed.resize(G.n); best_choosed.resize(G.n);
for(int v = 0; v < G.n; ++v) choosed[v] = -1;
match.resize(Q_graph.n);
for(int q = 0; q < match.size(); ++q) match[q] = -1;
//backtrack_assign(0, 0);
match[1] = 2; choosed[2] = 1; dp_on_tree();
}
void run() {
random_coloring();
cout << "random coloring done\n";
pre_assignment();
}
void init_trace_best_matching() {
for(int v = 0; v < G.n; ++v) color[v] = best_coloring[v];
choosed = best_choosed;
for(int q = 0; q < Q_graph.n; ++q)
match[q] = -1;
for(int v = 0; v < G.n; ++v)
if (choosed[v] != -1)
match[choosed[v]] = v;
init_before_dp_on_tree();
DFS(Q_tree.root);
}
void trace_best_matching() {
inserted_nodes.resize(0);
map_to = vector<int>(Q_tree.n, -1);
if (MODE == DEBUG_MODE) write_log("start trace best matching...\n");
if (equals(best_match_score, -INF)) {
cout << "No matching found!\n";
write_log("No matching found!\n");
if (MODE == DEBUG_MODE) write_log("No matching found!\ntrace best matching done\n");
return;
}
write_log("best_match_score(in a connected component) = " + my_to_string(best_match_score) + "\n");
cout << "trace result with best_match_score = " << best_match_score << endl;
init_trace_best_matching();
trace_result_matching_fm(Q_tree.root, best_root_map_to, best_color_set, best_n_del_left);
if (MODE == DEBUG_MODE) write_log("trace best matching done\n");
write_log("map_to = {");
for(int q = 0; q < Q_tree.n; ++q) write_log(my_to_string(map_to[q]) + ",");
write_log("}\n");
write_log("inserted_nodes = {");
for(int v : inserted_nodes) write_log(my_to_string(v) + ",");
write_log("}\n");
}
void init_vector(vector<vector<vector<double>>> &v, int dim1, int dim2, int dim3, double val) {
assert(min(dim1, min(dim2, dim3)) >= 0);
v.resize(dim1);
for(int i = 0; i < dim1; ++i) {
v[i].resize(dim2);
for(int j = 0; j < dim2; ++j) {
v[i][j].resize(dim3);
for(int k = 0; k < dim3; ++k) {
v[i][j][k] = val;
}
}
}
}
void init_vector(vector<vector<vector<vector<double>>>> &v, int dim1, int dim2, int dim3, int dim4, double val) {
assert(min(dim1, min(dim2, min(dim3, dim4))) >= 0);
cout << "4 dims = " << dim1 << " " << dim2 << " " << dim3 << " " << dim4 << " " << dim1 * dim2 * dim3 * dim4 << endl;
v.resize(dim1);
for(int i = 0; i < dim1; ++i) {
v[i].resize(dim2);
for(int j = 0; j < dim2; ++j) {
v[i][j].resize(dim3);
for(int k = 0; k < dim3; ++k) {
v[i][j][k].resize(dim4);
for(int t = 0; t < dim4; ++t)
v[i][j][k][t] = val;
}
}
}
}
void init_vector(vector<vector<vector<vector<int>>>> &v, int dim1, int dim2, int dim3, int dim4, int val) {
assert(min(dim1, min(dim2, min(dim3, dim4))) >= 0);
v.resize(dim1);
for(int i = 0; i < dim1; ++i) {
v[i].resize(dim2);
for(int j = 0; j < dim2; ++j) {
v[i][j].resize(dim3);
for(int k = 0; k < dim3; ++k) {
v[i][j][k].resize(dim4);
for(int t = 0; t < dim4; ++t)
v[i][j][k][t] = val;
}
}
}
}
void init_vector(vector<vector<vector<vector<vector<int>>>>> &v, int dim1, int dim2, int dim3, int dim4, int dim5, double val) {
assert(min(dim1, min(dim2, min(dim3, min(dim4, dim5)))) >= 0);
v.resize(dim1);
for(int i = 0; i < dim1; ++i) {
v[i].resize(dim2);
for(int j = 0; j < dim2; ++j) {
v[i][j].resize(dim3);
for(int k = 0; k < dim3; ++k) {
v[i][j][k].resize(dim4);
for(int t = 0; t < dim4; ++t) {
v[i][j][k][t].resize(dim5);
for(int u = 0; u < dim5; ++u)
v[i][j][k][t][u] = val;
}
}
}
}
}
void init_vector_dimension() {
init_vector(fm, Q_tree.n, G.n, (1 << n_colors), n_del + 1, -INF);
init_vector(fi, Q_tree.n, G.n, (1 << n_colors), n_del + 1, -INF);
init_vector(fd, Q_tree.n, G.n, (1 << n_colors), n_del + 1, -INF);
init_vector(fm_temp, G.n, (1 << n_colors), n_del + 1, -INF);
trace_fm_color.resize(Q_tree.n);
trace_fm_n_del_left.resize(Q_tree.n);
trace_fm_nxt_vertex.resize(Q_tree.n);
init_vector(trace_fi_nxt_vertex, Q_tree.n, G.n, (1 << n_colors), n_del + 1, -1);
init_vector(trace_fd_nxt_vertex, Q_tree.n, G.n, (1 << n_colors), n_del + 1, -1);
for(int u = 0; u < Q_tree.n; ++u) {
init_vector(trace_fm_color[u], Q_tree.get_num_child(u), G.n, (1 << n_colors), n_del + 1, -1);
init_vector(trace_fm_n_del_left[u], Q_tree.get_num_child(u), G.n, (1 << n_colors), n_del + 1, -1);
init_vector(trace_fm_nxt_vertex[u], Q_tree.get_num_child(u), G.n, (1 << n_colors), n_del + 1, -1);
}
}
void solve() {
cout << "enter solve()\n";
init_vector_dimension();
cout << "init dim done\n";
int n_loops = 1;
best_match_score = -INF;
best_coloring.resize(G.n);
cout << "while loop\n";
while (n_loops > 0) {
n_loops--;
if (MODE == DEBUG_MODE) write_log("n_loops = " + my_to_string(n_loops));
run();
if (MODE == DEBUG_MODE) write_log("run() done\n");
}
trace_best_matching();
}
void set_graph(Graph &g) {
G = g;
}
}
namespace tree_match_graph {
Graph G;
vector<int> match;
double best_match_score;
int best_root_map_to, best_color_set, best_n_del_left;
vector<int> best_coloring;
vector<vector<vector<vector<double>>>> fm, fi, fd; //f(u, v, color_set_use, num_deletion_left)
vector<vector<vector<double>>> fm_temp;
vector<vector<vector<vector<vector<int>>>>> trace_fm_color, trace_fm_n_del_left, trace_fm_nxt_vertex;
vector<vector<vector<vector<int>>>> trace_fi_nxt_vertex, trace_fd_nxt_vertex;
vector<int> choosed, best_choosed;
vector<bool> can_use_color_set;
double pre_assign_score;
//variables stored result
vector<int> inserted_nodes;
vector<int> map_to; //map_to[q] = v => q is map to v; map_to[q] = -1 => q is deleted node
double get_similar_score(int q, int v) {
return similar_score[graph_to_tree::origin[q]][v];
}
bool can_map(int color_set_use, int v) {
if (!can_use_color_set[color_set_use]) return false;
if (choosed[v] != -1) return true;
return (get_bit(color_set_use, color[v]) == 1);
}
bool can_map(int u, int color_set_use, int v) {
int ou = graph_to_tree::origin[u];
if (match[ou] == -1)
return (can_map(color_set_use, v) && homologous(ou, v));
else return (match[ou] == v);
}
bool can_delete(int q) {
int oq = graph_to_tree::origin[q];
if (match[oq] != -1) return false;
return (Q_graph.get_deg(oq) == 2);
}
bool can_insert(int v) {
return ((G.get_deg(v) == 2) && (choosed[v] == -1));
}
int add_vertex(int color_set, int vertex) {
return (choosed[vertex] == -1) ? (color_set + (1 << color[vertex])) : color_set;
}
int remove_vertex(int color_set, int vertex) {
return (choosed[vertex] == -1) ? (color_set - (1 << color[vertex])) : color_set;
}
void update_fm(int q, int v, int color_set_prev, int n_del_left_prev, int k_th_child, int color_set_on_child, int n_del_left_on_child) {
if (!can_use_color_set[color_set_prev] || !can_use_color_set[color_set_on_child]) return;
if (equals(fm[q][v][color_set_prev][n_del_left_prev], -INF)) return;
if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_prev = "
+ my_to_string(color_set_prev) + ", n_del_left_prev = " + my_to_string(n_del_left_prev)
+ ", k_th_child = " + my_to_string(k_th_child) + ", color_set_on_child = "
+ my_to_string(color_set_on_child) + ", n_del_left_on_child = " + my_to_string(n_del_left_on_child) + ")...\n");
int color_set_use = color_set_prev | color_set_on_child;
int n_del_left = n_del_left_prev + n_del_left_on_child;
int child = Q_tree.child[q][k_th_child];
for(pair<int, double> &neighbor : G.adj[v]) {
int u = neighbor.first; double w = neighbor.second;
if (can_map(child, color_set_on_child, u)) {
//map child -> u
if (!equals(fm[child][u][color_set_on_child][n_del_left_on_child], -INF))
if (maximize(fm_temp[v][color_set_use][n_del_left], fm[q][v][color_set_prev][n_del_left_prev]
+ fm[child][u][color_set_on_child][n_del_left_on_child] + w))
{
trace_fm_color[q][k_th_child][v][color_set_use][n_del_left] = color_set_on_child;
trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left] = n_del_left_on_child;
trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left] = u;
};
//insert child
if (can_insert(u) && (!equals(fi[child][u][color_set_on_child][n_del_left_on_child], -INF))) {
if (maximize(fm_temp[v][color_set_use][n_del_left], fm[q][v][color_set_prev][n_del_left_prev]
+ fi[child][u][color_set_on_child][n_del_left_on_child] + w))
{
trace_fm_color[q][k_th_child][v][color_set_use][n_del_left] = color_set_on_child;
trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left] = n_del_left_on_child;
trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left] = - u - 1;
};
}
}
}
if (can_delete(child) && (!equals(fd[child][v][color_set_on_child][n_del_left_on_child], -INF))) {
//delete child
if (maximize(fm_temp[v][color_set_use][n_del_left], fm[q][v][color_set_prev][n_del_left_prev]
+ fd[child][v][color_set_on_child][n_del_left_on_child]))
{
trace_fm_color[q][k_th_child][v][color_set_use][n_del_left] = color_set_on_child;
trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left] = n_del_left_on_child;
trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left] = v; //keep
};
}
if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_prev = "
+ my_to_string(color_set_prev) + ", n_del_left_prev = " + my_to_string(n_del_left_prev)
+ ", k_th_child = " + my_to_string(k_th_child) + ", color_set_on_child = "
+ my_to_string(color_set_on_child) + ", n_del_left_on_child = " + my_to_string(n_del_left_on_child) + ") done\n");
}
void update_fm(int q, int k_th_child) {
if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", k_th_child = " + my_to_string(k_th_child) + ")....\n");
for(int v = 0; v < G.n; ++v)
for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
fm_temp[v][color_set][n_del_left] = -INF;
for(int color_set_prev = (1 << n_colors) - 1; color_set_prev >= 0; --color_set_prev)
if (can_use_color_set[color_set_prev])
for(int n_del_left_prev = 0; n_del_left_prev <= n_del; ++n_del_left_prev) {
for(int color_set_on_child = 0; color_set_on_child < (1 << n_colors); ++color_set_on_child)
if ((can_use_color_set[color_set_on_child]) &&((color_set_prev + color_set_on_child) == (color_set_prev | color_set_on_child)))
for(int n_del_left_on_child = 0; n_del_left_on_child <= n_del - n_del_left_prev; ++n_del_left_on_child)
for(int v = 0; v < G.n; ++v) {
if (can_map(q, color_set_prev, v))
update_fm(q, v, color_set_prev, n_del_left_prev, k_th_child, color_set_on_child, n_del_left_on_child);
}
}
for(int v = 0; v < G.n; ++v)
for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
fm[q][v][color_set][n_del_left] = fm_temp[v][color_set][n_del_left];
if (MODE == DEBUG_MODE) write_log("update_fm(q = " + my_to_string(q) + ", k_th_child = " + my_to_string(k_th_child) + ") done\n");
}
// color[v] belongs to color_set_use
void update_fi(int q, int v, int color_set_use, int n_del_left) {
if (!can_use_color_set[color_set_use]) return;
if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
int new_color_set = color_set_use - (1 << color[v]);
for(pair<int, double> &neighbor : G.adj[v]) {
int u = neighbor.first; double w = neighbor.second;
if (can_map(new_color_set, u)) {
if (can_map(q, new_color_set, u) && (!equals(fm[q][u][new_color_set][n_del_left], -INF)))
if (maximize(fi[q][v][color_set_use][n_del_left], per_ins + fm[q][u][new_color_set][n_del_left] + w)) {
trace_fi_nxt_vertex[q][v][color_set_use][n_del_left] = u;
};
if (can_insert(u) && (!equals(fi[q][u][new_color_set][n_del_left], -INF))) {
maximize(fi[q][v][color_set_use][n_del_left], per_ins + fi[q][u][new_color_set][n_del_left] + w);
trace_fi_nxt_vertex[q][v][color_set_use][n_del_left] = - u - 1;
}
}
}
if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
}
void update_fi(int q) {
if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ")....\n");
for(int v = 0; v < G.n; ++v)
if (can_insert(v))
for(int color_set_use = 0; color_set_use < (1 << n_colors); ++color_set_use)
if (can_use_color_set[color_set_use])
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
if (can_map(color_set_use, v))
update_fi(q, v, color_set_use, n_del_left);
if (MODE == DEBUG_MODE) write_log("update_fi(q = " + my_to_string(q) + ") done\n");
}
void update_fd(int q, int v, int color_set_use, int n_del_left) {
if (!can_use_color_set[color_set_use]) return;
if (n_del_left < 1) return;
if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = " + my_to_string(color_set_use)
+ ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
int q_nxt = Q_tree.child[q][0];
for(pair<int, double> &neighbor : G.adj[v]) {
int u = neighbor.first; double w = neighbor.second;
if (can_map(color_set_use, u)) {
if (can_map(q_nxt, color_set_use, u) && (!equals(fm[q_nxt][u][color_set_use][n_del_left - 1], -INF))) {
if (maximize(fd[q][v][color_set_use][n_del_left], per_del + fm[q_nxt][u][color_set_use][n_del_left - 1] + w)) {
trace_fd_nxt_vertex[q][v][color_set_use][n_del_left] = u;
};
}
if (!equals(fi[q_nxt][u][color_set_use][n_del_left - 1], -INF)) {
if (maximize(fd[q][v][color_set_use][n_del_left], per_del + fi[q_nxt][u][color_set_use][n_del_left - 1] + w)) {
trace_fd_nxt_vertex[q][v][color_set_use][n_del_left] = - u - 1;
};
}
}
}
if (can_delete(q_nxt) && (n_del_left > 0) && (!equals(fd[q_nxt][v][color_set_use][n_del_left - 1], -INF))) {
if (maximize(fd[q][v][color_set_use][n_del_left], per_del + fd[q_nxt][v][color_set_use][n_del_left - 1])) {
}
trace_fd_nxt_vertex[q][v][color_set_use][n_del_left] = v;
};
}
if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = " + my_to_string(color_set_use)
+ ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
}
void update_fd(int q) {
if (!can_delete(q)) return;
if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ")....\n");
for(int v = 0; v < G.n; ++v)
for(int color_set_use = 0; color_set_use < (1 << n_colors); ++color_set_use)
if (can_use_color_set[color_set_use])
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left)
update_fd(q, v, color_set_use, n_del_left);
if (MODE == DEBUG_MODE) write_log("update_fd(q = " + my_to_string(q) + ") done\n");
}
void init_dp(int q) {
if (MODE == DEBUG_MODE) write_log("init_dp(q = " + my_to_string(q) + ")...\n");
for(int v = 0; v < G.n; ++v)
for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
fm[q][v][color_set][n_del_left] = -INF;
fi[q][v][color_set][n_del_left] = -INF;
fd[q][v][color_set][n_del_left] = -INF;
}
for(int v = 0; v < G.n; ++v)
if (can_map(q, (1 << color[v]), v)) {
fm[q][v][add_vertex(0, v)][0] = (match[q] == -1) ? get_similar_score(q, v) : 0.0;
}
if (MODE == DEBUG_MODE) write_log("init_dp(q = " + my_to_string(q) + ") done\n");
}
void write_log_dp_values(int q) {
write_log("get dp values at node " + my_to_string(q) + "...\n");
write_log("get fm(q = " + my_to_string(q) + ")\n");
for(int v = 0; v < G.n; ++v)
for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
if (!equals(fm[q][v][color_set][n_del_left], -INF))
write_log("fm(" + my_to_string(q) + "," + my_to_string(v) + "," + my_to_string(color_set) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fm[q][v][color_set][n_del_left]) + "\n");
}
write_log("get fi(q = " + my_to_string(q) + ")\n");
for(int v = 0; v < G.n; ++v)
for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
if (!equals(fi[q][v][color_set][n_del_left], -INF))
write_log("fi(" + my_to_string(q) + "," + my_to_string(v) + "," + my_to_string(color_set) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fi[q][v][color_set][n_del_left]) + "\n");
}
write_log("get fd(q = " + my_to_string(q) + ")\n");
for(int v = 0; v < G.n; ++v)
for(int color_set = 0; color_set < (1 << n_colors); ++color_set)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
if (!equals(fd[q][v][color_set][n_del_left], -INF))
write_log("fd(" + my_to_string(q) + "," + my_to_string(v) + "," + my_to_string(color_set) + "," + my_to_string(n_del_left) + ") = " + my_double_to_string(fd[q][v][color_set][n_del_left]) + "\n");
}
write_log("get dp values at node " + my_to_string(q) + " done\n");
}
void DFS(int u) {
if (MODE == DEBUG_MODE) write_log("DFS have just enter node " + my_to_string(u) + "\n");
init_dp(u);
for(int k = 0; k < Q_tree.child[u].size(); ++k) {
if (MODE == DEBUG_MODE) write_log("start DFS child " + my_to_string(Q_tree.child[u][k]) + " of " + my_to_string(u) + "\n");
DFS(Q_tree.child[u][k]);
update_fm(u, k);
}
update_fi(u);
update_fd(u);
if (MODE == DEBUG_MODE) write_log("DFS subtree rooted at " + my_to_string(u) + " done\n");
if (MODE == DEBUG_MODE) write_log_dp_values(u);
}
//forward declaration
void trace_result_matching_fm(int q, int v, int color_set_use, int n_del_left);
void trace_result_matching_fi(int q, int v, int color_set_use, int n_del_left);
void trace_result_matching_fd(int q, int v, int color_set_use, int n_del_left);
void trace_result_matching_fm(int q, int v, int color_set_use, int n_del_left) {
if (MODE == DEBUG_MODE) write_log("trace_result_matching_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
if (MODE == DEBUG_MODE) write_log("with fm = " + my_double_to_string(fm[q][v][color_set_use][n_del_left]));
if (MODE == DEBUG_MODE) write_log("cost match mode " + my_to_string(q) + "->"
+ my_to_string(v) + " = " + my_double_to_string(get_similar_score(q, v)) + "\n");
map_to[q] = v;
for(int k_th_child = (int)(Q_tree.child[q].size()) - 1; k_th_child >= 0; --k_th_child) {
int child = Q_tree.child[q][k_th_child];
int u = trace_fm_nxt_vertex[q][k_th_child][v][color_set_use][n_del_left];
if (MODE == DEBUG_MODE) write_log("k_th_child = " + my_to_string(k_th_child)
+ ", child = " + my_to_string(child) + ", u = " + my_to_string(u) + "\n");
if (u == v) {
trace_result_matching_fd(child, v, trace_fm_color[q][k_th_child][v][color_set_use][n_del_left],
trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left]);
}
else if (u >= 0) {
if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(u)
+ "=" + my_double_to_string(G.get_weight(v, u)));
trace_result_matching_fm(child, u, trace_fm_color[q][k_th_child][v][color_set_use][n_del_left],
trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left]);
}
else { // u < 0
if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(-u-1)
+ "=" + my_double_to_string(G.get_weight(v, -u-1)));
trace_result_matching_fi(child, -u - 1, trace_fm_color[q][k_th_child][v][color_set_use][n_del_left],
trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left]);
}
int nxt_color_set = color_set_use - trace_fm_color[q][k_th_child][v][color_set_use][n_del_left];
int nxt_n_del_left = n_del_left - trace_fm_n_del_left[q][k_th_child][v][color_set_use][n_del_left];
color_set_use = nxt_color_set;
n_del_left = nxt_n_del_left;
}
if (MODE == DEBUG_MODE) write_log("trace_result_matching_fm(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
}
void trace_result_matching_fi(int q, int v, int color_set_use, int n_del_left) {
if (MODE == DEBUG_MODE) write_log("trace_result_matching_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
if (MODE == DEBUG_MODE) write_log("with fi = " + my_double_to_string(fi[q][v][color_set_use][n_del_left]));
inserted_nodes.push_back(v);
int u = trace_fi_nxt_vertex[q][v][color_set_use][n_del_left];
if (MODE == DEBUG_MODE) write_log("u = " + my_to_string(u) + "\n");
if (u >= 0) {
if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(u)
+ "=" + my_double_to_string(G.get_weight(v, u)));
trace_result_matching_fm(q, u, color_set_use - (1 << color[v]), n_del_left);
}
else { //u < 0
if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(-u-1)
+ "=" + my_double_to_string(G.get_weight(v, -u-1)));
trace_result_matching_fi(q, -u - 1, color_set_use - (1 << color[v]), n_del_left);
}
if (MODE == DEBUG_MODE) write_log("trace_result_matching_fi(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
}
void trace_result_matching_fd(int q, int v, int color_set_use, int n_del_left) {
if (MODE == DEBUG_MODE) write_log("trace_result_matching_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ")...\n");
if (MODE == DEBUG_MODE) write_log("with fd = " + my_double_to_string(fd[q][v][color_set_use][n_del_left]));
int u = trace_fd_nxt_vertex[q][v][color_set_use][n_del_left];
if (MODE == DEBUG_MODE) write_log("u = " + my_to_string(u) + "\n");
int q_nxt = Q_tree.child[q][0];
if (u == v) {
trace_result_matching_fd(q_nxt, v, color_set_use, n_del_left - 1);
}
else if (u >= 0) {
if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(u)
+ "=" + my_double_to_string(G.get_weight(v, u)));
trace_result_matching_fm(q_nxt, u, color_set_use, n_del_left - 1);
}
else { // u < 0
if (MODE == DEBUG_MODE) write_log("edge cost = " + my_to_string(v) + "->" + my_to_string(-u-1)
+ "=" + my_double_to_string(G.get_weight(v, -u-1)));
trace_result_matching_fi(q_nxt, -u - 1, color_set_use, n_del_left - 1);
}
if (MODE == DEBUG_MODE) write_log("trace_result_matching_fd(q = " + my_to_string(q) + ", v = " + my_to_string(v) + ", color_set_use = "
+ my_to_string(color_set_use) + ", n_del_left = " + my_to_string(n_del_left) + ") done\n");
}
void get_result() {
if (MODE == DEBUG_MODE) write_log("get_result()...\n");
double this_best_score = -INF;
int root_map_to = -1, start_color_set = -1, start_n_del_left = -1;
for(int v = 0; v < G.n; ++v)
//map Q.root -> v
for(int color_set_use = 0; color_set_use < (1 << n_colors); ++color_set_use)
for(int n_del_left = 0; n_del_left <= n_del; ++n_del_left) {
if ((MODE == DEBUG_MODE) && (!equals(fm[Q_tree.root][v][color_set_use][n_del_left], -INF)))
write_log("fm(" + my_to_string(Q_tree.root) + "," + my_to_string(v) + "," + my_to_string(color_set_use) + "," +