<commit_before>/**
 * Copyright 2013 <NAME>
 *
 * This file is part of SA-GraphLib.
 *
 * SA-GraphLib is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * SA-GraphLib is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with SA-GraphLib.  If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * This program computes the overlap of each pair of vertices
 * given by the user.
 */

#include <signal.h>
#include <google/profiler.h>

#include <tr1/unordered_set>

#include "graph_engine.h"

/**
 * This contains all vertices that we want to compute pair-wise overlap.
 */
std::vector<vertex_id_t> overlap_vertices;

template<class InputIterator1, class InputIterator2, class Skipper,
	class Merger, class OutputIterator>
size_t unique_merge(InputIterator1 it1, InputIterator1 last1,
		InputIterator2 it2, InputIterator2 last2, Skipper skip,
		Merger merge, OutputIterator result)
{
	OutputIterator result_begin = result;
	while (it1 != last1 && it2 != last2) {
		if (*it2 < *it1) {
			typename std::iterator_traits<OutputIterator>::value_type v = *it2;
			++it2;
			while (it2 != last2 && v == *it2) {
				v = merge(v, *it2);
				++it2;
			}
			if (!skip(v))
				*(result++) = v;
		}
		else if (*it1 < *it2) {
			typename std::iterator_traits<OutputIterator>::value_type v = *it1;
			++it1;
			while (it1 != last1 && v == *it1) {
				v = merge(v, *it1);
				++it1;
			}
			if (!skip(v))
				*(result++) = v;
		}
		else {
			typename std::iterator_traits<OutputIterator>::value_type v = *it1;
			v = merge(v, *it2);
			++it2;
			while (it2 != last2 && v == *it2) {
				v = merge(v, *it2);
				++it2;
			}
			++it1;
			while (it1 != last1 && v == *it1) {
				v = merge(v, *it1);
				++it1;
			}
			if (!skip(v))
				*(result++) = v;
		}
	}

	while (it1 != last1) {
		typename std::iterator_traits<OutputIterator>::value_type v = *it1;
		++it1;
		while (it1 != last1 && v == *it1) {
			v = merge(v, *it1);
			++it1;
		}
		if (!skip(v))
			*(result++) = v;
	}

	while (it2 != last2) {
		typename std::iterator_traits<OutputIterator>::value_type v = *it2;
		++it2;
		while (it2 != last2 && v == *it2) {
			v = merge(v, *it2);
			++it2;
		}
		if (!skip(v))
			*(result++) = v;
	}
	return result - result_begin;
}

class skip_self
{
	vertex_id_t id;
public:
	skip_self(vertex_id_t id) {
		this->id = id;
	}

	bool operator()(vertex_id_t id) {
		return this->id == id;
	}
};

class merge_edge
{
public:
	vertex_id_t operator()(vertex_id_t e1, vertex_id_t e2) {
		assert(e1 == e2);
		return e1;
	}
};

size_t get_unique_neighbors(const page_vertex &vertex,
		std::vector<vertex_id_t> &neighbors)
{
	neighbors.resize(vertex.get_num_edges(edge_type::BOTH_EDGES));
	size_t num_neighbors = unique_merge(
			vertex.get_neigh_begin(edge_type::IN_EDGE),
			vertex.get_neigh_end(edge_type::IN_EDGE),
			vertex.get_neigh_begin(edge_type::OUT_EDGE),
			vertex.get_neigh_end(edge_type::OUT_EDGE),
			skip_self(vertex.get_id()), merge_edge(),
			neighbors.begin());
	neighbors.resize(num_neighbors);
	return num_neighbors;
}

size_t get_common_vertices(const std::vector<vertex_id_t> &vertices1,
		const std::vector<vertex_id_t> &vertices2)
{
	size_t common = 0;
	size_t i, j;
	// We assume both vectors are sorted in the ascending order.
	// We only need to scan them together to extract the common elements.
	for (i = 0, j = 0; i < vertices1.size() && j < vertices2.size();) {
		if (vertices1[i] == vertices2[j]) {
			common++;
			i++;
			j++;
		}
		else if (vertices1[i] > vertices2[j])
			j++;
		else
			i++;

	}
	return common;
}

