-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.py
97 lines (77 loc) · 2.78 KB
/
graph.py
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
#-----------------------------------------------------------------------
# graph.py
#-----------------------------------------------------------------------
import sys
import stdlib.stdio as stdio
from stdlib.instream import InStream
#-----------------------------------------------------------------------
class Graph:
# Construct a new Graph object. If a filename is specified,
# populate the Graph object by reading data from the specified
# file with the specified delimiter.
def __init__(self, filename=None, delimiter=None):
self._e = 0
self._adj = dict()
if filename is not None:
instream = InStream(filename)
while instream.hasNextLine():
line = instream.readLine()
names = line.split(delimiter)
for i in range(1, len(names)):
self.addEdge(names[0], names[i])
# Add an edge to self between vertex v and vertex w.
def addEdge(self, v, w):
if not self.hasVertex(v): self._adj[v] = set()
if not self.hasVertex(w): self._adj[w] = set()
if not self.hasEdge(v, w):
self._e += 1
self._adj[v].add(w)
self._adj[w].add(v)
# Return an iterable collection containing all neighbors of
# vertex v in self.
def adjacentTo(self, v):
return iter(self._adj[v])
# Return an iterable collection of all vertices in self.
def vertices(self):
return iter(self._adj)
# Return True if vertex v is in self, and False otherwise.
def hasVertex(self, v):
return v in self._adj
# Return True if v-w is an edge in self, and False otherwise.
def hasEdge(self, v, w):
return w in self._adj[v]
# Return the number of vertices in self.
def countV(self):
return len(self._adj)
# Return the number of edges in self.
def countE(self):
return self._e
# Return the degree of vertex v of self.
def degree(self, v):
return len(self._adj[v])
# Return a string representation of self.
def __str__(self):
s = ''
for v in self.vertices():
s += v + ' '
for w in self.adjacentTo(v):
s += w + ' '
s += '\n'
return s
#-----------------------------------------------------------------------
# For testing. Accept string file as a command-line argument. Create a
# Graph object by reading from file. Write the Graph object to standard
# output.
def main():
file = sys.argv[1]
graph = Graph(file)
stdio.writeln(graph)
if __name__ == '__main__':
main()
#-----------------------------------------------------------------------
# python graph.py tinygraph.txt
# A G H B C
# G A C
# H A B
# B A H C
# C A G B