EE 607 Spring 2006
Project 3
Due April 14, 2006 (friday), 10 points
Write a program that has
Input: A bipartite
multigraph, i.e., a pair of nodes can have multiple edges between
them. Since the multigraph is bipartite, the nodes are
partitioned into two sets L and R, where the nodes in L are {L1, L2,
...., Lm} and the nodes in R are {R1, R2,...., Rn}.
Output: A link coloring
that uses the minimum number of colors. The colors are the
integers 1, 2, ....
The input will be a text file with the following format. The
first line indicates the number of nodes m and n in the multigraph.
The next set of lines describes the node pairs with edges
between. The first of the lines has the number of node
pairs. Each subsequent line is for a node pair. A line with
the values x
y w implies that the node pair (Lx, Ry) has w edges between them.
The output will be a display on the console. The first line will
be "Number of colors =" followed by the number of colors required
(i.e., the makespan or degree of the multigraph). The next line
will be "Node pairs with color 1", followed by the list of node pairs
that have edges with color 1. After this, will be a line with
"Node pairs with color 2", followed by the list of node pairs that have
edges with color 2, and so forth.
The executable should be labeled "linkColor607". It has one
argument, which is the name of the input file with the mulitgraph
information. It then displays its output.
Example : Suppose we have
a text file labeled "colorTest":
3 2
5
1
1 1
2
1 1
2
2 1
3
1 1
3
2 2
For an example, click here.
Then after typing
linkColor607
colorTest.txt
The output may look like the following (note that the solution is not
unique, so your program may have a different and correct solution)
Number of
colors = 3
Node pairs
with color 1
1 1
3 2
Node pairs
with color 2
2 1
3 2
Node pairs
with color 3
2 2
3 1
What to turn in. Have
your program be executable on spectra.eng.hawaii.edu Put your
source code and makefile in a directory in spectra. Make sure
that your makefile will compile the code and create the excecutable
"linkColor607". Tar and gzip the directory on spectra.
Then email the gzipped file to me with the email header "EE 607 Project
4".