1 /*--------------------------------------------------------------------------------------------------
2 DataDraw is a CASE tool for generating data structures in C from simple descriptions.
3 --------------------------------------------------------------------------------------------------*/
4 #include <stdlib.h>
5 #include <string.h>
6 #include "graph.h"
7 #include "codatabase.h"
8
9 #define NUM_RAND_NODES 40000
10 #define NUM_RAND_EDGES 100000
11
12 /*--------------------------------------------------------------------------------------------------
13 Just see if a color has been used by a neighbor.
14 --------------------------------------------------------------------------------------------------*/
createLargeRandomGraph(void)15 static void createLargeRandomGraph(void)
16 {
17 grGraph graph = grGraphCreate(utSymCreate("RandGraph"));
18 grNode node, fromNode, toNode;
19 grNodeArray nodes = grNodeArrayAlloc();
20 int32 xNode, xEdge, xRandFrom, xRandTo;
21
22 srand(42);
23 for(xNode = 0; xNode < NUM_RAND_NODES; xNode++) {
24 node = grNodeCreate(graph, utSymCreateFormatted("N%u", xNode));
25 grNodeArrayAppendNode(nodes, node);
26 }
27 for(xEdge = 0; xEdge < NUM_RAND_EDGES; xEdge++) {
28 xRandFrom = rand() % NUM_RAND_NODES;
29 xRandTo = rand() % NUM_RAND_NODES;
30 fromNode = grNodeArrayGetiNode(nodes, xRandFrom);
31 toNode = grNodeArrayGetiNode(nodes, xRandTo);
32 grEdgeCreate(fromNode, toNode);
33 }
34 grNodeArrayFree(nodes);
35 }
36
37 /*--------------------------------------------------------------------------------------------------
38 Just see if a color has been used by a neighbor.
39 --------------------------------------------------------------------------------------------------*/
colorAlreadyUsed(grNode node,uint32 color)40 static bool colorAlreadyUsed(
41 grNode node,
42 uint32 color)
43 {
44 grNode otherNode;
45 grEdge edge;
46
47 grForeachNodeEdge(node, edge) {
48 otherNode = grEdgeFindOtherNode(edge, node);
49 if(coNodeColored(otherNode) && coNodeGetColor(otherNode) == color) {
50 return true;
51 }
52 } grEndNodeEdge;
53 return false;
54 }
55
56 /*--------------------------------------------------------------------------------------------------
57 Just find a color that has not yet been used to color adjacent nodes. It's a dumb N^2 loop.
58 --------------------------------------------------------------------------------------------------*/
findUnusedColor(grNode node)59 static uint32 findUnusedColor(
60 grNode node)
61 {
62 grGraph graph = grNodeGetGraph(node);
63 uint32 color;
64
65 for(color = 0; color < coGraphGetNumColors(graph); color++) {
66 if(!colorAlreadyUsed(node, color)) {
67 return color;
68 }
69 }
70 return 0;
71 }
72
73 /*--------------------------------------------------------------------------------------------------
74 This is a lame attempt to color the graph with a stupid greedy algorithm: just pick an unused
75 color, and if none exist, color a node 0.
76 --------------------------------------------------------------------------------------------------*/
colorGraph(grGraph graph)77 static void colorGraph(
78 grGraph graph)
79 {
80 grNode node;
81 uint32 unusedColor;
82
83 grForeachGraphNode(graph, node) {
84 unusedColor = findUnusedColor(node);
85 coNodeSetColor(node, unusedColor);
86 coNodeSetColored(node, true);
87 } grEndGraphNode;
88 }
89
90 /*--------------------------------------------------------------------------------------------------
91 Write out a colored graph.
92 --------------------------------------------------------------------------------------------------*/
writeGraph(grGraph graph)93 static void writeGraph(
94 grGraph graph)
95 {
96 grNode node;
97
98 grForeachGraphNode(graph, node) {
99 printf("Node %s color %u\n", grNodeGetName(node), coNodeGetColor(node));
100 } grEndGraphNode;
101 }
102
103 /*--------------------------------------------------------------------------------------------------
104 This is the actual main routine.
105 --------------------------------------------------------------------------------------------------*/
main(int argc,char ** argv)106 int main(
107 int argc,
108 char **argv)
109 {
110 grGraph graph;
111 uint32 numColors;
112 bool runManager = false;
113 uint32 colorsArg = 1;
114 uint32 fileArg = 2;
115
116 if(argc < 3 || (argc == 4 && strcmp(argv[1], "-m")) || argc > 4) {
117 printf("Usage: %s [-m] <colors> command.txt\n"
118 " -m - this option starts the database manager after coloring.\n"
119 " This will graph commands to build a graph, and then color it.\n",
120 argv[0]);
121 exit(1);
122 }
123 if(argc == 4) {
124 runManager = true;
125 colorsArg = 2;
126 fileArg = 3;
127 }
128 numColors = atoi(argv[colorsArg]);
129 utStart();
130 grStart();
131 createLargeRandomGraph(); /* Just so we have a reason to use a sparse extension */
132 grCommandInterpreter(argv[fileArg]); /* Read in a small graph from command line */
133 graph = grRootGetLastGraph(grTheRoot); /* Last graph will be the last one created */
134 if(graph == grGraphNull) {
135 utExit("No graph to color!");
136 }
137 coDatabaseStart(); /* This extends all the graph and node objects with extra fields */
138 coGraphSetNumColors(graph, numColors);
139 colorGraph(graph);
140 writeGraph(graph);
141 if(runManager) {
142 utManager();
143 }
144 coDatabaseStop();
145 grStop();
146 utStop(true);
147 return 0;
148 }
149