API tools faq
paste
Advertisement
infologica

minimum path-list graph

infologica
May 15th, 2024
130
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 11.34 KB | None | 0 0
raw download clone embed print report
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <stdio.h>
  4. #include <string.h>
  5. #include <errno.h>
  6.  
  7. #define MIN(x, y) ((x) < (y) ? (x) : (y))
  8. typedef enum {ALB, GRI, NEGRU} color;
  9. #define INF 9999999
  10.  
  11. #define DIE(assertion, call_description)            \
  12.     do                                              \
  13.     {                                               \
  14.         if (assertion)                              \
  15.         {                                           \
  16.             fprintf(stderr, "(%s, %d): ", __FILE__, \
  17.                     __LINE__);                      \
  18.             perror(call_description);               \
  19.             exit(errno);                            \
  20.         }                                           \
  21.     } while (0)
  22.  
  23. #define MAX_QUEUE_SIZE 100
  24.  
  25. typedef struct ll_node_t ll_node_t;
  26. typedef struct linked_list_t linked_list_t;
  27. typedef struct queue_t queue_t;
  28. typedef struct list_graph_t list_graph_t;
  29.  
  30. /* Helper data structures definitions */
  31. struct ll_node_t
  32. {
  33.     void* data;
  34.     ll_node_t* next;
  35. };
  36.  
  37. struct linked_list_t
  38. {
  39.     ll_node_t* head;
  40.     unsigned int data_size;
  41.     unsigned int size;
  42. };
  43.  
  44. struct queue_t
  45. {
  46.     unsigned int max_size;
  47.     unsigned int size;
  48.     unsigned int data_size;
  49.     unsigned int read_idx;
  50.     unsigned int write_idx;
  51.     void **buff;
  52. };
  53.  
  54. struct list_graph_t
  55. {
  56.     linked_list_t** neighbors;
  57.     int nodes;
  58. };
  59.  
  60. linked_list_t* ll_create(unsigned int data_size);
  61. static ll_node_t* get_nth_node(linked_list_t* list, unsigned int n);
  62. void ll_add_nth_node(linked_list_t* list, unsigned int n, const void* new_data);
  63. ll_node_t* ll_remove_nth_node(linked_list_t* list, unsigned int n);
  64. unsigned int ll_get_size(linked_list_t* list);
  65. void ll_free(linked_list_t** pp_list);
  66. void ll_print_int(linked_list_t* list);
  67. void ll_print_string(linked_list_t* list);
  68.  
  69. queue_t* q_create(unsigned int data_size, unsigned int max_size);
  70. unsigned int q_get_size(queue_t* q);
  71. unsigned int q_is_empty(queue_t* q);
  72. void* q_front(queue_t* q);
  73. int q_dequeue(queue_t* q);
  74. int q_enqueue(queue_t* q, void* new_data);
  75. void q_clear(queue_t* q);
  76. void q_free(queue_t* q);
  77.  
  78. list_graph_t* lg_create(int nodes);
  79. void lg_add_edge(list_graph_t* graph, int src, int dest);
  80. static ll_node_t *find_node(linked_list_t *ll, int node, unsigned int *pos);
  81. int lg_has_edge(list_graph_t* graph, int src, int dest);
  82. linked_list_t* lg_get_neighbours(list_graph_t* graph, int node);
  83. void lg_remove_edge(list_graph_t* graph, int src, int dest);
  84. void lg_free(list_graph_t* graph);
  85.  
  86. /*
  87.     TODO
  88.  
  89.     Prints the nodes which make up the minimum path between src and dest.
  90.  
  91.     For example, if the minimum path between A and B is A->C->D->E->F->B, then
  92.     this function will print "A C D E F B".
  93.  
  94.     Output format:
  95.  
  96.     node_1 node_2 node_3 ... node_k
  97.  
  98.     For the purpose of finding minimum paths, the given graph
  99.     can be either oriented or unoriented. For this exercise, the graph
  100.     is oriented.
  101. */
  102.  
  103. void print_min_path(list_graph_t *graph, int src, int dest)
  104. {
  105.     int d[graph->nodes];
  106.     int p[graph->nodes];
  107.     int stare[graph->nodes];
  108.  
  109.     for (int i = 0; i < graph->nodes; i++) {
  110.         d[i] = INF;
  111.         p[i] = -1;
  112.         stare[i] = ALB;
  113.     }
  114.  
  115.     if (!graph)
  116.         return;
  117.  
  118.     queue_t* q = q_create(sizeof(int), graph->nodes);
  119.  
  120.     /* Marcam nodul de start ca vizitat si il adaugam in coada */
  121.     q_enqueue(q, &src);
  122.     stare[src] = GRI;
  123.     d[src] = 0;
  124.  
  125.     // Parcurgerea BFS
  126.     while (!q_is_empty(q)) {
  127.         // Extragem un nod din coadă
  128.         int current_node;
  129.         memcpy(&current_node, q_front(q), sizeof(int));
  130.         q_dequeue(q);
  131.  
  132.         // Parcurgem vecinii nodului curent
  133.         ll_node_t* neighbor = graph->neighbors[current_node]->head;
  134.         while (neighbor != NULL) {
  135.             int neighbor_node = *(int*)neighbor->data;
  136.             /* Verificam daca vecinul nu a fost vizitat inca */
  137.             if (stare[neighbor_node] == ALB) {
  138.                 /* Il marcam ca vizitat si il adaugam in coada pentru a fi vizitat ulterior */
  139.                 stare[neighbor_node] = GRI;
  140.                 p[neighbor_node] = current_node;
  141.                 d[neighbor_node] = d[current_node] + 1;
  142.                 q_enqueue(q, &neighbor_node);
  143.             }
  144.             neighbor = neighbor->next;
  145.         }
  146.     }
  147.     int v[graph->nodes];
  148.     int i = 0;
  149.    
  150.     if(p[dest] == -1) {
  151.         printf("No path found\n");
  152.         q_free(q);
  153.         return;
  154.     }
  155.     while (p[dest] != -1) {
  156.         v[i] = dest;
  157.         dest = p[dest];
  158.         i++;
  159.     }
  160.     v[i] = dest;
  161.  
  162.     for(int j = i; i >=0; i--) {
  163.         printf("%d ", v[i]);
  164.     }
  165.  
  166.     // Eliberam memoria pentru coada
  167.     q_free(q);
  168. }
  169.  
  170. int main()
  171. {
  172.     int n, m, src, dest;
  173.     list_graph_t *graph;
  174.  
  175.     scanf("%d%d", &n, &m);
  176.     graph = lg_create(n);
  177.  
  178.     // Read graph edges
  179.     for (int i = 0; i < m; ++i) {
  180.         scanf("%d%d", &src, &dest);
  181.         lg_add_edge(graph, src, dest);
  182.     }
  183.  
  184.     // Read src & dest for min path
  185.     scanf("%d%d", &src, &dest);
  186.  
  187.     print_min_path(graph, src, dest);
  188.  
  189.     lg_free(graph);
  190.     return 0;
  191. }
  192.  
  193. /* Helper data structures functions */
  194. linked_list_t *
  195. ll_create(unsigned int data_size)
  196. {
  197.     linked_list_t *ll = calloc(1, sizeof(*ll));
  198.     DIE(!ll, "calloc list");
  199.  
  200.     ll->data_size = data_size;
  201.  
  202.     return ll;
  203. }
  204.  
  205. static ll_node_t *
  206. get_nth_node(linked_list_t *list, unsigned int n)
  207. {
  208.     unsigned int len = list->size - 1;
  209.     unsigned int i;
  210.     ll_node_t *node = list->head;
  211.  
  212.     n = MIN(n, len);
  213.  
  214.     for (i = 0; i < n; ++i)
  215.         node = node->next;
  216.  
  217.     return node;
  218. }
  219.  
  220. static ll_node_t *
  221. create_node(const void *new_data, unsigned int data_size)
  222. {
  223.     ll_node_t *node = calloc(1, sizeof(*node));
  224.     DIE(!node, "calloc node");
  225.  
  226.     node->data = malloc(data_size);
  227.     DIE(!node->data, "malloc data");
  228.  
  229.     memcpy(node->data, new_data, data_size);
  230.  
  231.     return node;
  232. }
  233.  
  234. void ll_add_nth_node(linked_list_t *list, unsigned int n, const void *new_data)
  235. {
  236.     ll_node_t *new_node, *prev_node;
  237.  
  238.     if (!list)
  239.         return;
  240.  
  241.     new_node = create_node(new_data, list->data_size);
  242.  
  243.     if (!n || !list->size)
  244.     {
  245.         new_node->next = list->head;
  246.         list->head = new_node;
  247.     }
  248.     else
  249.     {
  250.         prev_node = get_nth_node(list, n - 1);
  251.         new_node->next = prev_node->next;
  252.         prev_node->next = new_node;
  253.     }
  254.  
  255.     ++list->size;
  256. }
  257.  
  258. ll_node_t *
  259. ll_remove_nth_node(linked_list_t *list, unsigned int n)
  260. {
  261.     ll_node_t *prev_node, *removed_node;
  262.  
  263.     if (!list || !list->size)
  264.         return NULL;
  265.  
  266.     if (!n)
  267.     {
  268.         removed_node = list->head;
  269.         list->head = removed_node->next;
  270.         removed_node->next = NULL;
  271.     }
  272.     else
  273.     {
  274.         prev_node = get_nth_node(list, n - 1);
  275.         removed_node = prev_node->next;
  276.         prev_node->next = removed_node->next;
  277.         removed_node->next = NULL;
  278.     }
  279.  
  280.     --list->size;
  281.  
  282.     return removed_node;
  283. }
  284.  
  285. unsigned int
  286. ll_get_size(linked_list_t *list)
  287. {
  288.     return !list ? 0 : list->size;
  289. }
  290.  
  291. void ll_free(linked_list_t **pp_list)
  292. {
  293.     ll_node_t *node;
  294.  
  295.     if (!pp_list || !*pp_list)
  296.         return;
  297.  
  298.     while ((*pp_list)->size)
  299.     {
  300.         node = ll_remove_nth_node(*pp_list, 0);
  301.         free(node->data);
  302.         free(node);
  303.     }
  304.  
  305.     free(*pp_list);
  306.     *pp_list = NULL;
  307. }
  308.  
  309. void ll_print_int(linked_list_t *list)
  310. {
  311.     ll_node_t *node = list->head;
  312.  
  313.     for (; node; node = node->next)
  314.         printf("%d ", *(int *)node->data);
  315.     printf("\n");
  316. }
  317.  
  318. void ll_print_string(linked_list_t *list)
  319. {
  320.     ll_node_t *node = list->head;
  321.  
  322.     for (; node; node = node->next)
  323.         printf("%s ", (char *)node->data);
  324.     printf("\n");
  325. }
  326.  
  327. queue_t *
  328. q_create(unsigned int data_size, unsigned int max_size)
  329. {
  330.     queue_t *q = calloc(1, sizeof(*q));
  331.     DIE(!q, "calloc queue failed");
  332.  
  333.     q->data_size = data_size;
  334.     q->max_size = max_size;
  335.  
  336.     q->buff = malloc(max_size * sizeof(*q->buff));
  337.     DIE(!q->buff, "malloc buffer failed");
  338.  
  339.     return q;
  340. }
  341.  
  342. unsigned int
  343. q_get_size(queue_t *q)
  344. {
  345.     return !q ? 0 : q->size;
  346. }
  347.  
  348. unsigned int
  349. q_is_empty(queue_t *q)
  350. {
  351.     return !q ? 1 : !q->size;
  352. }
  353.  
  354. void *
  355. q_front(queue_t *q)
  356. {
  357.     if (!q || !q->size)
  358.         return NULL;
  359.  
  360.     return q->buff[q->read_idx];
  361. }
  362.  
  363. int q_dequeue(queue_t *q)
  364. {
  365.     if (!q || !q->size)
  366.         return 0;
  367.  
  368.     free(q->buff[q->read_idx]);
  369.  
  370.     q->read_idx = (q->read_idx + 1) % q->max_size;
  371.     --q->size;
  372.     return 1;
  373. }
  374.  
  375. int q_enqueue(queue_t *q, void *new_data)
  376. {
  377.     void *data;
  378.     if (!q || q->size == q->max_size)
  379.         return 0;
  380.  
  381.     data = malloc(q->data_size);
  382.     DIE(!data, "malloc data failed");
  383.     memcpy(data, new_data, q->data_size);
  384.  
  385.     q->buff[q->write_idx] = data;
  386.     q->write_idx = (q->write_idx + 1) % q->max_size;
  387.     ++q->size;
  388.  
  389.     return 1;
  390. }
  391.  
  392. void q_clear(queue_t *q)
  393. {
  394.     unsigned int i;
  395.     if (!q || !q->size)
  396.         return;
  397.  
  398.     for (i = q->read_idx; i != q->write_idx; i = (i + 1) % q->max_size)
  399.         free(q->buff[i]);
  400.  
  401.     q->read_idx = 0;
  402.     q->write_idx = 0;
  403.     q->size = 0;
  404. }
  405.  
  406. void q_free(queue_t *q)
  407. {
  408.     if (!q)
  409.         return;
  410.  
  411.     q_clear(q);
  412.     free(q->buff);
  413.     free(q);
  414. }
  415.  
  416. static int is_node_in_graph(int n, int nodes)
  417. {
  418.     return n >= 0 && n < nodes;
  419. }
  420.  
  421. list_graph_t *
  422. lg_create(int nodes)
  423. {
  424.     int i;
  425.  
  426.     list_graph_t *g = malloc(sizeof(*g));
  427.     DIE(!g, "malloc graph failed");
  428.  
  429.     g->neighbors = malloc(nodes * sizeof(*g->neighbors));
  430.     DIE(!g->neighbors, "malloc neighbours failed");
  431.  
  432.     for (i = 0; i != nodes; ++i)
  433.         g->neighbors[i] = ll_create(sizeof(int));
  434.  
  435.     g->nodes = nodes;
  436.  
  437.     return g;
  438. }
  439.  
  440. void lg_add_edge(list_graph_t *graph, int src, int dest)
  441. {
  442.     if (
  443.         !graph || !graph->neighbors || !is_node_in_graph(src, graph->nodes) || !is_node_in_graph(dest, graph->nodes))
  444.         return;
  445.  
  446.     ll_add_nth_node(graph->neighbors[src], graph->neighbors[src]->size, &dest);
  447. }
  448.  
  449. static ll_node_t *find_node(linked_list_t *ll, int node, unsigned int *pos)
  450. {
  451.     ll_node_t *crt = ll->head;
  452.     unsigned int i;
  453.  
  454.     for (i = 0; i != ll->size; ++i)
  455.     {
  456.         if (node == *(int *)crt->data)
  457.         {
  458.             *pos = i;
  459.             return crt;
  460.         }
  461.  
  462.         crt = crt->next;
  463.     }
  464.  
  465.     return NULL;
  466. }
  467.  
  468. int lg_has_edge(list_graph_t *graph, int src, int dest)
  469. {
  470.     unsigned int pos;
  471.  
  472.     if (
  473.         !graph || !graph->neighbors || !is_node_in_graph(src, graph->nodes) || !is_node_in_graph(dest, graph->nodes))
  474.         return 0;
  475.  
  476.     return find_node(graph->neighbors[src], dest, &pos) != NULL;
  477. }
  478.  
  479. linked_list_t *
  480. lg_get_neighbours(list_graph_t *graph, int node)
  481. {
  482.     if (
  483.         !graph || !graph->neighbors || !is_node_in_graph(node, graph->nodes))
  484.         return NULL;
  485.  
  486.     return graph->neighbors[node];
  487. }
  488.  
  489. void lg_remove_edge(list_graph_t *graph, int src, int dest)
  490. {
  491.     unsigned int pos;
  492.  
  493.     if (
  494.         !graph || !graph->neighbors || !is_node_in_graph(src, graph->nodes) || !is_node_in_graph(dest, graph->nodes))
  495.         return;
  496.  
  497.     if (!find_node(graph->neighbors[src], dest, &pos))
  498.         return;
  499.  
  500.     ll_remove_nth_node(graph->neighbors[src], pos);
  501. }
  502.  
  503. void lg_free(list_graph_t *graph)
  504. {
  505.     int i;
  506.  
  507.     for (i = 0; i != graph->nodes; ++i)
  508.         ll_free(graph->neighbors + i);
  509.  
  510.     free(graph->neighbors);
  511.     free(graph);
  512. }
  513.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!