Problem statement: Given an undirected graph E. Build a C++ program to color it using greedy algorithm. You will read input from the file "graph.txt", the first line contains the total number of nodes n and the total number of edges m, each of the (m+1) line contains two positive integers representing an edge. The result should be printed out to the file "coloredgraph.dot", which represents the colored graph in DOT language. (Nodes are indexed from 1 to n)
For example:
Input:
5 5
1 2
2 3
3 4
4 1
1 5
Output:
graph E
{
5 [fillcolor=red, style=filled];
4 [fillcolor=red, style=filled];
1 [fillcolor=green, style=filled];
3 [fillcolor=green, style=filled];
2 [fillcolor=red, style=filled];
1 -- 2;
2 -- 3;
3 -- 4;
4 -- 1;
1 -- 5;
}
I built a C++ program to color the graph and then stored the result in array color[] (in which color[i-1] is the color of nodes i). For example, from the input above, i got the result color[] = {0, 1, 0, 1, 1} (I used number 0 -> n-1 to represent colors. These numbers could represent any colour available in DOT/Graphviz, different numbers mean different colours. In this case, 0 could mean black/white/etc and 1 could mean green/blue/etc, but 1 and 0 have to represent two different colours). But i'm currently stuck at how the result that i found could be converted to a .dot file with the format as required above. I'm just a beginner in C++ and i have no prior experience with DOT or Graphviz. Could anyone help me to print the output as required, using the result that I found? Many thanks for any advice.
Greedy algorithm implementation can be found here: https://www.geeksforgeeks.org/graph-coloring-set-2-greedy-algorithm/
P/s : Sorry for my bad English
You can print the file with:
std::cout << "graph E\n{\n";
for (std::size_t i = 0; i < nodes; ++i) {
std::cout << (i+1) << "[fillcolor=" << color[i] << ", style=filled];\n";
}
for (std::size_t i = 0; i < edges.size(); ++i) {
std::cout << edges[i][0] << " -- " << edges[i][1] << ";\n";
}
std::cout << "}\n";