Line data Source code
1 : #include <stdio.h> // ?
2 : #include "LG_internal.h" // ?
3 : #include "LAGraph_test.h" // for TEST_CHECK
4 : #include "LAGraphX.h" // for LAGraph_coloring_independent_set
5 : #include "LG_Xtest.h" // for LG_check_coloring
6 :
7 :
8 : char msg[LAGRAPH_MSG_LEN];
9 : LAGraph_Graph G = NULL;
10 :
11 : #define LEN 512
12 : char filename[LEN + 1];
13 :
14 : const char* matrix_files[] = {
15 : "ldbc-undirected-example-unweighted.mtx",
16 : };
17 :
18 1 : void test_coloring(void)
19 : {
20 : #if LAGRAPH_SUITESPARSE
21 : // ------------------------------------------------
22 : // setup
23 : // ------------------------------------------------
24 :
25 : /* required initialization */
26 1 : LAGraph_Init(msg);
27 1 : LG_Random_Init(msg);
28 :
29 : /* initializing A (matrix) and C (color vector) */
30 1 : GrB_Matrix A = NULL;
31 1 : GrB_Vector C = NULL;
32 :
33 : /* open matrix market file */
34 1 : snprintf(filename, LEN, LG_DATA_DIR "%s", "ldbc-undirected-example-unweighted.mtx");
35 1 : FILE *f = fopen(filename, "r");
36 1 : TEST_CHECK(f != NULL);
37 1 : OK(LAGraph_MMRead(&A, f, msg));
38 1 : OK(fclose(f));
39 1 : OK(LAGraph_New(&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg));
40 1 : TEST_CHECK(A == NULL); // A has been moved into G->A
41 :
42 : // ------------------------------------------------
43 : // run algorithm independent set
44 : // ------------------------------------------------
45 :
46 : // OK (LG_SET_BURBLE (false)) ;
47 :
48 1 : int num_colors = 0;
49 1 : double time = LAGraph_WallClockTime();
50 1 : LAGraph_coloring_independent_set(&C, &num_colors, G, msg);
51 1 : time = LAGraph_WallClockTime() - time;
52 :
53 1 : OK (LG_SET_BURBLE (false)) ;
54 :
55 1 : printf("\nTook %g seconds\n", time);
56 1 : printf("Initial Matrix:\n"); LAGraph_Matrix_Print(G->A, LAGraph_SHORT, stdout, msg);
57 1 : printf("Final color vector:\n"); LAGraph_Vector_Print(C, LAGraph_SHORT, stdout, msg);
58 :
59 :
60 : // ------------------------------------------------
61 : // check if coloring is valid
62 : // ------------------------------------------------
63 :
64 1 : OK (LG_check_coloring(G, C, msg));
65 1 : printf("Number of Colors: %d\n", num_colors);
66 :
67 : // induce no assigned color error
68 : #if defined ( COVERAGE )
69 1 : GrB_free(&C);
70 1 : C = NULL;
71 1 : LAGraph_Delete(&G, msg);
72 1 : snprintf(filename, LEN, LG_DATA_DIR "%s", "ldbc-undirected-example-unweighted.mtx");
73 1 : f = fopen(filename, "r");
74 1 : TEST_CHECK(f != NULL);
75 1 : OK(LAGraph_MMRead(&A, f, msg));
76 1 : OK(fclose(f));
77 1 : OK(LAGraph_New(&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg));
78 1 : TEST_CHECK(A == NULL); // A has been moved into G->A
79 :
80 : GrB_Vector C_dummy;
81 1 : GrB_Vector_new (&C_dummy, GrB_UINT64, 1);
82 1 : int check_coloring_result = LG_check_coloring(G, C, msg);
83 1 : TEST_CHECK (check_coloring_result == -1);
84 : #endif
85 :
86 : // ------------------------------------------------
87 : // run algorithm independent set with hack
88 : // ------------------------------------------------
89 :
90 : // hack the random number generator to induce an error condition
91 : #if defined ( COVERAGE )
92 1 : GrB_free(&C);
93 1 : C = NULL;
94 1 : LAGraph_Delete(&G, msg);
95 1 : snprintf(filename, LEN, LG_DATA_DIR "%s", "ldbc-undirected-example-unweighted.mtx");
96 1 : f = fopen(filename, "r");
97 1 : TEST_CHECK(f != NULL);
98 1 : OK(LAGraph_MMRead(&A, f, msg));
99 1 : OK(fclose(f));
100 1 : OK(LAGraph_New(&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg));
101 1 : TEST_CHECK(A == NULL); // A has been moved into G->A
102 :
103 1 : printf ("Hack the random number generator to induce a stall:\n") ;
104 1 : random_hack = true ;
105 1 : int result = LAGraph_coloring_independent_set(&C, &num_colors, G, msg);
106 1 : random_hack = false ;
107 1 : printf ("hack msg: %d %s\n", result, msg) ;
108 1 : TEST_CHECK (result == LAGRAPH_CONVERGENCE_FAILURE) ;
109 : #endif
110 :
111 : // ------------------------------------------------
112 : // run algorithm maximal independent set
113 : // ------------------------------------------------
114 :
115 1 : GrB_free(&C);
116 1 : C = NULL;
117 1 : LAGraph_Delete(&G, msg);
118 :
119 : /* open matrix market file */
120 1 : snprintf(filename, LEN, LG_DATA_DIR "%s", "ldbc-undirected-example-unweighted.mtx");
121 1 : f = fopen(filename, "r");
122 1 : TEST_CHECK(f != NULL);
123 1 : OK(LAGraph_MMRead(&A, f, msg));
124 1 : OK(fclose(f));
125 1 : OK(LAGraph_New(&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg));
126 1 : TEST_CHECK(A == NULL); // A has been moved into G->A
127 :
128 1 : printf("Initial Matrix:\n"); LAGraph_Matrix_Print(G->A, LAGraph_SHORT, stdout, msg);
129 :
130 1 : num_colors = 0;
131 1 : time = LAGraph_WallClockTime();
132 1 : LAGraph_coloring_MIS(&C, &num_colors, G, msg);
133 1 : time = LAGraph_WallClockTime() - time;
134 :
135 1 : OK (LG_SET_BURBLE (false)) ;
136 :
137 1 : printf("\nTook %g seconds\n", time);
138 :
139 1 : printf("Final color vector:\n"); LAGraph_Vector_Print(C, LAGraph_SHORT, stdout, msg);
140 :
141 :
142 : // ------------------------------------------------
143 : // check if coloring is valid
144 : // ------------------------------------------------
145 :
146 1 : OK (LG_check_coloring(G, C, msg));
147 1 : printf("Number of Colors: %d\n", num_colors);
148 :
149 :
150 : /* clean up (don't understand this) */
151 1 : OK(LAGraph_Delete(&G, msg));
152 1 : LAGraph_Finalize(msg);
153 1 : LG_Random_Finalize(msg);
154 : #endif
155 1 : }
156 :
157 : TEST_LIST =
158 : {
159 : {"coloring", test_coloring},
160 : {NULL, NULL}
161 : };
|