Snippets
Revised by
orrp
012dd98
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 | # -*- coding: utf-8 -*-
# By orrp (http://www.wisdom.weizmann.ac.il/~orrp/).
# Draws the Margulis-Gabber-Galil construction.
# Click on nodes to highlight their neighbors and view the conductance
# of the resulting set.
import argparse
import sys
import networkx as nx
from matplotlib import pyplot as plt
GRAPH_COLOR = '#F1F1F1'
SET_COLOR = '#FF0000'
BOUNDARY_COLOR = '#FFB3B3'
NODE_SIZE = None # Defaults to something nice.
def flatten(ll):
"""Flattens a list of lists into a 1-dimensional list."""
return [x for l in ll for x in l]
class MGG:
def __init__(self, n):
self._n = n
self._set = []
# Construct MGG_n
edges = [((x, y), v) for x in range(n)
for y in range(n) for v in self.get_neighbors((x, y))]
self._graph = nx.Graph(edges)
self.draw()
# Listen for click
self.cid = plt.gca().figure.canvas.mpl_connect('button_press_event', self)
def set_set(self, new_set):
self._set = new_set
# The MGG construction
def plus(self, a, b):
return (a + b) % self._n
def S(self, u):
return u[0], self.plus(u[1], u[0])
def S_inverse(self, u):
return u[0], self.plus(u[1], -u[0])
def T(self, u):
return self.plus(u[0], u[1]), u[1]
def T_inverse(self, u):
return self.plus(u[0], -u[1]), u[1]
def get_neighbors(self, u):
"""Returns list of all edges incident at u as a list of pairs"""
nbs = [self.S(u), self.S_inverse(u), self.T(u), self.T_inverse(u)]
nbs += [(u[0], self.plus(u[1], 1)), (u[0], self.plus(u[1], -1)),
(self.plus(u[0], 1), u[1]), (self.plus(u[0], -1), u[1])]
return nbs
# Drawing
def cross_edges(self, s, t):
"""Returns a list of edges that cross from s to t, where s and t are lists of nodes."""
return [edge for edge in self._graph.edges()
if (edge[0] in s and edge[1] in t) or (edge[0] in t and edge[1] in s)]
def draw(self):
# So that the graph is drawn as a grid
pos = dict([(n, n) for n in self._graph.nodes()])
# Draw rest of graph
print(pos)
nx.draw_networkx(self._graph, node_color=GRAPH_COLOR, node_size=NODE_SIZE,
edge_color=GRAPH_COLOR, pos=pos, with_labels=False)
# Draw set edges
set_edges = self.cross_edges(self._set, self._set)
nx.draw_networkx(self._graph, nodelist=self._set,
node_color=SET_COLOR, node_size=NODE_SIZE,
edgelist=set_edges, edge_color=SET_COLOR, pos=pos, with_labels=False)
# Draw boundary edges
set_complement = [u for u in self._graph.nodes() if u not in self._set]
boundary_edges = self.cross_edges(self._set, set_complement)
boundary_nodes = [u for u in flatten(
boundary_edges) if u not in self._set]
nx.draw_networkx(self._graph, nodelist=boundary_nodes,
node_color=BOUNDARY_COLOR, node_size=NODE_SIZE,
edgelist=boundary_edges, edge_color=BOUNDARY_COLOR,
pos=pos, with_labels=False)
# Draw text
text = "S="
if self._set:
text += "{" + str(self._set)[1:-1] + "}"
else:
text += "∅"
set_density = min(len(self._set), len(set_complement))
if set_density > 0:
boundary_density = len(boundary_edges)
text += "\nΦ(S)=" + str(boundary_density) + "/" + str(set_density) + \
"≅" + str(boundary_density / float(set_density))
plt.gca().set_title(text)
# Handling user input
def closest_node(self, point):
return int(round(point[0])) % self._n, int(round(point[1])) % self._n
def __call__(self, event):
if event.inaxes != plt.gca().axes:
return
event_node = (self.closest_node((event.xdata, event.ydata)))
if event_node in self._set:
self._set = [u for u in self._set if u != event_node]
else:
self._set.append(event_node)
self.draw()
plt.gca().figure.canvas.draw()
if __name__ == '__main__':
if sys.version_info[0] < 3:
print("Python 3 or a more recent version is required.")
exit(1)
parser = argparse.ArgumentParser(
description="Play around with the Margulis-Gabber-Galil construction")
parser.add_argument(dest='n', type=int, metavar='n',
help='modulus on which the graph will be constructed (integer)')
MGG(parser.parse_args().n)
plt.show()
|
You can clone a snippet to your computer for local editing. Learn more.