Branch data     Line data    Source code

       1                 :            : #include "graph.h"
       2                 :            : 
       3                 :            : #include <stdio.h>
       4                 :            : #include <stdlib.h>
       5                 :            : #include <limits.h>
       6                 :            : #include <assert.h>
       7                 :            : #include <string.h>
       8                 :            : #include "vstack.h"
       9                 :            : #include "bitbool.h"
      10                 :            : 
      11                 :            : //#define DEBUG
      12                 :            : #include "debug.h"
      13                 :            : 
      14                 :            : /* static const cmph_uint8 bitmask[8] = { 1, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 6, 1 << 7 }; */
      15                 :            : /* #define GETBIT(array, i) (array[(i) / 8] & bitmask[(i) % 8]) */
      16                 :            : /* #define SETBIT(array, i) (array[(i) / 8] |= bitmask[(i) % 8]) */
      17                 :            : /* #define UNSETBIT(array, i) (array[(i) / 8] &= (~(bitmask[(i) % 8]))) */
      18                 :            : 
      19                 :            : #define abs_edge(e, i) (e % g->nedges + i * g->nedges)
      20                 :            : 
      21                 :            : struct __graph_t
      22                 :            : {
      23                 :            :         cmph_uint32 nnodes;
      24                 :            :         cmph_uint32 nedges;
      25                 :            :         cmph_uint32 *edges;
      26                 :            :         cmph_uint32 *first;
      27                 :            :         cmph_uint32 *next;
      28                 :            :         cmph_uint8  *critical_nodes;   /* included -- Fabiano*/
      29                 :            :         cmph_uint32 ncritical_nodes;   /* included -- Fabiano*/
      30                 :            :         cmph_uint32 cedges;
      31                 :            :         int shrinking;
      32                 :            : };
      33                 :            : 
      34                 :            : static cmph_uint32 EMPTY = UINT_MAX;
      35                 :            : 
      36                 :          0 : graph_t *graph_new(cmph_uint32 nnodes, cmph_uint32 nedges)
      37                 :            : {
      38                 :          0 :         graph_t *graph = (graph_t *)malloc(sizeof(graph_t));
      39         [ #  # ]:          0 :         if (!graph) return NULL;
      40                 :            : 
      41                 :          0 :         graph->edges = (cmph_uint32 *)malloc(sizeof(cmph_uint32) * 2 * nedges);
      42                 :          0 :         graph->next =  (cmph_uint32 *)malloc(sizeof(cmph_uint32) * 2 * nedges);
      43                 :          0 :         graph->first = (cmph_uint32 *)malloc(sizeof(cmph_uint32) * nnodes);
      44                 :          0 :         graph->critical_nodes = NULL; /* included -- Fabiano*/
      45                 :          0 :         graph->ncritical_nodes = 0;   /* included -- Fabiano*/
      46                 :          0 :         graph->nnodes = nnodes;
      47                 :          0 :         graph->nedges = nedges;
      48                 :            : 
      49                 :          0 :         graph_clear_edges(graph);
      50                 :          0 :         return graph;
      51                 :            : }
      52                 :            : 
      53                 :            : 
      54                 :          0 : void graph_destroy(graph_t *graph)
      55                 :            : {
      56                 :            :         DEBUGP("Destroying graph\n");
      57                 :          0 :         free(graph->edges);
      58                 :          0 :         free(graph->first);
      59                 :          0 :         free(graph->next);
      60                 :          0 :         free(graph->critical_nodes); /* included -- Fabiano*/
      61                 :          0 :         free(graph);
      62                 :          0 :         return;
      63                 :            : }
      64                 :            : 
      65                 :          0 : void graph_print(graph_t *g)
      66                 :            : {
      67                 :            :         cmph_uint32 i, e;
      68         [ #  # ]:          0 :         for (i = 0; i < g->nnodes; ++i)
      69                 :            :         {
      70                 :            :                 DEBUGP("Printing edges connected to %u\n", i);
      71                 :          0 :                 e = g->first[i];
      72         [ #  # ]:          0 :                 if (e != EMPTY)
      73                 :            :                 {
      74                 :          0 :                         printf("%u -> %u\n", g->edges[abs_edge(e, 0)], g->edges[abs_edge(e, 1)]);
      75         [ #  # ]:          0 :                         while ((e = g->next[e]) != EMPTY)
      76                 :            :                         {
      77                 :          0 :                                 printf("%u -> %u\n", g->edges[abs_edge(e, 0)], g->edges[abs_edge(e, 1)]);
      78                 :            :                         }
      79                 :            :                 }
      80                 :            :                         
      81                 :            :         }
      82                 :          0 :         return;
      83                 :            : }
      84                 :            : 
      85                 :          0 : void graph_add_edge(graph_t *g, cmph_uint32 v1, cmph_uint32 v2)
      86                 :            : {
      87                 :          0 :         cmph_uint32 e = g->cedges;
      88                 :            : 
      89         [ #  # ]:          0 :         assert(v1 < g->nnodes);
      90         [ #  # ]:          0 :         assert(v2 < g->nnodes);
      91         [ #  # ]:          0 :         assert(e < g->nedges);
      92         [ #  # ]:          0 :         assert(!g->shrinking);
      93                 :            : 
      94                 :          0 :         g->next[e] = g->first[v1];
      95                 :          0 :         g->first[v1] = e;
      96                 :          0 :         g->edges[e] = v2;
      97                 :            : 
      98                 :          0 :         g->next[e + g->nedges] = g->first[v2];
      99                 :          0 :         g->first[v2] = e + g->nedges;
     100                 :          0 :         g->edges[e + g->nedges] = v1;
     101                 :            : 
     102                 :          0 :         ++(g->cedges);
     103                 :          0 : }
     104                 :            : 
     105                 :          0 : static int check_edge(graph_t *g, cmph_uint32 e, cmph_uint32 v1, cmph_uint32 v2)
     106                 :            : {
     107                 :            :         DEBUGP("Checking edge %u %u looking for %u %u\n", g->edges[abs_edge(e, 0)], g->edges[abs_edge(e, 1)], v1, v2);
     108   [ #  #  #  # ]:          0 :         if (g->edges[abs_edge(e, 0)] == v1 && g->edges[abs_edge(e, 1)] == v2) return 1;
     109   [ #  #  #  # ]:          0 :         if (g->edges[abs_edge(e, 0)] == v2 && g->edges[abs_edge(e, 1)] == v1) return 1;
     110                 :          0 :         return 0;
     111                 :            : }
     112                 :            : 
     113                 :          0 : cmph_uint32 graph_edge_id(graph_t *g, cmph_uint32 v1, cmph_uint32 v2)
     114                 :            : {
     115                 :            :         cmph_uint32 e;
     116                 :          0 :         e = g->first[v1];
     117         [ #  # ]:          0 :         assert(e != EMPTY);
     118         [ #  # ]:          0 :         if (check_edge(g, e, v1, v2)) return abs_edge(e, 0);
     119                 :            :         do
     120                 :            :         {
     121                 :          0 :                 e = g->next[e];
     122         [ #  # ]:          0 :                 assert(e != EMPTY);
     123                 :            :         }
     124         [ #  # ]:          0 :         while (!check_edge(g, e, v1, v2));
     125                 :          0 :         return abs_edge(e, 0);
     126                 :            : }
     127                 :          0 : static void del_edge_point(graph_t *g, cmph_uint32 v1, cmph_uint32 v2)
     128                 :            : {
     129                 :            :         cmph_uint32 e, prev;
     130                 :            : 
     131                 :            :         DEBUGP("Deleting edge point %u %u\n", v1, v2);
     132                 :          0 :         e = g->first[v1];
     133         [ #  # ]:          0 :         if (check_edge(g, e, v1, v2)) 
     134                 :            :         {
     135                 :          0 :                 g->first[v1] = g->next[e];
     136                 :            :                 //g->edges[e] = EMPTY;
     137                 :            :                 DEBUGP("Deleted\n");
     138                 :          0 :                 return;
     139                 :            :         }
     140                 :            :         DEBUGP("Checking linked list\n");
     141                 :            :         do
     142                 :            :         {
     143                 :          0 :                 prev = e;
     144                 :          0 :                 e = g->next[e];
     145         [ #  # ]:          0 :                 assert(e != EMPTY);
     146                 :            :         }
     147         [ #  # ]:          0 :         while (!check_edge(g, e, v1, v2));
     148                 :            : 
     149                 :          0 :         g->next[prev] = g->next[e];
     150                 :            :         //g->edges[e] = EMPTY;
     151                 :            :         DEBUGP("Deleted\n");
     152                 :            : }
     153                 :            : 
     154                 :            :         
     155                 :          0 : void graph_del_edge(graph_t *g, cmph_uint32 v1, cmph_uint32 v2)
     156                 :            : {
     157                 :          0 :         g->shrinking = 1;
     158                 :          0 :         del_edge_point(g, v1, v2);
     159                 :          0 :         del_edge_point(g, v2, v1);
     160                 :          0 : }
     161                 :            : 
     162                 :          0 : void graph_clear_edges(graph_t *g)
     163                 :            : {
     164                 :            :         cmph_uint32 i;
     165         [ #  # ]:          0 :         for (i = 0; i < g->nnodes; ++i) g->first[i] = EMPTY;
     166         [ #  # ]:          0 :         for (i = 0; i < g->nedges*2; ++i) 
     167                 :            :         {
     168                 :          0 :                 g->edges[i] = EMPTY;
     169                 :          0 :                 g->next[i] = EMPTY;
     170                 :            :         }
     171                 :          0 :         g->cedges = 0;
     172                 :          0 :         g->shrinking = 0;
     173                 :          0 : }
     174                 :            : 
     175                 :          0 : static cmph_uint8 find_degree1_edge(graph_t *g, cmph_uint32 v, cmph_uint8 *deleted, cmph_uint32 *e)
     176                 :            : {
     177                 :          0 :         cmph_uint32 edge = g->first[v];
     178                 :          0 :         cmph_uint8 found = 0;
     179                 :            :         DEBUGP("Checking degree of vertex %u\n", v);
     180         [ #  # ]:          0 :         if (edge == EMPTY) return 0;
     181         [ #  # ]:          0 :         else if (!(GETBIT(deleted, abs_edge(edge, 0)))) 
     182                 :            :         {
     183                 :          0 :                 found = 1;
     184                 :          0 :                 *e = edge;
     185                 :            :         }
     186                 :            :         while(1)
     187                 :            :         {
     188                 :          0 :                 edge = g->next[edge];
     189         [ #  # ]:          0 :                 if (edge == EMPTY) break;
     190         [ #  # ]:          0 :                 if (GETBIT(deleted, abs_edge(edge, 0))) continue;
     191         [ #  # ]:          0 :                 if (found) return 0;
     192                 :            :                 DEBUGP("Found first edge\n");
     193                 :          0 :                 *e = edge;
     194                 :          0 :                 found = 1;
     195                 :            :         }
     196                 :          0 :         return found;
     197                 :            : }
     198                 :            : 
     199                 :          0 : static void cyclic_del_edge(graph_t *g, cmph_uint32 v, cmph_uint8 *deleted)
     200                 :            : {
     201                 :            : 
     202                 :          0 :         cmph_uint32 e = 0;
     203                 :            :         cmph_uint8 degree1;
     204                 :          0 :         cmph_uint32 v1 = v;
     205                 :          0 :         cmph_uint32 v2 = 0;
     206                 :            : 
     207                 :          0 :         degree1 = find_degree1_edge(g, v1, deleted, &e);
     208         [ #  # ]:          0 :         if (!degree1) return;
     209                 :            :         while(1) 
     210                 :            :         {
     211                 :            :                 DEBUGP("Deleting edge %u (%u->%u)\n", e, g->edges[abs_edge(e, 0)], g->edges[abs_edge(e, 1)]);
     212                 :          0 :                 SETBIT(deleted, abs_edge(e, 0));
     213                 :            :                 
     214                 :          0 :                 v2 = g->edges[abs_edge(e, 0)];
     215         [ #  # ]:          0 :                 if (v2 == v1) v2 = g->edges[abs_edge(e, 1)];
     216                 :            : 
     217                 :            :                 DEBUGP("Checking if second endpoint %u has degree 1\n", v2); 
     218                 :          0 :                 degree1 = find_degree1_edge(g, v2, deleted, &e);
     219         [ #  # ]:          0 :                 if (degree1) 
     220                 :            :                 {
     221                 :            :                         DEBUGP("Inspecting vertex %u\n", v2);
     222                 :          0 :                         v1 = v2;
     223                 :            :                 }
     224                 :          0 :                 else break;
     225                 :            :         }
     226                 :            : }
     227                 :            : 
     228                 :          0 : int graph_is_cyclic(graph_t *g)
     229                 :            : {
     230                 :            :         cmph_uint32 i;
     231                 :            :         cmph_uint32 v;
     232                 :          0 :         cmph_uint8 *deleted = (cmph_uint8 *)malloc((g->nedges*sizeof(cmph_uint8))/8 + 1);
     233                 :          0 :         size_t deleted_len = g->nedges/8 + 1;
     234                 :          0 :         memset(deleted, 0, deleted_len);
     235                 :            : 
     236                 :            :         DEBUGP("Looking for cycles in graph with %u vertices and %u edges\n", g->nnodes, g->nedges);
     237         [ #  # ]:          0 :         for (v = 0; v < g->nnodes; ++v)
     238                 :            :         {
     239                 :          0 :                 cyclic_del_edge(g, v, deleted);
     240                 :            :         }
     241         [ #  # ]:          0 :         for (i = 0; i < g->nedges; ++i)
     242                 :            :         {
     243         [ #  # ]:          0 :                 if (!(GETBIT(deleted, i))) 
     244                 :            :                 {
     245                 :            :                         DEBUGP("Edge %u %u->%u was not deleted\n", i, g->edges[i], g->edges[i + g->nedges]);
     246                 :          0 :                         free(deleted);
     247                 :          0 :                         return 1;
     248                 :            :                 }
     249                 :            :         }
     250                 :          0 :         free(deleted);
     251                 :          0 :         return 0;
     252                 :            : }
     253                 :            : 
     254                 :          0 : cmph_uint8 graph_node_is_critical(graph_t * g, cmph_uint32 v) /* included -- Fabiano */
     255                 :            : {
     256                 :          0 :         return (cmph_uint8)GETBIT(g->critical_nodes,v);
     257                 :            : }
     258                 :            : 
     259                 :          0 : void graph_obtain_critical_nodes(graph_t *g) /* included -- Fabiano*/
     260                 :            : {
     261                 :            :         cmph_uint32 i;
     262                 :            :         cmph_uint32 v;
     263                 :          0 :         cmph_uint8 *deleted = (cmph_uint8 *)malloc((g->nedges*sizeof(cmph_uint8))/8+1);
     264                 :          0 :         size_t deleted_len = g->nedges/8 + 1;
     265                 :          0 :         memset(deleted, 0, deleted_len);
     266                 :          0 :         free(g->critical_nodes);
     267                 :          0 :         g->critical_nodes = (cmph_uint8 *)malloc((g->nnodes*sizeof(cmph_uint8))/8 + 1);
     268                 :          0 :         g->ncritical_nodes = 0;
     269                 :          0 :         memset(g->critical_nodes, 0, (g->nnodes*sizeof(cmph_uint8))/8 + 1);
     270                 :            :         DEBUGP("Looking for the 2-core in graph with %u vertices and %u edges\n", g->nnodes, g->nedges);
     271         [ #  # ]:          0 :         for (v = 0; v < g->nnodes; ++v)
     272                 :            :         {
     273                 :          0 :                 cyclic_del_edge(g, v, deleted);
     274                 :            :         }
     275                 :            : 
     276         [ #  # ]:          0 :         for (i = 0; i < g->nedges; ++i)
     277                 :            :         {
     278         [ #  # ]:          0 :                 if (!(GETBIT(deleted,i))) 
     279                 :            :                 {
     280                 :            :                         DEBUGP("Edge %u %u->%u belongs to the 2-core\n", i, g->edges[i], g->edges[i + g->nedges]);
     281         [ #  # ]:          0 :                         if(!(GETBIT(g->critical_nodes,g->edges[i]))) 
     282                 :            :                         {
     283                 :          0 :                           g->ncritical_nodes ++;
     284                 :          0 :                           SETBIT(g->critical_nodes,g->edges[i]);
     285                 :            :                         }
     286         [ #  # ]:          0 :                         if(!(GETBIT(g->critical_nodes,g->edges[i + g->nedges]))) 
     287                 :            :                         {
     288                 :          0 :                           g->ncritical_nodes ++;
     289                 :          0 :                           SETBIT(g->critical_nodes,g->edges[i + g->nedges]);
     290                 :            :                         }
     291                 :            :                 }
     292                 :            :         }
     293                 :          0 :         free(deleted);
     294                 :          0 : }
     295                 :            : 
     296                 :          0 : cmph_uint8 graph_contains_edge(graph_t *g, cmph_uint32 v1, cmph_uint32 v2) /* included -- Fabiano*/
     297                 :            : {
     298                 :            :         cmph_uint32 e;
     299                 :          0 :         e = g->first[v1];
     300         [ #  # ]:          0 :         if(e == EMPTY) return 0;
     301         [ #  # ]:          0 :         if (check_edge(g, e, v1, v2)) return 1;
     302                 :            :         do
     303                 :            :         {
     304                 :          0 :                 e = g->next[e];
     305         [ #  # ]:          0 :                 if(e == EMPTY) return 0;
     306                 :            :         }
     307         [ #  # ]:          0 :         while (!check_edge(g, e, v1, v2));
     308                 :          0 :         return 1;
     309                 :            : }
     310                 :            : 
     311                 :          0 : cmph_uint32 graph_vertex_id(graph_t *g, cmph_uint32 e, cmph_uint32 id) /* included -- Fabiano*/
     312                 :            : {
     313                 :          0 :   return (g->edges[e + id*g->nedges]);
     314                 :            : }
     315                 :            : 
     316                 :          0 : cmph_uint32 graph_ncritical_nodes(graph_t *g) /* included -- Fabiano*/
     317                 :            : {
     318                 :          0 :   return g->ncritical_nodes;
     319                 :            : }
     320                 :            : 
     321                 :          0 : graph_iterator_t graph_neighbors_it(graph_t *g, cmph_uint32 v)
     322                 :            : {
     323                 :            :         graph_iterator_t it;
     324                 :          0 :         it.vertex = v;
     325                 :          0 :         it.edge = g->first[v];
     326                 :          0 :         return it;
     327                 :            : }
     328                 :          0 : cmph_uint32 graph_next_neighbor(graph_t *g, graph_iterator_t* it)
     329                 :            : {
     330                 :            :         cmph_uint32 ret;
     331         [ #  # ]:          0 :         if(it->edge == EMPTY) return GRAPH_NO_NEIGHBOR; 
     332         [ #  # ]:          0 :         if (g->edges[it->edge] == it->vertex) ret = g->edges[it->edge + g->nedges];
     333                 :          0 :         else ret = g->edges[it->edge];
     334                 :          0 :         it->edge = g->next[it->edge];
     335                 :          0 :         return ret;
     336                 :            : }
     337                 :            :         
     338                 :            :