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             :     GrB_free (&local_color) ;       \
       7             :     GrB_free (&weight) ;            \
       8             :     GrB_free (&in_curr_subset) ;    \
       9             :     GrB_free (&max_weights) ;
      10             : 
      11             : #undef  LG_FREE_ALL
      12             : #define LG_FREE_ALL                 \
      13             :     LG_FREE_WORK ;
      14             : 
      15           2 : int LAGraph_coloring_independent_set
      16             : (
      17             :     // output
      18             :     GrB_Vector *color,
      19             :     int *num_colors,
      20             : 
      21             :     // input
      22             :     LAGraph_Graph G,
      23             :     char *msg
      24             : )
      25             : {
      26             : #if LAGRAPH_SUITESPARSE
      27             : 
      28           2 :     bool verbose = false;
      29           2 :     GrB_Vector local_color = NULL;
      30           2 :     GrB_Vector weight = NULL;
      31           2 :     GrB_Vector in_curr_subset = NULL;
      32           2 :     GrB_Vector max_weights = NULL;
      33             : 
      34             :     GrB_Index n;
      35           2 :     GRB_TRY (GrB_Matrix_nrows(&n, G->A)) ;
      36             : 
      37           2 :     GrB_Type Int = (n < UINT32_MAX) ? GrB_UINT32 : GrB_UINT64 ;
      38             : 
      39             :     /* initialize local copy of color to SPARSE vector */
      40           2 :     GRB_TRY(GrB_Vector_new(&local_color, Int, n));
      41             : 
      42             :     // lg_set_format_hint -> bitmap
      43           2 :     GRB_TRY (LG_SET_FORMAT_HINT (local_color, LG_BITMAP)) ;
      44             : 
      45             :     /* weights initialized randomly
      46             :     *  seed of 20 was chosen arbitrarily */   
      47           2 :     GRB_TRY(GrB_Vector_new(&weight, GrB_UINT64, n));
      48           2 :     GRB_TRY(GrB_assign (weight, NULL, NULL, 0, GrB_ALL, n, NULL));
      49             : 
      50             :     // LG_TRY(LAGraph_Random_Seed(weight, 2, msg));
      51           2 :     LG_TRY (LAGraph_Random_Seed(weight, 20, msg)) ;
      52             : 
      53           2 :     GRB_TRY(GrB_Vector_new(&in_curr_subset, GrB_BOOL, n));
      54             : 
      55           2 :     GRB_TRY(GrB_Vector_new(&max_weights, GrB_UINT64, n));
      56           2 :     double tlast = LAGraph_WallClockTime ( ) ;
      57           2 :     double tnow = 0 ;
      58           2 :     LG_SET_BURBLE(true) ;
      59             : 
      60             :     /* algorithm start */
      61             :     int64_t curr_color;
      62           7 :     for (curr_color = 1; curr_color < n+1; curr_color++) {
      63             :         /* mxv - find maximum of all neighboring weights */
      64             : 
      65             :         // FUTURE WORK: try using a set of sparse candidate nodes, not yet colored
      66           8 :         GRB_TRY(GrB_mxv(max_weights, local_color, GrB_NULL,
      67             :             GrB_MAX_SECOND_SEMIRING_UINT64, G->A, weight, GrB_DESC_RSC));
      68             : 
      69             :         /* eWiseAdd - 1 if current weight > max neighboring weight */
      70           7 :         GRB_TRY(GrB_eWiseMult(in_curr_subset, GrB_NULL, GrB_NULL, GrB_GT_UINT64, weight, max_weights, GrB_NULL));
      71             : 
      72             :         /* select - select all entries in in_curr_subset that are true, and delete falses */
      73           7 :         GRB_TRY(GrB_select(in_curr_subset, GrB_NULL, GrB_NULL, GrB_VALUEEQ_BOOL, in_curr_subset, true, GrB_NULL));
      74           7 :         tnow = LAGraph_WallClockTime ( ) ;
      75           7 :         double tthis = tnow - tlast ;
      76           7 :         tlast = tnow ;
      77             : 
      78             :         GrB_Index nvals_local_color;
      79           7 :         GRB_TRY(GrB_Vector_nvals(&nvals_local_color, local_color));
      80             : 
      81             :         /* check if in_curr_subset is empty then break */
      82             :         GrB_Index nvals_in_curr_subset;
      83           7 :         GRB_TRY(GrB_Vector_nvals(&nvals_in_curr_subset, in_curr_subset));
      84           7 :         if (nvals_in_curr_subset == 0) { 
      85             :             GrB_Index nvals_local_color;
      86           3 :             GRB_TRY(GrB_Vector_nvals(&nvals_local_color, local_color));
      87           2 :             if (nvals_local_color < n) {
      88           1 :                 LG_ASSERT_MSG (false, LAGRAPH_CONVERGENCE_FAILURE,
      89             :                     "LAGraph_coloring_independent_set: in_curr_subset is empty, but nvals (local_color) < n") ;
      90             :             }
      91           1 :             break;
      92             :         }
      93             : 
      94             :         /* assign - write current color to C vector according to in_curr_subset mask */
      95           5 :         GRB_TRY(GrB_assign(local_color, in_curr_subset, GrB_NULL, curr_color, GrB_ALL, n, GrB_DESC_S));
      96             :         
      97             :         /* assign - write 0 to weight according to in_curr_subset mask */
      98           5 :         GRB_TRY(GrB_assign(weight, in_curr_subset, GrB_NULL, 0, GrB_ALL, n, GrB_DESC_S));
      99             :     }
     100             :     
     101           1 :     LG_SET_BURBLE(false) ;
     102             : 
     103           1 :     (*num_colors) = curr_color - 1;
     104           1 :     (*color) = local_color;
     105           1 :     local_color = NULL ;
     106           1 :     LG_FREE_ALL ;
     107           1 :     return (GrB_SUCCESS) ;
     108             : #else
     109             :     return (GrB_NOT_IMPLEMENTED) ;
     110             : #endif
     111             : }