| Posted By: dxfist |
4/18/2007 11:33:00 PM |
|
| |
I need help on this edge coloring program.
/*
Problem A): Given an undirected graph bool W[][] (as above), the graph coloring problem is to determine the minimum number of colors needed to color the vertices of the graph so that no two adjacent vertices (vertices with an edge between them) are colored the same color. The greedy algorithm starts with color 1, and goes through the vertices in order, coloring as many of them as possible with color 1. When this is done, we go to color 2 and color in order as many as possible. We keep going until all vertices are colored.
Write this function: int GreedyColor(int n, bool W[ ][ ], int vcolor[ ])
which returns the number of colors this greedy algorithm arrives at for graph W, and sets array vcolor to the coloring that it finds. Write a program that can reads the value of n and a graph W from a file and then calls GreedyColor with this graph. Output your results. (For graphs of size 20 or larger, do not printout the colorings, just how many it took—you can delete these from your output file before printing.) WHAT IS THE RUNNING TIME OF YOUR PROGRAM, IN TERMS OF n?
Sample input: (Note, the 8 vertex graph is the one we did in class)
4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
8
0 1 0 0 0 0 0 1
1 0 1 1 0 0 1 1
0 1 0 1 0 0 0 0
0 1 1 0 1 0 1 0
0 0 0 1 0 1 1 0
0 0 0 0 1 0 1 0
0 1 0 1 1 1 0 1
1 1 0 0 0 0 1 0
Sample output:
Graph # 1: This 4-vertex graph greedily colored with 1 color:
vcolor[1] = 1
vcolor[2] = 1
vcolor[3] = 1
vcolor[4] = 1
Graph # 2: This 8-vertex graph greedily colored with 4 colors:
vcolor[1] = 1
vcolor[2] = 2
vcolor[3] = 1
vcolor[4] = 3
vcolor[5] = 1
vcolor[6] = 2
vcolor[7] = 4
vcolor[8] = 3
Problem B): Implement the functions:
void m_coloring(int i, int n, int m, int W[MAX][MAX],
int vcolor[], bool & solutionFound)
{
}
bool promising(int i, int vcolor[], int W[MAX][MAX])
{
}
Change the implementation from the book so that only the first solution found is printed out, and once this solution is found, the recursion is aborted as soon as possible. You may not use the exit( ) function to do this, as you will want the program to keep running. You will need to add conditions that will allow the functions to backtrack immediately to the top level and out.
Use these functions within a loop to find the fewest number of colors needed to color the graphs given in the file “graphs.txt”. Modify the greedy_template.cpp file to get started.
Once you read in an n and a graph W, use the m_coloring function with m = 1. If no solution is found, call m_coloring again with m = 2. Keep trying higher values of m until a solution is found. State how many colors is optimal and print out one solution. Then your function m_coloring will stop processing this graph and no more solutions for this graph will be printed. Then move on to reading the next graph, until there are no more graphs.
Use as your input file: “graphs2.txt”. It took mine about 5 minutes to run. Don’t use “graphs.txt” with the 100-vertex graph. For graphs of size 20 or more, do not output the coloring, as in the first problem.
Sample Output: (Sample input same as problem A).
Graph # 1: Optimal number of colors for this 4-vertex graph is: 1.
vcolor[1] = 1
vcolor[2] = 1
vcolor[3] = 1
vcolor[4] = 1
Graph # 2: Optimal number of colors for this 8-vertex graph is: 3.
vcolor[1] = 1
vcolor[2] = 2
vcolor[3] = 1
vcolor[4] = 3
vcolor[5] = 2
vcolor[6] = 3
vcolor[7] = 1
vcolor[8] = 3
*/
Code:
#include
#include
#include
using namespace std;
ofstream outData; // Global--bad style; should pass it everywhere.
void output_matrix(int n, int Matrix[MAX][MAX])
{
int row, col;
outData
for (col = 1; col
outData
|
|