Initial commit0.0.0

8 files changed, 1227 insertions, 0 deletions

diff --git a/src/graphcoloring/graphs/colormenu.cpp b/src/graphcoloring/graphs/colormenu.cpp
new file mode 100644
index 0000000..e466de2
--- /dev/null
+++ b/src/graphcoloring/graphs/colormenu.cpp
@@ -0,0 +1,120 @@
+////////////////////////////////////////////////////////////////////////////////
+// Copyright (C) 2018 Leo Tenenbaum
+// This file is part of GraphColoring.
+//
+// GraphColoring 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.
+//
+// GraphColoring 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 GraphColoring.  If not, see <https://www.gnu.org/licenses/>.
+////////////////////////////////////////////////////////////////////////////////
+
+#include "colormenu.hpp"
+
+#include "../level.hpp"
+#include "utils/geometry.hpp"
+
+namespace graphcoloring {
+
+int ColorMenu::number_of_color_menus = 0;
+
+ColorMenu::ColorMenu(gui::Window* window_, int x_, int y_,
+	const gui::Position& viewport_position_,
+	std::function<void(gui::Color)> color_click_callback_)
+	: window(window_), x(x_), y(y_), viewport_position(viewport_position_),
+	  color_click_callback(color_click_callback_)
+{
+	number_of_color_menus++;
+	if (number_of_color_menus == 1)
+	{
+		MakeButtons();
+		callback_id = window->SetMousedownCallback([this](gui::Window*,int x,int y){
+			if (!IsInsideMenu(x,y) && close_callback)
+				close_callback();
+
+		});
+	}
+	else
+	{
+		callback_id = -1;
+	}
+}
+
+ColorMenu::~ColorMenu()
+{
+	if (callback_id != -1)
+		window->RemoveMousedownCallback(callback_id);
+	number_of_color_menus--;
+}
+
+void ColorMenu::SetCloseCallback(std::function<void()> close_callback_)
+{
+	close_callback = close_callback_;
+}
+
+int ColorMenu::GetWidth() const
+{
+	int number_of_colors = Level::colors.size();
+	return SPACING  + (SPACING + 2 * CIRCLE_RADIUS) * number_of_colors;
+}
+
+int ColorMenu::GetHeight() const
+{
+	return 2 * (CIRCLE_RADIUS + SPACING);
+}
+
+void ColorMenu::MakeButtons()
+{
+	int xpos = x + SPACING;
+	for (gui::Color color : Level::colors)
+	{
+		gui::Position pos(xpos, y + SPACING, 0, 0, nullptr,
+			&negative_viewport_position);
+		gui::Size size(CIRCLE_RADIUS);
+		std::unique_ptr<gui::Button> button(
+			new gui::Button(window, "", pos, size,
+				color, gui::Alignment::LEFT, gui::Alignment::TOP,
+				gui::Button::Shape::CIRCLE));
+		button->SetCommand([this,color] (){
+			if (!color_click_callback) return;
+			color_click_callback(color);
+		}, GDK_BUTTON_PRIMARY);
+		buttons.push_back(std::move(button));
+		xpos += SPACING + 2 * CIRCLE_RADIUS;
+	}
+}
+
+void ColorMenu::Render()
+{
+	if (callback_id == -1) // Failed to create ColorMenu
+	{
+		close_callback();
+		return;
+	}
+
+	int view_x = viewport_position.x;
+	int view_y = viewport_position.y;
+	negative_viewport_position.SetPos(-view_x, -view_y);
+
+	window->SetDrawColor(BACKGROUND_COLOR);
+	window->DrawRectangle(x-view_x, y-view_y, GetWidth(), GetHeight(), true);
+	for (std::unique_ptr<gui::Button>& button : buttons)
+		button->Render();
+}
+
+bool ColorMenu::IsInsideMenu(int mx, int my) const
+{
+	return utils::geometry::InRectangle(mx, my,
+		x-viewport_position.X(), y-viewport_position.Y(),
+		GetWidth(), GetHeight());
+}
+
+} // namespace graphcoloring
+
diff --git a/src/graphcoloring/graphs/colormenu.hpp b/src/graphcoloring/graphs/colormenu.hpp
new file mode 100644
index 0000000..3062654
--- /dev/null
+++ b/src/graphcoloring/graphs/colormenu.hpp
@@ -0,0 +1,58 @@
+////////////////////////////////////////////////////////////////////////////////
+// Copyright (C) 2018 Leo Tenenbaum
+// This file is part of GraphColoring.
+//
+// GraphColoring 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.
+//
+// GraphColoring 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 GraphColoring.  If not, see <https://www.gnu.org/licenses/>.
+////////////////////////////////////////////////////////////////////////////////
+
+#ifndef GRAPHCOLORING_GRAPHS_COLORMENU_H_
+#define GRAPHCOLORING_GRAPHS_COLORMENU_H_
+
+#include "gui/window.hpp"
+#include "gui/button.hpp"
+
+#include <memory>
+
+namespace graphcoloring {
+
+class ColorMenu {
+public:
+	ColorMenu(gui::Window* window, int x, int y,
+		const gui::Position& viewport_position,
+		std::function<void(gui::Color)> color_click_callback);
+	virtual ~ColorMenu();
+	void Render();
+	void SetCloseCallback(std::function<void()> close_callback);
+	int GetWidth() const;
+	int GetHeight() const;
+	bool IsInsideMenu(int x, int y) const; // Is this mouse position inside the menu?
+private:
+	void MakeButtons();
+	static constexpr int CIRCLE_RADIUS = 20;
+	static constexpr int SPACING = 10;
+	static constexpr gui::Color BACKGROUND_COLOR = 0x222222FF;
+	static int number_of_color_menus; // Number of color menus open.
+	int callback_id;
+	gui::Window* const window;
+	const int x, y;
+	const gui::Position& viewport_position;
+	gui::Position negative_viewport_position;
+	std::vector<std::unique_ptr<gui::Button>> buttons;
+	std::function<void(gui::Color)> color_click_callback;
+	std::function<void()> close_callback;
+};
+
+} // namespace graphcoloring
+
+#endif // GRAPHCOLORING_GRAPHS_COLORMENU_H_
diff --git a/src/graphcoloring/graphs/edge.cpp b/src/graphcoloring/graphs/edge.cpp
new file mode 100644
index 0000000..91adc1d
--- /dev/null
+++ b/src/graphcoloring/graphs/edge.cpp
@@ -0,0 +1,191 @@
+////////////////////////////////////////////////////////////////////////////////
+// Copyright (C) 2018 Leo Tenenbaum
+// This file is part of GraphColoring.
+//
+// GraphColoring 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.
+//
+// GraphColoring 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 GraphColoring.  If not, see <https://www.gnu.org/licenses/>.
+////////////////////////////////////////////////////////////////////////////////
+
+#include "edge.hpp"
+
+#define _USE_MATH_DEFINES
+#include <cmath>
+#include <cassert>
+
+#include "utils/geometry.hpp"
+#include "utils/errors.hpp"
+
+namespace graphcoloring {
+
+int Edge::id_counter = 0;
+
+void Edge::ResetID()
+{
+	id_counter = 0;
+}
+
+
+Edge::Edge(gui::Window* window_, Vertex& from_, Vertex& to_, gui::Color color_,
+	const gui::Position& viewport_position_, bool directed_)
+	: id(id_counter++), from(from_), to(to_), window(window_),
+	  viewport_position(viewport_position_)
+{
+	color = color_;
+	directed = directed_;
+	color_menu = nullptr;
+	mousedown_callback_id =
+		window->SetMousedownCallback([this] (gui::Window*, int x, int y) {
+			MouseCallback(x, y);
+		});
+	x_keyup_callback_id =
+		window->SetKeyupCallback([this] (gui::Window*) {
+			if (hovering && !is_delete_protected && delete_callback
+			 && !is_locked)
+				delete_callback();
+		}, GDK_KEY_x);
+}
+
+Edge::~Edge()
+{
+	window->RemoveMousedownCallback(mousedown_callback_id);
+	window->RemoveKeyupCallback(x_keyup_callback_id, GDK_KEY_x);
+}
+
+int Edge::OtherEndpoint(int vertex_id) const
+{
+	if (from.id == vertex_id) return to.id;
+	if (to.id == vertex_id) return from.id;
+	utils::errors::Die("No other endpoint.");
+	return -1;
+}
+
+void Edge::Lock()
+{
+	is_locked = true;
+}
+
+void Edge::Unlock()
+{
+	is_locked = false;
+}
+
+bool Edge::IsHovering() const
+{
+	return hovering;
+}
+
+bool Edge::IsAdjacentTo(const Edge& edge) const
+{
+	return edge.HasEndpoint(from.id) || edge.HasEndpoint(to.id);
+}
+
+void Edge::SetDeleteCallback(std::function<void()> delete_callback_)
+{
+	delete_callback = delete_callback_;
+}
+
+gui::Color Edge::Color() const
+{
+	return color;
+}
+
+bool Edge::ChangeColor(gui::Color new_color)
+{
+	if (is_color_protected) return false;
+	color = new_color;
+	return true;
+}
+
+bool Edge::HasEndpoints(int id1, int id2) const
+{
+	if (from.id == id1 && to.id == id2)
+		return true;
+	return !directed && from.id == id2 && to.id == id1;
+}
+
+bool Edge::HasEndpoint(int v_id) const
+{
+	return from.id == v_id || to.id == v_id;
+}
+
+void Edge::Render(bool is_in_path)
+{
+	int dist = utils::geometry::PointToLineSegmentDistance(
+		window->GetMouseX(), window->GetMouseY(),
+		from.RenderX(), from.RenderY(), to.RenderX(), to.RenderY(),
+		EDGE_CLICK_TOLERANCE);
+	hovering = dist < EDGE_CLICK_TOLERANCE && dist != -1;
+	int from_x = from.RenderX();
+	int from_y = from.RenderY();
+	int to_x   =   to.RenderX();
+	int to_y   =   to.RenderY();
+
+	double theta1 = utils::geometry::LineAngle(from_x, from_y, to_x, to_y);
+	double theta2 = utils::geometry::LineAngle(to_x, to_y, from_x, from_y);
+
+	int x1 = from_x + Vertex::VERTEX_RADIUS * std::cos(theta1);
+	int y1 = from_y + Vertex::VERTEX_RADIUS * std::sin(theta1);
+
+	int x2 = to_x + Vertex::VERTEX_RADIUS * std::cos(theta2);
+	int y2 = to_y + Vertex::VERTEX_RADIUS * std::sin(theta2);
+
+	window->SetDrawColor(is_in_path ? gui::colors::WHITE : color);
+	window->DrawLine(x1, y1, x2, y2);
+
+	if (directed)
+	{
+		double theta3 = theta2 - M_PI / 4;
+		double theta4 = theta2 + M_PI / 4;
+
+		int x3 = x2 + ARROW_SIZE * std::cos(theta3);
+		int y3 = y2 + ARROW_SIZE * std::sin(theta3);
+
+		int x4 = x2 + ARROW_SIZE * std::cos(theta4);
+		int y4 = y2 + ARROW_SIZE * std::sin(theta4);
+
+		window->DrawLine(x2, y2, x3, y3);
+		window->DrawLine(x2, y2, x4, y4);
+	}
+
+}
+
+void Edge::RenderColorMenu()
+{
+	if (color_menu != nullptr)
+		color_menu->Render();
+}
+
+
+void Edge::MouseCallback(int mouse_x, int mouse_y)
+{
+	if (!hovering || color_menu != nullptr || is_color_protected
+	 || is_locked)
+		return;
+
+	std::function<void(gui::Color)> callback = [this] (gui::Color color) {
+		assert(ChangeColor(color));
+		color_menu = nullptr;
+	};
+
+	color_menu = std::make_unique<ColorMenu>(window,
+		mouse_x+viewport_position.X(), mouse_y+viewport_position.Y(),
+		viewport_position, callback);
+
+	std::function<void()> close_callback = [this] () {
+		color_menu = nullptr;
+	};
+	color_menu->SetCloseCallback(close_callback);
+}
+
+
+} // namespace graphcoloring
diff --git a/src/graphcoloring/graphs/edge.hpp b/src/graphcoloring/graphs/edge.hpp
new file mode 100644
index 0000000..d5350b8
--- /dev/null
+++ b/src/graphcoloring/graphs/edge.hpp
@@ -0,0 +1,71 @@
+////////////////////////////////////////////////////////////////////////////////
+// Copyright (C) 2018 Leo Tenenbaum
+// This file is part of GraphColoring.
+//
+// GraphColoring 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.
+//
+// GraphColoring 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 GraphColoring.  If not, see <https://www.gnu.org/licenses/>.
+////////////////////////////////////////////////////////////////////////////////
+
+#ifndef GRAPHCOLORING_GRAPHS_EDGE_H_
+#define GRAPHCOLORING_GRAPHS_EDGE_H_
+
+#include "vertex.hpp"
+
+#include "gui/window.hpp"
+
+namespace graphcoloring {
+
+class Edge {
+public:
+	static void ResetID();
+	Edge(gui::Window* window, Vertex& from, Vertex& to,
+		gui::Color color, const gui::Position& viewport_position,
+		bool directed = false);
+	virtual ~Edge();
+	int OtherEndpoint(int vertex_id) const;
+	void Lock();
+	void Unlock();
+	bool IsHovering() const;
+	bool IsAdjacentTo(const Edge& edge) const;
+	void SetDeleteCallback(std::function<void()> delete_callback);
+	bool ChangeColor(gui::Color new_color); // Returns false if edge is color protected.
+	gui::Color Color() const;
+	bool HasEndpoint(int id) const; // Does this edge have this endpoint?
+	bool HasEndpoints(int id1, int id2) const; // Does this edge have these endpoints?
+	void Render(bool is_in_path = false);
+	void RenderColorMenu(); // Color menu rendering is handled separately
+	const int id;
+	Vertex& from;
+	Vertex& to;
+	bool is_color_protected = false;
+	bool is_delete_protected = false;
+private:
+	void MouseCallback(int mouse_x, int mouse_y);
+	static constexpr int EDGE_CLICK_TOLERANCE = 10;
+	static constexpr int ARROW_SIZE = 10;
+	static int id_counter;
+	gui::Window* const window;
+	gui::Color color;
+	std::unique_ptr<ColorMenu> color_menu;
+	const gui::Position& viewport_position;
+	bool directed;
+	bool hovering = false;
+	bool is_locked = false;
+	int mousedown_callback_id;
+	int x_keyup_callback_id;
+	std::function<void()> delete_callback;
+};
+
+} // namespace graphcoloring
+
+#endif // GRAPHCOLORING_GRAPHS_EDGE_H_
diff --git a/src/graphcoloring/graphs/graph.cpp b/src/graphcoloring/graphs/graph.cpp
new file mode 100644
index 0000000..7785a8f
--- /dev/null
+++ b/src/graphcoloring/graphs/graph.cpp
@@ -0,0 +1,419 @@
+////////////////////////////////////////////////////////////////////////////////
+// Copyright (C) 2018 Leo Tenenbaum
+// This file is part of GraphColoring.
+//
+// GraphColoring 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.
+//
+// GraphColoring 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 GraphColoring.  If not, see <https://www.gnu.org/licenses/>.
+////////////////////////////////////////////////////////////////////////////////
+
+#include "graph.hpp"
+
+#include <sstream>
+#include <cassert>
+#include <stack>
+
+#include "../level.hpp"
+#include "utils/errors.hpp"
+
+namespace graphcoloring {
+
+void Graph::ResetIDs()
+{
+	Vertex::ResetID();
+	Edge::ResetID();
+}
+
+Graph::Graph(gui::Window* window_, const gui::Position& viewport_position_,
+		bool directed_)
+	: window(window_), viewport_position(viewport_position_),
+	  edge_vertex(-1)
+{
+	directed = directed_;
+	can_add_new_vertices = true;
+	v_keyup_callback =
+		window->SetKeyupCallback([this] (gui::Window*) {
+			if (can_add_new_vertices && !is_locked)
+				AddVertex(window->GetMouseX()+viewport_position.X(),
+						  window->GetMouseY()+viewport_position.Y());
+		}, GDK_KEY_v);
+	e_keyup_callback =
+		window->SetKeyupCallback([this] (gui::Window*){EPressed();}, GDK_KEY_e);
+}
+
+Graph::~Graph()
+{
+	Clear();
+
+	window->RemoveKeyupCallback(v_keyup_callback, GDK_KEY_v);
+	window->RemoveKeyupCallback(e_keyup_callback, GDK_KEY_e);
+}
+
+int Graph::V() const
+{
+	return vertices.size();
+}
+
+int Graph::E() const
+{
+	return edges.size();
+}
+
+void Graph::AddOrigin(int id)
+{
+	origins.push_back(id);
+}
+
+void Graph::Clear()
+{
+	for (Vertex* v : vertices)
+		delete v;
+	for (Edge* e : edges)
+		delete e;
+	vertices.clear();
+	edges.clear();
+	ResetIDs();
+}
+
+void Graph::Lock()
+{
+	is_locked = true;
+	for (Vertex* v : vertices)
+		v->Lock();
+	for (Edge* e : edges)
+		e->Lock();
+}
+
+void Graph::Unlock()
+{
+	is_locked = false;
+	for (Vertex* v : vertices)
+		v->Unlock();
+	for (Edge* e : edges)
+		e->Unlock();
+}
+
+void Graph::EPressed()
+{
+	if (!can_add_new_edges || is_locked) return;
+	if (edge_vertex != -1 && !HasVertexWithID(edge_vertex)) // Check if vertex was deleted.
+		edge_vertex = -1;
+	int hover_id = GetHoveringVertex();
+	if (edge_vertex == -1)
+	{
+		edge_vertex = hover_id;
+	}
+	else if (hover_id != -1)
+	{
+		if (edge_vertex == hover_id) return; // Disallow self-loops
+		if (HasEdge(edge_vertex, hover_id)) return; // Disallow multiple edges between same vertices
+		if (GetVertexByID(hover_id).is_edge_protected) return;
+		AddEdge(edge_vertex, hover_id);
+		edge_vertex = -1; // Reset edge_vertex
+	}
+	else // User pressed e with no second vertex
+	{
+		edge_vertex = -1; // Cancel
+	}
+}
+
+bool Graph::HasVertexWithID(int id) const
+{
+	for (const Vertex* v : vertices)
+		if (v->id == id)
+			return true;
+	return false;
+}
+
+Vertex& Graph::GetVertexByID(int id)
+{
+	for (Vertex* v : vertices)
+		if (v->id == id)
+			return *v;
+	std::stringstream s;
+	s << "Failed to find vertex with id: " << id;
+	utils::errors::Die(s.str());
+	return *vertices[-1]; // So the compiler doesn't worry...
+}
+
+const Vertex& Graph::GetVertexByIDConst(int id) const
+{
+	for (const Vertex* v : vertices)
+		if (v->id == id)
+			return *v;
+	std::stringstream s;
+	s << "Failed to find vertex with id: " << id;
+	utils::errors::Die(s.str());
+	return *vertices[-1]; // So the compiler doesn't worry...
+}
+
+
+Edge& Graph::GetEdgeByEndpoints(int from, int to)
+{
+	for (Edge* e : edges)
+		if (e->from.id == from && e->to.id == to)
+			return *e;
+
+	std::stringstream s;
+	s << "Failed to find edge with end-points: " << from << ", " << to;
+	utils::errors::Die(s.str());
+	return *edges[-1]; // So the compiler doesn't worry...
+}
+
+const Edge& Graph::GetEdgeByEndpointsConst(int from, int to) const
+{
+	for (const Edge* e : edges)
+		if (e->HasEndpoints(from, to))
+			return *e;
+
+	std::stringstream s;
+	s << "Failed to find edge with end-points: " << from << ", " << to;
+	utils::errors::Die(s.str());
+	return *edges[-1]; // So the compiler doesn't worry...
+}
+
+bool Graph::HasEdgeWithID(int id) const
+{
+	for (const Edge* e : edges)
+		if (e->id == id)
+			return true;
+	return false;
+}
+
+Edge& Graph::GetEdgeByID(int id)
+{
+	for (Edge* e : edges)
+		if (e->id == id)
+			return *e;
+
+	std::stringstream s;
+	s << "Failed to find edge with id: " << id;
+	utils::errors::Die(s.str());
+	return *edges[-1];
+}
+
+
+const Edge& Graph::GetEdgeByIDConst(int id) const
+{
+	for (const Edge* e : edges)
+		if (e->id == id)
+			return *e;
+	std::stringstream s;
+	s << "Failed to find edge with id: " << id;
+	utils::errors::Die(s.str());
+	return *edges[-1];
+}
+
+int Graph::GetHoveringVertex() const
+{
+	for (const Vertex* v : vertices)
+		if (v->IsHovering())
+			return v->id;
+	return -1;
+}
+
+int Graph::GetHoveringEdge() const
+{
+	for (const Edge* e : edges)
+		if (e->IsHovering())
+			return e->id;
+	return -1;
+}
+
+int Graph::AddVertex(Vertex* v)
+{
+	vertices.push_back(v);
+	std::function<void()> f = [this, v] () {
+		RemoveVertex(v->id);
+	};
+	v->SetDeleteCallback(f);
+	DFS();
+	return v->id;
+}
+
+int Graph::AddVertex(Vertex& v)
+{
+	return AddVertex(&v);
+}
+
+int Graph::AddVertex(int x, int y)
+{
+	Vertex* v = new Vertex(window, Level::colors[0], x, y, viewport_position);
+	return AddVertex(v);
+}
+
+int Graph::AddEdge(Edge* e)
+{
+	edges.push_back(e);
+	e->SetDeleteCallback([this, e] () {
+		RemoveEdge(e->from.id, e->to.id);
+	});
+	DFS();
+	return e->id;
+}
+
+int Graph::AddEdge(Edge& e)
+{
+	return AddEdge(&e);
+}
+
+int Graph::AddEdge(int id1, int id2)
+{
+	if (!HasVertexWithID(id1)|| !HasVertexWithID(id2))
+		utils::errors::Die("Trying to create edge with non-existent vertex.");
+	Vertex& v1 = GetVertexByID(id1);
+	Vertex& v2 = GetVertexByID(id2);
+	Edge* e = new Edge(window, v1, v2, Level::colors[0], viewport_position,
+		directed);
+	return AddEdge(e);
+}
+
+bool Graph::HasEdge(int id1, int id2) const
+{
+	for (const Edge* e : edges)
+		if (e->HasEndpoints(id1, id2))
+			return true;
+	return false;
+}
+
+void Graph::RemoveVertex(int id)
+{
+	for (int i = 0; i < E(); i++)
+	{
+		if (edges[i]->from.id == id || edges[i]->to.id == id)
+		{
+			delete edges[i];
+			edges.erase(edges.begin() + i);
+			i--;
+		}
+	}
+
+	for (int i = 0; i < V(); i++)
+	{
+		if (vertices[i]->id == id)
+		{
+			delete vertices[i];
+			vertices.erase(vertices.begin()+i);
+			break;
+		}
+	}
+	DFS();
+}
+
+void Graph::RemoveEdge(int id1, int id2)
+{
+	for (int i = 0; i < E(); i++)
+	{
+		if (edges[i]->HasEndpoints(id1, id2))
+		{
+			delete edges[i];
+			edges.erase(edges.begin() + i);
+			break;
+
+		}
+	}
+	DFS();
+}
+
+int Graph::Degree(int id) const
+{
+	int degree = 0;
+	for (int i = 0; i < E(); i++)
+	{
+		if (edges[i]->from.id == id || edges[i]->to.id == id)
+			degree++;
+	}
+	return degree;
+}
+
+void Graph::DFS()
+{
+	std::stack<int> vertices;
+	for (int v : origins)
+		vertices.push(v);
+	connected.clear();
+	while (!vertices.empty())
+	{
+		int v = vertices.top();
+		vertices.pop();
+		if (connected.count(v))
+			continue;
+		connected.insert(v);
+		for (Edge* e : edges)
+		{
+			if (e->from.id == v && !connected.count(e->to.id))
+				vertices.push(e->to.id);
+			if (e->to.id == v && !connected.count(e->from.id))
+				vertices.push(e->from.id);
+
+		}
+	}
+}
+
+bool Graph::IsConnected(int id) const
+{
+	return connected.count(id) > 0;
+}
+
+bool Graph::IsConnected() const
+{
+	for (const Vertex* v : vertices)
+		if (!IsConnected(v->id))
+			return false;
+	return true;
+}
+
+void Graph::Render(const std::set<int>& edges_in_path,
+				   const std::set<int>& vertices_in_path, int last_vertex)
+{
+	// Display counter
+	window->SetTextSize(COUNTER_TEXT_SIZE);
+	window->SetDrawColor(0xCCCCCCFF);
+	std::stringstream counter_text;
+	counter_text << "Vertices: " << V() << ", Edges: " << E();
+	window->DrawText(counter_text.str(), 10, COUNTER_TEXT_SIZE+10);
+
+	if (edge_vertex != -1) // Draw line from edge vertex to mouse.
+	{
+		if (!HasVertexWithID(edge_vertex))
+		{
+			edge_vertex = -1;
+		}
+		else
+		{
+			Vertex& v = GetVertexByID(edge_vertex);
+			window->SetDrawColor(0x888888FF);
+			window->DrawLine(v.RenderX(), v.RenderY(),
+				window->GetMouseX(), window->GetMouseY());
+		}
+	}
+
+	for (Vertex* v : vertices)
+		v->Render(Degree(v->id), IsConnected(v->id) > 0,
+			vertices_in_path.count(v->id) > 0, last_vertex == v->id);
+	for (Edge* e : edges)
+		e->Render(edges_in_path.count(e->id) > 0);
+
+	for (Vertex* v : vertices)
+		v->RenderColorMenu();
+	for (Edge* e : edges)
+		e->RenderColorMenu();
+}
+
+void Graph::Render()
+{
+	std::set<int> edges_in_path;
+	std::set<int> vertices_in_path;
+	Render(edges_in_path, vertices_in_path, -1);
+}
+
+} // namespace graphcoloring
diff --git a/src/graphcoloring/graphs/graph.hpp b/src/graphcoloring/graphs/graph.hpp
new file mode 100644
index 0000000..d7223c4
--- /dev/null
+++ b/src/graphcoloring/graphs/graph.hpp
@@ -0,0 +1,88 @@
+////////////////////////////////////////////////////////////////////////////////
+// Copyright (C) 2018 Leo Tenenbaum
+// This file is part of GraphColoring.
+//
+// GraphColoring 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.
+//
+// GraphColoring 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 GraphColoring.  If not, see <https://www.gnu.org/licenses/>.
+////////////////////////////////////////////////////////////////////////////////
+
+#ifndef GRAPHCOLORING_GRAPHS_GRAPH_H_
+#define GRAPHCOLORING_GRAPHS_GRAPH_H_
+
+#include <set>
+
+#include "vertex.hpp"
+#include "edge.hpp"
+
+namespace graphcoloring {
+
+class Graph {
+public:
+	Graph(gui::Window* window, const gui::Position& viewport_position,
+		bool directed = false);
+	virtual ~Graph();
+	int V() const;
+	int E() const;
+	void AddOrigin(int id);
+	void Clear(); // Clear all vertices and edges
+	void Lock(); // Disallow changes to the graph
+	void Unlock(); // Allow changes to the graph
+	bool HasVertexWithID(int id) const;
+	Vertex& GetVertexByID(int id);
+	const Vertex& GetVertexByIDConst(int id) const;
+	Edge& GetEdgeByEndpoints(int from, int to);
+	const Edge& GetEdgeByEndpointsConst(int from, int to) const;
+	bool HasEdgeWithID(int id) const;
+	Edge& GetEdgeByID(int id);
+	const Edge& GetEdgeByIDConst(int id) const;
+	int GetHoveringVertex() const; // Returns ID of vertex which mouse is hovering over, -1 if no such vertex.
+	int GetHoveringEdge() const;
+	int AddVertex(Vertex& v);
+	int AddVertex(int x, int y); // Create vertex with some default parameters.
+	int AddEdge(Edge& e);
+	int AddEdge(int v1, int v2); // Create edge with some default parameters.
+	bool HasEdge(int id1, int id2) const; // Is there an edge between id1 and id2?
+	void RemoveVertex(int id);
+	void RemoveEdge(int id1, int id2);
+	int Degree(int id) const;
+	bool IsConnected(int id) const;
+	bool IsConnected() const;
+	void Render(const std::set<int>& edges_in_path,
+			    const std::set<int>& vertices_in_path, int last_vertex);
+	void Render();
+	bool can_add_new_vertices; // Can the user add more vertices?
+	bool can_add_new_edges;
+	std::vector<Vertex*> vertices;
+	std::vector<Edge*> edges;
+private:
+	static void ResetIDs(); // Reset edge and vertex IDs.
+	int AddVertex(Vertex* v);
+	int AddEdge(Edge* e);
+	void EPressed(); // e key was pressed
+	void DFS(); // Run a DFS on the graph to see which vertices are connected
+	static constexpr int COUNTER_TEXT_SIZE = 24;
+	gui::Window* const window;
+	const gui::Position& viewport_position;
+	bool directed;
+	std::vector<int> origins;
+	std::set<int> connected;
+	bool is_locked = false;
+
+	int edge_vertex; // First vertex in edge; -1 if not making edge.
+	int v_keyup_callback;
+	int e_keyup_callback;
+};
+
+} // namespace graphcoloring
+
+#endif // SRC_GRAPHCOLORING_GRAPHS_GRAPH_H_
diff --git a/src/graphcoloring/graphs/vertex.cpp b/src/graphcoloring/graphs/vertex.cpp
new file mode 100644
index 0000000..b4d3afe
--- /dev/null
+++ b/src/graphcoloring/graphs/vertex.cpp
@@ -0,0 +1,204 @@
+////////////////////////////////////////////////////////////////////////////////
+// Copyright (C) 2018 Leo Tenenbaum
+// This file is part of GraphColoring.
+//
+// GraphColoring 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.
+//
+// GraphColoring 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 GraphColoring.  If not, see <https://www.gnu.org/licenses/>.
+////////////////////////////////////////////////////////////////////////////////
+
+#include "vertex.hpp"
+
+#include <cassert>
+#include <iostream>
+
+#include "utils/geometry.hpp"
+#include "gui/button.hpp"
+#include "../graphcoloring.hpp"
+
+namespace graphcoloring {
+
+int Vertex::id_counter = 0;
+int Vertex::moving_vertex = -1;
+
+void Vertex::ResetID()
+{
+	id_counter = 0;
+}
+
+Vertex::Vertex(gui::Window* window_, gui::Color color_, int x_, int y_,
+	const gui::Position& viewport_position_)
+	: x(x_), y(y_), id(id_counter++),
+	  window(window_),
+	  color(color_),
+	  viewport_position(viewport_position_),
+	  color_menu(nullptr)
+{
+	SetClickCallback();
+	SetMoveCallbacks();
+	SetDeleteKeyCallback();
+}
+
+Vertex::~Vertex()
+{
+	if (moving_vertex == id) moving_vertex = -1;
+	window->RemoveMousedownCallback(mousedown_callback_id);
+	window->RemoveKeydownCallback(m_keydown_callback_id, GDK_KEY_m);
+	window->RemoveKeyupCallback(m_keyup_callback_id, GDK_KEY_m);
+	window->RemoveKeyupCallback(x_keyup_callback_id, GDK_KEY_x);
+}
+
+void Vertex::Lock()
+{
+	is_locked = true;
+	moving_vertex = -1;
+}
+
+void Vertex::Unlock()
+{
+	is_locked = false;
+}
+
+void Vertex::SetClickCallback()
+{
+	mousedown_callback_id =
+		window->SetMousedownCallback([this] (gui::Window*, int x, int y) {
+			MouseCallback(x, y);
+		}, GDK_BUTTON_PRIMARY);
+
+}
+
+void Vertex::SetMoveCallbacks()
+{
+	m_keydown_callback_id =
+		window->SetKeydownCallback([this] (gui::Window*) {
+			if (moving_vertex == -1 && hovering)
+			{
+				moving_vertex = id;
+			}
+		}, GDK_KEY_m);
+	m_keyup_callback_id =
+		window->SetKeyupCallback([this] (gui::Window*) {
+			moving_vertex = -1;
+		}, GDK_KEY_m);
+}
+
+void Vertex::SetDeleteKeyCallback()
+{
+	x_keyup_callback_id =
+		window->SetKeyupCallback([this] (gui::Window*) {
+			if (hovering && !is_delete_protected && !is_locked)
+			{
+				if (delete_callback)
+				{
+					delete_callback();
+				}
+			}
+		}, GDK_KEY_x);
+}
+
+void Vertex::SetDeleteCallback(std::function<void()> delete_callback_)
+{
+	delete_callback = delete_callback_;
+}
+
+bool Vertex::operator==(const Vertex other) const
+{
+	return id == other.id;
+}
+
+gui::Color Vertex::Color() const
+{
+	return color;
+}
+
+bool Vertex::ChangeColor(gui::Color new_color)
+{
+	if (is_color_protected) return false;
+	color = new_color;
+	return true;
+}
+
+int Vertex::RenderX() const
+{
+	return x - viewport_position.X();
+}
+
+int Vertex::RenderY() const
+{
+	return y - viewport_position.Y();
+}
+
+
+void Vertex::Render(int degree, bool filled, bool is_in_path,
+	bool is_last_vertex)
+{
+	int rx = RenderX(), ry = RenderY(); // Coordinates of circle
+
+	CheckIfMoving();
+
+	window->SetDrawColor(is_in_path ? gui::colors::WHITE : color);
+	if (is_last_vertex)
+		window->SetDrawColor(0x888888FF);
+	window->DrawCircle(rx, ry, VERTEX_RADIUS, filled);
+	window->SetTextSize(VERTEX_RADIUS*gui::Button::CIRCLE_TEXT_SIZE_FACTOR);
+
+	if (filled)
+		window->SetDrawColor(GraphColoring::BACKGROUND_COLOR);
+
+	hovering = utils::geometry::InCircle(
+		window->GetMouseX(), window->GetMouseY(), rx, ry, VERTEX_RADIUS);
+	if (hovering)
+	{
+		window->DrawText(std::to_string(degree), gui::Position(rx,ry),
+			gui::Alignment::CENTER, gui::Alignment::CENTER);
+	}
+}
+
+void Vertex::CheckIfMoving()
+{
+	if (moving_vertex == id)
+	{
+		x = window->GetMouseX() + viewport_position.X();
+		y = window->GetMouseY() + viewport_position.Y();
+	}
+}
+
+void Vertex::RenderColorMenu()
+{
+	if (color_menu != nullptr)
+		color_menu->Render();
+}
+
+
+void Vertex::MouseCallback(int mouse_x, int mouse_y)
+{
+	if (is_color_protected || is_locked) return;
+	if (hovering && color_menu == nullptr && !is_color_protected)
+	{
+		std::function<void(gui::Color)> callback = [this] (gui::Color color) {
+			assert(ChangeColor(color));
+			color_menu = nullptr;
+		};
+
+		color_menu = std::make_unique<ColorMenu>(window,
+			mouse_x+viewport_position.X(), mouse_y+viewport_position.Y(),
+			viewport_position, callback);
+
+		std::function<void()> close_callback = [this] () {
+			color_menu = nullptr;
+		};
+		color_menu->SetCloseCallback(close_callback);
+	}
+}
+
+} // namespace graphcoloring
diff --git a/src/graphcoloring/graphs/vertex.hpp b/src/graphcoloring/graphs/vertex.hpp
new file mode 100644
index 0000000..f5dea49
--- /dev/null
+++ b/src/graphcoloring/graphs/vertex.hpp
@@ -0,0 +1,76 @@
+////////////////////////////////////////////////////////////////////////////////
+// Copyright (C) 2018 Leo Tenenbaum
+// This file is part of GraphColoring.
+//
+// GraphColoring 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.
+//
+// GraphColoring 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 GraphColoring.  If not, see <https://www.gnu.org/licenses/>.
+////////////////////////////////////////////////////////////////////////////////
+
+#ifndef GRAPHCOLORING_GRAPHS_VERTEX_H_
+#define GRAPHCOLORING_GRAPHS_VERTEX_H_
+
+#include "gui/colors.hpp"
+#include "gui/window.hpp"
+#include "colormenu.hpp"
+
+namespace graphcoloring {
+
+class Vertex {
+public:
+	static void ResetID();
+	Vertex(gui::Window* window, gui::Color color, int x, int y,
+		const gui::Position& viewport_position);
+	virtual ~Vertex();
+	void Lock();
+	void Unlock();
+	void SetDeleteCallback(std::function<void()> delete_callback);
+	bool operator==(const Vertex other) const;
+	gui::Color Color() const;
+	bool ChangeColor(gui::Color new_color);
+	int RenderX() const; // x-position when rendered
+	int RenderY() const;
+	bool IsHovering() const { return hovering; }; // Is the mouse hovering over this vertex?
+	void Render(int degree, bool filled = false, bool is_in_path = false,
+		bool is_last_vertex = false);
+	void RenderColorMenu();
+	static constexpr int VERTEX_RADIUS = 40;
+	int x;
+	int y;
+	const int id;
+	bool is_color_protected = false;
+	bool is_edge_protected = false;
+	bool is_delete_protected = false;
+	static int moving_vertex; // id of vertex that is being moved, or -1 if no vertex is being moved.
+private:
+	void SetClickCallback();
+	void SetMoveCallbacks();
+	void SetDeleteKeyCallback();
+	void MouseCallback(int mouse_x, int mouse_y);
+	void CheckIfMoving();
+	static int id_counter;
+	std::function<void()> delete_callback;
+	int mousedown_callback_id;
+	int m_keydown_callback_id;
+	int m_keyup_callback_id;
+	int x_keyup_callback_id;
+	gui::Window* const window;
+	gui::Color color;
+	bool hovering = false;
+	bool is_locked = false;
+	const gui::Position& viewport_position;
+	std::unique_ptr<ColorMenu> color_menu;
+};
+
+} // namespace graphcoloring
+
+#endif // GRAPHCOLORING_GRAPHS_VERTEX_H_