完成无向图用最少的颜色着色,即相邻点的颜色不一致,要提交GraphColoring.py和graph.py两个模块。
下面是我写的GraphColoring.py的源代码：
import os
import sys
from graph import *
def CheckProperColoring(G):
"""
如果相邻的两个点颜色一样,返回真,否则返回假.
"""
flag = True
for v in G._color: # 对于每一个着色的点
for node in G.d[v]: # 当前节点的每个相邻点
if G.getColor(v) == G.getColor(node): # v点和相邻点颜色一致,则着色有一样的,着色方案错误!
flag = False
break
return flag
def main():
p = sys.argv
if len(p)<3:
print("Usage: $ python3 GraphColoring.py
graph.py的源代码，需要的联系本人，价格600元。
以下是作业要求详情:
1
CSE 30
Programming Abstractions: Python
Programming Assignment 6
In this project you will solve (approximately) the Graph Coloring (GC) problem discussed in class. Given
a graph ??, determine an assignment of colors from the set {1, 2, 3, … , ??} to the vertices of ?? so that no two
adjacent vertices are assigned the same color. Further, try to reduce the size ?? of the color set as far as
possible. Such an assignment is called a ??-coloring of ??, and ?? is said to be ??-colorable. The smallest ??
for which ?? is ??-colorable is called the chromatic number of ??, and is denoted ??(??). Any graph with ??
vertices is necessarily ??-colorable (just assign each vertex its own color). Therefore, any solution the GC
problem is expected to satisfy ??(??) ≤ ?? ≤ ??. However, for a general graph ??, the value ??(??) may not be
known, so in solving GC, one is left not knowing what value of ?? is the minimum. Indeed, this is the
difficulty.
Let us pause a moment and think about how we might solve this minimization problem exactly, i.e. find a
??-coloring with ?? = ??(??). An assignment of colors from {1, 2, 3, … , ??} to ??(??) = {1, 2, 3, … …, ??}, is
nothing but a mapping ??: {1, 2, 3, … … , ??} → {1, 2, 3, … , ??}. How many such mappings are there? This is
a counting problem right out of Discrete Mathematics (CSE 16). There are ?? ways to choose the color
??(1), then ?? ways to choose the color ??(2), then ?? ways to choose ??(3), …, and finally ?? ways to choose
??(??). Altogether, the number of ways of making these choices in succession is:
??��⋅ ??��⋅ �?? �⋅ ⋯��⋅�??
??
= ????
Therefore, the number of ??-color assignments to ??(??) is ????. Of course, not all of these mappings represent
proper ??-colorings, since adjacent vertices may be assigned the same color. Indeed, if ?? < ??(??), then no
such mappings are ??-colorings. Fortunately, it is easy to check whether a mapping is a ??-coloring or not.
Just step through all edges {??, ??} ∈ ??(??), and check that the colors ??(??) and ??(??) are different. If for some
{??, ??} ∈ ??(??), we have ??(??) = ??(??), then ?? is not a ??-coloring.
A brute force solution to this minimization problem is now clear. For each ?? = 1, 2, 3, …, enumerate all ????
mappings ??: {1, 2, 3, … … , ??} → {1, 2, 3, … , ??} (itself an interesting problem), then check each one to see if
it is a proper ??-coloring. The first (smallest) ?? for which this check succeeds is ??(??). Unfortunately, the
algorithm just described is utterly impractical for all but the smallest ??. Observe that the total number of
checks performed is
� ????
??(??)
??=1
≥ ??(??)??,
which grows very rapidly with the size ?? of the vertex set of ??. For instance, if ?? has ?? = 100 vertices
and ??(??) = 10, then more than 10100 checks must be performed. Even if each check could be performed
in a billionth of a second (far too optimistic), the amount of time consumed would be
1091 seconds = (3.168… ) ⋅ 1083 years.
For contrast, the current estimate of the age of the universe is only (13.772) ⋅ 109 years. There are ways
to improve the above algorithm, such as to consider only surjective mappings from {vertices} to {colors},
but nothing can overcome its basic inefficiency. If someone were to discover an efficient algorithm for the
2
Graph Coloring problem, it would be considered a major advancement in theoretical computer science, and
would win its inventor one million dollars. See
https://en.wikipedia.org/wiki/P_versus_NP_problem
and
https://en.wikipedia.org/wiki/Graph_coloring#Computational_complexity
for details.
Obviously then, our goal in this project must be more modest. Instead, you will create a program that only
approximates an optimal solution, and does it efficiently. There is a word for this: heuristic. A heuristic
for an optimization problem is a computational process that returns an answer that is likely to be a good
approximation to optimal, and is likely to be efficient in doing so. There may be a small set of problem
instances for which the approximation is bad, and some for which the runtime is long. An algorithm on the
other hand, is supposed to solve all instances of a problem, i.e. always return an optimal solution.
The heuristic you develop for the GC problem will be based on the reachable() and BFS() algorithms
discussed in class. These algorithms are very efficient and can be run on large graphs with thousands or
even millions of vertices. Both algorithms start at a source vertex and search outward from it, always
processing the next vertex nearest the source. This makes sense for the SSSP problem, since the goal is to
determine distances from the source. It may not make sense for the GC problem. Here is the general outline
followed by both algorithms.
1. start somewhere
2. while some vertex has not been “processed” (whatever that may mean)
3. pick the “best” such vertex ?? (whatever “best” means)
4. process ??
5. for each neighbor ?? of ??
6. “update” the vertex ?? (whatever “update” means)
Both reachable() and BFS() have a defined starting point, the source, which is one of the algorithm inputs.
For the GC problem we can start anywhere. Is there a best place to start? That will be up to you. Each
vertex ?? participates in a constraint with each of its neighbors ??, namely that color[??] ≠ color[??]. The
number of constraints on color[??] is the number of neighbors of ??, also called the degree of ??, denoted
deg(??). Should we pick the largest degree (most constraints) to start? The smallest (least constraints)?
Should we consider the degrees of the neighbors of ??? Should we ignore all this and just pick a random
starting vertex? These are all things for you to consider. Once you get a running program, you will be able
to do experiments, altering your heuristic in various ways to see if you get better results.
What does it mean to “process” a vertex ??? In this problem, it pretty clearly means assigning a color to ??,
although even this is open to interpretation. One thing your heuristic must do is to always produce a proper
??-coloring of ??. To this end you should, for each ?? ∈ ??(??), maintain a set ecs[??] containing the excluded
color set for ??, i.e. the set of colors that have already been assigned to its neighbors, and therefore cannot
be assigned to ??. Since our goal is to use the smallest possible number of colors, the color we assign to ??
should always be the smallest color in the set {1, 2, 3, … , ??} − ecs[??], i.e. pick the smallest color that can
be assigned. This assures that there will be no gaps in the set of colors used. In other words, if we manage
to find a 5-coloring using the set {1, 2, 3, 4, 5}, but the color 3 is never assigned, then we could have
achieved a 4-coloring.
3
If “process” ?? means to pick color[??], then to “update” one of its neighbors ?? ∈ adj[??], should mean to add
color[??] to ecs[??], so when it comes ??’s turn to be “processed”, we know what colors not to assign.
Finally, what should “best” mean on line 3 of the outline? This decision is where you will have the most
leeway to be creative in designing your heuristic. Here are some ideas. You may base the choice for what
is “best” on degrees again, i.e. pick an unprocessed (uncolored) vertex of either highest or lowest degree.
You might also pick one with the largest excluded color set, the idea being to put out the biggest fire first.
Another approach would be to pick a vertex closest to your starting point. In this case, you should maintain
a FIFO queue with the closest vertex at the front, just in BFS(). Then to “update” a neighbor ?? of ?? would
entail adding it to the back of the queue, as well as updating ecs[??]. You can refine all of these strategies
by combining them in various ways. For instance, pick ?? to be an uncolored vertex of maximum degree,
then break ties by picking one with largest ecs[??].
Program Specifications
You will write a module called graph.py containing a Graph class. This file should be based on the example
graphs.py discussed at length in class (note the different spellings). Begin by removing anything not
needed in this project, like the attributes _distance, _predecessor and _component, and functions
like findComponents() and getPredecessor(). Add the following attributes to your Graph class.
_color: a dictionary whose keys are vertices x, and value _color[x], the color of x
_ecs: a dictionary whose keys are vertices x, and value _ecs[x], the excluded color set of x
You may add other attributes that you deem necessary for your heuristic strategy. Include functions that
perform the actions described in their respective doc strings.
def Color(self):
“””
Determine a proper coloring of a graph by assigning a color from the
set {1, 2, 3, .., n} to each vertex, where n=|V(G)|, and no two adjacent
vertices have the same color. Try to minimize the number of colors
used. Return the subset {1, 2, .., k} of {1, 2, 3, .., n} consisting
of those colors actually used.
“””
pass
# end
def getColor(self, x):
“”” Return the color of x.”””
pass
# end
It is recommended (but not required) that you include a helper function as described below.
def _find_best(self, L):
“””Return the index of the best vertex in the list L.”””
pass
# end
The required function Colors() is of course the main event in this project. Again you may add other
functions as you deem appropriate.
4
Write a client program called GraphColoring.py containing the following functions.
def CheckProperColoring(G):
“””
Return True if no two adjacent vertices in G have like colors,
False otherwise.
“””
pass
# end
def main():
# check command line arguments and open files
# read each line of input file
# get number of vertices on first line, create vertex list
# create edge list from remaining lines
# create graph G
# Determine a proper coloring of G and print it to the output file
“””
# Check that the coloring is correct
print(file=outfile)
msg = ‘coloring is proper: {}’.format(CheckProperColoring(G))
print(msg, file=outfile )
“””
# end
You may follow the outline in function main() if you like, though it is not required. The code after the final
comment (triple quoted out) is for diagnostic purposes only, and intended for you to run your own tests.
Do not include those commands in your submitted version.
A sample run of your program is given below.
$ python3 GraphColoring.py
Usage: $ python3 GraphColoring.py
