-
Notifications
You must be signed in to change notification settings - Fork 0
/
generate.py
executable file
·147 lines (115 loc) · 4.81 KB
/
generate.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
140
141
142
143
144
145
146
147
import argparse
import json
import matplotlib.pyplot as plt
import math
import networkx as nx
import random
class RandomGraphGenerator:
def __init__(self, args):
self.args = args
def generate(self):
G = self.create_random_planar_graph(self.args.nodes, self.args.nprob, self.args.eprob)
is_planar, embedding = nx.check_planarity(G)
# sanity check
assert is_planar
# We assume that dividing by two always gives the correct amount of undirected
# edges because we add all edges that do not violate planarity in our
# generation algorithm. Adding a back-edge to another edge does not violate
# planarity because if it would, the already existing edge would've been
# incorrect. Thus, we add all back-edges and have 2m directed edges and m
# undirected edges.
# That also means dividing by two always produces an integer.
# Sanity check for 2m edges.
assert len(embedding.edges()) % 2 == 0
return embedding, nx.planar_layout(embedding)
def create_random_planar_graph(self, n, node_prob, edge_prob):
G = nx.Graph()
G.add_nodes_from(range(n))
for i in random.sample(range(n), k=int(n * node_prob)):
for j in random.sample(range(n), k=int(n * edge_prob)):
if i == j:
continue
G.add_edge(i, j)
if not nx.is_planar(G):
G.remove_edge(i, j)
return G
class CircularGraphGenerator:
def __init__(self, args):
self.args = args
def generate(self):
G = nx.Graph()
root_node = 0
G.add_node(root_node)
SPACING = 1.0
layout = {0: [0.0,0.0]}
previous_ring = [root_node]
for n in range(self.args.rings):
# Add a new ring around the current graph
ring = list(range(G.order(), G.order() + self.args.nodes))
G.add_nodes_from(ring)
# Connect the nodes in the ring
for i in range(self.args.nodes-1):
G.add_edge(ring[i], ring[i+1])
G.add_edge(ring[-1], ring[0])
# Connect nodes of this ring with the previous ring
if len(previous_ring) == 1:
# First ring is only connected with the root node
for i in range(self.args.nodes):
G.add_edge(previous_ring[0], ring[i])
else:
for i in range(self.args.nodes):
G.add_edge(previous_ring[i], ring[i])
# Generate layout positions
for i in range(self.args.nodes):
angle = i/self.args.nodes*2.0*math.pi
dist = (n + 1) * SPACING
x = math.sin(angle) * dist
y = math.cos(angle) * dist
layout[ring[i]] = [x, y]
previous_ring = ring
is_planar, embedding = nx.check_planarity(G)
# sanity check
assert is_planar
return embedding, layout
def main():
parser = argparse.ArgumentParser(
description='Generate random planar graphs')
parser.add_argument('--nodes', type=int, help='max number of nodes', required=True)
parser.add_argument('--nprob', type=float, help='probability that a node is created', required=True)
parser.add_argument('--eprob', type=float, help='probability that an edge is created', required=True)
parser.add_argument('--rings', type=int, help='amount of rings for circular graph', default=3)
parser.add_argument('--type', type=str, help='type of the graph', choices=['random', 'circular'], default='random')
parser.add_argument('outfile', type=str, help='destination file')
args = parser.parse_args()
number_nodes = args.nodes
outfile = args.outfile
if args.type == 'random':
gen = RandomGraphGenerator(args)
else:
gen = CircularGraphGenerator(args)
embedding, layout = gen.generate()
if args.type == 'circular':
number_nodes *= args.rings
number_nodes += 1
with open(outfile, "w", encoding="utf-8") as f:
f.write(f"{number_nodes}\n{int(len(embedding.edges()) / 2)}\n")
for node, dest_nodes in embedding.get_data().items():
for dest in dest_nodes:
f.write(f"{node} {dest}\n")
print(f"Edges: {int(len(embedding.edges()) / 2)}")
print(f"Output in '{outfile}'.")
layout_json = []
for vertex, position in layout.items():
x = position[0]
y = position[1]
layout_json.append({
'id': vertex,
'x': x,
'y': y,
})
with open(outfile + '.layout.json', 'w') as f:
json.dump(layout_json, f)
nx.draw_networkx(embedding, pos=layout, with_labels=True)
plt.savefig('graph.pdf', format='pdf', bbox_inches='tight')
if __name__ == "__main__":
main()