-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathsets.py
More file actions
38 lines (34 loc) · 1.26 KB
/
sets.py
File metadata and controls
38 lines (34 loc) · 1.26 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
## Some applicatoins that can be solved by using a set structure
## Python has built-in support for set
## Graph Walk Problem
## Find all the vertices of a DIRECTED graph that can be reached
## from a given vertex along the graph edges. The program should
## run in time Cm, where m is the total number of edges leaving
## the reachable vertices and C is a constant
## AHA: This a typical tree-walk (backtracking) algorithm, the
## output is a spanning tree rooted at the start node.
## A GRAPH is represented as a dict of node -> set(connected nodes...)
## Solution: change the structure of explored to perserve the spanning
## tree structure
def graph_walk(start, graph):
explored, frontier = {start: None}, [start]
while frontier:
u = frontier.pop()
for v in graph[u].difference(explored):
explored[v] = u
frontier.append(v)
return explored
## Tests
if __name__ == '__main__':
## test graph_walk
g1 = {
'a': set(['b', 'd']),
'b': set(['c']),
'c': set(),
'd': set(),
'e': set(['d', 'f']),
'f': set(),
}
assert graph_walk('a', g1) == {'a': None, 'c': 'b', 'b': 'a', 'd': 'a'}
assert graph_walk('e', g1) == {'e': None, 'd': 'e', 'f': 'e'}
print 'all tests pass'