From c55e185093a5ff40d9c6fa10787f625048495e86 Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Sun, 24 Feb 2019 02:02:50 -0600 Subject: [PATCH] more work was done --- lua/graph.lua | 25 +++++- main.lua | 107 ++++++++++++++++++++--- modules/graph_algorithms.c | 174 ++++++++++++++++++++++++++++++++++--- modules/graph_module.c | 3 + modules/graph_standard.c | 22 +++-- modules/graph_utils.c | 82 +++++++++++++++++ modules/graph_utils.h | 4 + modules/utils.c | 31 ++++++- modules/utils.h | 9 +- 9 files changed, 418 insertions(+), 39 deletions(-) diff --git a/lua/graph.lua b/lua/graph.lua index 1e406f4..9e91b8a 100644 --- a/lua/graph.lua +++ b/lua/graph.lua @@ -56,7 +56,7 @@ function Graph:addEdge(fromNode, toNode, weight) return edgeID1, edgeID2 end -function Graph:deleteEdge(edgeID) +function Graph:deleteArc(edgeID) assert(type(edgeID) == "number") local g = self.graph @@ -75,6 +75,21 @@ function Graph:getEdges() return edges end +function Graph:getEdgeID(from, to, weight) + local g = self.graph + local id = graphs.get_edge_by(g, from, to, weight) + return id +end + +function Graph:getEdge(edgeID) + return graphs.get_edge(self.graph, edgeID) +end + +function Graph:setEdgeWeight(edgeID, weight) + local g = self.graph + graphs.set_edge_weight(g, edgeID, weight) +end + function Graph:getNodePos(nodeID) return graphs.get_node_pos(self.graph, nodeID) end @@ -84,6 +99,14 @@ function Graph:setNodePos(nodeID, x, y) graphs.set_node_pos(self.graph, nodeID, x, y) end +function Graph:clear() + local nodes = self:getNodes() + + for _, node in pairs(nodes) do + self:deleteNode(node.id) + end +end + function Graph:dijkstras(startID, iterations) return graphs.dijkstras(self.graph, startID, iterations) end diff --git a/main.lua b/main.lua index fb84baf..2a784c0 100644 --- a/main.lua +++ b/main.lua @@ -14,18 +14,19 @@ function love.load() graph = Graph:new() - graph:addNode(100, 100) - graph:addNode(300, 100) - graph:addNode(200, 200) - graph:addNode(500, 400) - graph:addNode(300, 300) + -- graph:addNode(100, 100) + -- graph:addNode(300, 100) + -- graph:addNode(200, 200) + -- graph:addNode(500, 400) + -- graph:addNode(300, 300) - graph:addArc(0, 1) - graph:addEdge(0, 2) - graph:addArc(1, 3, 99) - graph:addEdge(1, 2) + -- graph:addArc(0, 1) + -- graph:addEdge(0, 2) + -- graph:addArc(1, 3, 99) + -- graph:addEdge(1, 2) regions = Regions:new() + graph_region = { -- needed for Regions calculations priority = 1; @@ -84,24 +85,38 @@ function love.load() self.isMouseDown = false end; } - regions:add(graph_region) + -- Sidebar regions:add { priority = 1; rect = { 0, 0, 200, 600 }; buttons = { { - text = "Add node", + text = "Clear", click = function() - graph:addNode(300, 300) + graph:clear() + end; + }; + { + text = "Add node", + placeX = 20, + placeY = 20, + click = function(self) + graph:addNode(self.placeX, self.placeY) + self.placeX = self.placeX + 40 + if self.placeX >= 600 then + self.placeX = 20 + self.placeY = self.placeY + 40 + end end; }; { text = "Delete node", click = function() graph:deleteNode(graph_region.selectedNode) + graph_region.selectedNode = nil end; }; { @@ -128,6 +143,21 @@ function love.load() end end; }; + { + text = "Delete arc"; + click = function() + local curr = graph_region.selectedNode + if curr == nil then return end + + graph_region.clickNodeFunction = function(node) + local id = graph:getEdgeID(curr, node.id, nil) + if id >= 0 then + graph:deleteArc(id) + end + graph_region.clickNodeFunction = nil + end + end; + }; { text = "Run Dijkstras", click = function() @@ -144,7 +174,7 @@ function love.load() draw = function(self) love.graphics.setFont(SIDEBAR_FONT) for i, button in ipairs(self.buttons) do - if self.mousePos >= (i - 1) * 60 + 10 and self.mousePos <= i * 60 + 10 then + if self.mousePos >= (i - 1) * 60 + 10 and self.mousePos < i * 60 - 10 then love.graphics.setColor(.4, .4, .4) else love.graphics.setColor(.2, .2, .2) @@ -159,7 +189,7 @@ function love.load() mousedown = function(self, x, y) for i, button in ipairs(self.buttons) do if y >= (i - 1) * 60 + 10 and y <= i * 60 + 10 then - button.click() + button.click(button) end end end; @@ -185,6 +215,8 @@ function love.load() -- mouseenter = function(self) end; -- mouseleave = function(self) end; -- } + + createWeightChanger(0) end local dijkstrasOpen = false @@ -211,12 +243,15 @@ function createDijskstraStepper(start) update = function(self) end; draw = function(self) + love.graphics.setFont(SIDEBAR_FONT) love.graphics.setColor(0, 0, 0, 0.7) love.graphics.rectangle("fill", 0, 0, 600, 50) love.graphics.setColor(1, 1, 1) love.graphics.polygon("fill", 265, 25, 295, 10, 295, 40) love.graphics.polygon("fill", 335, 25, 305, 10, 305, 40) + + love.graphics.printf("X", 540, 5, 50, "center", 0, 1.4, 1.4) end; mousedown = function(self, x, y) if x >= 265 and x <= 295 then @@ -245,6 +280,50 @@ function createDijskstraStepper(start) reg_id = regions:add(region) end +function createWeightChanger(edgeID) + regions:add { + priority = 100; + rect = { 200, 0, 200, 100 }; + + update = function(self) end; + draw = function(self) + love.graphics.setColor(0, 0, 0, 0.8) + love.graphics.rectangle("fill", 0, 0, 200, 100) + + love.graphics.setColor(1, 1, 1) + love.graphics.setFont(SIDEBAR_FONT) + love.graphics.printf("Weight", 0, 0, 200, "center") + + love.graphics.setFont(GRAPH_FONT) + love.graphics.printf("X", 0, 0, 190, "right") + + love.graphics.setFont(SIDEBAR_FONT) + local edge = graph:getEdge(edgeID) + if edge then + love.graphics.printf(tostring(edge.weight), 0, 45, 200, "center") + + love.graphics.setColor(0, 1, 0) + love.graphics.circle("fill", 160, 60, 20) + + love.graphics.setColor(1, 0, 0) + love.graphics.circle("fill", 40, 60, 20) + + love.graphics.setColor(1, 1, 1) + love.graphics.rectangle("fill", 156, 45, 8, 30) + love.graphics.rectangle("fill", 145, 56, 30, 8) + love.graphics.rectangle("fill", 25, 56, 30, 8) + end + end; + mousedown = function(self, x, y) + + end; + mouseup = function(self, x, y) end; + mousemove = function(self, x, y, dx, dy) end; + mouseenter = function(self) end; + mouseleave = function(self) end; + } +end + function love.mousepressed(x, y, button, isTouch, presses) regions:mousedown(x, y) end diff --git a/modules/graph_algorithms.c b/modules/graph_algorithms.c index c4fae9f..7f5773a 100644 --- a/modules/graph_algorithms.c +++ b/modules/graph_algorithms.c @@ -3,8 +3,9 @@ #include #include "graph_algorithms.h" +#include "graph_utils.h" -static dj_node_p depth_first_search(header head, int start_node) +static dj_node_p dj_search(header head, int start_node) { dj_node_p visited_nodes = insert_dj(NULL,start_node,0); sq_node_p stack = sq_push(NULL, start_node); @@ -28,17 +29,174 @@ static dj_node_p depth_first_search(header head, int start_node) } if (edge_walker == NULL) { - stack = sq_pop(stack); + pop(stack); } else { visited_nodes = insert_dj(visited_nodes, edge_walker->to_id, 0); - stack = sq_push(stack, edge_walker->to_id); + push(stack, edge_walker->to_id); } } return visited_nodes; } +int breadth_first_search(lua_State *L) +{ + header head = (header)lua_touserdata(L, 1); + int start_id = lua_tointeger(L, 2); + int iterations = lua_tointeger(L, 3); + + int previous_node = start_id; + + int current_iterations = 0; + + sq_node_p visited_nodes = NULL; + sq_node_p from_visited_nodes = NULL; + enque(visited_nodes, start_id); + enque(from_visited_nodes, start_id); + + + sq_node_p queue = NULL; + enque(queue, start_id); + + while(queue != NULL && current_iterations <= iterations) + { + int node_id = front(queue); + deque(queue); + + if(sq_contains(visited_nodes, node_id)) + continue; + + connect runner = find_node(head, node_id); + + edge edge_runner = runner->neighbor_list; //grab the neighbor list of our current node + + while(edge_runner != NULL) + { + enque(queue, edge_runner->to_id); + edge_runner = edge_runner->next_edge; + } + + enque(from_visited_nodes, previous_node); + previous_node = node_id; + enque(visited_nodes, node_id); + + current_iterations++; + } + + deque(visited_nodes); + deque(from_visited_nodes); + + + //BUILD OUT RETURN TO LUA + lua_newtable(L); + sq_node_p vwalker; + sq_node_p fvwalker; + int index = 1; + while (vwalker != NULL) + { + lua_pushnumber(L, index); + + lua_newtable(L); + + lua_pushnumber(L, front(fvwalker)); + lua_setfield(L, 3, "from"); + deque(fvwalker); + + lua_pushnumber(L, front(vwalker)); + lua_setfield(L, 3, "to"); + deque(vwalker); + + lua_settable(L, 1); + + index++; + } + + + sq_delete(visited_nodes); + sq_delete(from_visited_nodes); + sq_delete(queue); + return 1; +} + +int depth_first_search(lua_State *L) +{ + header head = (header)lua_touserdata(L, 1); + int start_id = lua_tointeger(L, 2); + int iterations = lua_tointeger(L, 3); + + int previous_node = start_id; + + int current_iterations = 0; + + sq_node_p visited_nodes = NULL; + sq_node_p from_visited_nodes = NULL; + enque(visited_nodes, start_id); + enque(from_visited_nodes, start_id); + + sq_node_p stack = NULL; + push(stack, start_id); + + while(stack != NULL && current_iterations <= iterations) + { + int node_id = top(stack); + pop(stack); + + if(sq_contains(visited_nodes, node_id)) + continue; + + connect runner = find_node(head, node_id); + + edge edge_runner = runner->neighbor_list; //grab the neighbor list of our current node + + while(edge_runner != NULL) + { + push(stack, edge_runner->to_id); + edge_runner = edge_runner->next_edge; + } + + enque(from_visited_nodes, previous_node); + previous_node = node_id; + enque(visited_nodes, node_id); + + current_iterations++; + } + + deque(from_visited_nodes); + deque(visited_nodes); + + + //BUILD OUT RETURN TO LUA + lua_newtable(L); + sq_node_p vwalker; + sq_node_p fvwalker; + int index = 1; + while (vwalker != NULL) + { + lua_pushnumber(L, index); + + lua_newtable(L); + + lua_pushnumber(L, front(fvwalker)); + lua_setfield(L, 3, "from"); + deque(fvwalker); + + lua_pushnumber(L, front(vwalker)); + lua_setfield(L, 3, "to"); + deque(vwalker); + + lua_settable(L, 1); + + index++; + } + + + sq_delete(visited_nodes); + sq_delete(from_visited_nodes); + sq_delete(stack); + return 1; +} + int dijkstras(lua_State *L) { header head = (header)lua_touserdata(L, 1); @@ -52,7 +210,7 @@ int dijkstras(lua_State *L) dj_node_p has_visited = insert_dj(NULL, start_id, 0); dj_node_p shortest_distance = insert_dj(NULL, start_id, 0); - dj_node_p connected_nodes = depth_first_search(head, start_id); + dj_node_p connected_nodes = dj_search(head, start_id); connected_nodes = remove_dj(connected_nodes, start_id); dj_node_p distance_walker = connected_nodes; @@ -73,11 +231,7 @@ int dijkstras(lua_State *L) int to = -1; while (visited_tmp != NULL) { - connect current_node = head->front; - while (current_node->node_id != visited_tmp->node_id) - { - current_node = current_node->next_node; - } + connect current_node = find_node(head, visited_tmp->node_id); edge edge_walker = current_node->neighbor_list; while (edge_walker != NULL) @@ -100,7 +254,7 @@ int dijkstras(lua_State *L) last_to = to; last_from = from; - if (is_in_list(connected_nodes,to) == 1) + if (is_in_list(connected_nodes, to) == 1) { connected_nodes = remove_dj(connected_nodes, to); } diff --git a/modules/graph_module.c b/modules/graph_module.c index 50e2f24..41f3cfd 100644 --- a/modules/graph_module.c +++ b/modules/graph_module.c @@ -18,6 +18,9 @@ int luaopen_graphs(lua_State *L) { "get_nodes", get_nodes }, { "get_edges", get_edges }, + { "get_edge_by", get_edge_by }, + { "get_edge", get_edge_id }, + { "set_edge_weight", set_edge_weight }, { "get_node_pos", get_node_pos }, { "set_node_pos", set_node_pos }, diff --git a/modules/graph_standard.c b/modules/graph_standard.c index d3f6c3f..cabbd73 100644 --- a/modules/graph_standard.c +++ b/modules/graph_standard.c @@ -216,31 +216,35 @@ int del_edge(lua_State *L) //we will have to walk through each node and walk through each edge of each node connect runner = head->front; - while(runner != NULL) + while (runner != NULL) { //now we will have to go through every edge within the node edge curr_edge = runner->neighbor_list; - if(curr_edge == NULL) //no neighbors - runner = runner->next_node; - - else if(curr_edge->edge_id == edge_id) //first edge is one to remove + if (curr_edge == NULL) { + //no neighbors + } + else if (curr_edge->edge_id == edge_id) //first edge is one to remove { runner->neighbor_list = curr_edge->next_edge; free(curr_edge); return 0; } - else //search through each edge { - while(curr_edge->next_edge != NULL) + edge follower = curr_edge; + curr_edge = curr_edge->next_edge; + while (curr_edge != NULL) { - if(curr_edge->next_edge->edge_id == edge_id) + if (curr_edge->edge_id == edge_id) { - curr_edge->next_edge = curr_edge->next_edge->next_edge; + follower->next_edge = curr_edge->next_edge; free(curr_edge); return 0; } + + follower = curr_edge; + curr_edge = curr_edge->next_edge; } } diff --git a/modules/graph_utils.c b/modules/graph_utils.c index 0a37f95..eec6ad0 100644 --- a/modules/graph_utils.c +++ b/modules/graph_utils.c @@ -1,3 +1,4 @@ +#include "utils.h" #include "graph_utils.h" int get_nodes(lua_State *L) @@ -68,6 +69,64 @@ int get_edges(lua_State *L) return 1; } +int get_edge_by(lua_State *L) +{ + header head = (header) lua_touserdata(L, 1); + int from = lua_tointeger(L, 2); + int to = lua_tointeger(L, 3); + + int weight; + if (lua_isnumber(L, 4)) + weight = lua_tointeger(L, 4); + else + weight = ANY_WEIGHT; + + edge e = find_edge(head, from, to, weight); + if (e == NULL) + lua_pushnumber(L, -1); + else + lua_pushnumber(L, e->edge_id); + + return 1; +} + +int get_edge_id(lua_State *L) +{ + header head = (header) lua_touserdata(L, 1); + int edge_id = lua_tointeger(L, 2); + lua_pop(L, 2); + + edge e = get_edge(head, edge_id); + if (e == NULL) { + lua_pushnil(L); + } else { + lua_newtable(L); + + lua_pushnumber(L, e->weight); + lua_setfield(L, 1, "weight"); + + lua_pushnumber(L, e->edge_id); + lua_setfield(L, 1, "id"); + } + + return 1; +} + +int set_edge_weight(lua_State *L) +{ + header head = (header) lua_touserdata(L, 1); + int edge_id = lua_tointeger(L, 2); + int new_weight = lua_tointeger(L, 3); + lua_pop(L, 3); + + edge e = get_edge(head, edge_id); + if (e == NULL) return 0; + + e->weight = new_weight; + + return 0; +} + // number, number get_node_pos(graph pointer, int node_id) int get_node_pos(lua_State *L) { @@ -164,4 +223,27 @@ edge find_edge(header head, int from_node, int to_node, int weight) } return jogger; +} + +edge get_edge(header head, int edge_id) +{ + connect jogger = head->front; + while (jogger != NULL) + { + edge curr_edge = jogger->neighbor_list; + + while (curr_edge != NULL) + { + if (curr_edge->edge_id == edge_id) + { + return curr_edge; + } + + curr_edge = curr_edge->next_edge; + } + + jogger = jogger->next_node; + } + + return NULL; } \ No newline at end of file diff --git a/modules/graph_utils.h b/modules/graph_utils.h index 0b37d95..b6f1f26 100644 --- a/modules/graph_utils.h +++ b/modules/graph_utils.h @@ -29,6 +29,9 @@ LUA_FUNCTION(get_nodes); } */ LUA_FUNCTION(get_edges); +LUA_FUNCTION(get_edge_by); +LUA_FUNCTION(get_edge_id); +LUA_FUNCTION(set_edge_weight); LUA_FUNCTION(get_node_pos); LUA_FUNCTION(set_node_pos); @@ -37,5 +40,6 @@ LUA_FUNCTION(print_graph); connect find_node(header head, int node_id); edge find_edge(header head, int from_node, int to_node, int weight); +edge get_edge(header head, int edge_id); #endif \ No newline at end of file diff --git a/modules/utils.c b/modules/utils.c index 20c10c9..4352cb5 100644 --- a/modules/utils.c +++ b/modules/utils.c @@ -1,8 +1,8 @@ +#include "utils.h" + #include #include -#include "utils.h" - int sq_top(sq_node_p stack_top) { if(stack_top == NULL) @@ -91,6 +91,20 @@ sq_node_p sq_deque(sq_node_p front_of_queue) return front_of_queue; } + +int sq_contains(sq_node_p sq, int val) +{ + while(sq != NULL) + { + if(sq->value == val) + return 1; + + sq = sq->next; + } + + return 0; +} + void sq_print(sq_node_p sq) { sq_node_p runner = sq; @@ -104,6 +118,19 @@ void sq_print(sq_node_p sq) puts(""); } +void sq_delete(sq_node_p sq) +{ + sq_node_p runner = sq; + + while(sq != NULL) + { + sq_node_p tmp = sq; + sq = sq->next; + + free(tmp); + } +} + dj_node_p insert_dj(dj_node_p front_of_list, int id, int distance) { dj_node_p new_node = (dj_node_p)malloc(sizeof(dj_node)); diff --git a/modules/utils.h b/modules/utils.h index 4cef2ce..293097c 100644 --- a/modules/utils.h +++ b/modules/utils.h @@ -22,6 +22,9 @@ sq_node_p sq_pop(sq_node_p stack_top); sq_node_p sq_enque(sq_node_p front_of_queue, int val); sq_node_p sq_deque(sq_node_p front_of_queue); +int sq_contains(sq_node_p sq, int val); +void sq_delete(sq_node_p sq); + void sq_print(sq_node_p sq); dj_node_p insert_dj(dj_node_p front_of_list, int id, int distance); @@ -34,8 +37,8 @@ int get_distance(dj_node_p front_of_list, int id); #define top(sq) (sq_top((sq))) #define front(sq) (sq_front((sq))) #define push(sq, val) ((sq) = sq_push( (sq), (val))) -#define pop(sq, val) ((sq) = sq_pop( (sq), (val))) +#define pop(sq) ((sq) = sq_pop( (sq))) #define enque(sq, val) ((sq) = sq_enque((sq), (val))) -#define deque(sq, val) ((sq) = sq_deque((sq), (val))) +#define deque(sq) ((sq) = sq_deque((sq))) -#endif \ No newline at end of file +#endif -- 2.25.1