From fa5222dc2ee8985f1dfc9cbe9aea61fa01004b09 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Mon, 16 Oct 2017 12:59:08 +0200 Subject: [PATCH] Push the WIP graphs handling code MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Not working yet Signed-off-by: Jérôme Benoit --- .gitignore | 1 + TP7/exo1/Makefile | 82 ++++++++++++++++ TP7/exo1/graphs.c | 110 +++++++++++++++++++++ TP7/exo1/graphs.h | 31 ++++++ TP7/exo1/list.h | 246 ++++++++++++++++++++++++++++++++++++++++++++++ TP7/exo1/main.c | 25 +++++ 6 files changed, 495 insertions(+) create mode 100644 TP7/exo1/Makefile create mode 100644 TP7/exo1/graphs.c create mode 100644 TP7/exo1/graphs.h create mode 100644 TP7/exo1/list.h create mode 100644 TP7/exo1/main.c diff --git a/.gitignore b/.gitignore index af82068..33f33d3 100644 --- a/.gitignore +++ b/.gitignore @@ -25,6 +25,7 @@ tas *.swp *~ +*.gch .build thumbs.db diff --git a/TP7/exo1/Makefile b/TP7/exo1/Makefile new file mode 100644 index 0000000..9870729 --- /dev/null +++ b/TP7/exo1/Makefile @@ -0,0 +1,82 @@ +# Sample Makefile to build simple project. +# +# This Makefile expect all source files (.c) to be at the same level, in the +# current working directory. +# +# It will automatically generate dependencies, compile all files, and produce a +# binary using the provided name. +# +# Set BINARY_NAME to the name of the binary file to build. +# Set BUILD_TYPE to either debug or release +# +# Automatic dependencies code from: +# http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/#tldr +BINARY_NAME=exo1 +BUILD_TYPE=debug + +# ==================================== +# DO NOT CHANGE STUFF BEYOND THIS LINE +# ==================================== + +all: $(BINARY_NAME) + +CC=gcc +LD=gcc + +WARN_FLAGS = -Wall -Wextra +STD_FLAG = -std=c11 + +ifeq ($(BUILD_TYPE),debug) +BUILDDIR := .build/debug +DEBUG_FLAG = -g +STRIP_FLAG = +OPTI_FLAG = -O0 +else +BUILDDIR := .build/release +DEBUG_FLAG = +STRIP_FLAG = -s +OPTI_FLAG = -O3 +endif + +CFLAGS := $(CFLAGS) $(WARN_FLAGS) $(STD_FLAG) $(OPTI_FLAG) $(DEBUG_FLAG) +LDFLAGS := $(LDFLAGS) $(STRIP_FLAG) + +OBJDIR := $(BUILDDIR)/objs +$(shell mkdir -p $(OBJDIR)) + +SRCS=$(wildcard *.c) +OBJS=$(patsubst %.c,$(OBJDIR)/%.o,$(SRCS)) + +DEPDIR := $(BUILDDIR)/deps +$(shell mkdir -p $(DEPDIR)) +DEPFLAGS = -MT $@ -MMD -MP -MF $(DEPDIR)/$*.Td +POSTCOMPILE = mv -f $(DEPDIR)/$*.Td $(DEPDIR)/$*.d + +$(BINARY_NAME): $(OBJS) + @echo "[LD ] $@" + @$(LD) $(CFLAGS) $(LDFLAGS) $^ $(LDLIBS) -o $@ + +$(OBJDIR)/%.o: %.c $(DEPDIR)/%.d + @echo "[C ] $*" + @$(CC) $(DEPFLAGS) $(CFLAGS) -c $< -o $@ + @$(POSTCOMPILE) + +$(DEPDIR)/%.d: ; + +.PRECIOUS: $(DEPDIR)/%.d + +include $(wildcard $(patsubst %,$(DEPDIR)/%.d,$(basename $(SRCS)))) + +run: + ./$(BINARY_NAME) + +clean: + @echo "[CLN]" + -@rm -r $(BUILDDIR) + -@rm $(BINARY_NAME) + +disassemble: $(BINARY_NAME) + objdump -d $< | less + +symbols: $(BINARY_NAME) + objdump -t $< | sort | less diff --git a/TP7/exo1/graphs.c b/TP7/exo1/graphs.c new file mode 100644 index 0000000..4347350 --- /dev/null +++ b/TP7/exo1/graphs.c @@ -0,0 +1,110 @@ +#include +#include + +#include "graphs.h" + +void init_adj_matrix(int adj_matrix[num_nodes][num_nodes]) { + for (unsigned int i = 0; i < num_nodes; i++) { + for (unsigned int j = 0; j < num_nodes; j++) { + adj_matrix[i][j] = 0; + } + } +} + +unsigned int num_successors_adj_matrix(unsigned int node, int adj_matrix[num_nodes][num_nodes]) { + unsigned int num_successors = 0; + + for (unsigned int i = 0; i < num_nodes; i++) { + if (adj_matrix[node][i] == 1) { + num_successors++; + } + } + return num_successors; +} + +unsigned int num_successors_adj_list(unsigned int node, succ_list_t* nodes[num_nodes]) { + struct list_head* list_iter = NULL; + unsigned int num_successors = 0; + + if (!list_empty(&nodes[node]->list)) { + list_for_each(list_iter, &nodes[node]->list) { + num_successors++; + } + } + return num_successors; +} + +bool has_successor_adj_matrix(unsigned int node, int adj_matrix[num_nodes][num_nodes]) { + + for (unsigned int i = 0; i < num_nodes; i++) { + if (adj_matrix[node][i] == 1) { + return true; + } + } + return false; +} + +void add_adj_list_cell(unsigned int node, bool is_valued, int value, succ_list_t* successors_list) { + succ_list_t* list_cell = (succ_list_t*)malloc(sizeof(succ_list_t)); + if (!list_cell) { + exit(EXIT_FAILURE); + } + + list_cell->num_node = node; + if (is_valued) list_cell->val = value; + list_add_tail(&(list_cell->list), &(successors_list->list)); +} + +void free_adj_list(succ_list_t* successors_list) { + succ_list_t* list_iter = NULL; + + while (!list_empty(&successors_list->list)) { + list_iter = list_entry(successors_list->list.next, succ_list_t, list); + list_del(&(list_iter->list)); + free(list_iter); + } +} + +void build_adj_list(unsigned int node, int adj_matrix[num_nodes][num_nodes], succ_list_t* successors_list) { + unsigned int num_successors = 0; + + num_successors = num_successors_adj_matrix(node, adj_matrix); + + for (unsigned int i = 0; i < num_successors && num_successors != 0; i++) { + if (adj_matrix[node][i] == 1) { + add_adj_list_cell(node, false, 0, successors_list); + } + } +} + +void convert_adj_matrix_to_adj_lists(int adj_matrix[num_nodes][num_nodes], succ_list_t* nodes[num_nodes]) { + succ_list_t succ_list_array[num_nodes]; + + for (unsigned int i = 0; i < num_nodes; i++) { + //init num_nodes linked list + INIT_LIST_HEAD(&(succ_list_array[i].list)); + //NOTE: the nodes array is NOT the head of the list, they point to the list head + build_adj_list(i, adj_matrix, &succ_list_array[i]); + //if list_array[i] not empty, then nodes[i] = &list_array[i] else = NULL + } +} + +void display_adj_matrix(int adj_matrix[num_nodes][num_nodes]) { + for (unsigned int i = 0; i < num_nodes; i++) { + for (unsigned int j = 0; j < num_nodes; j++) { + printf("%d ", adj_matrix[i][j]); + } + printf("\n"); + } +} + +void display_adj_lists(succ_list_t* nodes[num_nodes]) { + succ_list_t* list_iter = NULL; + + for (unsigned int i = 0; i < num_nodes; i++) { + list_for_each_entry(list_iter, &nodes[i]->list, list) { + printf("%d ", list_iter->num_node); + } + printf("\n"); + } +} diff --git a/TP7/exo1/graphs.h b/TP7/exo1/graphs.h new file mode 100644 index 0000000..734b96f --- /dev/null +++ b/TP7/exo1/graphs.h @@ -0,0 +1,31 @@ +#ifndef GRAPHS_H +#define GRAPHS_H + +#include +#include + +#include "list.h" + +/* number of nodes or vertices or points */ +//const unsigned int num_nodes = 10; +#define num_nodes 5 + +/* Adjacency matrix */ +/* for a valued graph */ +int M[num_nodes][num_nodes]; +/* for an oriented graph */ +//bool M[num_nodes][num_nodes]; + +/* Adjacency list */ +typedef struct succ_list_s { + unsigned int num_node; + int val; + struct list_head list; +} succ_list_t; +//succ_list_t* nodes[num_nodes] = { NULL }; + +void display_adj_matrix(int adj_matrix[num_nodes][num_nodes]); +void convert_adj_matrix_to_adj_lists(int adj_matrix[num_nodes][num_nodes], succ_list_t* nodes[num_nodes]); +void display_adj_lists(succ_list_t* nodes[num_nodes]); + +#endif diff --git a/TP7/exo1/list.h b/TP7/exo1/list.h new file mode 100644 index 0000000..b9d8cba --- /dev/null +++ b/TP7/exo1/list.h @@ -0,0 +1,246 @@ +#ifndef __LIST_H +#define __LIST_H + +/* This file is from Linux Kernel (include/linux/list.h) + * and modified by simply removing hardware prefetching of list items. + * Here by copyright, credits attributed to wherever they belong. + * Kulesh Shanmugasundaram (kulesh [squiggly] isis.poly.edu) + */ + +/* + * Simple doubly linked list implementation. + * + * Some of the internal functions ("__xxx") are useful when + * manipulating whole lists rather than single entries, as + * sometimes we already know the next/prev entries and we can + * generate better code by using them directly rather than + * using the generic single-entry routines. + */ + +struct list_head { + struct list_head *next, *prev; +}; + +#define typeof __typeof__ + +#define LIST_HEAD_INIT(name) { &(name), &(name) } + +#define LIST_HEAD(name) \ + struct list_head name = LIST_HEAD_INIT(name) + +#define INIT_LIST_HEAD(ptr) do { \ + (ptr)->next = (ptr); (ptr)->prev = (ptr); \ +} while (0) + +/* + * Insert a new entry between two known consecutive entries. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __list_add(struct list_head *new, + struct list_head *prev, + struct list_head *next) +{ + next->prev = new; + new->next = next; + new->prev = prev; + prev->next = new; +} + +/** + * list_add - add a new entry + * @new: new entry to be added + * @head: list head to add it after + * + * Insert a new entry after the specified head. + * This is good for implementing stacks. + */ +static inline void list_add(struct list_head *new, struct list_head *head) +{ + __list_add(new, head, head->next); +} + +/** + * list_add_tail - add a new entry + * @new: new entry to be added + * @head: list head to add it before + * + * Insert a new entry before the specified head. + * This is useful for implementing queues. + */ +static inline void list_add_tail(struct list_head *new, struct list_head *head) +{ + __list_add(new, head->prev, head); +} + +/* + * Delete a list entry by making the prev/next entries + * point to each other. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __list_del(struct list_head *prev, struct list_head *next) +{ + next->prev = prev; + prev->next = next; +} + +/** + * list_del - deletes entry from list. + * @entry: the element to delete from the list. + * Note: list_empty on entry does not return true after this, the entry is in an undefined state. + */ +static inline void list_del(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); + entry->next = (void *) 0; + entry->prev = (void *) 0; +} + +/** + * list_del_init - deletes entry from list and reinitialize it. + * @entry: the element to delete from the list. + */ +static inline void list_del_init(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); + INIT_LIST_HEAD(entry); +} + +/** + * list_move - delete from one list and add as another's head + * @list: the entry to move + * @head: the head that will precede our entry + */ +static inline void list_move(struct list_head *list, struct list_head *head) +{ + __list_del(list->prev, list->next); + list_add(list, head); +} + +/** + * list_move_tail - delete from one list and add as another's tail + * @list: the entry to move + * @head: the head that will follow our entry + */ +static inline void list_move_tail(struct list_head *list, + struct list_head *head) +{ + __list_del(list->prev, list->next); + list_add_tail(list, head); +} + +/** + * list_empty - tests whether a list is empty + * @head: the list to test. + */ +static inline int list_empty(struct list_head *head) +{ + return head->next == head; +} + +static inline void __list_splice(struct list_head *list, + struct list_head *head) +{ + struct list_head *first = list->next; + struct list_head *last = list->prev; + struct list_head *at = head->next; + + first->prev = head; + head->next = first; + + last->next = at; + at->prev = last; +} + +/** + * list_splice - join two lists + * @list: the new list to add. + * @head: the place to add it in the first list. + */ +static inline void list_splice(struct list_head *list, struct list_head *head) +{ + if (!list_empty(list)) + __list_splice(list, head); +} + +/** + * list_splice_init - join two lists and reinitialise the emptied list. + * @list: the new list to add. + * @head: the place to add it in the first list. + * + * The list at @list is reinitialised + */ +static inline void list_splice_init(struct list_head *list, + struct list_head *head) +{ + if (!list_empty(list)) { + __list_splice(list, head); + INIT_LIST_HEAD(list); + } +} + +/** + * list_entry - get the struct for this entry + * @ptr: the &struct list_head pointer. + * @type: the type of the struct this is embedded in. + * @member: the name of the list_struct within the struct. + */ +#define list_entry(ptr, type, member) \ + ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) + +/** + * list_for_each - iterate over a list + * @pos: the &struct list_head to use as a loop counter. + * @head: the head for your list. + */ +#define list_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); \ + pos = pos->next) +/** + * list_for_each_prev - iterate over a list backwards + * @pos: the &struct list_head to use as a loop counter. + * @head: the head for your list. + */ +#define list_for_each_prev(pos, head) \ + for (pos = (head)->prev; pos != (head); \ + pos = pos->prev) + +/** + * list_for_each_safe - iterate over a list safe against removal of list entry + * @pos: the &struct list_head to use as a loop counter. + * @n: another &struct list_head to use as temporary storage + * @head: the head for your list. + */ +#define list_for_each_safe(pos, n, head) \ + for (pos = (head)->next, n = pos->next; pos != (head); \ + pos = n, n = pos->next) + +/** + * list_for_each_entry - iterate over list of given type + * @pos: the type * to use as a loop counter. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry(pos, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) + +/** + * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry + * @pos: the type * to use as a loop counter. + * @n: another type * to use as temporary storage + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry_safe(pos, n, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member), \ + n = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = n, n = list_entry(n->member.next, typeof(*n), member)) + + +#endif diff --git a/TP7/exo1/main.c b/TP7/exo1/main.c new file mode 100644 index 0000000..883865b --- /dev/null +++ b/TP7/exo1/main.c @@ -0,0 +1,25 @@ +#include + +#include "graphs.h" + +int main() { + int adj_matrix[num_nodes][num_nodes] = { + {0, 0, 0, 1, 0}, + {0, 0, 1, 0, 0}, + {0, 0, 0, 0, 0}, + {0, 1, 0, 0, 1}, + {1, 1, 1, 0, 0} + }; + succ_list_t* nodes[num_nodes] = { NULL }; + for (unsigned int i = 0; i < num_nodes; i++) { + LIST_HEAD(nodes); + } + + display_adj_matrix(adj_matrix); + + convert_adj_matrix_to_adj_lists(adj_matrix, nodes); + + display_adj_lists(nodes); + + return 0; +} -- 2.34.1