size_t get_union_vertices(const std::vector<vertex_id_t> &vertices1,
		const std::vector<vertex_id_t> &vertices2)
{
	std::tr1::unordered_set<vertex_id_t> set(vertices1.begin(),
			vertices1.end());
	set.insert(vertices2.begin(), vertices2.end());
	return set.size();
}

class union_set
{
	std::tr1::unordered_set<vertex_id_t> set;
	pthread_mutex_t lock;
public:
	union_set() {
		pthread_mutex_init(&lock, NULL);
	}

	void add(const std::vector<vertex_id_t> &vec) {
		pthread_mutex_lock(&lock);
		set.insert(vec.begin(), vec.end());
		pthread_mutex_unlock(&lock);
	}

	size_t get_size() const {
		return set.size();
	}
} vertex_union;

class intersection_set
{
	int num_added;
	std::vector<vertex_id_t> set;
	pthread_mutex_t lock;
public:
	intersection_set() {
		num_added = 0;
		pthread_mutex_init(&lock, NULL);
	}

	void add(const std::vector<vertex_id_t> &vec);

	size_t get_size() const {
		return set.size();
	}

	vertex_id_t get(int idx) const {
		return set[idx];
	}
} vertex_intersection;

void intersection_set::add(const std::vector<vertex_id_t> &vec)
{
	std::vector<vertex_id_t> copy(vec);
	std::sort(copy.begin(), copy.end());

	std::vector<vertex_id_t> new_set;
	pthread_mutex_lock(&lock);
	num_added++;
	if (num_added == 1) {
		set = copy;
	}
	else {
		size_t i, j;
		// We assume both vectors are sorted in the ascending order.
		// We only need to scan them together to extract the common elements.
		for (i = 0, j = 0; i < set.size() && j < copy.size();) {
			if (set[i] == copy[j]) {
				new_set.push_back(set[i]);
				i++;
				j++;
			}
			else if (set[i] > copy[j])
				j++;
			else
				i++;

		}
		set = new_set;
	}
	pthread_mutex_unlock(&lock);
}

class overlap_vertex: public compute_vertex
{
	unsigned num_joined;
	std::vector<vertex_id_t> *neighbors;
public:
	overlap_vertex() {
		num_joined = 0;
		neighbors = NULL;
	}

	overlap_vertex(vertex_id_t id, const vertex_index *index1): compute_vertex(
			id, index1) {
		num_joined = 0;
		neighbors = NULL;
	}

	bool run(graph_engine &graph, const page_vertex &vertex) {
		if (vertex.get_id() == get_id())
			return run_on_itself(graph, vertex);
		else
			return run_on_neighbor(graph, vertex);
	}

	bool run_on_itself(graph_engine &graph, const page_vertex &vertex) {
		neighbors = new std::vector<vertex_id_t>();
		get_unique_neighbors(vertex, *neighbors);
		std::sort(neighbors->begin(), neighbors->end());
		vertex_union.add(*neighbors);
		vertex_intersection.add(*neighbors);
		std::vector<vertex_id_t> req_vertices;
		BOOST_FOREACH(vertex_id_t id, overlap_vertices) {
			if (id != get_id())
				req_vertices.push_back(id);
		}
		graph.request_vertices(*this, req_vertices.data(), req_vertices.size());
		return false;
	}

	bool run_on_neighbor(graph_engine &graph, const page_vertex &vertex) {
		num_joined++;
		std::vector<vertex_id_t> neigh_neighbors;
		get_unique_neighbors(vertex, neigh_neighbors);
		std::sort(neigh_neighbors.begin(), neigh_neighbors.end());
		size_t common = get_common_vertices(*neighbors, neigh_neighbors);
		size_t vunion = get_union_vertices(*neighbors,
				neigh_neighbors);
		printf("v%u:v%u, common: %ld, union: %ld, overlap: %f\n",
				get_id(), vertex.get_id(), common, vunion,
				((double) common) / vunion);
		// We only need to join with all other vertices.
		return num_joined == overlap_vertices.size() - 1;
	}

