From 3751c41e6a142483225057af52d645bb5556baa3 Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Fri, 22 Feb 2019 00:40:30 -0600 Subject: [PATCH] third commit --- Makefile | 3 +- main.lua | 2 +- modules/graph_algorithms.c | 8 +++ modules/graph_algorithms.h | 4 ++ modules/graph_module.c | 9 +++- modules/graph_standard.c | 9 ++-- modules/graph_types.h | 2 + modules/graph_utils.c | 90 ++++++++++++++++++++++++++++++- modules/graph_utils.h | 4 +- modules/utils.c | 105 +++++++++++++++++++++++++++++++++++++ modules/utils.h | 12 +++++ test.lua | 21 ++++++++ 12 files changed, 258 insertions(+), 11 deletions(-) create mode 100644 modules/graph_algorithms.c create mode 100644 modules/graph_algorithms.h create mode 100644 modules/utils.c create mode 100644 modules/utils.h create mode 100644 test.lua diff --git a/Makefile b/Makefile index c0f56f0..bdb0d7a 100644 --- a/Makefile +++ b/Makefile @@ -1,4 +1,3 @@ - CC=gcc OBJ_FILES=$(shell find ./modules -name '*.c' | grep -Eo '^\.[^\.]*' | xargs printf '%s.o\n') FLAGS= @@ -16,4 +15,4 @@ $(TARGET): link all: $(TARGET) clean: - (rm $(OBJS) 2>/dev/null) || true \ No newline at end of file + (rm $(OBJ_FILES) 2>/dev/null) || true diff --git a/main.lua b/main.lua index 3162e34..409a62b 100644 --- a/main.lua +++ b/main.lua @@ -15,4 +15,4 @@ function love.update() end function love.draw() -end \ No newline at end of file +end diff --git a/modules/graph_algorithms.c b/modules/graph_algorithms.c new file mode 100644 index 0000000..6217b56 --- /dev/null +++ b/modules/graph_algorithms.c @@ -0,0 +1,8 @@ +#include +#include + +#include "utils.h" +#include "graph_utils.h" +#include "graph_types.h" + + diff --git a/modules/graph_algorithms.h b/modules/graph_algorithms.h new file mode 100644 index 0000000..ceead3d --- /dev/null +++ b/modules/graph_algorithms.h @@ -0,0 +1,4 @@ +#ifndef __GRAPH_ALGORITHM_H__ +#define __GRAPH_ALGORITHM_H__ + +#endif \ No newline at end of file diff --git a/modules/graph_module.c b/modules/graph_module.c index fdd897e..77b77f8 100644 --- a/modules/graph_module.c +++ b/modules/graph_module.c @@ -5,7 +5,7 @@ int luaopen_graphs(lua_State *L) { - printf("LOADING MODULE\n"); + printf("LOADING MODULE...\n"); const luaL_Reg functions[] = { { "create_graph", create_graph }, @@ -14,9 +14,14 @@ int luaopen_graphs(lua_State *L) { "add_directed", add_directed }, { "add_undirected", add_undirected }, { "del_edge", del_edge }, + + { "get_nodes", get_nodes }, + { "get_edges", get_edges }, + { "print_graph", print_graph }, + { NULL, NULL } }; luaL_register(L, "graphs", functions); return 1; -} \ No newline at end of file +} diff --git a/modules/graph_standard.c b/modules/graph_standard.c index 5d1f62d..24405aa 100644 --- a/modules/graph_standard.c +++ b/modules/graph_standard.c @@ -27,6 +27,7 @@ int add_node(lua_State *L) header head = (header)lua_touserdata(L,1); connect new_node = (connect)malloc(sizeof(node)); new_node->next_node = NULL; + new_node->neighbor_list = NULL; if (head->node_count == 0) { @@ -71,7 +72,7 @@ int del_node(lua_State *L) while(walker->node_id != nid && walker != NULL){ if(walker->node_id > nid) { - puts("c'mon brendan..."); + puts("NODE NOT FOUND FOR DELETE"); return 0; } follower = walker; @@ -79,7 +80,7 @@ int del_node(lua_State *L) } if (walker == NULL) { - puts("brother, this node don't exist"); + puts("NODE NOT FOUND FOR DELETE"); return 0; } @@ -102,7 +103,6 @@ int del_node(lua_State *L) { if (edge_walker->to_id == nid) { - edge_walker = edge_walker->next_edge; if (edge_walker == node_walker->neighbor_list) { node_walker->neighbor_list = node_walker->neighbor_list->next_edge; @@ -112,6 +112,7 @@ int del_node(lua_State *L) delete_walker->next_edge = edge_walker; delete_walker = delete_walker->next_edge; } + edge_walker = edge_walker->next_edge; free(delete_walker); } else @@ -265,4 +266,4 @@ static connect find_node(header head, int node_id) } return runner; -} +} diff --git a/modules/graph_types.h b/modules/graph_types.h index 862a34c..62573bc 100644 --- a/modules/graph_types.h +++ b/modules/graph_types.h @@ -13,6 +13,8 @@ typedef struct node { int node_id; int edge_count; struct node* next_node; + + lua_Number x, y; } node, *connect; typedef struct { diff --git a/modules/graph_utils.c b/modules/graph_utils.c index 7242520..cb9e4d1 100644 --- a/modules/graph_utils.c +++ b/modules/graph_utils.c @@ -1 +1,89 @@ -#include "graph_utils.h" \ No newline at end of file +#include "graph_utils.h" + +int get_nodes(lua_State *L) +{ + header head = (header) lua_touserdata(L, 1); + lua_pop(L, 1); + + lua_newtable(L); + + int index = 1; + for (connect jogger = head->front; jogger != NULL; jogger = jogger->next_node) { + lua_pushnumber(L, index); + lua_newtable(L); + + lua_pushnumber(L, jogger->node_id); + lua_setfield(L, 3, "id"); + + lua_pushnumber(L, jogger->x); + lua_setfield(L, 3, "x"); + lua_pushnumber(L, jogger->y); + lua_setfield(L, 3, "y"); + + lua_settable(L, 1); + + index++; + } + + return 1; +} + +int get_edges(lua_State *L) +{ + header head = (header) lua_touserdata(L, 1); + lua_pop(L, 1); + + lua_newtable(L); + + int index = 1; + for (connect jogger = head->front; jogger != NULL; jogger = jogger->next_node) { + int node_id = jogger->node_id; + + for (edge swimmer = jogger->neighbor_list; swimmer != NULL; swimmer = swimmer->next_edge) { + lua_pushnumber(L, index); + lua_newtable(L); + + lua_pushnumber(L, swimmer->edge_id); + lua_setfield(L, 3, "id"); + + lua_pushnumber(L, node_id); + lua_setfield(L, 3, "from_node"); + + lua_pushnumber(L, swimmer->to_id); + lua_setfield(L, 3, "to_node"); + + lua_pushnumber(L, swimmer->weight); + lua_setfield(L, 3, "weight"); + + lua_settable(L, 1); + + index++; + } + } + + return 1; +} + + +int print_graph(lua_State *L) +{ + header head = (header)lua_touserdata(L,1); + + connect node_walker = head->front; + edge edge_walker; + + while (node_walker != NULL) + { + printf("%d: ", node_walker->node_id); + edge_walker = node_walker->neighbor_list; + while (edge_walker != NULL) + { + printf("(%d,%d), ", edge_walker->to_id, edge_walker->weight); + edge_walker = edge_walker->next_edge; + } + printf("\n"); + node_walker = node_walker->next_node; + } + + return 0; +} \ No newline at end of file diff --git a/modules/graph_utils.h b/modules/graph_utils.h index 106faad..78e85ad 100644 --- a/modules/graph_utils.h +++ b/modules/graph_utils.h @@ -20,9 +20,11 @@ LUA_FUNCTION(get_nodes); { id = , from_node = , - to_node = + to_node = , + weight = number, } */ LUA_FUNCTION(get_edges); +LUA_FUNCTION(print_graph); #endif \ No newline at end of file diff --git a/modules/utils.c b/modules/utils.c new file mode 100644 index 0000000..be76908 --- /dev/null +++ b/modules/utils.c @@ -0,0 +1,105 @@ +#include +#include + +#include "utils.h" + +int top(sq_node_p stack_top) +{ + if(stack_top == NULL) + { + puts("STACK EMPTY"); + return SQ_EMPTY; + } + return stack_top->value; +} + +int front(sq_node_p queue_front) +{ + if(queue_front == NULL) + { + puts("QUEUE EMPTY"); + return SQ_EMPTY; + } + return queue_front->value; +} + +//FUNCTIONS HANDELING CHANGING THE STACK +sq_node_p push(sq_node_p stack_top, int val) +{ + sq_node_p new_node = (sq_node_p)malloc(sizeof(sq_node)); + new_node->value = val; + new_node->next = stack_top; + return new_node; +} + +sq_node_p pop(sq_node_p stack_top) +{ + sq_node_p temp = stack_top; + + if(temp == NULL) + { + puts("STACK IS ALREADY EMPTY"); + return NULL; + } + + stack_top = stack_top->next; + + int n = temp->value; + free(temp); + + return stack_top; +} + +//FUNCTIONS HANDELING CHANGING THE QUEUE +sq_node_p enque(sq_node_p front_of_queue, int val) +{ + sq_node_p new_node = (sq_node_p)malloc(sizeof(sq_node)); + new_node->value = val; + new_node->next = NULL; //this will be at the back of the queue + + if(front_of_queue == NULL) + front_of_queue = new_node; + else + { + sq_node_p runner = front_of_queue; + + while(runner->next != NULL) //get to the end of the queue + { + runner = runner->next; + } + + runner->next = new_node; //add new node to the end of the queue + } + + return front_of_queue; +} + +sq_node_p deque(sq_node_p front_of_queue) +{ + if(front_of_queue == NULL) + { + puts("QUEUE IS ALREADY EMPTY"); + return NULL; + } + + sq_node_p temp = front_of_queue; + + front_of_queue = front_of_queue->next; + + free(temp); //dump the removed queue + + return front_of_queue; +} + +void print_sq(sq_node_p sq) +{ + sq_node_p runner = sq; + + while(runner != NULL) + { + printf("%d ", runner->value); + runner = runner->next; + } + + puts(""); +} \ No newline at end of file diff --git a/modules/utils.h b/modules/utils.h new file mode 100644 index 0000000..30e4052 --- /dev/null +++ b/modules/utils.h @@ -0,0 +1,12 @@ +#ifndef __UTILS_H__ +#define __UTILS_H__ + +#define SQ_EMPTY -8675309 + +typedef struct sq_node { + int value; + struct sq_node * next; +} sq_node, *sq_node_p; + + +#endif \ No newline at end of file diff --git a/test.lua b/test.lua new file mode 100644 index 0000000..5b43e21 --- /dev/null +++ b/test.lua @@ -0,0 +1,21 @@ +require "graphs" + +local graph = graphs.create_graph() +graphs.add_node(graph) +graphs.add_node(graph) +graphs.add_node(graph) +graphs.add_undirected(graph,0,1,10) +local edges = graphs.get_edges(graph) +for k, v in ipairs(edges) do + print(k, v.id, v.from_node, v.to_node, v.weight) +end + +graphs.del_node(graph,1) +graphs.add_node(graph) +--graphs.del_edge(graph,0) +--graphs.print_graph(graph) + +local nodes = graphs.get_nodes(graph) +for k, v in ipairs(nodes) do + print(k, v.id, v.x, v.y) +end \ No newline at end of file -- 2.25.1