From 166f9b169a7c2b992bee2ce95f5d7ae790de4cdd Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Fri, 22 Feb 2019 17:05:34 -0600 Subject: [PATCH] fifth commit (starting visualizations) --- lua/graph.lua | 76 +++++++++++++++++++++++++++++++ lua/utils.lua | 3 ++ main.lua | 64 +++++++++++++++++++++----- modules/graph_algorithms.c | 92 ++++++++++++++++++++++++++++++++++++-- modules/graph_algorithms.h | 4 ++ modules/graph_module.c | 5 +++ modules/graph_standard.c | 29 +++--------- modules/graph_types.h | 2 +- modules/graph_utils.c | 86 ++++++++++++++++++++++++++++++++--- modules/graph_utils.h | 11 +++++ modules/utils.c | 86 +++++++++++++++++++++++++++++++++++ modules/utils.h | 13 ++++++ 12 files changed, 429 insertions(+), 42 deletions(-) create mode 100644 lua/graph.lua create mode 100644 lua/utils.lua diff --git a/lua/graph.lua b/lua/graph.lua new file mode 100644 index 0000000..a0a871a --- /dev/null +++ b/lua/graph.lua @@ -0,0 +1,76 @@ +require "graphs" + +local Graph = {} +function Graph:new() + local obj = { + graph = graphs.create_graph() + } + + local mt = { __index = Graph } + setmetatable(obj, mt) + + return obj +end + +-- Returns new node id +function Graph:addNode(x, y) + x = x or 0 + y = y or 0 + + local g = self.graph + local nodeID = graphs.add_node(g) + graphs.set_node_pos(g, nodeID, x, y) + + return nodeID +end + +function Graph:deleteNode(nodeID) + assert(type(nodeID) == "number") + local g = self.graph + + graphs.del_node(g, nodeID) +end + +function Graph:addArc(fromNode, toNode, weight) + assert(type(fromNode) == "number") + assert(type(toNode) == "number") + weight = weight or 1 + + local g = self.graph + local edgeID = graphs.add_directed(g, fromNode, toNode, weight) + + return edgeID +end + +function Graph:addEdge(fromNode, toNode, weight) + assert(type(fromNode) == "number") + assert(type(toNode) == "number") + weight = weight or 1 + + local g = self.graph + local edgeID1 = graphs.add_directed(g, fromNode, toNode, weight) + local edgeID2 = graphs.add_directed(g, toNode, fromNode, weight) + + return edgeID1, edgeID2 +end + +function Graph:deleteEdge(edgeID) + assert(type(edgeID) == "number") + + local g = self.graph + graphs.del_edge(g, edgeID) +end + +function Graph:getNodes() + local g = self.graph + local nodes = graphs.get_nodes(g) + return nodes +end + +function Graph:getEdges() + local g = self.graph + local edges = graphs.get_edges(g) + return edges +end + +return Graph \ No newline at end of file diff --git a/lua/utils.lua b/lua/utils.lua new file mode 100644 index 0000000..069d984 --- /dev/null +++ b/lua/utils.lua @@ -0,0 +1,3 @@ +function math.lerp(a, b, t) + return a + (b - a) * t +end diff --git a/main.lua b/main.lua index 19d5536..50d5e68 100644 --- a/main.lua +++ b/main.lua @@ -1,22 +1,66 @@ -require "graphs" +require "lua.utils" +local Graph = require "lua.graph" -function love.load() - local graph = graphs.create_graph() +local graph = nil - local node1 = graphs.add_node(graph) - local node2 = graphs.add_node(graph) - local node3 = graphs.add_node(graph) +function love.load() + graph = Graph:new() - print("NODES", node1, node2, node3) + graph:addNode(100, 100) + graph:addNode(300, 100) + graph:addNode(200, 200) + graph:addNode(500, 400) - graphs.add_directed(graph, node1, node2, 2) - graphs.add_directed(graph, node2, node3, 4) + graph:addArc(0, 1) + graph:addEdge(0, 2) + graph:addArc(1, 3) + graph:addEdge(1, 2) - graphs.print_graph(graph) + love.graphics.setBackgroundColor(0.5, 0.5, 0.5) end function love.update() end +function drawGraph(graph) + local nodes = graph:getNodes() + local edges = graph:getEdges() + + love.graphics.setLineWidth(4) + for _, edge in pairs(edges) do + love.graphics.setColor(0, 0, 0) + local x1 = nodes[edge.from_node].x + local y1 = nodes[edge.from_node].y + local x2 = nodes[edge.to_node].x + local y2 = nodes[edge.to_node].y + + love.graphics.line(x1, y1, x2, y2) + + if edge.directed then + local cx = math.lerp(x1, x2, 0.5) + local cy = math.lerp(y1, y2, 0.5) + + local alpha = math.atan2(x2 - x1, y2 - y1) + + local arrowSize = 15 + local triangle = { + cx + arrowSize * math.sin(alpha + 0 * math.pi / 3), cy + arrowSize * math.cos(alpha + 0 * math.pi / 3), + cx + arrowSize * math.sin(alpha + 2 * math.pi / 3), cy + arrowSize * math.cos(alpha + 2 * math.pi / 3), + cx + arrowSize * math.sin(alpha + 4 * math.pi / 3), cy + arrowSize * math.cos(alpha + 4 * math.pi / 3) + } + + love.graphics.polygon("fill", triangle) + end + end + + for _, node in pairs(nodes) do + love.graphics.setColor(0, 0, 0) + love.graphics.circle("fill", node.x, node.y, 20) + love.graphics.setColor(255, 255, 255) + love.graphics.circle("fill", node.x, node.y, 17) + end +end + function love.draw() + drawGraph(graph) end diff --git a/modules/graph_algorithms.c b/modules/graph_algorithms.c index 6217b56..0f199ad 100644 --- a/modules/graph_algorithms.c +++ b/modules/graph_algorithms.c @@ -1,8 +1,94 @@ #include #include -#include "utils.h" -#include "graph_utils.h" -#include "graph_types.h" +#include "graph_algorithms.h" +static ll_node_p depth_first_search(header head, int start_node) +{ + ll_node_p visited_nodes = insert_ll(NULL,start_node,0); + sq_node_p stack = sq_push(NULL, start_node); + while (stack != NULL) + { + int node_id = top(stack); + connect walker = head->front; + while (walker != NULL && walker->node_id != node_id) + { + walker = walker->next_node; + } + if (walker == NULL) + { + return NULL; + } + + edge edge_walker = walker->neighbor_list; + while (edge_walker != NULL && is_in_list(visited_nodes, edge_walker->to_id) == 1) + { + edge_walker = edge_walker->next_edge; + } + if (edge_walker == NULL) + { + stack = sq_pop(stack); + } + else + { + visited_nodes = insert_ll(visited_nodes, edge_walker->to_id, 0); + stack = sq_push(stack, edge_walker->to_id); + } + } + return visited_nodes; +} + +int dijkstras(lua_State *L) +{ + header head = (header)lua_touserdata(L, 1); + int start_id = lua_tointeger(L, 2); + int iterations = lua_tointeger(L, 3); + + connect walker = head->front; + + ll_node_p has_visited = insert_ll(NULL, start_id, 0); + ll_node_p shortest_distance = insert_ll(NULL, start_id, 0); + ll_node_p connected_nodes = depth_first_search(head,start_id); + + + while (connected_nodes != NULL) + { + ll_node_p visited_tmp = has_visited; + int shortest_distance_tmp = -1; + int from = -1; + 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; + } + + edge edge_walker = current_node->neighbor_list; + while (edge_walker != NULL) + { + int distance_to_current_node = get_distance(shortest_distance, current_node->node_id); + if (is_in_list(has_visited, edge_walker->to_id) == 0 || distance_to_current_node + edge_walker->weight < get_distance(shortest_distance,edge_walker->to_id)) + { + if (shortest_distance_tmp == -1 || distance_to_current_node + edge_walker->weight < shortest_distance_tmp) + { + shortest_distance_tmp = distance_to_current_node + edge_walker->weight; + from = has_visited->node_id; + to = edge_walker->to_id; + } + } + } + visited_tmp = visited_tmp->next; + } + remove_ll(connected_nodes, to); + //shortest_distance + } + //Start at start node + //Check shortest distance to all connected nodes from all visited nodes + //Repeat with closest node + + + return 1; +} diff --git a/modules/graph_algorithms.h b/modules/graph_algorithms.h index 838f9ef..4cc8572 100644 --- a/modules/graph_algorithms.h +++ b/modules/graph_algorithms.h @@ -1,6 +1,10 @@ #ifndef __GRAPH_ALGORITHM_H__ #define __GRAPH_ALGORITHM_H__ +#include "utils.h" +#include "graph_utils.h" +#include "graph_types.h" +LUA_FUNCTION(dijkstras); #endif \ No newline at end of file diff --git a/modules/graph_module.c b/modules/graph_module.c index 77b77f8..50e2f24 100644 --- a/modules/graph_module.c +++ b/modules/graph_module.c @@ -2,6 +2,7 @@ #include "graph_standard.h" #include "graph_utils.h" +#include "graph_algorithms.h" int luaopen_graphs(lua_State *L) { @@ -17,7 +18,11 @@ int luaopen_graphs(lua_State *L) { "get_nodes", get_nodes }, { "get_edges", get_edges }, + { "get_node_pos", get_node_pos }, + { "set_node_pos", set_node_pos }, + { "print_graph", print_graph }, + { "dijkstras", dijkstras }, { NULL, NULL } }; diff --git a/modules/graph_standard.c b/modules/graph_standard.c index f7b0aea..5c287b3 100644 --- a/modules/graph_standard.c +++ b/modules/graph_standard.c @@ -2,9 +2,9 @@ #include #include +#include "graph_utils.h" #include "graph_standard.h" -static connect find_node(header head, int node_id); static void add_edge(header head, int from_node, int to_node, int edge_weight); // graph pointer create_graph() @@ -28,6 +28,8 @@ int add_node(lua_State *L) connect new_node = (connect)malloc(sizeof(node)); new_node->next_node = NULL; new_node->neighbor_list = NULL; + new_node->x = 0; + new_node->y = 0; if (head->node_count == 0) { @@ -59,7 +61,7 @@ int add_node(lua_State *L) return 1; } -// del_node(graph pointer, int nodeID) +// void del_node(graph pointer, int nodeID) int del_node(lua_State *L) { header head = (header)lua_touserdata(L,1); @@ -189,6 +191,7 @@ int add_directed(lua_State *L) return 0; } +// add_undirected(graph pointer, int from, int to, int weight) int add_undirected(lua_State *L) { header head = (header)lua_touserdata(L, 1); @@ -204,6 +207,7 @@ int add_undirected(lua_State *L) return 0; } +// del_edge(graph pointer, edge_id) int del_edge(lua_State *L) { header head = (header)lua_touserdata(L, 1); @@ -245,24 +249,3 @@ int del_edge(lua_State *L) return 0; } -static connect find_node(header head, int node_id) -{ - //walk through node list to find from node - connect runner = head->front; - if(runner == NULL) - { - puts("GRAPH HEADER LIST IS EMPTY"); - return NULL; //graph is empty - } - - //run through list of nodes until node with passed node_id is found - while(runner->node_id != node_id) - { - if(runner == NULL) - return NULL; //from id is never found - - runner = runner->next_node; //move to next node in list - } - - return runner; -} diff --git a/modules/graph_types.h b/modules/graph_types.h index 62573bc..03d9d39 100644 --- a/modules/graph_types.h +++ b/modules/graph_types.h @@ -23,6 +23,6 @@ typedef struct { int next_edge_id; } head_structure, *header; -#define LUA_FUNCTION(func) int (func)(lua_State*) +#define LUA_FUNCTION(func) int (func)(lua_State* L) #endif \ No newline at end of file diff --git a/modules/graph_utils.c b/modules/graph_utils.c index 809b706..9388fa5 100644 --- a/modules/graph_utils.c +++ b/modules/graph_utils.c @@ -7,9 +7,8 @@ int get_nodes(lua_State *L) lua_newtable(L); // Push a new table onto the stack - int index = 1; for (connect jogger = head->front; jogger != NULL; jogger = jogger->next_node) { - lua_pushnumber(L, index); // Push the next index of the node, sets up for settable call + lua_pushnumber(L, jogger->node_id); lua_newtable(L); // Push on the table that will store each node // Add the fields to our node table @@ -24,8 +23,6 @@ int get_nodes(lua_State *L) // Put our node table in the table we are returning lua_settable(L, 1); - - index++; } return 1; @@ -58,6 +55,10 @@ int get_edges(lua_State *L) lua_pushnumber(L, swimmer->weight); lua_setfield(L, 3, "weight"); + int is_directed = (find_edge(head, swimmer->to_id, node_id, swimmer->weight) == NULL); + lua_pushboolean(L, is_directed); + lua_setfield(L, 3, "directed"); + lua_settable(L, 1); index++; @@ -67,9 +68,40 @@ int get_edges(lua_State *L) return 1; } +// number, number get_node_pos(graph pointer, int node_id) +int get_node_pos(lua_State *L) +{ + header head = (header) lua_touserdata(L, 1); + int node_id = lua_tointeger(L, 2); + lua_pop(L, 2); + + connect node = find_node(head, node_id); + + lua_pushnumber(L, node->x); + lua_pushnumber(L, node->y); + return 2; +} + +// void set_node_pos(graph pointer, int node_id, number x, y) +int set_node_pos(lua_State *L) +{ + header head = (header) lua_touserdata(L, 1); + int node_id = lua_tointeger(L, 2); + lua_Number x = lua_tonumber(L, 3); + lua_Number y = lua_tonumber(L, 4); + lua_pop(L, 4); + + connect node = find_node(head, node_id); + + node->x = x; + node->y = y; + + return 0; +} + int print_graph(lua_State *L) { - header head = (header)lua_touserdata(L,1); + header head = (header)lua_touserdata(L, 1); connect node_walker = head->front; edge edge_walker; @@ -88,4 +120,48 @@ int print_graph(lua_State *L) } return 0; +} + +connect find_node(header head, int node_id) +{ + //walk through node list to find from node + connect runner = head->front; + if(runner == NULL) + { + return NULL; //graph is empty + } + + //run through list of nodes until node with passed node_id is found + while(runner->node_id != node_id) + { + if(runner == NULL) + return NULL; //from id is never found + + runner = runner->next_node; //move to next node in list + } + + return runner; +} + +edge find_edge(header head, int from_node, int to_node, int weight) +{ + connect node = find_node(head, from_node); + + if (node == NULL) + { + return NULL; // No edge could be found + } + + edge jogger = node->neighbor_list; + while (jogger != NULL) + { + if (jogger->to_id == to_node && (weight == ANY_WEIGHT || weight == jogger->weight)) + { + break; + } + + jogger = jogger->next_edge; + } + + return jogger; } \ No newline at end of file diff --git a/modules/graph_utils.h b/modules/graph_utils.h index 78e85ad..0b37d95 100644 --- a/modules/graph_utils.h +++ b/modules/graph_utils.h @@ -7,12 +7,15 @@ #include "graph_types.h" +#define ANY_WEIGHT -56489 + /* Returns all nodes in the form: { id = , x = , y = } + indexed by node_id */ LUA_FUNCTION(get_nodes); @@ -22,9 +25,17 @@ LUA_FUNCTION(get_nodes); from_node = , to_node = , weight = number, + directed = boolean, } */ LUA_FUNCTION(get_edges); + +LUA_FUNCTION(get_node_pos); +LUA_FUNCTION(set_node_pos); + 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); + #endif \ No newline at end of file diff --git a/modules/utils.c b/modules/utils.c index d5fa0c1..afbb519 100644 --- a/modules/utils.c +++ b/modules/utils.c @@ -102,4 +102,90 @@ void sq_print(sq_node_p sq) } puts(""); +} + +ll_node_p insert_ll(ll_node_p front_of_list, int id, int distance) +{ + ll_node_p new_node = (ll_node_p)malloc(sizeof(ll_node)); + new_node->next = NULL; + new_node->node_id = id; + new_node->distance = distance; + + if (front_of_list == NULL) + { + front_of_list = new_node; + return front_of_list; + } + else + { + ll_node_p walker = front_of_list; + while (walker->next != NULL) + { + walker = walker->next; + } + walker->next = new_node; + return front_of_list; + } +} + +ll_node_p remove_ll(ll_node_p front_of_list, int id) +{ + ll_node_p walker = front_of_list; + ll_node_p follower = walker; + while (walker != NULL && walker->node_id != id) + { + follower = walker; + walker = walker->next; + } + if (walker == NULL) + { + printf("bruh\n"); + return front_of_list; + } + else if (walker == front_of_list) + { + front_of_list = front_of_list->next; + free(walker); + return front_of_list; + } + else + { + follower->next = walker->next; + free(walker); + return front_of_list; + } +} + +int is_in_list(ll_node_p front_of_list, int id) +{ + ll_node_p walker = front_of_list; + while (walker != NULL && walker->node_id != id) + { + walker = walker->next; + } + if (walker == NULL) + { + return 0; + } + else + { + return 1; + } +} + +int get_distance(ll_node_p front_of_list, int id) +{ + ll_node_p walker = front_of_list; + while (walker != NULL && walker->node_id != id) + { + walker = walker->next; + } + if (walker == NULL) + { + return -1; + } + else + { + return walker->distance; + } } \ No newline at end of file diff --git a/modules/utils.h b/modules/utils.h index eee22b8..15d7bcf 100644 --- a/modules/utils.h +++ b/modules/utils.h @@ -8,6 +8,12 @@ typedef struct sq_node { struct sq_node * next; } sq_node, *sq_node_p; +typedef struct ll_node { + int node_id; + int distance; + struct ll_node * next; +} ll_node, *ll_node_p; + int sq_top(sq_node_p stack_top); int sq_front(sq_node_p queue_front); @@ -18,7 +24,14 @@ sq_node_p sq_deque(sq_node_p front_of_queue); void sq_print(sq_node_p sq); +ll_node_p insert_ll(ll_node_p front_of_list, int id, int distance); +ll_node_p remove_ll(ll_node_p front_of_list, int id); +int is_in_list(ll_node_p front_of_list, int id); +int get_distance(ll_node_p front_of_list, int id); + // Helper macros that make the call site of these functions cleaner +#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 enque(sq, val) ((sq) = sq_enque((sq), (val))) -- 2.25.1