tree_decomposition.cpp

#include "tree_decomposition.h"
#include "io_helper.h"
#include <string>
#include <vector>
#include <algorithm>
#include <cassert>
#include "heap.h"
#include "tiny_id_func.h"
#include "contraction_graph.h"
#include "id_multi_func.h"
using namespace std;

void print_tree_decompostion(const std::string&file_name, ArrayIDIDFunc tail, ArrayIDIDFunc head, const ArrayIDIDFunc&order){
	const int node_count = tail.image_count();
	assert(node_count > 1);

	auto inv_order = inverse_permutation(order);
	tail = chain(tail, inv_order);
	head = chain(head, inv_order);

	vector<vector<int>>nodes_in_bag;
	ArrayIDFunc<vector<int>>bags_of_node(node_count);

	auto is_left_subset_of_right = [](const std::vector<int>&l, const std::vector<int>&r){
		auto i = l.begin(), j = r.begin();

		for(;;){
			if(i == l.end())
				return true;
			if(j == r.end())
				return false;

			if(*i < *j)
				return false;
			if(*i == *j)
				++i;
			++j;
		}
	};

	auto compute_intersection_size = [](const std::vector<int>&l, const std::vector<int>&r){
		auto i = l.begin(), j = r.begin();
		int n = 0;
		for(;;){
			if(i == l.end() || j == r.end())
				return n;
			if(*i < *j)
				++i;
			else if(*i > *j)
				++j;
			else{
				++i;
				++j;
				++n;
			}
		}
	};

	auto on_new_potential_maximal_clique = [&](int lowest_node_in_clique, std::vector<int>clique){
		for(auto b:bags_of_node(lowest_node_in_clique))
			if(is_left_subset_of_right(clique, nodes_in_bag[b]))
				return;
		int bag_id = nodes_in_bag.size();
		for(auto x:clique)
			bags_of_node[x].push_back(bag_id);
		nodes_in_bag.push_back(move(clique));
	};


	{
		BitIDFunc is_root(node_count);
		is_root.fill(true);
		std::vector<int>upper_neighborhood_of_z;
		int z = -1;
		compute_chordal_supergraph(
			tail, head, 
			[&](int x, int y){
				is_root.set(x, false);
				if(z != -1 && z != x){
					upper_neighborhood_of_z.push_back(z);
					sort(upper_neighborhood_of_z.begin(), upper_neighborhood_of_z.end());
					on_new_potential_maximal_clique(z, move(upper_neighborhood_of_z));
					upper_neighborhood_of_z.clear();
				}
				z = x;
				upper_neighborhood_of_z.push_back(y);
			}
		);
		upper_neighborhood_of_z.push_back(z);
		sort(upper_neighborhood_of_z.begin(), upper_neighborhood_of_z.end());
		on_new_potential_maximal_clique(z, move(upper_neighborhood_of_z));
								
		for(int x=0; x<node_count; ++x){
			if(is_root(x)){
				on_new_potential_maximal_clique(x, {x});
			}
		}
	}



	int bag_count = nodes_in_bag.size();

	int maximum_bag_size = 0;
	for(auto&b:nodes_in_bag)
		if((int)b.size() > maximum_bag_size)
			maximum_bag_size = b.size();


	save_text_file(
		file_name, 
		[&](std::ostream&out){
			out << "s td "<< nodes_in_bag.size() << ' ' << maximum_bag_size << ' ' << node_count << '\n';
			for(int i=0; i<bag_count; ++i){
				out << "b "<<(i+1);
				for(auto x:nodes_in_bag[i])
					out << ' ' << (order(x)+1);
				out << '\n';
				
			}

			{
				auto output_backbone_edge = [&](int b, int p){
					out << (b+1) << ' ' << (p+1) << '\n';
				};

				std::vector<int>tail, head, weight;

				for(int b=0; b<bag_count; ++b){
					vector<int>neighbor_bags;
					for(auto x:nodes_in_bag[b]){
						vector<int>tmp;
						std::set_union(
							bags_of_node[x].begin(), bags_of_node[x].end(),
							neighbor_bags.begin(), neighbor_bags.end(),
							std::back_inserter(tmp)
						);
						neighbor_bags.swap(tmp);
					}
					for(auto p:neighbor_bags){
						if(p != b){
							tail.push_back(b);
							head.push_back(p);
							weight.push_back(compute_intersection_size(nodes_in_bag[b], nodes_in_bag[p]));
						}
					}
				}

				int arc_count = tail.size();

				auto out_arc = invert_id_id_func(
					id_id_func(
						arc_count, bag_count, 
						[&](unsigned a){return tail[a];}
					)
				);

				BitIDFunc in_tree(bag_count);
				in_tree.fill(false);
				max_id_heap<int>q(arc_count);
		
				for(int b=0; b<bag_count; ++b){
					if(!in_tree(b)){
						if(b != 0)
							output_backbone_edge(0, b);
						in_tree.set(b, true);
						for(int a:out_arc(b))
							q.push(a, weight[a]);
						while(!q.empty()){
							int xy = q.pop();
							
							int x = tail[xy];
							int y = head[xy];

							assert(in_tree(x));

							if(!in_tree(y)){
								output_backbone_edge(x, y);
								in_tree.set(y, true);
								for(int yz:out_arc(y)){
									assert(!q.contains(yz));
									q.push(yz, weight[yz]);
								}
							}
						}
						
					}
				}
			}
		}
	);
}