-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.py
139 lines (120 loc) · 4.16 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
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
134
135
136
137
138
139
# Copyright (c) 2018 Bart Massey
# Graph Representations
import random
# These classes support edge-list, adjacency-list and
# adjacency-matrix graph representations. The graphs
# may be directed or undirected. Undirected
# graphs will be explicitly represented with pairs
# of directed edges in all representations.
class GraphEL(object):
def __init__(self, nvertices, edges, directed=True):
"Create an edge-list graph."
self.nvertices = nvertices
self.directed = directed
if directed:
self.edges = edges
else:
self.edges = set()
for v1, v2 in edges:
self.edges.add((v1, v2))
self.edges.add((v2, v1))
self.edges = list(self.edges)
def undirected(self):
"Return the undirected version of a directed edge-list graph."
assert self.directed
return GraphEL(self.nvertices, self.edges, directed=False)
def toGraphAL(self):
"Return the adjacency-list representation of an edge-list graph."
return GraphAL(self.nvertices, self.edges, self.directed)
def __repr__(self):
return "GraphEL({}, {}, directed={})".format(
self.nvertices,
self.edges,
self.directed
)
def __eq__(self, g):
if type(g) is GraphAL:
g = g.toGraphEL()
if self.directed != g.directed:
return False
if self.nvertices != g.nvertices:
return False
return set(self.edges) == set(g.edges)
class GraphAL(object):
def __init__(self, nvertices, edges, directed=True):
"Create an adjacency-list graph."
self.nvertices = nvertices
self.directed = directed
if directed:
self.neighbors = [[] for _ in range(nvertices)]
for v1, v2 in edges:
self.neighbors[v1].append(v2)
else:
neighbors = [set() for _ in range(nvertices)]
for v1, v2 in edges:
neighbors[v1].add(v2)
neighbors[v2].add(v1)
self.neighbors = []
for v in range(nvertices):
self.neighbors.append(list(neighbors[v]))
def toGraphEL(self):
"Return the edge-list representation of an adjacency-list graph."
edges = []
for v1 in range(self.nvertices):
for v2 in self.neighbors[v1]:
edges.append((v1, v2))
return GraphEL(self.nvertices, edges, self.directed)
def __repr__(self):
return "GraphAL({}, {}, directed={})".format(
self.nvertices,
self.neighbors,
self.directed
)
def __eq__(self, g):
self.toGraphEL() == g
def cycle_shuffle(l):
"Produce a permutation of l in cyclic order."
n = len(l)
for i in range(n-1):
j = random.randrange(i+1, n)
l[i], l[j] = l[j], l[i]
def randgraph(nvertices, nedges):
"""Produce a random connected directed graph
with nvertices vertices and nedges "extra" edges."""
assert nedges <= nvertices * (nvertices - 1) - (nvertices - 1)
edges = set()
line = list(range(nvertices))
cycle_shuffle(line)
for i in range(len(line) - 1):
edges.add((line[i], line[i+1]))
all_edges = [(v1, v2)
for v1 in range(nvertices)
for v2 in range(nvertices)
if v1 != v2]
assert len(all_edges) == nvertices * (nvertices - 1)
random.shuffle(all_edges)
if nedges > 0:
for e in all_edges:
if e not in edges:
edges.add(e)
nedges -= 1
if nedges <= 0:
break
return GraphEL(nvertices, list(edges))
g = randgraph(4, 0)
print(g)
print(g.toGraphAL())
g = g.undirected()
print(g)
print(g.toGraphAL())
for _ in range(100):
nvertices = random.randrange(2, 20)
max_edges = nvertices * (nvertices - 1)
max_nedges = max_edges - nvertices + 1
nedges = random.randrange(max_nedges + 1)
def roundtrip(g_el):
g_al = g_el.toGraphAL()
assert g_el == g_al.toGraphEL()
g_el = randgraph(nvertices, nedges)
roundtrip(g_el)
roundtrip(g_el.undirected())