-
Notifications
You must be signed in to change notification settings - Fork 0
/
GraphUtil.py
37 lines (30 loc) · 915 Bytes
/
GraphUtil.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
"""
A script having a set of simple functions to check graph properties.
"""
class UndirectedGraph:
def __init__(self, V, E):
self.V = V
self.E = E
def __str__(self):
graph_str = ''
for start in self.E.keys():
for stop in self.E[start]:
graph_str += start + ' ' + stop + '\n'
return graph_str
def check_vertex_cover(G, S):
"""
Returns True if set S is a vertex cover of the edge set E,
False otherwise.
S is implemented as a set
E is implemented as an adjacency list mapping a vertex to a list
of edges
"""
for start in G.E.keys():
if start in S:
# vertex start is already in the cover
# so we needn't check its corresponding edges
continue
for end in G.E[start]:
if not (end in S):
return False
return True