66 lines
1.5 KiB
Python
66 lines
1.5 KiB
Python
#!/usr/bin/env python3
|
|
|
|
import sys
|
|
|
|
import matplotlib.pyplot as plt
|
|
import networkx
|
|
import networkx as nx
|
|
|
|
input_file = sys.argv[1]
|
|
|
|
G = nx.Graph()
|
|
with open(input_file) as fd:
|
|
for line in fd.readlines():
|
|
a, b = line.rstrip().split("-")
|
|
G.add_edge(a, b)
|
|
|
|
trio_cliques: list[list[str]] = list()
|
|
lan = None
|
|
for clique in nx.enumerate_all_cliques(G):
|
|
if lan is None or len(clique) > len(lan):
|
|
lan = clique
|
|
if len(clique) != 3:
|
|
continue
|
|
if not any(c.startswith("t") for c in clique):
|
|
continue
|
|
trio_cliques.append(clique)
|
|
|
|
|
|
part1_ans = len(trio_cliques)
|
|
assert lan is not None
|
|
part2_ans = ",".join(sorted(lan))
|
|
|
|
print(f"{part1_ans=}")
|
|
print(f"{part2_ans=}")
|
|
|
|
|
|
trio_nodes = set(node for trio_clique in trio_cliques for node in trio_clique)
|
|
trio_edges = set(
|
|
edge
|
|
for clique in trio_cliques
|
|
for edge in list(nx.edge_boundary(G, clique, clique))
|
|
)
|
|
lan_edges = set(nx.edge_boundary(G, lan, lan))
|
|
|
|
for node in trio_nodes:
|
|
G.nodes[node]["color"] = "green"
|
|
for edge in trio_edges:
|
|
G.edges[edge]["color"] = "green"
|
|
G.edges[edge]["weight"] = 2
|
|
|
|
for node in lan:
|
|
G.nodes[node]["color"] = "red"
|
|
for edge in lan_edges:
|
|
# G.edges[edge]["color"] = "red"
|
|
G.edges[edge]["weight"] = 5
|
|
|
|
node_colors = [G.nodes[node].get("color", "blue") for node in G.nodes()]
|
|
edge_colors = [G.edges[edge].get("color", "blue") for edge in G.edges()]
|
|
node_pos = nx.layout.spring_layout(G)
|
|
|
|
|
|
nx.draw(
|
|
G, node_color=node_colors, edge_color=edge_colors, pos=node_pos, with_labels=True
|
|
)
|
|
plt.show()
|