Python图着色算法答案_CSE 30_Programming Assignment 6美国留学生Python作业pa6答案




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
     return flag

def main():

    p = sys.argv
    if len(p)<3:
        print("Usage: $ python3  ")
        infile = sys.argv[1]
        if not os.path.exists(infile):
            print(f"[Errno 2] No such file or directory: '{infile}'")
            print("Usage: $ python3  ")
            outfile=sys.argv[2]          # 输出文件
            f = open(infile)
            items = []
            for item in f:

            amounts = int(items[0])     # 顶点数
            vs = [str(v) for v in range(1,amounts+1)] # [1,2,3,4....]顶点表
            g = {}                      # 初始化图
            for v in vs:g[v] = list()

            for item in items[1:]:
                v,a = item.split(' ')   # 顶点 相邻点    
                g[v].append(a)          # 添加到v点的相邻点列表

            for item in items[1:]:
                v,a = item.split(' ')   # 顶点 相邻点    
                g[a].append(v)          # 添加到v点的相邻点列表

            g = Graph(g)                # 实例化图
            g.Color()                   # 对进行着色

            colors = set(g._color.values())
            color_amounts = len(colors)
            outstring = f'{color_amounts} colors used : {colors}\n\n'
            outstring = outstring  + 'vertext     color\n'
            outstring = outstring  + '_________________\n'
            for i in range(1,amounts+1):
                s = f"{i:3d}          {g.getColor(str(i)):3d}\n"
                outstring = outstring + s
            msg = '\n\ncoloring is proper: {}'.format(CheckProperColoring(g))
            outstring = outstring + msg

            of = open(outfile,'w')           
            print(outstring, file=of )

if __name__ == "__main__":



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
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
� 𝑘𝑘𝑛𝑛
≥ 𝜒𝜒(𝐺𝐺)𝑛𝑛,
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
Graph Coloring problem, it would be considered a major advancement in theoretical computer science, and
would win its inventor one million dollars. See
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.
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 containing a Graph class. This file should be based on the example 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.
# end
def getColor(self, x):
“”” Return the color of x.”””
# 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.”””
# end
The required function Colors() is of course the main event in this project. Again you may add other
functions as you deem appropriate.
Write a client program called containing the following functions.
def CheckProperColoring(G):
Return True if no two adjacent vertices in G have like colors,
False otherwise.
# 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
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
Usage: $ python3
$ python3 in
Usage: $ python3
$ python3 in out
[Errno 2] No such file or directory: ‘in’
Usage: $ python3
$ python3 in1 out1
As you can see, your program should do basic checks of the command line inputs, as in previous projects.
It will then read from an input file, and write to an output file, both named on the command line.
File Formats
An input file will contain a single positive integer on line 1, giving the number of vertices in a graph. Each
subsequent line will contain two integers, separated by a space, giving the ends of an edge in the graph. A
blank line in the file terminates the input, and no lines after it will be read. The following example represents
a graph with 15 vertices.
1 7
2 3
2 6
3 7
4 10
5 9
5 10
6 7
6 11
7 12
8 13
9 13
9 14
10 15
14 15
One possible output file to match this input is given below.
3 colors used: {1, 2, 3}
vertex color
1 1
2 1
3 3
4 1
5 1
6 3
7 2
8 2
9 2
10 2
11 1
12 1
13 1
14 1
15 3
The first line of the output file gives the number of colors used, then lists the colors in set braces. This is
followed by a blank line, then a table listing each vertex and its corresponding color. As usual your output
formatting must match this exactly for full credit. The file, posted in Examples/pa6,
may help achieve the column formatting. A set of seven matched pairs of input-output files are also posted
in the same directory. The above pair is in2-out2. You’ll also find the program which
will create a properly formatted, random input file for this project.
If you draw the above graph, you will find that it contains the 5-cycle (5, 10, 15, 14, 9, 5), which we know
requires 3 colors. Therefore the 3-coloring given in the above output file is optimal, and 𝜒𝜒(𝐺𝐺) = 3 in this
case. In general, you should not expect your output file to contain an optimal coloring, but only to establish
the inequality 𝜒𝜒(𝐺𝐺) ≤ 𝑘𝑘, where 𝑘𝑘 is the size of your color set. Not all of the output files given in
Examples/pa6 are optimal, and for the larger ones, it is probably impossible to tell what 𝜒𝜒(𝐺𝐺) actually is.
Of all our programming projects thus far, this one perhaps affords you the greatest freedom in developing
your own techniques. It is recommended that you begin by writing a program that always produces a proper
coloring. Once that is done, experiment with different strategies to improve your results. As you
experiment, you will likely find that your estimate of 𝜒𝜒(𝐺𝐺) improves on some examples (by getting smaller),
and worsens on others.
Start this project as soon as possible and get help from TAs and course tutors as needed. Turn in your two
files and to Gradescope before the due date.

本站所有作品,教程等皆为原创,版权所有。只供个人及单位内部研究使用,对外展示或传播必需经本站同意,且注明来自本站。培训机构等用本站资源培训学生,需经本站授权。一旦付款,表示同意本站知识付费原则:数字商品,不支持退款。亦可直接向微信号scratch8付款购买。入住QQ群:225792826 和爱好者共同交流,并且能下载免费提供的Python资源(需提供真实姓名才可入群)
李兴球的博客_Python创意编程技术前沿_pygame » Python图着色算法答案_CSE 30_Programming Assignment 6美国留学生Python作业pa6答案


李兴球博客 风火轮编程主页