Line data    Source code

       1             : #define LAGRAPH_COLORING_RETURN_VALUES
       2             : #define LAGRAPH_COLORING_INVALID_COLORING   (-5501)
       3             : 
       4             : #include "LG_internal.h"
       5             : #include "LG_test.h"
       6             : #include "LG_Xtest.h"
       7             : 
       8             : #undef  LG_FREE_WORK
       9             : #define LG_FREE_WORK                            \
      10             : {                                               \
      11             :     LAGraph_Free ((void **) &Ap, NULL) ;        \
      12             :     LAGraph_Free ((void **) &Ai, NULL) ;        \
      13             :     LAGraph_Free ((void **) &Ax, NULL) ;        \
      14             : }
      15             : 
      16           3 : int LG_check_coloring
      17             : (
      18             :     LAGraph_Graph G,
      19             :     GrB_Vector C,
      20             :     char *msg
      21             : )
      22             : {
      23             : #if LAGRAPH_SUITESPARSE
      24             :     // ------------------------------------------------
      25             :     // check if coloring is valid
      26             :     // ------------------------------------------------
      27             : 
      28             :     /* extract graph in CSC form
      29             :     *  CSC form:
      30             :     *  Ap: start and end indices of Ai that represent a column of A
      31             :     *  Ai: values that represent the row indices of A where there is a value
      32             :     *       - in our case, these are the neighbors' IDs
      33             :     *  Ax: the values of that edge, stored in the same order as Ai
      34             :     *       - in our case, all values are 1
      35             :     *  note: CSC is same as CSR for undirected graphs
      36             :     *        maybe use the one that's more efficient
      37             :     *        ( prevent converting from one to other )
      38             :     *
      39             :     *  convert Ap_size from bytes to indices
      40             :     *   - make sure to loop only up to Ap_size - 1
      41             :     *     when checking [Ap_index] to [Ap_index + 1]
      42             :     * 
      43             :     *  traverse through unpacked matrix and
      44             :     *  check current node's color against its neighbors
      45             :     *   - Ap_index: current node
      46             :     *   - Ai_index: a neighbor
      47             :     */
      48             :    
      49           3 :     GrB_Index *Ap = NULL;
      50           3 :     GrB_Index *Ai = NULL;
      51           3 :     void *Ax = NULL;
      52             :     GrB_Index Ap_size, Ai_size, Ax_size;
      53           3 :     GRB_TRY(GxB_Matrix_unpack_CSC(G->A, &Ap, &Ai, &Ax, &Ap_size, &Ai_size, &Ax_size, NULL, NULL, NULL));
      54             :     
      55           3 :     Ap_size = Ap_size / sizeof(GrB_Index);
      56             : 
      57             :     GrB_Index Ap_index;
      58             :     GrB_Index Ai_index;
      59             :     GrB_Index Ai_index_start, Ai_index_end;
      60             : 
      61          21 :     for (GrB_Index i = 0; i < Ap_size - 1; i++) {
      62             :         int color;
      63          19 :         if (GrB_Vector_extractElement(&color, C, i) != GrB_SUCCESS) {
      64           1 :             printf("error: node %" PRIu64 " has no assigned color!\n", i);
      65           1 :             return -1;
      66             :         }
      67             :     }
      68             : 
      69             :     int current_color, neighbor_color;
      70          20 :     for (Ap_index = 0; Ap_index < Ap_size - 1; Ap_index++) {
      71             :         
      72          18 :         Ai_index_start = Ap[Ap_index];
      73          18 :         Ai_index_end = Ap[Ap_index + 1];
      74             : 
      75          18 :         GRB_TRY(GrB_Vector_extractElement(&current_color, C, Ap_index));
      76             : 
      77          66 :         for (Ai_index = Ai_index_start; Ai_index < Ai_index_end; Ai_index++) {
      78             : 
      79             :             // skip self-edges
      80          48 :             if (Ai[Ai_index] != Ap_index) {
      81          48 :                 GRB_TRY(GrB_Vector_extractElement(&neighbor_color, C, Ai[Ai_index]));
      82          48 :                 LG_ASSERT_MSG(neighbor_color != current_color, LAGRAPH_COLORING_INVALID_COLORING, "found 2 connected nodes with the same color");
      83             :             }
      84             :         }
      85             :     }
      86             : 
      87           2 :     LG_FREE_WORK;
      88           2 :     return (GrB_SUCCESS);
      89             : #else
      90             :     return (GrB_NOT_IMPLEMENTED) ;
      91             : #endif
      92             : }