以下关于Graphs图的作业已完成，需要请联系本人微信scratch8(李兴球, 406273900@qq.com)
本人提供国内外大学生Python作业辅导，Python作业答疑，C语言作业辅导与答疑，大中小学生编程培训服务。
以下蓝色*线以下文本格式请忽视, 只是为了搜索引擎抓取的需要,及让您知道,本人已经解决了这问题。
*************************************************************************************
Before you turn this problem in, make sure everything runs as expected. First, restart the kernel (in the menubar, select Kernel Restart) and then run all cells (in the menubar, select Cell Run All).
Make sure you fill in any place that says YOUR CODE HERE or “YOUR ANSWER HERE”, as well as your name and collaborators below:
NAME = “” COLLABORATORS = “”
CSE 30 Fall 2021 – Homework 10 家庭作业10
Graphs 图
Instructions 介绍
Please disregard the YOUR NAME and COLLABORATORS above. They are put there atomatically by the grading tool. You can find instructions on how to work on a homework on Canvas. Here is a short summary:
Submitting your work 提供你的作业
To submit your work:
First, click on “Runtime > Restart and run all”, and check that you get no errors. This enables you to catch any error you might have introduced, and not noticed, due to your running cells out of order.
Second, download the notebook in .ipynb format (File > Download .ipynb) and upload the
.ipynb file to this form.
You can submit multiple times; the last submission before the deadline is the one that counts.
Homework format 家作格式
For each question in this notebook, there is: 每个问题
A text description of the problem. 都有一个描述
One or more places where you have to insert your solution. You need to complete every place marked: 在下面的位置写上你的代码
# YOUR CODE HERE
and you should not modify any other place.
One or more test cells. Each cell is worth some number of points, marked at the top. You should not modify these tests cells. The tests pass if no error is printed out: when there is a statement that says, for instance:
assert x == 2
then the test passes if x has value 2, and fails otherwise. You can insert a print(x) (for this case!) somewhere if you want to debug your work; it is up to you.
Notes:
Your code will be tested both according to the tests you can see (the assert statements you can see), and additional tests. This prevents you from hard-coding the answer to the particular questions posed. Your code should solve the general intended case, not hard-code the particular answer for the values used in the tests.
Please do not delete or add cells! The test is autograded, and if you modify the test by adding or deleting cells, even if you re-add cells you delete, you may not receive credit.
Please do not import modules that are not part of the standard library. You do not need any, and they will likely not available in the grading environment, leading your code to fail.
If you are inactive too long, your notebook might get disconnected from the back-end. Your work is never lost, but you have to re-run all the cells before you continue.
You can write out print statements in your code, to help you test/debug it. But remember: the code is graded on the basis of what it outputs or returns, not on the basis of what it prints.
TAs and tutors have access to this notebook, so if you let them know you need their help, they can look at your work and give you advice.
Grading
Each cell where there are tests is worth a certain number of points. You get the points allocated to a cell only if you pass all the tests in the cell. 每个单元有提供一些测试的地方，你可以自己测试下自己的代码能不能通过。
The tests in a cell include both the tests you can see, and other, similar, tests that are used for grading only. Therefore, you cannot hard-code the solutions: you really have to solve the essence of the problem, to receive the points in a cell.
Code of Conduct
Work on the test yourself, alone. 你可以自己单独测试
You can search documentation on the web, on sites such as the Python documentation sites, Stackoverflow, and similar, and you can use the results. 你可以在网上搜索文档资料，例如Python的文档站，或Stackoverflow及相似的网站，使用相关的结果。
You cannot share your work with others or solicit their help.
一个有向图G=(V,E)由一系列的顶点和边组成。
A (directed) graph G = (V , E) consists of a set of vertices (or nodes) , and a set of edges
E ⊆ V × V .
图的一个例子
An example of a graph with V = {a, b, c, d, e, f, g} and
E = {(a, b), (a, c), (a, d), (b, d), (c, a), (c, e), (d, b), (d, c), (f, g), (g, f)}.
如何表示图呢? 就像真实生活一样，直接用一系列顶点和边表示图就行了。
How should we represent a graph? A general principle of software development — really, of life — is: failing special reasons, always go for the simplest solution. So our first attempt consists in storing a graph exactly according to its definition: as a set of vertices and a set of edges.
class Graph(object):
def init (self, vertices=None, edges=None):
# We use set below, just in case somebody passes a list to the initializer. self.vertices = set(vertices or [])
self.edges = set(edges or [])
g = Graph(vertices={‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’},
edges={(‘a’, ‘b’), (‘a’, ‘c’), (‘a’, ‘d’), (‘b’, ‘d’),
(‘c’, ‘a’), (‘c’, ‘e’), (‘d’, ‘b’), (‘d’, ‘c’), (‘f’, ‘g’), (‘g’, ‘f’)})
不错，但是，如何显示图呢?
Great, but, how do we display graphs? And what can we do with them?
我们给图增加show方法，使用networkx这个库来显示图。
Let’s first of all add a method .show() that will enable us to look at a graph; this uses the library
networkx.
import networkx as nx # Library for displaying graphs.
class Graph(object):
def init (self, vertices=None, edges=None):
# We use set below, just in case somebody passes a list to the initializer. self.vertices = set(vertices or [])
self.edges = set(edges or [])
def show(self):
g = nx.DiGraph() g.add_nodes_from(self.vertices) g.add_edges_from(self.edges) nx.draw(g, with_labels=True)
g = Graph(vertices={‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’},
edges={(‘a’, ‘b’), (‘a’, ‘c’), (‘a’, ‘d’), (‘b’, ‘d’),
(‘c’, ‘a’), (‘c’, ‘e’), (‘d’, ‘b’), (‘d’, ‘c’), (‘f’, ‘g’), (‘g’, ‘f’)})
g.show()
这和我们手工画的图相比还不太完美? 但它确实表明了此图的含义。
Ok, this is not nearly as pretty as what we generated by hand, but it will have to do.
One-Step Reachability and Graph Representations
图的常见操作是什么? 基本操作是增加顶点和增加边。
What are conceivable operations on graphs? There are some basic ones, such as adding a vertex and adding an edge. These are easily taken care of.
import networkx as nx # Library for displaying graphs. class Graph(object):
def init (self, vertices=None, edges=None):
# We use set below, just in case somebody passes a list to the initializer. self.vertices = set(vertices or [])
self.edges = set(edges or [])
def show(self):
g = nx.DiGraph() g.add_nodes_from(self.vertices) g.add_edges_from(self.edges) nx.draw(g, with_labels=True)
def add_vertex(self, v): self.vertices.add(v)
def add_edge(self, e):
self.edges.add(e)
进一步地说，一张图表示一系列顶点的连接，一个通常的问题是是否一个点能通过一条边或更多的边到达另一个点？
Further, a graph represents a set of connections between vertices, so a very elementary question to ask is the following: if we are at vertex , can we get to another vertex by following one or more edges?
As a first step towards the solution, we want to compute the set of vertices reachable from in one step, by following one edge; we call these vertices the successors of
写一个函数，叫g.successors(u)，表示u点的后续顶点。 .
Writing a function g.successors(u) that returns the set of successors of is simple enough. Note that the code directly mimicks the mathematical definition:
Successors(u) = {v ∈ V ∣ (u, v) ∈ E} .
import networkx as nx # Library for displaying graphs. class Graph(object):
def init (self, vertices=None, edges=None):
# We use set below, just in case somebody passes a list to the initializer. self.vertices = set(vertices or [])
self.edges = set(edges or [])
def show(self):
g = nx.DiGraph() g.add_nodes_from(self.vertices) g.add_edges_from(self.edges) nx.draw(g, with_labels=True)
def add_vertex(self, v): self.vertices.add(v)
def add_edge(self, e): self.edges.add(e)
def successors(self, u):
“””Returns the set of successors of vertex u”””
return {v for v in self.vertices if (u, v) in self.edges}
g = Graph(vertices={‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’},
edges={(‘a’, ‘b’), (‘a’, ‘c’), (‘a’, ‘d’), (‘b’, ‘d’),
(‘c’, ‘a’), (‘c’, ‘e’), (‘d’, ‘b’), (‘d’, ‘c’), (‘f’, ‘g’), (‘g’, ‘f’)})
g.successors(‘a’)
But there’s a rub. The method successors, as written, requires us to loop over the whole set of vertices. Because self.edges is a set, represented as a hash table, once we have a pair (u, v), checking
(v, u) in self.edges
is efficient. But typically, graphs have a locality structure, so that each node is connected only to a small subset of the total vertices; having to loop over all vertices to find the successors of a vertex is a great waste. It is as if I asked you to what places you can get from San Francisco with a direct flight, and to answer, you started to rattle off all of the world’s cities, from Aachen, Aalborg, Aarhus,
…, all the way to Zürich, Zuwarah, Zwolle, and for each city you checked if there’s a flight from San Francisco to that city! Clearly not the best method.
Given that our main use for graphs is to answer reachability-type questions, a better idea is to store the edges via a dictionary that associates with each vertex the set of successors of the vertex. The vertices will simply be the keys of the dictionary.
import networkx as nx # Library for displaying graphs. class Graph(object):
def init (self, vertices=None, edges=None): self.s = {u: set() for u in vertices or []} for u, v in (edges or []):
self.add_edge((u, v))
def show(self):
g = nx.DiGraph() g.add_nodes_from(self.s.keys())
g.add_edges_from([(u, v) for u in self.s for v in self.s[u]]) nx.draw(g, with_labels=True)
def add_vertex(self, v): if v not in self.s:
self.s[v] = set()
def add_edge(self, e): u, v = e self.add_vertex(u) self.add_vertex(v) self.s[u].add(v)
@property
def vertices(self):
return set(self.s.keys())
def successors(self, u):
“””Returns the set of successors of vertex u””” return self.s[u]
g = Graph(vertices={‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’},
edges={(‘a’, ‘b’), (‘a’, ‘c’), (‘a’, ‘d’), (‘b’, ‘d’),
(‘c’, ‘a’), (‘c’, ‘e’), (‘d’, ‘b’), (‘d’, ‘c’), (‘f’, ‘g’), (‘g’, ‘f’)})
g.show() print(g.successors(‘a’))
Graph Reachability 图的可到达性
We now come to one of the fundamental graph algorithms, in fact, perhaps the most fundamental algorithm for graphs: computing the set of vertices reachable from a given starting vertex.
Exploring what is reachable from a graph vertex is a truly basic task, and variations on the algorithm can be used to answer related questions, such as whether a vertex is reachable from a given starting vertex.
The algorithm keeps two sets of vertices: 这个算法包括两个顶点的集合。
The set of open vertices: these are the vertices that are known to be reachable, and whose successors have not yet been explored.
The set of closed vertices: these are the vertices that are known to be reachable, and whose successors we have already explored.
Intially, the set of open vertices contains only the starting vertex, and the set of closed vertices is empty, as we have completed no exploration. Repeatedly, we pick an open vertex, we move it to the closed set, and we put all its successor vertices — except those that are closed already — in the open set. The algorithm continues until there are no more open vertices; at that point, the set of
reachable vertices is equal to the closed vertices.
If there is one graph algorithm that you must learn by heart, and that you should be able to write even when you hang upside down from monkeybars, this is it.
Let us write the algorithm as a function first.
def reachable(g, v):
“””Given a graph g, and a starting vertex v, returns the set of states reachable from v in g.”””
vopen = {v} vclosed = set()
while len(vopen) > 0: u = vopen.pop() vclosed.add(u)
vopen.update(g.successors(u) – vclosed) return vclosed
print(reachable(g, ‘a’))
print(reachable(g, ‘g’))
To visualize the algorithm, let us write a version where at each iteration, open vertices are drawn in red and closed ones in green
def reachable(g, v):
“””Given a graph g, and a starting vertex v, returns the set of states reachable from v in g.”””
vopen = {v} vclosed = set()
while len(vopen) > 0: u = vopen.pop() vclosed.add(u)
vopen.update(g.successors(u) – vclosed) return vclosed
reachable(g, ‘a’)
Breadth-First and Depth-First Search 宽度和深度优先搜索
Breadth First 广度优先搜索
In breadth-first search, we explore in concentric circles emanating from the starting point: first all vertices at distance 1, then all vertices at distance 2, and so on. In general, we explore all vertices at distance ≤ n before we explore vertices at distances .
To implement breadth-first search, we store the open vertices vopen as a list rather than a set. We then explore vertices in the order they have been added to vopen : this ensures that vertices closer to the search origin are explored earlier than farther-away vertices.
The difference in code between reachability search, and its specialized breadth-first version, is minimal.
def breath_first(g, v):
“””Given a graph g, and a starting vertex v, returns the set of states reachable from v in g.”””
# vopen is a FIFO: first in, first out. Like a normal queue.
# we add elements from the end, and pop them from the beginning. vopen = [v]
vclosed = set()
while len(vopen) > 0:
u = vopen.pop(0) # Pop from the beginning vclosed.add(u)
# vopen.update(g.successors(u) – vclosed) for w in g.successors(u) – vclosed:
if w not in vopen:
vopen.append(w) # Add to the end return vclosed
gg = Graph(vertices={},
edges={(‘a’, ‘b’), (‘b’, ‘c’), (‘c’, ‘d’),
(‘a’, ‘u’), (‘u’, ‘v’), (‘v’, ‘w’), (‘u’, ‘z’)})
breath_first(gg, ‘a’)
We see that we explore and before any of their successors are explored, and similarly, we explore , , and before or .
Depth-First Search 深度优先搜索
In depth-first search, we follow a path as long as possible, and only when we come to an end do we explore other nodes. In depth-first search, the most recent visited vertex, the one added last to the list of open vertices, is the one that will be explored first.
The difference in code from breadth-first search is minimal. In breadth-first search, the vertex to be explored next is the oldest among the open ones:
u = vopen.pop(0)
In depth-first search, it will be the newest among the open ones:
u = vopen.pop()
That’s the whole difference.
def depth_first(g, v):
“””Given a graph g, and a starting vertex v, returns the set of states reachable from v in g.”””
# vopen is a stack / LIFO: last in, first out. Like a stack.
# we add elements from the end, and pop them from the end. vopen = [v]
vclosed = set()
while len(vopen) > 0:
u = vopen.pop() # THIS is the difference: there is no 0 in the parentheses. vclosed.add(u)
# vopen.update(g.successors(u) – vclosed) for w in g.successors(u) – vclosed:
if w not in vopen: vopen.append(w)
return vclosed
depth_first(gg, ‘a’)
We see how in depth-first search we explore completely one side of the successors of , consisting
of u, v, w,
, before exploring the other side b, c, d.
Problem 1: Returning the edges 第一个问题，返回所有边
In our latest implementation, we do not have direct access to the edges of the graph. In other words, for a graph g, we cannot do:
for (u, v) in g.edges:
…
We ask you to write an iterator over edges, to make the above code work. The iterator should yield the edges of the graph, one by one.
### An iterator for the set of edges
def graph_edges(self):
“””Yields the edges of the graph, one by one. Each edge is yielded as a pair of vertices (source, destination). “””
# YOUR CODE HERE
Graph.edges = property(graph_edges)
# YOUR CODE HERE
Here are some tests.
### 10 points: simple tests e = [(1, 2), (1, 3), (2, 3)]
g = Graph(vertices=[1, 2, 3], edges=e) assert set(g.edges) == set(e)
import types
# You need to build a generator, one of those things with the yield statement. assert isinstance(g.edges, types.GeneratorType)
Here are some randomized test.
### 10 points: random tests import random
for _ in range(10):
num_vertices = random.randint(4, 10)
num_edges = random.randint(1, num_vertices * num_vertices) vertices = random.sample(range(0, 1000), num_vertices)
edges = {(random.choice(vertices), random.choice(vertices)) for _ in range(num_edges)} g = Graph(vertices=vertices, edges=edges)
assert set(g.edges) == edges
Problem 2: Is a graph a tree? 第二个问题，图是一棵树吗?
A tree is a graph (V , E) with two special properties: Every vertex has at most one incoming edge.
Either there are no vertices, or there is a vertex with no incoming edges, called the root, from which all other vertices are reachable.
If the second property does not hold, incidentally, the graph is called a forest.
Write an is_tree function such that is_tree(g) returns True if the graph g is a tree, False otherwise.
### Implementation of tree test
def is_tree(g):
“””Returns True iff the graph is a tree.”””
# YOUR CODE HERE
### 10 points: Tests for `is_tree`
| g = Graph(vertices=[1, |
2, |
3], |
edges=[(1, |
2), |
(1, |
3)]) |
| assert is_tree(g) |
|
|
|
|
|
|
| g = Graph(vertices=[1, |
2, |
3], |
edges=[(1, |
2), |
(2, |
3), (1, 3)]) |
| assert not is_tree(g) |
|
|
|
|
|
|
| g = Graph(vertices=[1, |
2, |
3], |
edges=[(1, |
3), |
(2, |
3)]) |
| assert not is_tree(g) |
|
|
|
|
|
|
### 10 points: More tests for `is_tree`
g = Graph() assert is_tree(g)
Problem 3: Reachability using either of two graphs 第三个问题，两图的可到达性。
In this problem, you are given two graphs g1 , g2 , that share the same set of vertices. You have to write a function can_reach(v, g1, g2, w) , which returns True iff you can go from vertex v to vertex w using either edges of g1 or g2 . Note that to go from v to w , you can use one or more edges from g1 and one or more edges of g2 , mixed in any way you like. To solve the problem, you have to modify the reachability algorithms so that edges from either graph can be used.
Hint: Modify the reachability algorithm.
def can_reach(v, g1, g2, w):
“””Given two graphs g1, g2 that share the same vertices, and two verteces v, w, returns True if you can go from v to w using edges of either g1 or g2 (mixed any way you want) and False otherwise.”””
# YOUR CODE HERE
### 10 points: simple tests for can_reach
vertices = {1, 2, 3, 4, 5, 6, 7}
g1 = Graph(vertices=vertices, edges=[(1, 2), (3, 4)])
g2 = Graph(vertices=vertices, edges=[(2, 3), (4, 5), (6, 7)]) assert can_reach(1, g1, g2, 2)
assert can_reach(1, g1, g2, 3) assert can_reach(1, g1, g2, 4) assert can_reach(1, g1, g2, 5) assert not can_reach(1, g1, g2, 6) assert not can_reach(1, g1, g2, 7)
### 10 points: more advanced tests for can_reach vertices = set(range(100))
# g1 edges go from n to 2n, g2 edges go from n to 3n.
g1 = Graph(vertices=vertices, edges=[(n, 2 * n) for n in range(100) if 2 * n < 100]) g2 = Graph(vertices=vertices, edges=[(n, 3 * n) for n in range(100) if 3 * n < 100]) assert can_reach(1, g1, g2, 6)
assert can_reach(1, g1, g2, 24) assert can_reach(1, g1, g2, 32) assert can_reach(1, g1, g2, 9) assert not can_reach(1, g1, g2, 15) assert not can_reach(1, g1, g2, 60) assert can_reach(5, g1, g2, 15) assert can_reach(5, g1, g2, 30)
提供国内外大学生Python作业辅导，Python作业答疑，C语言作业辅导与答疑，有偿服务。
