diff options
Diffstat (limited to 'src/graphcoloring/levels')
23 files changed, 2031 insertions, 0 deletions
diff --git a/src/graphcoloring/levels/colorloader.cpp b/src/graphcoloring/levels/colorloader.cpp new file mode 100644 index 0000000..a580333 --- /dev/null +++ b/src/graphcoloring/levels/colorloader.cpp @@ -0,0 +1,142 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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 "colorloader.hpp" + +#include "utils/errors.hpp" +#include "../level.hpp" +#include "../graphcoloring.hpp" + +namespace graphcoloring { + +ColorLoader::ColorLoader() +{ +} + +void ColorLoader::LoadDocument(const pugi::xml_document& document) +{ + Level::colors.clear(); + pugi::xml_node colors_node = document.child("colors"); + for (pugi::xml_node color_node : colors_node.children("color")) + { + std::string name = color_node.attribute("name").value(); + gui::Color color = + gui::colors::FromAttribute(color_node.attribute("color")); + int vertex_points = color_node.attribute("vertex-points").as_int(0); + int edge_points = color_node.attribute("edge-points").as_int(0); + color_names[name] = color; + vertex_color_points[color] = vertex_points; + edge_color_points[color] = edge_points; + Level::colors.push_back(color); + } +} + +gui::Color ColorLoader::GetColorByName(std::string name) const +{ + if (color_names.count(name) == 0) + utils::errors::Die("Could not find color: " + name); + return color_names.at(name); +} + +gui::Color ColorLoader::GetColorFromAttribute(pugi::xml_attribute attr) const +{ + if (attr.empty()) + return Level::colors[0]; + else + return GetColorByName(attr.value()); +} + +std::string ColorLoader::GetColorName(gui::Color color) const +{ + for (std::pair<std::string, gui::Color> color_name : color_names) + if (color_name.second == color) + return color_name.first; + utils::errors::Die("Could not find color."); + return ""; +} + +int ColorLoader::GetVertexPoints(gui::Color color) const +{ + if (vertex_color_points.count(color) == 0) + utils::errors::Die("Could not find color."); + return vertex_color_points.at(color); +} + +int ColorLoader::GetEdgePoints(gui::Color color) const +{ + if (edge_color_points.count(color) == 0) + utils::errors::Die("Could not find color."); + return edge_color_points.at(color); +} + +void ColorLoader::RenderColorPoints(gui::Window* window) const +{ + window->SetDrawColor(GraphColoring::BACKGROUND_COLOR); + window->Clear(); + int x = 10, y = 10; + const int w = COLOR_POINTS_COLUMN_WIDTH, h = Vertex::VERTEX_RADIUS * 2; + for (gui::Color color : Level::colors) + { + if (edge_color_points.at(color) == 0) continue; + RenderEdgeColorPoints(window, color, x, y); + y += h + 10; + if (y > window->GetHeight()-h-10) + { + y = 10; + x += w + 10; + } + } + for (gui::Color color : Level::colors) + { + if (vertex_color_points.at(color) == 0) continue; + RenderVertexColorPoints(window, color, x, y); + y += h + 10; + if (y > window->GetHeight()-h-10) + { + y = 10; + x += w + 10; + } + } + +} + +void ColorLoader::RenderEdgeColorPoints(gui::Window* window, gui::Color color, + int x, int y) const +{ + const int w = COLOR_POINTS_COLUMN_WIDTH, h = Vertex::VERTEX_RADIUS*2; + window->SetDrawColor(rules::RenderColor(color)); + window->DrawLine(x, y+h/2, x+w/4, y+h/2); + window->SetTextSize(48); + window->DrawText(std::to_string(GetEdgePoints(color)), + gui::Position(x+w, y), gui::Alignment::RIGHT, gui::Alignment::TOP); +} + +void ColorLoader::RenderVertexColorPoints(gui::Window* window, gui::Color color, + int x, int y) const +{ + const int w = COLOR_POINTS_COLUMN_WIDTH, r = Vertex::VERTEX_RADIUS; + window->SetDrawColor(rules::RenderColor(color)); + window->DrawCircle(x+r, y+r, r, false); + window->SetTextSize(48); + window->DrawText(std::to_string(GetVertexPoints(color)), + gui::Position(x+w, y+r), gui::Alignment::RIGHT, gui::Alignment::CENTER); +} + + + +} // namespace graphcoloring diff --git a/src/graphcoloring/levels/colorloader.hpp b/src/graphcoloring/levels/colorloader.hpp new file mode 100644 index 0000000..c5f52cc --- /dev/null +++ b/src/graphcoloring/levels/colorloader.hpp @@ -0,0 +1,54 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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_LEVELS_COLORLOADER_H_ +#define GRAPHCOLORING_LEVELS_COLORLOADER_H_ + +#include <map> +#include <string> + +#include "gui/window.hpp" +#include "pugi/pugixml.hpp" + +namespace graphcoloring { + +class ColorLoader { +public: + ColorLoader(); + virtual ~ColorLoader(){} + void LoadDocument(const pugi::xml_document& document); + gui::Color GetColorByName(std::string name) const; + gui::Color GetColorFromAttribute(pugi::xml_attribute attr) const; + std::string GetColorName(gui::Color color) const; + int GetVertexPoints(gui::Color color) const; + int GetEdgePoints(gui::Color color) const; + void RenderColorPoints(gui::Window* window) const; + std::map<std::string, gui::Color> color_names; + std::map<gui::Color, int> vertex_color_points; + std::map<gui::Color, int> edge_color_points; +private: + static constexpr int COLOR_POINTS_COLUMN_WIDTH = 200; + void RenderVertexColorPoints(gui::Window* window, gui::Color color, + int x, int y) const; + void RenderEdgeColorPoints(gui::Window* window, gui::Color color, + int x, int y) const; +}; + +} // namespace graphcoloring + +#endif // GRAPHCOLORING_LEVELS_COLORLOADER_H_ diff --git a/src/graphcoloring/levels/globalloader.cpp b/src/graphcoloring/levels/globalloader.cpp new file mode 100644 index 0000000..05b8cda --- /dev/null +++ b/src/graphcoloring/levels/globalloader.cpp @@ -0,0 +1,45 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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 "globalloader.hpp" + +namespace graphcoloring { + +GlobalLoader::GlobalLoader() +{ +} + +void GlobalLoader::LoadDocument(const pugi::xml_document& document) +{ + vertex_protections = + document.child("global-vertex-protections").attribute("protect").value(); + edge_protections = + document.child("global-edge-protections").attribute("protect").value(); +} + +bool GlobalLoader::IsVertexProtected(char protection) const +{ + return vertex_protections.find(protection) != std::string::npos; +} + +bool GlobalLoader::IsEdgeProtected(char protection) const +{ + return edge_protections.find(protection) != std::string::npos; +} + +} // namespace graphcoloring diff --git a/src/graphcoloring/levels/globalloader.hpp b/src/graphcoloring/levels/globalloader.hpp new file mode 100644 index 0000000..7a0b739 --- /dev/null +++ b/src/graphcoloring/levels/globalloader.hpp @@ -0,0 +1,40 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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_LEVELS_GLOBALLOADER_H_ +#define GRAPHCOLORING_LEVELS_GLOBALLOADER_H_ + +#include "pugi/pugixml.hpp" + +namespace graphcoloring { + +class GlobalLoader { +public: + GlobalLoader(); + virtual ~GlobalLoader() {} + void LoadDocument(const pugi::xml_document& document); + bool IsVertexProtected(char protection) const; + bool IsEdgeProtected(char protection) const; +private: + std::string vertex_protections; + std::string edge_protections; +}; + +} // namespace graphcoloring + +#endif // GRAPHCOLORING_LEVELS_GLOBALLOADER_H_ diff --git a/src/graphcoloring/levels/graphloader.cpp b/src/graphcoloring/levels/graphloader.cpp new file mode 100644 index 0000000..9b8b4b4 --- /dev/null +++ b/src/graphcoloring/levels/graphloader.cpp @@ -0,0 +1,178 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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 "graphloader.hpp" + +#include <sstream> + +#include "utils/errors.hpp" +#include "../level.hpp" +#include "../graphcoloring.hpp" + +namespace graphcoloring { + +GraphLoader::GraphLoader(const ColorLoader& color_loader_, + const GlobalLoader& global_loader_) + : color_loader(color_loader_), global_loader(global_loader_) +{} + +void GraphLoader::LoadDocument(const pugi::xml_document& document, Graph& graph) +{ + pugi::xml_node graph_node = document.child("graph"); + for (pugi::xml_node vertex_node : graph_node.children("vertex")) + ReadVertex(vertex_node, graph); + for (pugi::xml_node edge_node : graph_node.children("edge")) + ReadEdge(edge_node, graph); +} + +bool GraphLoader::IsVertexProtected(std::string protections, char protection) + const +{ + bool is_protected = protections.find(protection) != std::string::npos; + if (global_loader.IsVertexProtected(protection)) + is_protected = true; + return is_protected; +} +bool GraphLoader::IsEdgeProtected(std::string protections, char protection) + const +{ + bool is_protected = protections.find(protection) != std::string::npos; + if (global_loader.IsEdgeProtected(protection)) + is_protected = true; + return is_protected; +} + +void GraphLoader::ReadVertex(pugi::xml_node vertex_node, Graph& graph) +{ + int x = vertex_node.attribute("x").as_int(); + int y = vertex_node.attribute("y").as_int(); + + int v_id = graph.AddVertex(x, y); + Vertex& v = graph.GetVertexByID(v_id); + + if (!vertex_node.attribute("origin").empty()) + { + v.is_delete_protected = true; + graph.AddOrigin(v_id); + } + + + + if (!vertex_node.attribute("id").empty()) + { + vertex_ids[vertex_node.attribute("id").value()] = v.id; + } + + gui::Color color + = color_loader.GetColorFromAttribute(vertex_node.attribute("color")); + v.ChangeColor(color); + // NOTE: This next line does handle the case where there is no protect + // specified; pugixml will default to "". + std::string protections = vertex_node.attribute("protect").value(); + v.is_color_protected = IsVertexProtected(protections, PROTECT_COLOR); + v.is_delete_protected = IsVertexProtected(protections, PROTECT_DELETE); + v.is_edge_protected = IsVertexProtected(protections, PROTECT_EDGE); +} + +void GraphLoader::ReadEdge(pugi::xml_node edge_node, Graph& graph) +{ + std::string v1_name = edge_node.attribute("v1").value(); + std::string v2_name = edge_node.attribute("v2").value(); + + int v1 = GetVertexByName(v1_name); + int v2 = GetVertexByName(v2_name); + if (v1 == -1) + utils::errors::Die("There is no vertex named " + v1_name); + if (v2 == -1) + utils::errors::Die("There is no vertex named " + v2_name); + + int e_id = graph.AddEdge(v1, v2); + Edge& e = graph.GetEdgeByID(e_id); + if (!edge_node.attribute("id").empty()) + { + edge_ids[edge_node.attribute("id").value()] = e.id; + } + gui::Color color + = color_loader.GetColorFromAttribute(edge_node.attribute("color")); + e.ChangeColor(color); + + std::string protections = edge_node.attribute("protect").value(); + e.is_color_protected = IsEdgeProtected(protections, PROTECT_COLOR); + e.is_delete_protected = IsEdgeProtected(protections, PROTECT_DELETE); +} + +void GraphLoader::WriteVertex(const Vertex& vertex, pugi::xml_node& node) const +{ + node.set_name("vertex"); + node.append_attribute("x") = vertex.x; + node.append_attribute("y") = vertex.y; + node.append_attribute("id") = vertex.id; + node.append_attribute("color") = color_loader.GetColorName(vertex.Color()) + .c_str(); + std::stringstream protections; + if (vertex.is_color_protected) protections << PROTECT_COLOR; + if (vertex.is_delete_protected) protections << PROTECT_DELETE; + if (vertex.is_edge_protected) protections << PROTECT_EDGE; + node.append_attribute("protect") = protections.str().c_str(); +} + +void GraphLoader::WriteEdge(const Edge& edge, pugi::xml_node& node) const +{ + node.set_name("edge"); + node.append_attribute("v1") = edge.from.id; + node.append_attribute("v2") = edge.to.id; + node.append_attribute("id") = edge.id; + node.append_attribute("color") = color_loader.GetColorName(edge.Color()) + .c_str(); + std::stringstream protections; + if (edge.is_color_protected) protections << PROTECT_COLOR; + if (edge.is_delete_protected) protections << PROTECT_DELETE; + node.append_attribute("protect") = protections.str().c_str(); +} + +void GraphLoader::WriteGraph(const Graph& graph, pugi::xml_node& node) const +{ + for (const Vertex* v : graph.vertices) + { + pugi::xml_node vertex_node = node.append_child("vertex"); + WriteVertex(*v, vertex_node); + } + for (const Edge* e : graph.edges) + { + pugi::xml_node edge_node = node.append_child("edge"); + WriteEdge(*e, edge_node); + } +} + +int GraphLoader::GetVertexByName(const std::string& name) const +{ + if (vertex_ids.count(name)) + return vertex_ids.at(name); + else + return -1; +} + +int GraphLoader::GetEdgeByName(const std::string& name) const +{ + if (edge_ids.count(name)) + return edge_ids.at(name); + else + return -1; +} + +} // namespace graphcoloring diff --git a/src/graphcoloring/levels/graphloader.hpp b/src/graphcoloring/levels/graphloader.hpp new file mode 100644 index 0000000..b17f7e8 --- /dev/null +++ b/src/graphcoloring/levels/graphloader.hpp @@ -0,0 +1,57 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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_LEVELS_GRAPHLOADER_H_ +#define GRAPHCOLORING_LEVELS_GRAPHLOADER_H_ + +#include <memory> + +#include "../graphs/graph.hpp" +#include "pugi/pugixml.hpp" +#include "colorloader.hpp" +#include "globalloader.hpp" + +namespace graphcoloring { + +class GraphLoader { +public: + GraphLoader(const ColorLoader& color_loader, + const GlobalLoader& global_loader); + virtual ~GraphLoader() {} + // Load document into graph + void LoadDocument(const pugi::xml_document& document, Graph& graph); + // Returns id of vertex, or -1 if there is no vertex with that name. + int GetVertexByName(const std::string& name) const; + int GetEdgeByName(const std::string& name) const; + void WriteGraph(const Graph& graph, pugi::xml_node& node) const; + std::map<std::string, int> vertex_ids; + std::map<std::string, int> edge_ids; +private: + bool IsVertexProtected(std::string protections, char protection) const; + bool IsEdgeProtected(std::string protections, char protection) const; + void ReadVertex(pugi::xml_node vertex_node, Graph& graph); + void ReadEdge(pugi::xml_node edge_node, Graph& graph); + void WriteVertex(const Vertex& vertex, pugi::xml_node& node) const; + void WriteEdge(const Edge& edge, pugi::xml_node& node) const; + const ColorLoader& color_loader; + const GlobalLoader& global_loader; +}; + +} // namespace graphcoloring + +#endif // GRAPHCOLORING_LEVELS_GRAPHLOADER_H_ diff --git a/src/graphcoloring/levels/paths/path.cpp b/src/graphcoloring/levels/paths/path.cpp new file mode 100644 index 0000000..6528b18 --- /dev/null +++ b/src/graphcoloring/levels/paths/path.cpp @@ -0,0 +1,207 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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 "path.hpp" + +#include <cassert> +#include <algorithm> + +namespace graphcoloring { + +constexpr gui::Color Path::ANY_COLOR; + +Path::Path(gui::Window* window_, + Graph& graph_, const RuleLoader& rule_loader_, + const ColorLoader& color_loader_) + : window(window_), graph(graph_), rule_loader(rule_loader_), + color_loader(color_loader_) +{ + window->SetMouseupCallback([this] (gui::Window*,int,int) { + RightClick(); + }, GDK_BUTTON_SECONDARY); + window->SetKeyupCallback([this] (gui::Window*) { + ResetPath(); + }, GDK_KEY_q); +} + +void Path::LoadFromNode(pugi::xml_node node) +{ + std::string name = node.name(); + + if (name == "cycle") + type = Type::CYCLE; + else + type = Type::PATH; + + points_starting_value = node.attribute("points").as_int(0); + + for (pugi::xml_node point_node : node.children()) + { + std::string name = point_node.name(); + if (name != "edge") continue; + std::string color_str = point_node.attribute("color").value(); + gui::Color color; + if (color_str == "any") + color = ANY_COLOR; + else + color = + color_loader.GetColorFromAttribute( + point_node.attribute("color")); + color_operations[color] = LoadOperation(point_node); + } +} + +void Path::LoadFromDocument(const pugi::xml_document& document) +{ + for (pugi::xml_node node : document.children()) + { + std::string name = node.name(); + if (name != "cycle" && name != "path") continue; + LoadFromNode(node); + break; + } +} + +Path::operation_t Path::LoadOperation(pugi::xml_node node) +{ + int val = node.attribute("val").as_int(0); + std::map<std::string, operation_t> operations = { + {"+", [val] (int a) { return a + val; }}, + {"-", [val] (int a) { return a - val; }}, + {"*", [val] (int a) { return a * val; }}, + {"/", [val] (int a) { return a / val; }}, + {"%", [val] (int a) { return a % val; }} + }; + std::string op = node.attribute("op").value(); + return operations[op]; +} + +void Path::RightClick() +{ + if (!IsPath()) return; + if (!rule_loader.IsValid(graph)) return; + int vertex_id = graph.GetHoveringVertex(); + if (vertex_id == -1) return; + graph.Lock(); + if (last_vertex == -1) + { + last_vertex = vertex_id; + if (first_vertex == -1) + first_vertex = vertex_id; + return; + } + if (last_vertex == vertex_id) // Remove end of path + { + if (path.size() == 0) + { + ResetPath(); + return; + } + int edge_id = path.at(path.size()-1); + path.pop_back(); + last_vertex = + graph.GetEdgeByIDConst(edge_id).OtherEndpoint(last_vertex); + return; + } + if (!graph.HasEdge(last_vertex, vertex_id)) + { + return; + } + int edge_id = graph.GetEdgeByEndpointsConst(last_vertex, vertex_id).id; + if (std::find(path.begin(), path.end(), edge_id) != path.end()) // Duplicate edge + return; + path.push_back(edge_id); + last_vertex = vertex_id; +} + +void Path::ResetPath() +{ + if (!IsPath()) return; + graph.Unlock(); + path = std::vector<int>(); + is_making_path = false; + first_vertex = -1; + last_vertex = -1; +} + +std::vector<int> Path::GetPath() const +{ + return path; +} + +std::set<int> Path::PathEdgeSet() const +{ + return std::set<int>(path.begin(), path.end()); + +} + +std::set<int> Path::PathVertexSet() const +{ + std::set<int> vertices; + if (last_vertex != -1) + vertices.insert(last_vertex); + for (int e : path) + { + const Edge& edge = graph.GetEdgeByIDConst(e); + vertices.insert(edge.from.id); + vertices.insert(edge.to.id); + } + return vertices; +} + +int Path::LastVertex() const +{ + return last_vertex; +} + +bool Path::IsMakingPath() const +{ + return is_making_path; +} + +bool Path::IsPath() const +{ + return type != Type::NO_PATH; +} + +int Path::Points() const +{ + if (!IsPath()) return 0; + if (type == Type::CYCLE) + { + if (path.size() < 2) + return 0; + if (first_vertex != last_vertex) + return 0; + } + int points = points_starting_value; + for (int e : path) + { + const Edge& edge = graph.GetEdgeByIDConst(e); + if (color_operations.count(edge.Color()) + && color_operations.at(edge.Color())) + points = color_operations.at(edge.Color())(points); + + if (color_operations.count(ANY_COLOR) + && color_operations.at(ANY_COLOR)) + points = color_operations.at(ANY_COLOR)(points); + } + return points; +} + +} // namespace graphcoloring diff --git a/src/graphcoloring/levels/paths/path.hpp b/src/graphcoloring/levels/paths/path.hpp new file mode 100644 index 0000000..294b1a2 --- /dev/null +++ b/src/graphcoloring/levels/paths/path.hpp @@ -0,0 +1,70 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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_LEVELS_PATHS_PATH_H_ +#define GRAPHCOLORING_LEVELS_PATHS_PATH_H_ + +#include "gui/window.hpp" +#include "graphcoloring/levels/rules/ruleloader.hpp" + +namespace graphcoloring { + +class Path { +public: + Path(gui::Window* window, + Graph& graph, const RuleLoader& rule_loader, + const ColorLoader& color_loader); + virtual ~Path() {} + void LoadFromDocument(const pugi::xml_document& document); + void ResetPath(); + bool IsPath() const; // Is there a path in the document? + std::vector<int> GetPath() const; + std::set<int> PathEdgeSet() const; + std::set<int> PathVertexSet() const; + int LastVertex() const; // -1 if no last vertex + bool IsMakingPath() const; + int Points() const; +private: + enum class Type + { + NO_PATH, // There is no path in the document. + CYCLE, + PATH + }; + typedef std::function<int(int)> operation_t; + static constexpr gui::Color ANY_COLOR = 0; + void LoadFromNode(pugi::xml_node node); + void RightClick(); + operation_t LoadOperation(pugi::xml_node node); + gui::Window* window; + Graph& graph; + const RuleLoader& rule_loader; + const ColorLoader& color_loader; + Type type = Type::NO_PATH; + bool is_making_path = false; + int first_vertex = -1; + int last_vertex = -1; + std::vector<int> path; + int points_starting_value = 0; + std::map<gui::Color, operation_t> color_operations; + +}; + +} // namespace graphcoloring + +#endif // GRAPHCOLORING_LEVELS_PATHS_PATH_H_ diff --git a/src/graphcoloring/levels/pointcalculator.cpp b/src/graphcoloring/levels/pointcalculator.cpp new file mode 100644 index 0000000..09f761e --- /dev/null +++ b/src/graphcoloring/levels/pointcalculator.cpp @@ -0,0 +1,48 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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 "pointcalculator.hpp" + +namespace graphcoloring { + +PointCalculator::PointCalculator(const ValueLoader& value_loader_, + const RuleLoader& rule_loader_, const ColorLoader& color_loader_, + const Path& path_) + : value_loader(value_loader_), rule_loader(rule_loader_), + color_loader(color_loader_), path(path_) +{} + +int PointCalculator::Points(const Graph& graph, bool check_if_invalid) const +{ + if (check_if_invalid) + { + bool is_valid = rule_loader.IsValid(graph); + if (!is_valid) return 0; + } + int points = value_loader.Points(graph); + for (const Vertex* v : graph.vertices) + points += color_loader.GetVertexPoints(v->Color()); + for (const Edge* e : graph.edges) + points += color_loader.GetEdgePoints(e->Color()); + + points += path.Points(); + + return points; +} + +} // namespace graphcoloring diff --git a/src/graphcoloring/levels/pointcalculator.hpp b/src/graphcoloring/levels/pointcalculator.hpp new file mode 100644 index 0000000..5baee6c --- /dev/null +++ b/src/graphcoloring/levels/pointcalculator.hpp @@ -0,0 +1,45 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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_LEVELS_POINTCALCULATOR_H_ +#define GRAPHCOLORING_LEVELS_POINTCALCULATOR_H_ + +#include "valueloader.hpp" +#include "colorloader.hpp" +#include "rules/ruleloader.hpp" +#include "paths/path.hpp" + +namespace graphcoloring { + +class PointCalculator { +public: + PointCalculator(const ValueLoader& value_loader, + const RuleLoader& rule_loader, const ColorLoader& color_loader, + const Path& path); + int Points(const Graph& graph, bool check_if_invalid = true) const; + virtual ~PointCalculator() {} +private: + const ValueLoader& value_loader; + const RuleLoader& rule_loader; + const ColorLoader& color_loader; + const Path& path; +}; + +} // namespace graphcoloring + +#endif // GRAPHCOLORING_LEVELS_POINTCALCULATOR_H_ diff --git a/src/graphcoloring/levels/rules/boundrule.cpp b/src/graphcoloring/levels/rules/boundrule.cpp new file mode 100644 index 0000000..0aef4af --- /dev/null +++ b/src/graphcoloring/levels/rules/boundrule.cpp @@ -0,0 +1,135 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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 "boundrule.hpp" + +#include "graphcoloring/level.hpp" +#include "utils/errors.hpp" + +namespace graphcoloring { +namespace rules { + +BoundRule::BoundRule(gui::Color color_, int bound_, bool bound_type_, + bool rule_type_) + : color(color_), bound(bound_), bound_type(bound_type_), + rule_type(rule_type_) +{} + + +BoundRule::BoundRule(pugi::xml_node node, const ColorLoader& color_loader) +{ + LoadFromNode(node, color_loader); +} + +void BoundRule::LoadFromNode(pugi::xml_node node, + const ColorLoader& color_loader) +{ + std::string name(node.name()); + if (name.substr(name.length()-7) == std::string("minimum")) + bound_type = MINIMUM; + else + bound_type = MAXIMUM; + + if (name.substr(0,name.length()-8) == std::string("vertex")) + rule_type = VERTEX_RULE; + else + rule_type = EDGE_RULE; + color = ColorFromAttribute(node.attribute("color"), color_loader); + bound = node.attribute(bound_type == MINIMUM ? "min" : "max").as_int(0); +} + +bool BoundRule::CheckAllCounts(const Graph& graph) const +{ + std::map<gui::Color, int> counts; + for (gui::Color color : Level::colors) + counts[color] = 0; + if (rule_type == VERTEX_RULE) + { + for (const Vertex* v : graph.vertices) + { + if (counts.count(v->Color())) + counts[v->Color()]++; + } + } + else + { + for (const Edge* e : graph.edges) + { + if (counts.count(e->Color())) + counts[e->Color()]++; + else + counts[e->Color()] = 1; + } + } + for (std::pair<gui::Color, int> count : counts) + { + if (bound_type == MINIMUM && count.second < bound) + return false; + if (bound_type == MAXIMUM && count.second > bound) + return false; + } + return true; +} + +bool BoundRule::ObeysRule(const Graph& graph) const +{ + if (color == SAME_COLOR) // For same, check if any color is out of bounds. + return CheckAllCounts(graph); + + int count = 0; + if (rule_type == VERTEX_RULE) + { + for (const Vertex* v : graph.vertices) + if (IsSameColor(v->Color(), color)) + count++; + } + else + { + for (const Edge* e : graph.edges) + if (IsSameColor(e->Color(), color)) + count++; + } + return bound_type == MINIMUM ? (count >= bound) : (count <= bound); +} + +int BoundRule::Render(gui::Window* window, int x, int y, int width) const +{ + int r = Vertex::VERTEX_RADIUS; + window->SetDrawColor(RenderColor(color)); + if (rule_type == VERTEX_RULE) + { + window->DrawCircle(x+r, y+r, r, false); + } + else + { + window->DrawLine(x, y+r, x+width/4, y+r); + } + window->SetTextSize(r*2); + window->DrawText(std::to_string(bound), gui::Position(x+width, y+r), + gui::Alignment::RIGHT, gui::Alignment::CENTER); + window->DrawText(bound_type == MAXIMUM ? ">" : "<", + gui::Position(x+width/2, y+r), + gui::Alignment::CENTER, gui::Alignment::CENTER); + window->SetDrawColor(0xFF0000FF); + window->DrawLine(x+3*width/8, y, x+5*width/8, y+2*r); + return r*2; +} + + +} // namespace rules +} // namespace graphcoloring diff --git a/src/graphcoloring/levels/rules/boundrule.hpp b/src/graphcoloring/levels/rules/boundrule.hpp new file mode 100644 index 0000000..a1c5e09 --- /dev/null +++ b/src/graphcoloring/levels/rules/boundrule.hpp @@ -0,0 +1,55 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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_LEVELS_RULES_BOUNDRULE_H_ +#define GRAPHCOLORING_LEVELS_RULES_BOUNDRULE_H_ + +#include "graphcoloring/graphs/graph.hpp" + +#include "rules.hpp" +#include "rule.hpp" + +namespace graphcoloring { +namespace rules { + +class BoundRule : public Rule { +public: + BoundRule(gui::Color color = ANY_COLOR, + int bound = 0, bool bound_type = MAXIMUM, + bool rule_type = VERTEX_RULE); + BoundRule(pugi::xml_node node, const ColorLoader& color_loader); + void LoadFromNode(pugi::xml_node node, const ColorLoader& color_loader); + virtual ~BoundRule() {} + bool ObeysRule(const Graph& graph) const; + int Render(gui::Window* window, int x, int y, int width) const; +private: + bool CheckAllCounts(const Graph& graph) const; + static constexpr bool EDGE_RULE = false; + static constexpr bool VERTEX_RULE = true; + static constexpr bool MINIMUM = false; + static constexpr bool MAXIMUM = true; + gui::Color color; + int bound; + bool bound_type; + bool rule_type; +}; + +} // namespace rules +} // namespace graphcoloring + +#endif // GRAPHCOLORING_LEVELS_RULES_BOUNDRULE_H_ diff --git a/src/graphcoloring/levels/rules/edgerule.cpp b/src/graphcoloring/levels/rules/edgerule.cpp new file mode 100644 index 0000000..e2a3a74 --- /dev/null +++ b/src/graphcoloring/levels/rules/edgerule.cpp @@ -0,0 +1,82 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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 "edgerule.hpp" + +namespace graphcoloring { +namespace rules { + +EdgeRule::EdgeRule(gui::Color vcolor1, gui::Color vcolor2, gui::Color ecolor) + : vertex_color1(vcolor1), vertex_color2(vcolor2), edge_color(ecolor) +{} + +EdgeRule::EdgeRule(pugi::xml_node node, const ColorLoader& color_loader) +{ + LoadFromNode(node, color_loader); +} + +void EdgeRule::LoadFromNode(pugi::xml_node node,const ColorLoader& color_loader) +{ + vertex_color1 = ColorFromAttribute(node.attribute("v1"), color_loader); + vertex_color2 = ColorFromAttribute(node.attribute("v2"), color_loader); + edge_color = ColorFromAttribute(node.attribute("edge"), color_loader); +} + +bool EdgeRule::ObeysRule(const Edge& edge) const +{ + ResetSameColor(); + if (!IsSameColor(edge.Color(), edge_color)) return true; + + gui::Color v1 = edge.from.Color(); + gui::Color v2 = edge.to.Color(); + bool obeys + = !((IsSameColor(v1,vertex_color1) && IsSameColor(v2,vertex_color2)) + || (IsSameColor(v2,vertex_color1) && IsSameColor(v1,vertex_color2))); + ResetSameColor(); + return obeys; +} + +bool EdgeRule::ObeysRule(const Graph& graph) const +{ + for (const Edge* e : graph.edges) + if (!ObeysRule(*e)) + return false; + return true; +} + +int EdgeRule::Render(gui::Window* window, int x, int y, int width) const +{ + int r = Vertex::VERTEX_RADIUS; + // First vertex + window->SetDrawColor(RenderColor(vertex_color1)); + window->DrawCircle(x+r, y+r, r, false); + // Edge + window->SetDrawColor(RenderColor(edge_color)); + window->DrawLine(x+2*r, y+r, x+width-2*r, y+r); + // Second vertex + window->SetDrawColor(RenderColor(vertex_color2)); + window->DrawCircle(x+width-r, y+r, r, false); + // Red line + window->SetDrawColor(0xFF0000FF); + window->DrawLine(x+width/2-r/2, y+r/2, x+width/2+r/2, y+3*r/2); + return r*2; + +} + +} // namespace rules +} // namespace graphcoloring diff --git a/src/graphcoloring/levels/rules/edgerule.hpp b/src/graphcoloring/levels/rules/edgerule.hpp new file mode 100644 index 0000000..187baf7 --- /dev/null +++ b/src/graphcoloring/levels/rules/edgerule.hpp @@ -0,0 +1,51 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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_LEVELS_RULES_EDGERULE_H_ +#define GRAPHCOLORING_LEVELS_RULES_EDGERULE_H_ + +#include "graphcoloring/graphs/graph.hpp" +#include "rules.hpp" +#include "rule.hpp" + +namespace graphcoloring { +namespace rules { + +class EdgeRule : public Rule { +public: + EdgeRule(gui::Color vertex_color1 = ANY_COLOR, + gui::Color vertex_color2 = ANY_COLOR, + gui::Color edge_color = ANY_COLOR); + EdgeRule(pugi::xml_node node, const ColorLoader& color_loader); + void LoadFromNode(pugi::xml_node node, const ColorLoader& color_loader); + bool ObeysRule(const Graph& graph) const; + int Render(gui::Window* window, int x, int y, int width) const; + virtual ~EdgeRule() {} +private: + bool ObeysRule(const Edge& edge) const; + gui::Color vertex_color1; + gui::Color vertex_color2; + gui::Color edge_color; + +}; + +} // namespace rules +} // namespace graphcoloring + +#endif // GRAPHCOLORING_LEVELS_RULES_EDGERULE_H_ diff --git a/src/graphcoloring/levels/rules/rule.hpp b/src/graphcoloring/levels/rules/rule.hpp new file mode 100644 index 0000000..5856fc0 --- /dev/null +++ b/src/graphcoloring/levels/rules/rule.hpp @@ -0,0 +1,37 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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_LEVELS_RULES_RULE_H_ +#define GRAPHCOLORING_LEVELS_RULES_RULE_H_ + +#include "graphcoloring/graphs/graph.hpp" + +namespace graphcoloring { +namespace rules { + +class Rule { +public: + virtual ~Rule() {} + virtual bool ObeysRule(const Graph& graph) const = 0; + virtual int Render(gui::Window* window, int x, int y, int width) const = 0; // Returns height +}; + +} // namespace rules +} // namespace graphcoloring + +#endif /* GRAPHCOLORING_LEVELS_RULES_RULE_H_ */ diff --git a/src/graphcoloring/levels/rules/ruleloader.cpp b/src/graphcoloring/levels/rules/ruleloader.cpp new file mode 100644 index 0000000..e741594 --- /dev/null +++ b/src/graphcoloring/levels/rules/ruleloader.cpp @@ -0,0 +1,92 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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 "ruleloader.hpp" + +#include "graphcoloring/graphcoloring.hpp" + +namespace graphcoloring { + +RuleLoader::RuleLoader() {} + +void RuleLoader::LoadDocument(const pugi::xml_document& document, + const ColorLoader& color_loader) +{ + for (pugi::xml_node rule_node : document.child("rules").children()) + { + std::string name = rule_node.name(); + if (name == "connected") + connected_rule = true; + // These node methods will check the name of the node. + LoadEdgeRule(rule_node, color_loader); + LoadMaximumRule(rule_node, color_loader); + + } +} + +void RuleLoader::LoadEdgeRule(pugi::xml_node node, + const ColorLoader& color_loader) +{ + std::string name = node.name(); + if (name != "edge-rule") return; + rules::EdgeRule rule(node, color_loader); + edge_rules.push_back(rule); + all_rules.push_back(std::make_unique<rules::EdgeRule>(rule)); +} + +void RuleLoader::LoadMaximumRule(pugi::xml_node node, + const ColorLoader& color_loader) +{ + std::string name = node.name(); + if (name != "vertex-maximum" && name != "edge-maximum" + && name != "vertex-minimum" && name != "edge-minimum") + return; + rules::BoundRule rule(node, color_loader); + maximum_rules.push_back(rule); + all_rules.push_back(std::make_unique<rules::BoundRule>(rule)); +} + + +bool RuleLoader::IsValid(const Graph& graph) const +{ + for (auto& rule : all_rules) + if (!rule->ObeysRule(graph)) + return false; + if (connected_rule && !graph.IsConnected()) + return false; + return true; +} + +void RuleLoader::RenderRules(gui::Window* window) const +{ + window->SetDrawColor(GraphColoring::BACKGROUND_COLOR); + window->Clear(); + int x = 10, y = 10; + for (auto& rule : all_rules) + { + if (y >= window->GetHeight()-2*Vertex::VERTEX_RADIUS-10) + { + y = 10; + x += 50 + RULE_COLUMN_WIDTH; + } + int height = rule->Render(window, x, y, RULE_COLUMN_WIDTH); + y += height + 10; + } +} + +} // namespace graphcoloring diff --git a/src/graphcoloring/levels/rules/ruleloader.hpp b/src/graphcoloring/levels/rules/ruleloader.hpp new file mode 100644 index 0000000..8089cb5 --- /dev/null +++ b/src/graphcoloring/levels/rules/ruleloader.hpp @@ -0,0 +1,53 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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_LEVELS_RULELOADER_H_ +#define GRAPHCOLORING_LEVELS_RULELOADER_H_ + +#include "pugi/pugixml.hpp" + +#include "graphcoloring/levels/colorloader.hpp" +#include "graphcoloring/graphs/graph.hpp" +#include "boundrule.hpp" +#include "edgerule.hpp" + +namespace graphcoloring { + +class RuleLoader { +public: + static constexpr gui::Color ANY_COLOR = 0x00000000; + RuleLoader(); + virtual ~RuleLoader() {} + void LoadDocument(const pugi::xml_document& document, + const ColorLoader& color_loader); + bool IsValid(const Graph& graph) const; // O(Rules * Edges) + void RenderRules(gui::Window* window) const; +private: + void LoadEdgeRule(pugi::xml_node node, const ColorLoader& color_loader); + void LoadMaximumRule(pugi::xml_node node, const ColorLoader& color_loader); + static constexpr int RULE_COLUMN_WIDTH = 200; + std::vector<rules::EdgeRule> edge_rules; + std::vector<rules::BoundRule> maximum_rules; + bool connected_rule = false; // true if the graph should be connected + std::vector<std::unique_ptr<rules::Rule>> all_rules; + +}; + +} // namespace graphcoloring + +#endif // GRAPHCOLORING_LEVELS_RULELOADER_H_ diff --git a/src/graphcoloring/levels/rules/rules.cpp b/src/graphcoloring/levels/rules/rules.cpp new file mode 100644 index 0000000..2b9537f --- /dev/null +++ b/src/graphcoloring/levels/rules/rules.cpp @@ -0,0 +1,72 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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 "rules.hpp" + +namespace graphcoloring { +namespace rules { + +static gui::Color same_color = ANY_COLOR; + +void ResetSameColor() { same_color = ANY_COLOR; } + +bool IsSameColor(gui::Color color1, gui::Color color2) +{ + if (color1 == ANY_COLOR || color2 == ANY_COLOR) + return true; + + if (same_color == ANY_COLOR) + { + if (color1 == SAME_COLOR && color2 != SAME_COLOR) + { + same_color = color2; + return true; + } + if (color2 == SAME_COLOR && color1 != SAME_COLOR) + { + same_color = color1; + return true; + } + } + if (color1 == SAME_COLOR && color2 == same_color) + return true; + if (color2 == SAME_COLOR && color1 == same_color) + return true; + + return color1 == color2; +} + +gui::Color RenderColor(gui::Color color) +{ + if (color == ANY_COLOR) + return gui::colors::WHITE; + if (color == SAME_COLOR) + return 0x666666FF; + return color; +} + +gui::Color ColorFromAttribute(pugi::xml_attribute attr, + const ColorLoader& color_loader) +{ + if (attr.empty()) return ANY_COLOR; + if (std::string(attr.value()) == "same") return SAME_COLOR; + return attr.empty() ? ANY_COLOR : color_loader.GetColorFromAttribute(attr); +} + +} // namespace rules +} // namespace graphcoloring diff --git a/src/graphcoloring/levels/rules/rules.hpp b/src/graphcoloring/levels/rules/rules.hpp new file mode 100644 index 0000000..2e6d83c --- /dev/null +++ b/src/graphcoloring/levels/rules/rules.hpp @@ -0,0 +1,42 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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_LEVELS_RULES_RULES_H_ +#define GRAPHCOLORING_LEVELS_RULES_RULES_H_ + +#include "pugi/pugixml.hpp" +#include "../colorloader.hpp" + +namespace graphcoloring { +namespace rules { + +constexpr gui::Color ANY_COLOR = 0; +constexpr gui::Color SAME_COLOR = 1; // Refers to patterns like same-red-same, which can mean blue-red-blue, red-red-red, etc. +extern void ResetSameColor(); // Forget about "same" color +extern bool IsSameColor(gui::Color color1, gui::Color color2); +extern gui::Color RenderColor(gui::Color color); // Turns ANY_COLOR into white. +extern gui::Color ColorFromAttribute(pugi::xml_attribute attr, + const ColorLoader& color_loader); // ANY_COLOR if attribute is empty. + +} // namespace rules +} // namespace graphcoloring + + + +#endif /* SRC_GRAPHCOLORING_LEVELS_RULES_RULES_HPP_ */ diff --git a/src/graphcoloring/levels/value.cpp b/src/graphcoloring/levels/value.cpp new file mode 100644 index 0000000..f84d019 --- /dev/null +++ b/src/graphcoloring/levels/value.cpp @@ -0,0 +1,304 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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 "value.hpp" + +#include <algorithm> +#include <sstream> + +#include "utils/errors.hpp" + +namespace graphcoloring { + +std::map<std::string, Value::operation_t> Value::operation_table; + +Value::Value() : type(Type::NULL_TYPE) {} + +Value::Value(int val_) +{ + val = val_; + type = Type::VALUE; +} + +Value::Value(std::vector<Value> list_) +{ + list = list_; + type = Type::LIST; +} + +Value::Value(const std::string& string) +{ + FromString(string); +} + +void Value::FromString(const std::string& string) +{ + const std::map<std::string, Type> type_map = + { + {"", Type::NULL_TYPE}, + {"V", Type::NUMBER_OF_VERTICES}, + {"E", Type::NUMBER_OF_EDGES}, + {"vertices", Type::VERTICES}, + {"edges", Type::EDGES} + }; + if (type_map.count(string)) + { + type = type_map.at(string); + return; + } + try + { + val = std::stoi(string); + type = Type::VALUE; + } + catch (std::invalid_argument&) + { + // NOTE: Does not check if variable exists! This means that errors + // will only be caught when the variable is evaluated, but it allows + // out-of-order declaration. + type = Type::VARIABLE; + variable_name = string; + } +} + + +Value::Value(pugi::xml_node node) +{ + std::string name = node.name(); + if (name == "op") + { + std::string v1 = node.attribute("val1").value(); + std::string v2 = node.attribute("val2").value(); + std::string op = node.attribute("op").value(); + type = Type::OPERATION; + val1 = std::shared_ptr<Value>(new Value(v1)); + val2 = std::shared_ptr<Value>(new Value(v2)); + ReadOperation(op); + } + else if (name == "var") + { + FromString(node.attribute("val").value()); + } + else if (name == "map" || name == "fold") + { + if (name == "map") + type = Type::MAP; + else + type = Type::FOLD; + std::string op = node.attribute("op").value(); + std::string v = node.attribute("val").value(); + std::string start = node.attribute("start").value(); + if (v == "") + utils::errors::Die("No argument passed to " + name + "."); + ReadOperation(op); + val1 = std::shared_ptr<Value>(new Value(v)); + fold_start = std::shared_ptr<Value>(new Value(start)); + } + else if (name == "zip") + { + type = Type::ZIP; + std::string op = node.attribute("op").value(); + std::string v1 = node.attribute("val1").value(); + std::string v2 = node.attribute("val2").value(); + if (v1 == "" || v2 == "") + utils::errors::Die("Empty argument passed to zip."); + ReadOperation(op); + val1 = std::shared_ptr<Value>(new Value(v1)); + val2 = std::shared_ptr<Value>(new Value(v2)); + } + else + { + utils::errors::Die("Unknown tag: " + name); + } +} + +Value::operation_t Value::SimpleOperation(std::function<int(int,int)> op) +{ + return [op](const Graph&, int a, int b) { return op(a, b); }; +} + +Value::operation_t Value::SimpleBoolOperation(std::function<bool(int,int)> op) +{ + return [op](const Graph&, int a, int b) { return op(a, b) ? 1 : 0; }; +} + +Value::operation_t Value::SimpleLogicOperation(std::function<bool(bool,bool)>op) +{ + return [op](const Graph&, int a, int b) { + return op(a != 0, b != 0) ? 1 : 0; + }; +} + +void Value::InitializeOperationTable() +{ + operation_table = { + {"min", SimpleOperation([](int a, int b)->int{return std::min(a,b);})}, + {"max", SimpleOperation([](int a, int b)->int{return std::max(a,b);})}, + {"+", SimpleOperation(std::plus<int>())}, + {"-", SimpleOperation(std::minus<int>())}, + {"*", SimpleOperation(std::multiplies<int>())}, + {"/", SimpleOperation(std::divides<int>())}, + {"%", SimpleOperation(std::modulus<int>())}, + {"=", SimpleBoolOperation(std::equal_to<int>())}, + {"!=", SimpleBoolOperation(std::not_equal_to<int>())}, + {"<", SimpleBoolOperation(std::less<int>())}, + {">", SimpleBoolOperation(std::greater<int>())}, + {"<=", SimpleBoolOperation(std::less_equal<int>())}, + {">=", SimpleBoolOperation(std::greater_equal<int>())}, + {"and", SimpleLogicOperation(std::logical_and<bool>())}, + {"or", SimpleLogicOperation(std::logical_or<bool>())}, + {"not", SimpleLogicOperation([](bool a, bool b)->bool{ + return !a; // Ignore second argument. + })}, + {"v1", [](const Graph& graph, int e, int)->int { + return graph.GetEdgeByIDConst(e).from.id; + }}, + {"v2", [](const Graph& graph, int e, int)->int { + return graph.GetEdgeByIDConst(e).to.id; + }}, + {"connected", [](const Graph& graph, int v1, int v2)->int { + if (!graph.HasVertexWithID(v1) || !graph.HasVertexWithID(v2)) + return 0; + return graph.HasEdge(v1, v2) ? 1 : 0; + }}, + {"degree", [](const Graph& graph, int v, int)->int { + return graph.Degree(v); + }}, + {"vertex-color", [](const Graph& graph, int v_id, int)->int { + const Vertex& v = graph.GetVertexByIDConst(v_id); + return (int)v.Color(); + }}, + {"edge-color", [](const Graph& graph, int e_id, int)->int { + const Edge& e = graph.GetEdgeByIDConst(e_id); + return (int)e.Color(); + }} + }; +} + +void Value::ReadOperation(std::string op) +{ + if (operation_table.size() == 0) + InitializeOperationTable(); + if (operation_table.count(op)) + { + operation = operation_table[op]; + } + else + { + utils::errors::Die("Invalid operation: " + op); + } +} + +std::vector<int> Value::EvalListOperation(const Graph& graph, + std::function<Value(std::string)> lookup_variable) const +{ + switch (type) + { + case Type::VARIABLE: + return lookup_variable(variable_name) + .EvalListOperation(graph, lookup_variable); + case Type::VERTICES: + { + std::vector<int> list; + for (const Vertex* v : graph.vertices) + { + list.push_back(v->id); + } + return list; + } + case Type::EDGES: + { + std::vector<int> list; + for (const Edge* e : graph.edges) + { + list.push_back(e->id); + } + return list; + } + case Type::LIST: + { + std::vector<int> out; + for (Value v : list) + out.push_back(v.Eval(graph, lookup_variable)); + return out; + } + case Type::MAP: + { + std::vector<int> in = val1->EvalListOperation(graph, lookup_variable); + std::vector<int> out; + for (int v : in) + out.push_back(operation(graph, v, 0)); + return out; + } + case Type::ZIP: + { + std::vector<int> in1= val1->EvalListOperation(graph, lookup_variable); + std::vector<int> in2= val2->EvalListOperation(graph, lookup_variable); + std::vector<int> out; + for (int i = 0; i < (int)std::min(in1.size(),in2.size()); i++) + out.push_back(operation(graph, in1[i], in2[i])); + return out; + } + default: break; + } + std::stringstream s; + s << "Invalid list operation: " << (int)type << "."; + utils::errors::Die(s.str()); + return std::vector<int>(); +} + +int Value::Eval(const Graph& graph, + std::function<Value(std::string)> lookup_variable) const +{ + switch (type) + { + case Type::NULL_TYPE: + return 0; + case Type::VALUE: + return val; + case Type::VARIABLE: + return lookup_variable(variable_name).Eval(graph, lookup_variable); + case Type::NUMBER_OF_VERTICES: + return graph.V(); + case Type::NUMBER_OF_EDGES: + return graph.E(); + case Type::OPERATION: + assert(operation); + return operation(graph, + val1->Eval(graph, lookup_variable), + val2->Eval(graph, lookup_variable)); + case Type::FOLD: + { + assert(operation); + int x = fold_start->Eval(graph, lookup_variable); + for (const Value& v : val1->EvalListOperation(graph, lookup_variable)) + { + x = operation(graph, x, v.Eval(graph, lookup_variable)); + } + return x; + } + + default: break; + } + std::stringstream s; + s << "Invalid operation: " << (int)type << "."; + utils::errors::Die(s.str()); + return -1; +} + +} // namespace graphcoloring diff --git a/src/graphcoloring/levels/value.hpp b/src/graphcoloring/levels/value.hpp new file mode 100644 index 0000000..789540e --- /dev/null +++ b/src/graphcoloring/levels/value.hpp @@ -0,0 +1,80 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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_LEVELS_VALUE_H_ +#define GRAPHCOLORING_LEVELS_VALUE_H_ + + +#include "pugi/pugixml.hpp" +#include "../graphs/graph.hpp" + +namespace graphcoloring { + +class Value { +public: + typedef std::function<int(const Graph&,int,int)> operation_t; + Value(); + Value(std::vector<Value> list); + Value(int val); + Value(const std::string& string); + Value(pugi::xml_node node); + virtual ~Value() {} + int Eval(const Graph& graph, + std::function<Value(std::string)> lookup_variable) const; + static void AddNodeToVariables(pugi::xml_node node); +private: + void FromString(const std::string& string); + void ReadOperation(std::string op); + static operation_t SimpleOperation(std::function<int(int,int)> op); // For operations which don't look at the graph. + // Bool operations return bools. + static operation_t SimpleBoolOperation(std::function<bool(int,int)> op); + // Logical operations take bools and return bools. + static operation_t SimpleLogicOperation(std::function<bool(bool,bool)> op); + static void InitializeOperationTable(); + std::vector<int> EvalListOperation(const Graph& graph, // Handles anything that returns a list. + std::function<Value(std::string)> lookup_variable) const; + operation_t operation; + static std::map<std::string, Value::operation_t> operation_table; + std::shared_ptr<Value> fold_start; + std::shared_ptr<Value> val1; + std::shared_ptr<Value> val2; + std::string variable_name; + int val = 0; + std::vector<Value> list; + enum class Type + { + NULL_TYPE, + VALUE, // This value represents a constant number + LIST, + VARIABLE, + NUMBER_OF_VERTICES, + NUMBER_OF_EDGES, + VERTICES, + EDGES, + OPERATION, + LIST_OPERATION, + MAP, + ZIP, + FOLD + }; + Type type; +}; + +} // namespace graphcoloring + +#endif // GRAPHCOLORING_LEVELS_VALUE_H_ diff --git a/src/graphcoloring/levels/valueloader.cpp b/src/graphcoloring/levels/valueloader.cpp new file mode 100644 index 0000000..527ce99 --- /dev/null +++ b/src/graphcoloring/levels/valueloader.cpp @@ -0,0 +1,96 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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 "valueloader.hpp" + +#include "../level.hpp" +#include "utils/errors.hpp" + +namespace graphcoloring { + +ValueLoader::ValueLoader() : objective_points(-1) {} + +void ValueLoader::AddNode(pugi::xml_node node) +{ + variables[node.attribute("id").value()] = Value(node); +} + +void ValueLoader::LoadGraph(const GraphLoader& graph_loader) +{ + for (const std::pair<std::string, int>& v_id : graph_loader.vertex_ids) + variables[v_id.first] = v_id.second; + for (const std::pair<std::string, int>& e_id : graph_loader.edge_ids) + variables[e_id.first] = e_id.second; +} + + +void ValueLoader::LoadColors(const ColorLoader& color_loader) +{ + for (std::pair<std::string, gui::Color> color : color_loader.color_names) + { + variables[color.first] = (int)color.second; + } +} + +void ValueLoader::LoadDocument(const pugi::xml_document& document) +{ + for (pugi::xml_node node : document.child("values").children()) + { + std::string name = node.name(); + if (name == "comment") continue; + if (name == "include") + { + pugi::xml_document doc; + std::string filename = node.attribute("file").value(); + std::string path = "assets/levels/" + filename + ".xml"; + doc.load_file(path.c_str()); + LoadDocument(doc); + } + else + { + AddNode(node); + } + } +} + + +int ValueLoader::VariableValue(const Graph& graph, + const std::string& name) const +{ + if (variables.count(name) == 0) + utils::errors::Die("Variable not found: " + name); + std::function<Value(std::string)> lookup_variable + = [this] (std::string name)->Value { + if (variables.count(name) == 0) + utils::errors::Die("Variable not found: " + name); + return variables.at(name); + }; + return variables.at(name).Eval(graph, lookup_variable); +} + +int ValueLoader::Points(const Graph& graph) const +{ + return VariableValue(graph, "points"); +} + +int ValueLoader::ObjectivePoints(const Graph& graph) const +{ + return VariableValue(graph, "objective"); +} + +} // namespace graphcoloring diff --git a/src/graphcoloring/levels/valueloader.hpp b/src/graphcoloring/levels/valueloader.hpp new file mode 100644 index 0000000..0035864 --- /dev/null +++ b/src/graphcoloring/levels/valueloader.hpp @@ -0,0 +1,46 @@ +//////////////////////////////////////////////////////////////////////////////// +// 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_LEVELS_VALUELOADER_H_ +#define GRAPHCOLORING_LEVELS_VALUELOADER_H_ + +#include "value.hpp" + +#include "graphloader.hpp" + +namespace graphcoloring { + +class ValueLoader { +public: + ValueLoader(); + virtual ~ValueLoader() {} + void LoadDocument(const pugi::xml_document& document); + void LoadGraph(const GraphLoader& graph_loader); // Loads edge & vertex IDs. + void LoadColors(const ColorLoader& color_loader); // Loads color names. + int VariableValue(const Graph& graph, const std::string& name) const; + int Points(const Graph& graph) const; + int ObjectivePoints(const Graph& graph) const; +private: + void AddNode(pugi::xml_node node); + std::map<std::string, Value> variables; + int objective_points; +}; + +} // namespace graphcoloring + +#endif // GRAPHCOLORING_LEVELS_VALUELOADER_H_ |