61 lines
1.8 KiB
Python
Executable File
61 lines
1.8 KiB
Python
Executable File
#!/usr/bin/python
|
|
|
|
# outputs the automaton as a graphviz dot file, arranging the vertices
|
|
# in levels according to their distance from the starting vertex
|
|
# to convert to a PDF, run:
|
|
# ./dot_graph.py | dot -Tpdf > output.pdf
|
|
|
|
import coxeter_automaton
|
|
from collections import deque
|
|
|
|
coxeter_matrix = [[1, 3, 3],
|
|
[3, 1, 3],
|
|
[3, 3, 1]]
|
|
|
|
# coxeter_matrix = [[1, 2, 0, 0, 0, 2],
|
|
# [2, 1, 2, 0, 0, 0],
|
|
# [0, 2, 1, 2, 0, 0],
|
|
# [0, 0, 2, 1, 2, 0],
|
|
# [0, 0, 0, 2, 1, 2],
|
|
# [2, 0, 0, 0, 2, 1]]
|
|
|
|
#coxeter_matrix = [[1, 0, 0],
|
|
# [0, 1, 0],
|
|
# [0, 0, 1]]
|
|
|
|
graph = coxeter_automaton.generate_automaton_coxeter_matrix(coxeter_matrix, lex_reduced = True)
|
|
|
|
#graph = coxeter_automaton.even_graph(graph)
|
|
|
|
colors = {0: "red", 1: "darkgreen", 2: "blue", 3: "orange", 4: "black", 5: "gray"}
|
|
|
|
todo = deque([0])
|
|
distances = [None]*len(graph)
|
|
distances[0] = 0
|
|
|
|
while todo:
|
|
node = todo.pop()
|
|
for newnode in graph[node]:
|
|
if newnode:
|
|
if not distances[newnode] or distances[newnode] > distances[node] + 1:
|
|
distances[newnode] = distances[node] + 1
|
|
todo.appendleft(newnode)
|
|
|
|
max_distance = max(filter(None, distances))
|
|
nodes_by_distance = [[] for _ in range(max_distance+1)]
|
|
for n,d in enumerate(distances):
|
|
if d != None:
|
|
nodes_by_distance[d].append(n)
|
|
|
|
print('digraph test123 {')
|
|
for dn in nodes_by_distance:
|
|
print('{rank = same; %s}' % "; ".join([str(x) for x in dn]))
|
|
|
|
for i,node in enumerate(graph):
|
|
for edge,j in enumerate(node):
|
|
if j:
|
|
# print('{i:d} -> {j:d} [color={color}];'.format(i = i, j = j, color = "black"))
|
|
print('{i:d} -> {j:d} [color={color}];'.format(i = i, j = j, color = colors[edge]))
|
|
|
|
print('}')
|