Graph & Operations with Adjacency-List representation.

list-graph.hpp

#ifndef LIST_GRAPH_HPP
#define LIST_GRAPH_HPP

#include <cstddef>
#include <queue>
#include <vector>

class ListGraph
{
public:
	
	using size_t = std::size_t;
	
	using vertex_t = std::size_t;
	
	struct Edge
	{
		Edge(vertex_t vertex_,
			 size_t edge_)
		: vertex(vertex_)
		, edge(edge_)
		{ }
		
		vertex_t vertex;
		
		size_t edge;
	};
	
	using adjacent_t = std::vector<Edge>;
	
	using connected_t = std::vector<adjacent_t>;
	
	using iterator = typename connected_t::const_iterator;
	
	
	ListGraph(size_t vertex_number = 0)
	: _vertices(vertex_number, adjacent_t())
	, _edges(0)
	{ }
	
	
	iterator begin() const
	{
		return _vertices.begin();
	}
	
	iterator end() const
	{
		return _vertices.end();
	}
	
	
	void add_vertex()
	{
		_vertices.push_back({});
	}
	
	void add_edge(vertex_t from, vertex_t to)
	{
		_assert_in_range(from);
		_assert_in_range(to);
		
		_vertices[from].push_back({to, _edges});
		
		if (from != to)
		{
			_vertices[to].push_back({from, _edges});
		}

		++_edges;
	}
	
	
	const adjacent_t& adjacent(vertex_t vertex) const
	{
		_assert_in_range(vertex);
		
		return _vertices[vertex];
	}
	
	inline const adjacent_t& operator[](vertex_t vertex) const
	{
		return adjacent(vertex);
	}
	
	
	inline size_t vertex_number() const noexcept
	{
		return _vertices.size();
	}
	
	inline size_t edge_number() const noexcept
	{
		return _edges;
	}
	
	inline bool is_empty() const
	{
		return _vertices.empty();
	}
	
	
private:

	void _assert_in_range(vertex_t vertex) const
	{
		if (vertex >= _vertices.size())
		{
			throw std::invalid_argument("Vertex is out of range!");
		}
	}
	
	connected_t _vertices;
	
	size_t _edges;
};

class Components
{
public:
	
	using size_t = ListGraph::size_t;
	
	using vertex_t = ListGraph::vertex_t;
	
	using component_t = std::vector<vertex_t>;
	
	using container_t = std::vector<component_t>;
	
	using iterator = container_t::const_iterator;
	
	
	Components(const ListGraph& graph)
	: _ids(graph.vertex_number())
	{
		std::vector<bool> visited(graph.vertex_number());
		
		size_t id = 0;
		
		for (vertex_t v = 0; v < graph.vertex_number(); ++v)
		{
			if (! visited[v])
			{
				_components.push_back({});
				
				_dfs(graph, v, id, visited);
				
				++id;
			}
		}
	}
	
	iterator begin() const
	{
		return _components.begin();
	}
	
	iterator end() const
	{
		return _components.end();
	}
	
	bool is_connected(vertex_t vertex, vertex_t target) const
	{
		_assert_in_range(vertex);
		_assert_in_range(target);
		
		return _ids[vertex] == _ids[target];
	}
	
	size_t id(vertex_t vertex) const
	{
		_assert_in_range(vertex);
		
		return _ids[vertex];
	}
	
	
	const container_t& components() const
	{
		return _components;
	}
	
	const component_t& component_of(vertex_t vertex) const
	{
		return _components[_ids[vertex]];
	}
	
	
	size_t number() const
	{
		return _components.size();
	}
	
private:
	
	void _assert_in_range(vertex_t vertex) const
	{
		if (vertex > _ids.size())
		{
			throw std::invalid_argument("Vertex number out of range!");
		}
	}
	
	void _dfs(const ListGraph& graph,
			  vertex_t vertex,
			  size_t id,
			  std::vector<bool>& visited)
	{
		if (visited[vertex]) return;
		
		visited[vertex] = true;
		
		_ids[vertex] = id;
		
		_components[id].push_back(vertex);
		
		for (const auto& adjacent : graph[vertex])
		{
			_dfs(graph, adjacent.vertex, id, visited);
		}
	}
	
	component_t _ids;
	
	container_t _components;
	
};

class ListGraphOperations
{
public:
	
	using size_t = ListGraph::size_t;
	
	using vertex_t = ListGraph::vertex_t;
	
	using adjacent_t = ListGraph::adjacent_t;
	
	using component_t = ListGraph::connected_t;
	
	
	static size_t degree(const ListGraph& graph, vertex_t vertex)
	{
		return graph[vertex].size();
	}
	
	static size_t max_degree(const ListGraph& graph)
	{
		size_t max = 0;
		
		for (vertex_t v = 0; v < graph.vertex_number(); ++v)
		{
			max = std::max(max, graph[v].size());
		}
		
		return max;
	}
	
	static size_t average_degree(const ListGraph& graph)
	{
		return (graph.edge_number() * 2) / graph.vertex_number();
	}
	
	static bool has_self_loop(const ListGraph& graph, vertex_t vertex)
	{
		for (const auto& adjacent : graph[vertex])
		{
			if (adjacent.vertex == vertex) return true;
		}
		
		return false;
	}
	
	static size_t self_loops(const ListGraph& graph)
	{
		size_t count = 0;
		
		for (vertex_t v = 0; v < graph.vertex_number(); ++v)
		{
			if (has_self_loop(graph, v)) ++count;
		}
		
		return count;
	}
	
