<commit_before>#include "graph.h"

#include <cassert>
#include <map>
#include <queue>

#include "bfs_visitors.h"

namespace lightfields {

Graph::Graph(const V2i& size, int n_link_value, std::size_t layer_count) : m_size(size) {
	m_tLinks = std::vector<TLinks>(layer_count, TLinks(size));
	m_nLinks = std::vector<NLinks>(layer_count, NLinks(size, n_link_value));
}

void Graph::setValue(const V2i& pos, const std::vector<int>& values) {
	assert(values.size() == m_tLinks.size());

	auto tit = m_tLinks.begin();
	auto vit = values.begin();

	int minFlow = values.front();

	while(tit != m_tLinks.end()) {
		tit->edge(pos).setCapacity(*vit);

		assert(*vit >= 0);
		assert(tit->edge(pos).residualCapacity() == *vit);

		minFlow = std::min(minFlow, *vit);

		++tit;
		++vit;
	}

	// speedup of the iterations - addresses the "trivial cases" removing the direct column
	// flow from source to sink
	if(minFlow > 0)
		for(tit = m_tLinks.begin(); tit != m_tLinks.end(); ++tit)
			tit->edge(pos).addFlow(minFlow);
}

std::size_t Graph::v2i(const V2i& v) const {
	return v.x + v.y*m_size.x;
}

V2i Graph::i2v(std::size_t v) const {
	v = v % (m_size.x*m_size.y);
	return V2i(v % m_size.x, v / m_size.x);
}

namespace {

struct QueueItem {
	Index current, parent;
};

}

bool Graph::iterate() {
	bool foundPath = false;

	BFSVisitors visited(m_size, m_nLinks.size());
	std::deque<QueueItem> q;

	{
		// initialize - source index has parent -1,-1
		const std::size_t end = m_size.x * m_size.y;
		for(std::size_t src_id=0; src_id<end; ++src_id) {
			const Index src_v = Index{i2v(src_id), 0};

			q.push_back(QueueItem{src_v, Index{V2i(-1, -1), 0}});
		}
	}

	// the core of the algorithm
	while(!q.empty()) {
		QueueItem item = q.front();
		q.pop_front();

		if(!visited.visited(item.current)) {
			visited.visit(item.current, item.parent);

			Index current_v = item.current;

			// try to move horizontally left
			if(current_v.pos.x > 0) {
				const Index new_v{V2i(current_v.pos.x-1, current_v.pos.y), current_v.n_layer};
				if(m_nLinks[current_v.n_layer].edge(current_v.pos, new_v.pos).residualCapacity() > 0)
					q.push_back(QueueItem{new_v, current_v});
			}

			// try to move horizontally right
			if(current_v.pos.x < m_size.x-1){
				const Index new_v{V2i(current_v.pos.x+1, current_v.pos.y), current_v.n_layer};
				if(m_nLinks[current_v.n_layer].edge(current_v.pos, new_v.pos).residualCapacity() > 0)
					q.push_back(QueueItem{new_v, current_v});
			}

			// try to move vertically up
			if(current_v.pos.y > 0) {
				const Index new_v{V2i(current_v.pos.x, current_v.pos.y-1), current_v.n_layer};
				if(m_nLinks[current_v.n_layer].edge(current_v.pos, new_v.pos).residualCapacity() > 0)
					q.push_back(QueueItem{new_v, current_v});
			}

			// try to move vertically down
			if(current_v.pos.y < m_size.y-1) {
				const Index new_v{V2i(current_v.pos.x, current_v.pos.y+1), current_v.n_layer};
				if(m_nLinks[current_v.n_layer].edge(current_v.pos, new_v.pos).residualCapacity() > 0)
					q.push_back(QueueItem{new_v, current_v});
			}

			// try to move up a layer (unconditional)
			if((current_v.n_layer > 0)) {
				const Index new_v{current_v.pos, current_v.n_layer-1};
				q.push_back(QueueItem{new_v, current_v});
			}

			// try to move down a layer
			if((current_v.n_layer < m_nLinks.size()-1)) {
				const Index new_v{current_v.pos, current_v.n_layer+1};
				if(m_tLinks[current_v.n_layer].edge(current_v.pos).residualCapacity() > 0)
					q.push_back(QueueItem{new_v, current_v});
			}

			// the potential exit point
			if(current_v.n_layer == m_nLinks.size()-1) {
				if(m_tLinks.back().edge(current_v.pos).residualCapacity() > 0) {
					foundPath = true;

					const int f = flow(visited, current_v);
					if(f > 0)
						doFlow(visited, current_v, f);
				}
			}
		}
	}

	return foundPath;
}

int Graph::flow(const BFSVisitors& visitors, const Index& end) const {
	assert(end.pos.x != -1 && end.pos.y != -1);
	assert(end.n_layer == m_nLinks.size()-1);

	// initial flow value based on the last T link (towards the sink)
	int result = m_tLinks.back().edge(end.pos).residualCapacity();


	Index current = end;
	Index parent = visitors.parent(current);

	while(parent.pos.x != -1 && parent.pos.y != -1) {
		assert(Index::sqdist(current, parent) == 1);

		// same layer - need to use N link
		if(current.n_layer == parent.n_layer)
			result = std::min(result, m_nLinks[current.n_layer].edge(parent.pos, current.pos).residualCapacity());

		// different layer down - need to use a T link (if the move is to higher layer)
		else if(current.n_layer > parent.n_layer)
			result = std::min(result, m_tLinks[parent.n_layer].edge(parent.pos).residualCapacity());

		// different layer up - "infinite capacity" back links have no impact on the flow

		// and move on
		current = parent;
		parent = visitors.parent(current);
	}

	assert(current.n_layer == 0);

	return result;
}

void Graph::doFlow(const BFSVisitors& visitors, const Index& end, int flow) {
	assert(end.pos.x != -1 && end.pos.y != -1);
	assert(end.n_layer == m_nLinks.size()-1);

	// initial flow value based on the last T link (towards the sink)
	m_tLinks.back().edge(end.pos).addFlow(flow);


	Index current = end;
	Index parent = visitors.parent(current);

	while(parent.pos.x != -1 && parent.pos.y != -1) {<commit_msg>Added visitor and flow early exits to Graph::iterate()<commit_after>#include "graph.h"

#include <cassert>
#include <map>
#include <queue>

#include "bfs_visitors.h"

namespace lightfields {

Graph::Graph(const V2i& size, int n_link_value, std::size_t layer_count) : m_size(size) {
	m_tLinks = std::vector<TLinks>(layer_count, TLinks(size));
	m_nLinks = std::vector<NLinks>(layer_count, NLinks(size, n_link_value));
}

void Graph::setValue(const V2i& pos, const std::vector<int>& values) {
	assert(values.size() == m_tLinks.size());

	auto tit = m_tLinks.begin();
	auto vit = values.begin();

	int minFlow = values.front();

	while(tit != m_tLinks.end()) {
		tit->edge(pos).setCapacity(*vit);

		assert(*vit >= 0);
		assert(tit->edge(pos).residualCapacity() == *vit);

		minFlow = std::min(minFlow, *vit);

		++tit;
		++vit;
	}

	// speedup of the iterations - addresses the "trivial cases" removing the direct column
	// flow from source to sink
	if(minFlow > 0)
		for(tit = m_tLinks.begin(); tit != m_tLinks.end(); ++tit)
			tit->edge(pos).addFlow(minFlow);
}

std::size_t Graph::v2i(const V2i& v) const {
	return v.x + v.y*m_size.x;
}

V2i Graph::i2v(std::size_t v) const {
	v = v % (m_size.x*m_size.y);
	return V2i(v % m_size.x, v / m_size.x);
}

namespace {

struct QueueItem {
	Index current, parent;
};

}

bool Graph::iterate() {
	bool foundPath = false;

	BFSVisitors visited(m_size, m_nLinks.size());
	std::deque<QueueItem> q;

	{
		// initialize - source index has parent -1,-1
		const std::size_t end = m_size.x * m_size.y;
		for(std::size_t src_id=0; src_id<end; ++src_id) {
			const Index src_v = Index{i2v(src_id), 0};

			visited.visit(src_v, Index{V2i(-1, -1), 0});
			q.push_back(QueueItem{src_v, Index{V2i(-1, -1), 0}});
		}
	}

	// the core of the algorithm
	while(!q.empty()) {
		QueueItem item = q.front();
		q.pop_front();

		Index current_v = item.current;

		// a potential exit point
		if(current_v.n_layer == m_nLinks.size()-1) {
			if(m_tLinks.back().edge(current_v.pos).residualCapacity() > 0) {
				foundPath = true;

				const int f = flow(visited, current_v);
				if(f > 0)
					doFlow(visited, current_v, f);
			}
		}

		// try to move horizontally left
		if(current_v.pos.x > 0) {
			const Index new_v{V2i(current_v.pos.x-1, current_v.pos.y), current_v.n_layer};
			if(!visited.visited(new_v) && m_nLinks[current_v.n_layer].edge(current_v.pos, new_v.pos).residualCapacity() > 0) {
				visited.visit(new_v, current_v);
				q.push_back(QueueItem{new_v, current_v});
			}
		}

		// try to move horizontally right
		if(current_v.pos.x < m_size.x-1){
			const Index new_v{V2i(current_v.pos.x+1, current_v.pos.y), current_v.n_layer};
			if(!visited.visited(new_v) && m_nLinks[current_v.n_layer].edge(current_v.pos, new_v.pos).residualCapacity() > 0) {
				visited.visit(new_v, current_v);
				q.push_back(QueueItem{new_v, current_v});
			}
		}

		// try to move vertically up
		if(current_v.pos.y > 0) {
			const Index new_v{V2i(current_v.pos.x, current_v.pos.y-1), current_v.n_layer};
			if(!visited.visited(new_v) && m_nLinks[current_v.n_layer].edge(current_v.pos, new_v.pos).residualCapacity() > 0) {
				visited.visit(new_v, current_v);
				q.push_back(QueueItem{new_v, current_v});
			}
		}

		// try to move vertically down
		if(current_v.pos.y < m_size.y-1) {
			const Index new_v{V2i(current_v.pos.x, current_v.pos.y+1), current_v.n_layer};
			if(!visited.visited(new_v) && m_nLinks[current_v.n_layer].edge(current_v.pos, new_v.pos).residualCapacity() > 0) {
				visited.visit(new_v, current_v);
				q.push_back(QueueItem{new_v, current_v});
			}
		}

		// try to move up a layer (unconditional)
		if((current_v.n_layer > 0)) {
			const Index new_v{current_v.pos, current_v.n_layer-1};
			if(!visited.visited(new_v)) {
				visited.visit(new_v, current_v);
				q.push_back(QueueItem{new_v, current_v});
			}
		}

		// try to move down a layer
		if((current_v.n_layer < m_nLinks.size()-1)) {
			const Index new_v{current_v.pos, current_v.n_layer+1};
			if(!visited.visited(new_v) && m_tLinks[current_v.n_layer].edge(current_v.pos).residualCapacity() > 0) {
				visited.visit(new_v, current_v);
				q.push_back(QueueItem{new_v, current_v});
			}
		}
	}

	return foundPath;
}

int Graph::flow(const BFSVisitors& visitors, const Index& end) const {
	assert(end.pos.x != -1 && end.pos.y != -1);
	assert(end.n_layer == m_nLinks.size()-1);

	// initial flow value based on the last T link (towards the sink)
	int result = m_tLinks.back().edge(end.pos).residualCapacity();


	Index current = end;
	Index parent = visitors.parent(current);

	while(result > 0 && parent.pos.x != -1 && parent.pos.y != -1) {
		assert(Index::sqdist(current, parent) == 1);

		// same layer - need to use N link
		if(current.n_layer == parent.n_layer)
			result = std::min(result, m_nLinks[current.n_layer].edge(parent.pos, current.pos).residualCapacity());

		// different layer down - need to use a T link (if the move is to higher layer)
		else if(current.n_layer > parent.n_layer)
			result = std::min(result, m_tLinks[parent.n_layer].edge(parent.pos).residualCapacity());

		// different layer up - "infinite capacity" back links have no impact on the flow

		// and move on
		current = parent;
		parent = visitors.parent(current);
	}

	assert(current.n_layer == 0 || result == 0);

	return result;
}

void Graph::doFlow(const BFSVisitors& visitors, const Index& end, int flow) {
	assert(end.pos.x != -1 && end.pos.y != -1);
	assert(end.n_layer == m_nLinks.size()-1);

	// initial flow value based on the last T link (towards the sink)
	m_tLinks.back().edge(end.pos).addFlow(flow);


	Index current = end;
	Index parent = visitors.parent(current);

	while(parent.pos.x != -1 && parent.pos.y != -1) {
{'fraction_non_alphanumeric': 0.16319854611540208, 'fraction_numerical': 0.010358927760109042, 'mean_word_length': 3.913392857142857, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 50, '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': '2622241', 'n_tokens_mistral': 4755, 'n_tokens_neox': 4290, 'n_words': 866}