Graph Coloring

Consider an undirected graph G = {V , E}. A vertex coloring of G is an assignment of colors to the vertices of G such that adjacent vertices have different colors. G is said to be n-colorable if there exists a coloring of G which uses n colors.

A link to my .out file.

Objective

Given a graph G, color it using the Welch-Powell Algorithm.

The Welch-Powell Algorithm below was taken from directly fromSchaum's Outlines, Discrete Mathematics, , third edition, Seymour Lipschutz and Marc Lipson:

Degree of a node: The number of edges into/out of the node.

    The input is a graph G
  1. Order the vertices of G according to decreasing degrees.
  2. Assign the first color C1 to the first vertex and then, in sequential order, assign C1 to each vertex which is not adjacent to a previous vertex which was assigned C1.
  3. Repeat Step 2 with a second color C2 and the subsequence of noncolored vertices.
  4. Repeat Step 3 with a third color C3, then a fourth color C4, and so on until all vertices are colored.
  5. Exit

To Do

Create an undirected graph object that colors the graph using the Welch-Powell Algorithm, prints the color of each node, and prints the number of colors.

The files to be created:

Public Member Functions

You must create the following public member functions:

You will also need several private member functions

Constructor


The graph is to be implemented with an adjacency list.
Your .h file should have:
typedef int nodetype;
A nodes in the adjacency list should be implemented:
struct node {
nodetype name;
node *next;
};
Your .h file will also need to have:
struct inDegree{
nodetype nodename;
int indegreeOfNode;
};
The number of nodes in the graph and the edges of the graph will be read in from a file.

Your constructor must first prompt the user for the name of the file and open the file. cassert should be used to ensure the file opened properly.

Your program can assume the file contains all integer data.

Read n in from the file - the number of nodes in the graph.


The names of the nodes will be 0 through n-1. Dynamically allocate an array of n pointers to nodes. Set each entry in the array to NULL.
An array of size n of type inDegree must be dynamically allocated to represent the degrees of each node. The array should be initialized with the node names 0-n-1 and indegree of 0.
You must also dynamically an array of ints of size n to store the color of each node. The constructor should initialize this array to uncolored.
Your program can assume all of the remaining data in the file is in pairs - edges in the graph.

Go into a loop reading pairs of nodes representing an edge from the file. When an "end of file condition" occurs, exit the loop.

The first node in the edge, n1, and then the second node in the edge, n2. Allocate a node to represent the edge, storing n2 in the name of the newly created node. Enter the newly created node into n1's adjacency list.

if (adj[n1] == NULL)

adj[n1] = pointer to newly created node

else

{

newly created node->next = adj[n1];

adj[n1] = newly created node;

}

Since the graph is undirected, you must also repeat the same process, allocating another node to represent the edge storing n1 as the node name and place it into n2's adjacency list.

Increment the indegree for both nodes in the inDegree array.

Upon completion of processing the input file:

Colorit

Colorit must return the number of colors

You must implement a private, stable sorting function that will be called by Colorit.

What is a stable sorting function?

Sort the indegree array and display the sorted array.

Color the graph

The initial color is 1. Each time a pass of the color algorithm is completed, the color must be incremented

Using the Welch-Powell algorithm, color the graph. The colors for each node are placed in the color array allocated and initialized by the constructor.

The function should return the number of colors (likely the currentcolor-1)

Printcolor

Print the color array

Destructor

Destroy all dynamically allocated memory

assigncolor.cpp

Your main program should

  1. Declare a graph object
  2. Color the graph
  3. Print the number of colors in the graph
  4. Print the coloring
This page is maintained by Barbara Bracken Last Modified 9/4/2017