	static bool is_connected(const ListGraph& graph, vertex_t vertex, vertex_t target)
	{
		if (vertex == target) return true;
		
		std::vector<bool> visited(graph.vertex_number());
		
		return _is_connected(graph, vertex, target, visited);
	}
	
	static size_t shortest_distance(const ListGraph& graph,
									vertex_t vertex,
									vertex_t target)
	{
		if (vertex == target) return 0;
		
		// O(N/2) = O(N) space
		std::queue<vertex_t> queue;
		
		queue.push(vertex);
		
		std::vector<bool> visited(graph.vertex_number());
		
		visited[vertex] = true;
		
		size_t distance = 0;
		
		vertex_t last_of_level = vertex;
		
		// O(N) time
		while (! queue.empty())
		{
			vertex = queue.front();
			
			queue.pop();
			
			if (vertex == target) return distance;
			
			visited[vertex] = true;
			
			for (const auto& adjacent : graph[vertex])
			{
				if (! visited[adjacent.vertex])
				{
					visited[adjacent.vertex] = true;
					
					queue.push(adjacent.vertex);
				}
			}
			
			if (vertex == last_of_level)
			{
				++distance;
				
				last_of_level = queue.back();
			}
		}
	
		throw std::invalid_argument("No path between these vertices!");
	}
	
	static std::vector<vertex_t> shortest_path(const ListGraph& graph,
											   vertex_t vertex,
											   vertex_t target)
	{
		if (vertex == target) return {};
		
		std::queue<vertex_t> queue;
		
		queue.push(vertex);
		
		std::vector<bool> visited(graph.vertex_number());
		
		visited[vertex] = true;
		
		std::vector<vertex_t> source(graph.vertex_number());
		
		size_t distance = 1;
		
		vertex_t last_of_level = vertex;
		
		while (! queue.empty())
		{
			vertex = queue.front();
			
			queue.pop();
			
			if (vertex == target) break;
			
			for (const auto& adjacent : graph[vertex])
			{
				if (! visited[adjacent.vertex])
				{
					visited[adjacent.vertex] = true;
					
					source[adjacent.vertex] = vertex;
					
					queue.push(adjacent.vertex);
				}
			}
			
			if (vertex == last_of_level)
			{
				++distance;
				
				last_of_level = queue.back();
			}
		}
		
		std::vector<vertex_t> path(distance);
		
		for (long i = distance - 1; i >= 0; --i)
		{
			path[i] = vertex;
			
			vertex = source[vertex];
		}
		
		return path;
	}
	
	static bool euler_tour_possible(const ListGraph& graph)
	{
		if (Components(graph).number() != 1) return false;
		
		for (vertex_t v = 0; v < graph.vertex_number(); ++v)
		{
			if (degree(graph, v) % 2 != 0) return false;
		}
		
		return true;
	}
	
	static std::vector<vertex_t> euler_tour(const ListGraph& graph)
	{
		if (! euler_tour_possible(graph))
		{
			throw std::invalid_argument("Euler tour not possible for this graph!");
		}
		
		std::vector<bool> visited(graph.edge_number());
		
		std::vector<vertex_t> path(graph.edge_number() + 1);
		
		_euler_tour(graph, 0, 0, path, visited);
		
		return path;
	}
	
	static bool is_bipartite(const ListGraph& graph,
							 const std::function<bool(vertex_t)>& predicate)
	{
		if (graph.is_empty()) return false;
		
		Components components(graph);
		
		for (const auto& c : components)
		{
			bool is = predicate(c[0]);
			
			std::vector<bool> visited(c.size());
			
			if (! _is_bipartite(graph, c[0], ! is, predicate, visited))
			{
				return false;
			}
		}
		
		return true;
	}
	
private:
	
	static bool _is_bipartite(const ListGraph& graph,
							  vertex_t vertex,
							  bool was,
							  const std::function<bool(vertex_t)>& predicate,
							  std::vector<bool>& visited)
	{
		bool is = predicate(vertex);
		
		if (is == was) return false;
		
		for (const auto& adjacent : graph[vertex])
		{
			if (! visited[adjacent.edge])
			{
				visited[adjacent.edge] = true;
				
				if (! _is_bipartite(graph,
									adjacent.vertex,
									is,
									predicate,
									visited))
				{
					return false;
				}
			}
		}
		
		return true;
	}
	
	static bool _euler_tour(const ListGraph& graph,
							vertex_t vertex,
							size_t edge_count,
							std::vector<vertex_t>& path,
							std::vector<bool>& visited)
	{
		if (edge_count == graph.edge_number())
		{
			path[edge_count] = vertex;
			
			return true;
		}
		
		for (const auto& adjacent : graph[vertex])
		{
			if (! visited[adjacent.edge])
			{
				auto copy = visited;
				
				copy[adjacent.edge] = true;
				
				if (_euler_tour(graph,
								adjacent.vertex,
								edge_count + 1,
								path,
								copy))
				{
					path[edge_count] = vertex;
					
					return true;
				}
			}
		}
		
		return false;
	}
	
	static bool _is_connected(const ListGraph& graph,
					   vertex_t vertex,
					   vertex_t target,
					   std::vector<bool>& visited)
	{
		if (visited[vertex]) return false;
		
		if (vertex == target) return true;
		
		visited[vertex] = true;
		
		for (const auto& adjacent : graph[vertex])
		{
			if (_is_connected(graph, adjacent.vertex, target, visited))
			{
				return true;
			}
		}
		
		return false;
	}

};

#endif /* LIST_GRAPH_HPP */