<commit_before>#include "clique.h"

#include <iostream>

namespace NetworKit {

Clique::Clique(const Graph& G) : G(G) {
}

//TODO: neighbors currently a dummy vector

std::vector<std::vector<node> > Clique::run(node& seed) {
	std::vector<std::vector<node> > result;

	std::vector<node> pxvector = G.nodes();
	//if there are large gaps between the bounds, change to unordered_map
	std::vector<node> pxlookup(G.upperNodeIdBound());
	G.forNodes([&] (node u) { 
		pxlookup[u] = std::find(pxvector.begin(), pxvector.end(), u) - pxvector.begin();
	});
	std::vector<std::vector<node> > neighbors(pxvector.size());
	G.forNodes([&] (node u) {
		neighbors[pxlookup[u]] = G.neighbors(u);
	});

	uint32_t xpbound = 1;

	//TODO: use degeneracy ordering of vertices.
	for (const node& u : G.nodes()) {
		auto pxvec2 = pxvector[0];
		std::swap(pxvector[pxlookup[u]], pxvector[0]);
		std::swap(pxlookup[u], pxlookup[pxvec2]);

		uint32_t xcount = 0;
		uint32_t pcount = 0;
		G.forNeighborsOf(u, [&] (node v) {
			if (pxlookup[v] < xpbound) { // v is in X
				auto pxvec2 = pxvector[xpbound - xcount - 1];
				std::swap(pxvector[pxlookup[v]], pxvector[xpbound - xcount - 1]);
				std::swap(pxlookup[v], pxlookup[pxvec2]);
				xcount += 1;
			} else { // v is in P
				auto pxvec2 = pxvector[xpbound + pcount];
				std::swap(pxvector[pxlookup[v]], pxvector[xpbound + pcount]);
				std::swap(pxlookup[v], pxlookup[pxvec2]);
				pcount += 1;
			}
		});

		std::vector<node> r;
		r.push_back(u);
		auto tmp = tomita(pxvector, pxlookup, neighbors, xpbound - xcount, xpbound, xpbound + pcount, r);
		result.insert(result.end(), tmp.begin(), tmp.end());
		xpbound++;
	}

	return result;
}

std::vector<std::vector<node> > Clique::tomita(std::vector<node>& pxvector, std::vector<node>& pxlookup, std::vector<std::vector<node> >& neighbors, uint32_t xbound, uint32_t xpbound, uint32_t pbound, std::vector<node>& r) {
	std::vector<std::vector<node> > result;
	if (xbound == pbound) { //if (X, P are empty)
		result.push_back(r);
		return result;
	}

	node u = findPivot(pxvector, pxlookup, neighbors, xbound, xpbound, pbound);
	std::vector<node> movedNodes;
	for (uint32_t i = xpbound; i < pbound; i++) {
		if (G.hasEdge(pxvector[i], u)) {
			break;
		}<commit_msg>Added (failing) asserts for scd/clique<commit_after>#include "clique.h"

#include <iostream>
#include <cassert>

namespace NetworKit {

Clique::Clique(const Graph& G) : G(G) {
}

//TODO: neighbors currently a dummy vector

std::vector<std::vector<node> > Clique::run(node& seed) {
	std::vector<std::vector<node> > result;

	std::vector<node> pxvector = G.nodes();
	//if there are large gaps between the bounds, change to unordered_map
	std::vector<node> pxlookup(G.upperNodeIdBound());
	G.forNodes([&] (node u) { 
		pxlookup[u] = std::find(pxvector.begin(), pxvector.end(), u) - pxvector.begin();
	});
	std::vector<std::vector<node> > neighbors(pxvector.size());
	G.forNodes([&] (node u) {
		neighbors[pxlookup[u]] = G.neighbors(u);
	});

	uint32_t xpbound = 1;

	//TODO: use degeneracy ordering of vertices.
	for (const node& u : G.nodes()) {
		auto pxvec2 = pxvector[0];
		std::swap(pxvector[pxlookup[u]], pxvector[0]);
		std::swap(pxlookup[u], pxlookup[pxvec2]);

		uint32_t xcount = 0;
		uint32_t pcount = 0;
		G.forNeighborsOf(u, [&] (node v) {
			if (pxlookup[v] < xpbound) { // v is in X
				auto pxvec2 = pxvector[xpbound - xcount - 1];
				std::swap(pxvector[pxlookup[v]], pxvector[xpbound - xcount - 1]);
				std::swap(pxlookup[v], pxlookup[pxvec2]);
				xcount += 1;
			} else { // v is in P
				auto pxvec2 = pxvector[xpbound + pcount];
				std::swap(pxvector[pxlookup[v]], pxvector[xpbound + pcount]);
				std::swap(pxlookup[v], pxlookup[pxvec2]);
				pcount += 1;
			}
		});

		#ifndef NDEBUG
		bool inRange = false;
		bool wasInRange = false;
		for (node v : pxvector) {
			if (G.hasEdge(u, v)) {
				assert(!wasInRange);

				inRange = true;
				if (v < u) {
					assert(pxlookup[v] < xpbound);
				} else {
					assert(pxlookup[v] >= xpbound);
				}
			} else {
				if (inRange) {
					wasInRange = true;
					inRange = false;
				}
			}
		}
		#endif

		std::vector<node> r;
		r.push_back(u);
		auto tmp = tomita(pxvector, pxlookup, neighbors, xpbound - xcount, xpbound, xpbound + pcount, r);
		result.insert(result.end(), tmp.begin(), tmp.end());
		xpbound++;
	}

	return result;
}

std::vector<std::vector<node> > Clique::tomita(std::vector<node>& pxvector, std::vector<node>& pxlookup, std::vector<std::vector<node> >& neighbors, uint32_t xbound, uint32_t xpbound, uint32_t pbound, std::vector<node>& r) {
	std::vector<std::vector<node> > result;
	if (xbound == pbound) { //if (X, P are empty)
		result.push_back(r);
		return result;
	}

	node u = findPivot(pxvector, pxlookup, neighbors, xbound, xpbound, pbound);
	std::vector<node> movedNodes;
	for (uint32_t i = xpbound; i < pbound; i++) {
		if (G.hasEdge(pxvector[i], u)) {
			break;
		}
{'fraction_non_alphanumeric': 0.1802408654827516, 'fraction_numerical': 0.011839150847111655, 'mean_word_length': 4.2631578947368425, 'pattern_counts': {'":': 0, '<': 50, '<?xml version=': 0, '>': 45, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, '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': '4012028', 'n_tokens_mistral': 2096, 'n_tokens_neox': 1931, 'n_words': 414}