以下全是问题描述，需要答案请联系博客微信scratch8
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?
很好，可是我们如何显示图呢？ 我们还能玩些啥？
Let’s first of all add a method .show() that will enable us to look at a graph; this uses the library networkx.
让我们添加一个show方法看看图到底长啥样，使用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()
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 ? .
作为求解的第一步，我们希望通过沿着一条边，一步计算从?可到达的顶点集；我们称这些顶点为?的后继顶点。
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:
编写一个函数g.successivers（u）来返回一组?的后续顶点非常简单。请注意，代码直接模拟了数学定义：
Successors(?)={?∈?∣(?,?)∈?}.
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),
这有个问题就是，上面的方法遍历了所有的顶点，由于self.edges是个集合，用哈希表来存储的，
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.
from collections import defaultdict
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。下面写了一个可视化的函数，可以显示。
import matplotlib.pyplot as plt
def color_draw(g, vopen, vclosed):
gg = nx.DiGraph()
gg.add_nodes_from(g.vertices)
gg.add_edges_from([(u, v) for u in g.vertices for v in g.successors(u)])
node_colors = ''.join([('r' if v in vopen else 'g' if v in vclosed else 'b')
for v in g.vertices])
nx.draw(gg, with_labels=True, node_color=node_colors)
plt.show()
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()
color_draw(g, vopen, vclosed)
while len(vopen) > 0:
u = vopen.pop()
vclosed.add(u)
vopen.update(g.successors(u) - vclosed)
color_draw(g, vopen, vclosed)
return vclosed
reachable(g, 'a')
Great! Let’s now endow our graph with a method that yields the vertices reachable from any given starting vertex.
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 true iff one can get from vertex v to vertex u by following
one edge."""
return self.s[u]
def __eq__(self, other):
"""We need to define graph equality."""
if self.vertices != other.vertices:
return False
for v, d in self.s.items():
if d != other.s[v]:
return False
return True
def __repr__(self):
r = "Graph:"
for v in self.vertices:
r += "\n %r : %r" % (v, self.s.get(v))
return r
def show(self):
g = nx.DiGraph()
g.add_nodes_from(self.vertices)
g.add_edges_from([(u, v) for u in self.vertices for v in self.s[u]])
nx.draw(g, with_labels=True)
def add_vertex(self, v):
self.vertices.add(v)
# We must be careful not to overwrite the successor relation
# in case v might already be present in the graph.
self.s[v] = self.s.get(v, set())
def add_edge(self, e):
"""Adds an edge e = (u, v) between two vertices u, v. If the
two vertices are not already in the graph, adds them."""
u, v = e
self.vertices.update({u, v})
# Initializes the successor function if needed.
self.s[u] = self.s.get(u, set()) | {v}
self.s[v] = self.s.get(v, set())
def successors(self, u):
"""Returns the set of successors of a vertex u"""
return self.s[u]
def reachable(self, v):
"""Returns the set of vertices reachable from an initial vertex v."""
vopen = {v}
vclosed = set()
while len(vopen) > 0:
u = vopen.pop()
vclosed.add(u)
vopen.update(self.s[u] - vclosed)
return vclosed
Testing the implementation
This seems to be a reasonable implementation. Let us do some tests, to check that everything works as expected. The nose tools are very handy for testing. We have written a _check function that enables us to test whether the definition of a graph is self consistent. Writing such consistency checks is very useful. In development, we may call them often. In production code, we may choose to call them at key points in the code, to prevent the propagation of errors to distant places in the code.
import random
vertices = list('abcdefghilmnopqrstuvz')
def random_vertices():
"""Returns a set of random vertices."""
return set(random.choices(vertices, k=12))
def random_edges(vs):
"""Returns a set of random edges, given a set of vertices."""
vxv = [(u, v) for u in vs for v in vs]
return set(random.choices(vxv, k=min(len(vxv), 50)))
def random_graph():
vs = random_vertices()
e = random_edges(vs)
return Graph(vertices=vs, edges=e)
for _ in range(100):
g = Graph()
vs = random_vertices()
es = random_edges(vs)
for e in es:
g.add_edge(e)
for _ in range(100):
vs = random_vertices()
es = list(random_edges(vs))
g1 = Graph(vertices=vs, edges=es)
g2 = Graph(vertices=vs)
g3 = Graph(vertices=vs)
esp = es[:] # Creates a copy.
random.shuffle(esp)
for e in es:
g2.add_edge(e)
for e in esp:
g3.add_edge(e)
assert g1 == g2
assert g1 == g3
Graph Operations
图的操作
What are useful, general graph operations we may implement? Here are a few.
Union and intersection.
Induced: given a graph ?=(?,?) and a set of vertices ? , we return the graph with set of vertices ?∩? and set of edges ?∩(?∩?×?∩?) . This is the portion of the original graph that only involves vertices in V.
Difference: Remove, from a graph ? , all vertices in a specified set ? , along with the edges that have an endpoint in ? .
We will have you implement graph union.
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())
@property
def edges(self):
return {(u, v) for u, d in self.s.items() for v in d}
def successors(self, u):
"""Returns the set of successors of vertex u"""
return self.s[u]
def __eq__(self, other):
"""We need to define graph equality."""
if self.vertices != other.vertices:
return False
for v, d in self.s.items():
if d != other.s[v]:
return False
return True
def __repr__(self):
r = "Graph:"
for v in self.vertices:
r += "\n %r : %r" % (v, self.s.get(v))
return r
def show(self):
g = nx.DiGraph()
g.add_nodes_from(self.vertices)
g.add_edges_from([(u, v) for u in self.vertices for v in self.s[u]])
nx.draw(g, with_labels=True)
def add_vertex(self, v):
self.vertices.add(v)
# We must be careful not to overwrite the successor relation
# in case v might already be present in the graph.
self.s[v] = self.s.get(v, set())
def add_edge(self, e):
"""Adds an edge e = (u, v) between two vertices u, v. If the
two vertices are not already in the graph, adds them."""
u, v = e
self.vertices.update({u, v})
# Initializes the successor function if needed.
self.s[u] = self.s.get(u, set()) | {v}
self.s[v] = self.s.get(v, set())
def successors(self, u):
"""Returns the set of successors of a vertex u"""
return self.s[u]
def reachable(self, v):
"""Returns the set of vertices reachable from an initial vertex v."""
vopen = {v}
vclosed = set()
while len(vopen) > 0:
u = vopen.pop()
vclosed.add(u)
vopen.update(self.s[u] - vclosed)
return vclosed
def __and__(self, g):
"""Returns the intersection of the current graph with a
specified graph g."""
return Graph(vertices=self.vertices & g.vertices,
edges=self.edges & g.edges)
def induced(self, vertex_set):
"""Returns the subgraph induced by the set of vertices vertex_set."""
common_vertices = vertex_set & self.vertices
gg = Graph(vertices = common_vertices)
for v in common_vertices:
gg.s[v] = self.s[v] & common_vertices
gg._check()
return gg
Question 1: Is a graph a tree?
问题一，判断图是否是一颗树，需要答案请联系微信pythonxia
A tree is a graph (?,?) 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 property that has value True if the graph is a tree, and has value False otherwise.
#@title Implementation of tree test
def graph_is_tree(self):
"""Returns True iff the graph is a tree."""
### YOUR CODE HERE
Graph.is_tree = property(graph_is_tree)
### 10 points: Tests for tree.
g = Graph(vertices=[1, 2, 3], edges=[(1, 2), (1, 3)])
assert g.is_tree
g = Graph(vertices=[1, 2, 3], edges=[(1, 2), (2, 3), (1, 3)])
assert not g.is_tree
g = Graph(vertices=[1, 2, 3], edges=[(1, 3), (2, 3)])
assert not g.is_tree
g = Graph(vertices=['a', 'b'], edges=[('a', 'b')])
assert g.is_tree
g = Graph(vertices=['a', 'b'], edges=[('a', 'b'), ('b', 'a')])
assert not g.is_tree
### 10 points: More tests for `is_tree`
g = Graph()
assert g.is_tree
g = Graph(vertices=['a', 'b', 'c', 'd'], edges=[('a', 'b'), ('c', 'd')])
assert not g.is_tree
g = Graph(vertices=['a', 'b', 'c', 'd'], edges=[('a', 'b'), ('b', 'c'), ('c', 'd')])
assert g.is_tree
Question 2: Count the Islands
问题2，数孤岛，需要答案请联系博主微信pythonxia
You need to write a function count_the_islands, which counts the islands of 1s in a matrix whose elements can be 0 or 1. Two 1s belong to the same island if they are adjacent horizontally or vertically. For example, the matrix:
000000000
001000001
011110011
001100110
000000000
contains two islands:
………
..1……
.1111….
..11…..
………
and
………
……..1
…….11
……11.
………
As another example, the matrix:
00010000
00001100
00000000
contains two islands, one containing one 1, the other containing two 1s, as being adjacient via the diagonal only does not count.
Your task is simple: write a function that, given as input a numpy matrix containing 0/1, returns an integer, indicating the number of islands. You should not modify the matrix that is passed to you.
Hint
There are two ways to solve this problem.
The first way consists in translating the matrix into a graph, where each node represents a position in the matrix containing a 1. For instance, the second matrix above would be translated into a graph with nodes (0, 3), (1, 4), (1, 5). Edges connect adjacent nodes. You can then use the algorithm for graph reachability to tell which nodes belong to the same island.
The second way consists in implementing the reachability algorithm on top of the matrix directly.
You can choose either way.
Note that if you have a matrix a as above,
np.argwhere(a)
returns the positions in a that are 1.
import numpy as np
# You can define here any auxiliary function you wish.
### YOUR CODE HERE
def count_the_islands(m):
"""Returns the number of islands in the matrix m."""
# My solution takes 14 lines of code.
### YOUR CODE HERE
### 4 points: simple tests.
a = np.array([
[0, 0, 1, 1, 0, 0],
[0, 1, 1, 0, 0, 1],
[0, 1, 0, 0, 1, 1]
])
assert count_the_islands(a) == 2
a = np.zeros((10, 12))
assert count_the_islands(a) == 0
a = np.ones((10, 12))
assert count_the_islands(a) == 1
a = np.array([
[0, 0, 1, 1, 0, 0],
[0, 1, 1, 0, 0, 1],
[0, 1, 0, 0, 1, 1],
[0, 1, 1, 0, 0, 1],
[0, 1, 0, 0, 1, 1]
])
assert count_the_islands(a) == 2
assert count_the_islands(1 - a) == 2
a = np.identity(7)
assert count_the_islands(a) == 7
assert count_the_islands(a) == 7
assert (a == np.identity(7)).all()
发表评论