-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.py
61 lines (41 loc) · 1.33 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
import re
from xml.dom.minidom import Document, parseString
class graph():
def __init__(self):
self.node_ch = {}
self.node_pa = {}
def nodes(self):
return list(self.node_ch.keys())
def edges(self):
return [ a for a in self._edges() ]
def _edges(self):
for n, childs in self.node_ch.items():
for child in childs:
yield (n, child)
def childrens(self, node):
return self.node_ch[node]
def parents(self, node):
return self.node_pa[node]
def has_node(self, node):
return node in self.node_ch
def add_node(self, node):
if node not in self.node_ch:
self.node_ch[node] = list()
self.node_pa[node] = list()
def add_edge(self, edge):
u, v = edge
if v in self.node_ch[u] and u in self.node_pa[v]:
#print('Edge exist!')
pass
else:
self.node_ch[u].append(v)
self.node_pa[v].append(u)
def read_from_file(self, filename):
with open(filename, 'r') as f:
for line in f:
match = re.match('(\d+),(\d+)', line)
if match:
u, v = match.groups()
self.add_node(u)
self.add_node(v)
self.add_edge((u, v))