This repository was archived by the owner on Nov 14, 2020. It is now read-only.
forked from davecom/ClassicComputerScienceProblemsInPython
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgraph.py
More file actions
134 lines (112 loc) · 5.63 KB
/
graph.py
File metadata and controls
134 lines (112 loc) · 5.63 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
# graph.py
# From Classic Computer Science Problems in Python Chapter 4
# Copyright 2018 David Kopec
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
from typing import TypeVar, Generic, List, Optional
from edge import Edge
V = TypeVar('V') # type of the vertices in the graph
class Graph(Generic[V]):
def __init__(self, vertices: List[V] = []) -> None:
self._vertices: List[V] = vertices
self._edges: List[List[Edge]] = [[] for _ in vertices]
@property
def vertex_count(self) -> int:
return len(self._vertices) # Number of vertices
@property
def edge_count(self) -> int:
return sum(map(len, self._edges)) # Number of edges
# Add a vertex to the graph and return its index
def add_vertex(self, vertex: V) -> int:
self._vertices.append(vertex)
self._edges.append([]) # add empty list for containing edges
return self.vertex_count - 1 # return index of added vertex
# This is an undirected graph,
# so we always add edges in both directions
def add_edge(self, edge: Edge) -> None:
self._edges[edge.u].append(edge)
self._edges[edge.v].append(edge.reversed())
# Add an edge using vertex indices (convenience method)
def add_edge_by_indices(self, u: int, v: int) -> None:
edge: Edge = Edge(u, v)
self.add_edge(edge)
# Add an edge by looking up vertex indices (convenience method)
def add_edge_by_vertices(self, first: V, second: V) -> None:
u: int = self._vertices.index(first)
v: int = self._vertices.index(second)
self.add_edge_by_indices(u, v)
# Find the vertex at a specific index
def vertex_at(self, index: int) -> V:
return self._vertices[index]
# Find the index of a vertex in the graph
def index_of(self, vertex: V) -> int:
return self._vertices.index(vertex)
# Find the vertices that a vertex at some index is connected to
def neighbors_for_index(self, index: int) -> List[V]:
return list(map(self.vertex_at, [e.v for e in self._edges[index]]))
# Lookup a vertice's index and find its neighbors (convenience method)
def neighbors_for_vertex(self, vertex: V) -> List[V]:
return self.neighbors_for_index(self.index_of(vertex))
# Return all of the edges associated with a vertex at some index
def edges_for_index(self, index: int) -> List[Edge]:
return self._edges[index]
# Lookup the index of a vertex and return its edges (convenience method)
def edges_for_vertex(self, vertex: V) -> List[Edge]:
return self.edges_for_index(self.index_of(vertex))
# Make it easy to pretty-print a Graph
def __str__(self) -> str:
desc: str = ""
for i in range(self.vertex_count):
desc += f"{self.vertex_at(i)} -> {self.neighbors_for_index(i)}\n"
return desc
if __name__ == "__main__":
# test basic Graph construction
city_graph: Graph[str] = Graph(["Seattle", "San Francisco", "Los Angeles", "Riverside", "Phoenix", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston", "Detroit", "Philadelphia", "Washington"])
city_graph.add_edge_by_vertices("Seattle", "Chicago")
city_graph.add_edge_by_vertices("Seattle", "San Francisco")
city_graph.add_edge_by_vertices("San Francisco", "Riverside")
city_graph.add_edge_by_vertices("San Francisco", "Los Angeles")
city_graph.add_edge_by_vertices("Los Angeles", "Riverside")
city_graph.add_edge_by_vertices("Los Angeles", "Phoenix")
city_graph.add_edge_by_vertices("Riverside", "Phoenix")
city_graph.add_edge_by_vertices("Riverside", "Chicago")
city_graph.add_edge_by_vertices("Phoenix", "Dallas")
city_graph.add_edge_by_vertices("Phoenix", "Houston")
city_graph.add_edge_by_vertices("Dallas", "Chicago")
city_graph.add_edge_by_vertices("Dallas", "Atlanta")
city_graph.add_edge_by_vertices("Dallas", "Houston")
city_graph.add_edge_by_vertices("Houston", "Atlanta")
city_graph.add_edge_by_vertices("Houston", "Miami")
city_graph.add_edge_by_vertices("Atlanta", "Chicago")
city_graph.add_edge_by_vertices("Atlanta", "Washington")
city_graph.add_edge_by_vertices("Atlanta", "Miami")
city_graph.add_edge_by_vertices("Miami", "Washington")
city_graph.add_edge_by_vertices("Chicago", "Detroit")
city_graph.add_edge_by_vertices("Detroit", "Boston")
city_graph.add_edge_by_vertices("Detroit", "Washington")
city_graph.add_edge_by_vertices("Detroit", "New York")
city_graph.add_edge_by_vertices("Boston", "New York")
city_graph.add_edge_by_vertices("New York", "Philadelphia")
city_graph.add_edge_by_vertices("Philadelphia", "Washington")
print(city_graph)
# Reuse BFS from Chapter 2 on city_graph
import sys
sys.path.insert(0, '..') # so we can access the Chapter2 package in the parent directory
from Chapter2.generic_search import bfs, Node, node_to_path
bfs_result: Optional[Node[V]] = bfs("Boston", lambda x: x == "Miami", city_graph.neighbors_for_vertex)
if bfs_result is None:
print("No solution found using breadth-first search!")
else:
path: List[V] = node_to_path(bfs_result)
print("Path from Boston to Miami:")
print(path)