261 lines
7.6 KiB
Python
261 lines
7.6 KiB
Python
from sys import argv
|
|
from pathlib import Path
|
|
from math import sin, cos, pi
|
|
|
|
from common import printc, printerr, replaceContent
|
|
|
|
class Matrix:
|
|
""" Adjacency matrix which supports 0 and 1 """
|
|
|
|
def __init__(self, matrix):
|
|
self.matrix = matrix
|
|
|
|
def __iter__(self):
|
|
return iter(self.matrix)
|
|
|
|
def __len__(self):
|
|
return len(self.matrix)
|
|
|
|
def __eq__(self, other):
|
|
return self.matrix == other
|
|
|
|
def __str__(self):
|
|
return "\n".join(' '.join('\033[32m1\033[0m' if b else '\033[31m0\033[0m' for b in line) for line in self)
|
|
|
|
def __getitem__(self, key):
|
|
return self.matrix[key]
|
|
|
|
def __setitem__(self, key, item):
|
|
self.matrix[key] = item
|
|
|
|
@classmethod
|
|
def fromGraph(cls, graph):
|
|
return graph.toMatrix()
|
|
|
|
@classmethod
|
|
def fromString(cls, string):
|
|
matrix = []
|
|
for line in string.split('\n'):
|
|
matrix.append([True if char == '1' else False for char in line])
|
|
|
|
if len(matrix) != len(matrix[0]):
|
|
raise ValueError('Matrix not covering all points')
|
|
|
|
return cls(matrix)
|
|
|
|
def toGraph(self):
|
|
nodes = [chr(i + 65) for i in range(len(self))]
|
|
|
|
edges = []
|
|
for i, line in enumerate(self):
|
|
edges += [(nodes[i],nodes[j]) for j, b in enumerate(line) if b]
|
|
|
|
return Graph(nodes, edges)
|
|
|
|
def toLaTeX(self):
|
|
return '\\begin{pmatrix}\n' \
|
|
+ '\n'.join(' ' + ' & '.join('1' if b else '0' for b in line) + ' \\\\' for line in self.matrix) \
|
|
+ '\n\\end{pmatrix}'
|
|
|
|
|
|
class Graph:
|
|
def __init__(self, nodes, edges): # Nodes = str, Edges = (str,str)
|
|
self.nodes = nodes
|
|
self.edges = edges
|
|
|
|
def __str__(self):
|
|
printc('Is undirected: ' + str(self.isUndirected()))
|
|
return \
|
|
f'Nodes: {" ".join(self.nodes)}\n' \
|
|
+ f'Edges: {" ".join(x+y for x,y in (self.undirectedEdgeSet() if self.isUndirected() else self.edges))}'
|
|
|
|
@classmethod
|
|
def fromMatrix(cls, matrix):
|
|
return matrix.toGraph()
|
|
|
|
@classmethod
|
|
def fromString(cls, string):
|
|
splitData = string.split('\n\n')
|
|
|
|
if splitData[0] == 'complete':
|
|
data1 = 'undirected'
|
|
nodes = [chr(i + 65) for i in range(int(splitData[1]))]
|
|
data2 = ' '.join(nodes)
|
|
data3 = '\n'.join([a+b for a in nodes for b in nodes if a != b])
|
|
elif splitData[0] == 'matrix':
|
|
return Graph.fromMatrix(Matrix.fromString(splitData[1]))
|
|
else:
|
|
data1, data2, data3 = splitData
|
|
|
|
graphType = data1
|
|
nodes = data2.split(' ')
|
|
edges = [(x,y) for x,y in data3.split('\n')]
|
|
|
|
if graphType == 'undirected':
|
|
edges = [(a,b) for a in nodes for b in nodes if (a,b) in edges or (b,a) in edges]
|
|
|
|
return cls(nodes, edges)
|
|
|
|
def toMatrix(self):
|
|
rows = []
|
|
for node in self.nodes:
|
|
rows.append([(node,node2) in self.edges for node2 in self.nodes])
|
|
return Matrix(rows)
|
|
|
|
def isUndirected(self):
|
|
matrix = self.toMatrix()
|
|
|
|
flipv = lambda matrix: list(reversed(matrix))
|
|
rot90cc = lambda matrix: list(list(x) for x in zip(*reversed(matrix)))
|
|
|
|
return matrix == rot90cc(flipv(matrix)) \
|
|
and all(matrix[i][i] == 0 for i in range(len(matrix)))
|
|
|
|
def undirectedEdgeSet(self):
|
|
edges = self.edges
|
|
if self.isUndirected():
|
|
edges = sorted(list(set((x,y) if x < y else (y,x) for x,y in edges)))
|
|
return edges
|
|
|
|
# def latexifyEulerPath(self):
|
|
# degrees = [sum(line) for line in self.toMatrix()]
|
|
|
|
# def latexifyEulerCircuit():
|
|
# pass
|
|
|
|
def getKruskalsSpanningTree(self, weigths): # weights = dict[str, int]
|
|
edges = []
|
|
connected_subgraphs = [set(v) for v in self.nodes]
|
|
|
|
if not all(n in ''.join(x+y for x,y in self.edges) for n in self.nodes):
|
|
printerr('Not all nodes are connected. There is no spanning tree to be made')
|
|
return
|
|
|
|
def find_subgraph_containing(v):
|
|
return [x for x in connected_subgraphs if v in x][0]
|
|
|
|
def merge_subgraphs_that_contains(u, v):
|
|
subgraph_v = find_subgraph_containing(v)
|
|
new_connected_subgraphs = [x for x in connected_subgraphs if v not in x]
|
|
new_connected_subgraphs = [subgraph_v.union(x) if u in x else x for x in new_connected_subgraphs]
|
|
return new_connected_subgraphs
|
|
|
|
sorted_edges = [ e for e in sorted(self.edges, key=lambda e: weigths[e[0] + e[1]]) ]
|
|
|
|
for u,v in sorted_edges:
|
|
if find_subgraph_containing(u) != find_subgraph_containing(v):
|
|
edges += [(u, v)]
|
|
connected_subgraphs = merge_subgraphs_that_contains(u, v)
|
|
|
|
edges += [(y,x) for x,y in edges]
|
|
|
|
return Graph(self.nodes, edges)
|
|
|
|
def toLaTeX(self):
|
|
zippedNodes = zip(self.nodes, generateNodeCoords(len(self.nodes)))
|
|
nodeString = '\n'.join(f'\\node ({name}) at ({x},{y}) {{${name}$}};' for name,(x,y) in zippedNodes)
|
|
|
|
if self.isUndirected():
|
|
edgeString = '\n'.join(f'\\draw ({x}) -- ({y});' for x,y in self.undirectedEdgeSet())
|
|
else:
|
|
edgeString = '\n'.join(
|
|
f'\\draw [-{{Latex[scale=1]}}, bend left=8] ({x}) to ({y});' if y != x and (y,x) in self.edges
|
|
else f'\\draw [-{{Latex[scale=1]}}] ({x}) to [{generateLoopInOutAngle(x, self.nodes)},looseness=8] ({y});' if x == y
|
|
else f'\\draw [-{{Latex[scale=1]}}] ({x}) to ({y});'
|
|
for x,y in self.edges
|
|
)
|
|
|
|
return (nodeString, edgeString)
|
|
|
|
def toLaTeXWithWeights(self, weights):
|
|
zippedNodes = zip(self.nodes, generateNodeCoords(len(self.nodes)))
|
|
nodeString = '\n'.join(f'\\node ({name}) at ({x},{y}) {{${name}$}};' for name,(x,y) in zippedNodes)
|
|
|
|
if self.isUndirected():
|
|
edgeString = '\n'.join(f'\\draw ({x}) -- ({y}) node [midway, above, sloped] (Tx{x+y}) {{{weights[x+y]}}};' for x,y in self.undirectedEdgeSet())
|
|
|
|
return (nodeString, edgeString)
|
|
|
|
|
|
def generateLoopInOutAngle(node, nodes):
|
|
baseAngle = 360 / len(nodes)
|
|
nodeNum = [i for i,n in enumerate(nodes) if n == node][0]
|
|
angle = nodeNum * baseAngle + 90
|
|
return f'out={angle + 15},in={angle - 15}'
|
|
|
|
|
|
def generateNodeCoords(n):
|
|
vectorLength = n / 2
|
|
degreeToTurn = (2 * pi) / n
|
|
|
|
|
|
nodeCoords = [(0, vectorLength)]
|
|
for node in range(n):
|
|
prev_x = nodeCoords[-1][0]
|
|
prev_y = nodeCoords[-1][1]
|
|
|
|
nodeCoords.append((
|
|
round(cos(degreeToTurn) * prev_x - sin(degreeToTurn) * prev_y, 5),
|
|
round(sin(degreeToTurn) * prev_x + cos(degreeToTurn) * prev_y, 5)
|
|
))
|
|
|
|
return nodeCoords
|
|
|
|
def extractWeights(string):
|
|
weights = dict()
|
|
lines = string.split('\n')
|
|
for i in range(4, len(lines)):
|
|
edge, weight = lines[i].split(' ')
|
|
weights[edge] = int(weight)
|
|
weights[edge[1] + edge[0]] = int(weight)
|
|
lines[i] = edge
|
|
return ('\n'.join(lines), weights)
|
|
|
|
def processFileContent(raw):
|
|
lines = raw.split('\n')
|
|
lines.pop(1)
|
|
outputType = lines.pop(0)
|
|
|
|
if lines[0] == 'kruskals':
|
|
lines[0] = 'undirected'
|
|
string, weights = extractWeights('\n'.join(lines))
|
|
graph1 = Graph.fromString(string)
|
|
graph2 = graph1.getKruskalsSpanningTree(weights)
|
|
return replaceContent(
|
|
(graph1.toLaTeXWithWeights(weights), graph2.toLaTeXWithWeights(weights)),
|
|
'Kruskals',
|
|
replaceF = lambda temp, cont:
|
|
temp.replace('%NODES1', cont[0][0])
|
|
.replace('%EDGES1', cont[0][1])
|
|
.replace('%NODES2', cont[1][0])
|
|
.replace('%EDGES2', cont[1][1])
|
|
)
|
|
|
|
|
|
graph = Graph.fromString('\n'.join(lines))
|
|
|
|
print(graph)
|
|
print(graph.toMatrix())
|
|
|
|
if outputType == 'toGraph':
|
|
content = graph.toLaTeX()
|
|
return replaceContent(
|
|
content,
|
|
'Graph',
|
|
replaceF = lambda temp, cont: temp.replace('%NODES', cont[0]).replace('%EDGES', cont[1])
|
|
)
|
|
else:
|
|
content = graph.toMatrix().toLaTeX()
|
|
return replaceContent(content, 'Matrix')
|
|
|
|
if __name__ == '__main__':
|
|
g = Graph.fromString('complete\n\n6')
|
|
print(g)
|
|
|
|
import random
|
|
|
|
d = dict()
|
|
for e in g.edges:
|
|
d[str(e)] = random.randint(0, 10)
|
|
|
|
print(g.getKruskalsSpanningTree(d)) |