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

Python海龟宝典含200多个原创的用turtle模块制作的创意程序,原名《Python趣味编程200例》。准备参加全国创意编程与智能设计大赛的同学们可以用来做参考。

完成无向图用最少的颜色着色,即相邻点的颜色不一致,要提交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  ")
    else:
        infile = sys.argv[1]
        if not os.path.exists(infile):
            print(f"[Errno 2] No such file or directory: '{infile}'")
            print("Usage: $ python3 GraphColoring.py  ")
        else:
            
            outfile=sys.argv[2]          # 输出文件
            f = open(infile)
            items = []
            for item in f:
                items.append(item.strip())
            f.close()

            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 )
            of.close()


if __name__ == "__main__":

    main()


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
$ python3 GraphColoring.py in
Usage: $ python3 GraphColoring.py
$ python3 GraphColoring.py in out
[Errno 2] No such file or directory: ‘in’
Usage: $ python3 GraphColoring.py
$ python3 GraphColoring.py 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.
5
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.
15
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 FormatNumbers.py, 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 RandomInput.py which
will create a properly formatted, random input file for this project.
6
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 graph.py and GraphColoring.py to Gradescope before the due date.

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

李兴球Python微信公众号文章列表

Python游戏海龟模块教程说明书与案例若干免费发放

爱的纪念_Python创意情景动画源代码解析

少儿Python编程到底学些什么?这些代码或许回答了问题.

Python编程家长会花絮_萍乡中小学Python家长会现场

火星路上等着你_少儿从小学什么最好呢?

国家大力整顿教育培训机构,Scratch或Python少儿编程还有得教吗?

鸿蒙系统支持Python开发_可视化编程特别兴趣小组

Scratch作品转Python作品_小猴接桃

python海龟数据可视化。第七次全国人口普查历年数据图表

你的孩子Python编程学到哪个阶段了?给孩子报编程的家长,务必仔细一读。

五一神女来对话,看看她们聊什么?赠Python教案等。

五一快乐有大礼,告诉大家我是如何上Python课的。

Python名堂多,趣味到处有,劈开机械手,帧帧是图片。速算达人之猫狮大战正在进行。 逐字动画不独享,自动生成皆有它。2行代码自动生成字幕gif动画。 Python之潮来临,我在安源区教师科技创新能力的Python讲座

小心你的Python程序,它会是你的一面镜子。小方块闯迷宫.py源代码简析。送Scratch算法集。?

铃儿响钉铛_音效怎能忘_Python配音之Pygame混音器

人面桃花相映红_winsound模块简介

《Python昨晚我想你了》_开源的游戏海龟模块实例案例浅析

《八猫联动初体验》_来自游戏海龟模块的问候

喜爱春天的人儿啊 心地纯洁的人_Python逐行像素显示

旋转之三叶炫彩扇_蟒蛇与海龟的表演

彩虹欢迎字幕_三模合体滚图形

《Python海龟宝典》简介

100%错误的算法还在用,明明没有错别字,说我有11个错别字

奇怪的Python代码,谁能帮我解释一下??

人造地球系统让人类文明充满整个宇宙之Python32768版

深夜,是什么把你的大脑搞成一团浆糊!再谈少儿编程!

5线城市萍乡的少儿Python寒假班学的是什么内容?

关于纯少儿编程课程进化的自然选择

Python海龟画图经典作品_国庆中秋双重喜庆源代码免费下载

海龟为什么要自杀!turtle制作游戏秘籍之一

朋友,你是否知道我在仰望着你_Python神笔马良案例集

酷酷的爆炸效果_Python海龟画图不仅仅是画图

虫子满屏爬_三bug多线程示例程序浅析 少儿Python视频课程A级简介

给的gif图片加文字水印_拆帧与合帧(免费下载180个Python创意源码

用Python制作酷炫图形之如意金箍棒_颜色增加模块应用

简单的用Python做酷炫图形与动画

sb3转exe,sb3素材提取器,编程小子apk, 未公开的pygame游戏集/scratch/python少儿编程免费下载集合

夜幕下的霓虹

学本领,探索更大的世界!

李兴球博客 风火轮编程主页
error: Content is protected !!