	void run_on_messages(graph_engine &,<commit_msg>[Graph]: overlap use the new interface.<commit_after>/**
 * Copyright 2013 <NAME>
 *
 * This file is part of SA-GraphLib.
 *
 * SA-GraphLib is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * SA-GraphLib is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with SA-GraphLib.  If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * This program computes the overlap of each pair of vertices
 * given by the user.
 */

#include <signal.h>
#include <google/profiler.h>

#include <tr1/unordered_set>

#include "graph_engine.h"

/**
 * This contains all vertices that we want to compute pair-wise overlap.
 */
std::vector<vertex_id_t> overlap_vertices;

template<class InputIterator1, class InputIterator2, class Skipper,
	class Merger, class OutputIterator>
size_t unique_merge(InputIterator1 it1, InputIterator1 last1,
		InputIterator2 it2, InputIterator2 last2, Skipper skip,
		Merger merge, OutputIterator result)
{
	OutputIterator result_begin = result;
	while (it1 != last1 && it2 != last2) {
		if (*it2 < *it1) {
			typename std::iterator_traits<OutputIterator>::value_type v = *it2;
			++it2;
			while (it2 != last2 && v == *it2) {
				v = merge(v, *it2);
				++it2;
			}
			if (!skip(v))
				*(result++) = v;
		}
		else if (*it1 < *it2) {
			typename std::iterator_traits<OutputIterator>::value_type v = *it1;
			++it1;
			while (it1 != last1 && v == *it1) {
				v = merge(v, *it1);
				++it1;
			}
			if (!skip(v))
				*(result++) = v;
		}
		else {
			typename std::iterator_traits<OutputIterator>::value_type v = *it1;
			v = merge(v, *it2);
			++it2;
			while (it2 != last2 && v == *it2) {
				v = merge(v, *it2);
				++it2;
			}
			++it1;
			while (it1 != last1 && v == *it1) {
				v = merge(v, *it1);
				++it1;
			}
			if (!skip(v))
				*(result++) = v;
		}
	}

	while (it1 != last1) {
		typename std::iterator_traits<OutputIterator>::value_type v = *it1;
		++it1;
		while (it1 != last1 && v == *it1) {
			v = merge(v, *it1);
			++it1;
		}
		if (!skip(v))
			*(result++) = v;
	}

	while (it2 != last2) {
		typename std::iterator_traits<OutputIterator>::value_type v = *it2;
		++it2;
		while (it2 != last2 && v == *it2) {
			v = merge(v, *it2);
			++it2;
		}
		if (!skip(v))
			*(result++) = v;
	}
	return result - result_begin;
}

class skip_self
{
	vertex_id_t id;
public:
	skip_self(vertex_id_t id) {
		this->id = id;
	}

	bool operator()(vertex_id_t id) {
		return this->id == id;
	}
};

class merge_edge
{
public:
	vertex_id_t operator()(vertex_id_t e1, vertex_id_t e2) {
		assert(e1 == e2);
		return e1;
	}
};

size_t get_unique_neighbors(const page_vertex &vertex,
		std::vector<vertex_id_t> &neighbors)
{
	neighbors.resize(vertex.get_num_edges(edge_type::BOTH_EDGES));
	size_t num_neighbors = unique_merge(
			vertex.get_neigh_begin(edge_type::IN_EDGE),
			vertex.get_neigh_end(edge_type::IN_EDGE),
			vertex.get_neigh_begin(edge_type::OUT_EDGE),
			vertex.get_neigh_end(edge_type::OUT_EDGE),
			skip_self(vertex.get_id()), merge_edge(),
			neighbors.begin());
	neighbors.resize(num_neighbors);
	return num_neighbors;
}

size_t get_common_vertices(const std::vector<vertex_id_t> &vertices1,
		const std::vector<vertex_id_t> &vertices2)
{
	size_t common = 0;
	size_t i, j;
	// We assume both vectors are sorted in the ascending order.
	// We only need to scan them together to extract the common elements.
	for (i = 0, j = 0; i < vertices1.size() && j < vertices2.size();) {
		if (vertices1[i] == vertices2[j]) {
			common++;
			i++;
			j++;
		}
		else if (vertices1[i] > vertices2[j])
			j++;
		else
			i++;

	}
	return common;
}

size_t get_union_vertices(const std::vector<vertex_id_t> &vertices1,
		const std::vector<vertex_id_t> &vertices2)
{
	std::tr1::unordered_set<vertex_id_t> set(vertices1.begin(),
			vertices1.end());
	set.insert(vertices2.begin(), vertices2.end());
	return set.size();
}

class union_set
{
	std::tr1::unordered_set<vertex_id_t> set;
	pthread_mutex_t lock;
public:
	union_set() {
		pthread_mutex_init(&lock, NULL);
	}

	void add(const std::vector<vertex_id_t> &vec) {
		pthread_mutex_lock(&lock);
		set.insert(vec.begin(), vec.end());
		pthread_mutex_unlock(&lock);
	}

	size_t get_size() const {
		return set.size();
	}
} vertex_union;

class intersection_set
{
	int num_added;
	std::vector<vertex_id_t> set;
	pthread_mutex_t lock;
public:
	intersection_set() {
		num_added = 0;
		pthread_mutex_init(&lock, NULL);
	}

	void add(const std::vector<vertex_id_t> &vec);

	size_t get_size() const {
		return set.size();
	}

	vertex_id_t get(int idx) const {
		return set[idx];
	}
} vertex_intersection;

void intersection_set::add(const std::vector<vertex_id_t> &vec)
{
	std::vector<vertex_id_t> copy(vec);
	std::sort(copy.begin(), copy.end());

	std::vector<vertex_id_t> new_set;
	pthread_mutex_lock(&lock);
	num_added++;
	if (num_added == 1) {
		set = copy;
	}
	else {
		size_t i, j;
		// We assume both vectors are sorted in the ascending order.
		// We only need to scan them together to extract the common elements.
		for (i = 0, j = 0; i < set.size() && j < copy.size();) {
			if (set[i] == copy[j]) {
				new_set.push_back(set[i]);
				i++;
				j++;
			}
			else if (set[i] > copy[j])
				j++;
			else
				i++;

		}
		set = new_set;
	}
	pthread_mutex_unlock(&lock);
}

class overlap_vertex: public compute_vertex
{
	unsigned num_joined;
	std::vector<vertex_id_t> *neighbors;
public:
	overlap_vertex() {
		num_joined = 0;
		neighbors = NULL;
	}

	overlap_vertex(vertex_id_t id, const vertex_index *index1): compute_vertex(
			id, index1) {
		num_joined = 0;
		neighbors = NULL;
	}

	virtual void run(graph_engine &graph) {
		vertex_id_t id = get_id();
		graph.request_vertices(*this, &id, 1);
	}

	void run(graph_engine &graph, const page_vertex &vertex) {
		if (vertex.get_id() == get_id())
			run_on_itself(graph, vertex);
		else
			run_on_neighbor(graph, vertex);
	}

	void run_on_itself(graph_engine &graph, const page_vertex &vertex) {
		neighbors = new std::vector<vertex_id_t>();
		get_unique_neighbors(vertex, *neighbors);
		std::sort(neighbors->begin(), neighbors->end());
		vertex_union.add(*neighbors);
		vertex_intersection.add(*neighbors);
		std::vector<vertex_id_t> req_vertices;
		BOOST_FOREACH(vertex_id_t id, overlap_vertices) {
			if (id != get_id())
				req_vertices.push_back(id);
		}
		graph.request_vertices(*this, req_vertices.data(), req_vertices.size());
	}

	void run_on_neighbor(graph_engine &graph, const page_vertex &vertex) {
		num_joined++;
		std::vector<vertex_id_t> neigh_neighbors;
		get_unique_neighbors(vertex, neigh_neighbors);
		std::sort(neigh_neighbors.begin(), neigh_neighbors.end());
		size_t common = get_common_vertices(*neighbors, neigh_neighbors);
		size_t vunion = get_union_vertices(*neighbors,
				neigh_neighbors);
		printf("v%u:v%u, common: %ld, union: %ld, overlap: %f\n",
				get_id(), vertex.get_id(), common, vunion,
				((double) common) / vunion);
	}

	void run_on_messages(graph_engine &,
{'fraction_non_alphanumeric': 0.14690651403652222, 'fraction_numerical': 0.014036522213137094, 'mean_word_length': 4.162504396763982, 'pattern_counts': {'":': 0, '<': 73, '<?xml version=': 0, '>': 73, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4916236', 'n_tokens_mistral': 6155, 'n_tokens_neox': 5579, 'n_words': 1312}