Line data    Source code

       1             : #include "LG_internal.h" // contains all internal grb operations
       2             : #include "LAGraphX.h"    // algorithm added to LAGraphX.h
       3             : 
       4             : #undef  LG_FREE_WORK
       5             : #define LG_FREE_WORK                \
       6             : {                                   \
       7             :     GrB_free (&local_color) ;       \
       8             :     GrB_free (&curr_MIS) ;          \
       9             : }
      10             : 
      11             : #undef  LG_FREE_ALL
      12             : #define LG_FREE_ALL                 \
      13             : {                                   \
      14             :     LG_FREE_WORK ;                  \
      15             : }
      16             : 
      17           1 : int LAGraph_coloring_MIS
      18             : (
      19             :     // output
      20             :     GrB_Vector *color,
      21             :     int *num_colors,
      22             : 
      23             :     // input
      24             :     LAGraph_Graph G,
      25             :     char *msg
      26             : )
      27             : {
      28           1 :     bool verbose = false;
      29           1 :     GrB_Vector local_color = NULL;
      30           1 :     GrB_Vector curr_MIS = NULL;
      31             :     GrB_Index n;
      32           1 :     GRB_TRY (GrB_Matrix_nrows(&n, G->A)) ;
      33             : 
      34           1 :     GrB_Type Int = (n < UINT32_MAX) ? GrB_UINT32 : GrB_UINT64 ;
      35             : 
      36             :     /* initialize local copy of color to SPARSE vector */
      37           1 :     GRB_TRY(GrB_Vector_new(&local_color, Int, n));
      38             : 
      39           1 :     LAGRAPH_TRY(LAGraph_DeleteSelfEdges(G, msg)) ;
      40           1 :     LAGRAPH_TRY(LAGraph_Cached_OutDegree(G, msg)) ;    
      41             : 
      42             :     /* algorithm start */
      43             :     GrB_Index colored_nodes;
      44             :     int64_t curr_color;
      45           3 :     for (curr_color = 1; curr_color < n+1; curr_color++) {
      46             : 
      47             :         /* compute MIS for current color */
      48           3 :         LAGRAPH_TRY(LAGraph_MaximalIndependentSet(&curr_MIS, G, 20, local_color, msg));
      49             : 
      50             :         /* assign - write current color to C vector according to in_curr_subset mask */
      51           3 :         GRB_TRY(GrB_assign(local_color, curr_MIS, GrB_NULL, curr_color, GrB_ALL, n, GrB_DESC_S));
      52             : 
      53           3 :         GrB_Vector_nvals(&colored_nodes, local_color);
      54           3 :         if (colored_nodes == n) {
      55           1 :             break;
      56             :         }
      57             : 
      58             :     }
      59             :     
      60           1 :     (*num_colors) = curr_color;
      61           1 :     (*color) = local_color;
      62           1 :     local_color = NULL ;
      63           1 :     LG_FREE_ALL ;
      64           1 :     return (GrB_SUCCESS) ;
      65             : }