はじめに
約30年前に大学で習った、全域木の列挙アルゴリズムをPythonで実装してみましたので、ご紹介します。
全域木とは、元のグラフの全ての点を含む木のことです。
アルゴリズム
- グラフの式表現を求めて、式表現を展開して列挙します。
- 例えば、三角形のグラフで各辺をそれぞれa,b,cとすると、式表現は組(abc)となり、これを展開するとab/ac/bcとなります。
- グラフの式表現は以下のように求められます。
- 辺の最初の式表現として、アルファベット1文字を持たせます。
- グラフは、式表現を維持しながら辺または辺と点を削除できます。
- グラフが1点になったときに式表現が求められます。
- グラフGの式表現（Expr(G))は、任意の1つの辺Eを選んで以下のように変形できます。(標準ルール)
- Expr(G) ＝ 和(積(組(Expr(E)), Expr(GからEを削除)), 積(Expr(E), Expr(GからEを縮約1)))
式表現には、以下の種類があります。
- 和(A, B): Aの要素とBの要素の和集合です。
- 積(A, B): Aの要素とBの要素の積集合(組合せて文字を並べたもの)です。
- 組(A): Aの要素ごとに、1文字づつ消去して展開します。例えば、組(abc)は、abとacとbcの3つに展開されます。
先ほどの標準ルールだけでもできますが、計算量を減らすために、特定のケースのルールを追加します。(標準ルールから導かれます)
- 辺Eが自己ループの場合: Expr(G) = 積(組(Expr(E)), Expr(GからEを削除))
- 辺Eの片方の端点の次数(接続する辺の数)=1の場合: Expr(G) = 積(Expr(E), Expr(GからEを縮約))
- 辺Eと辺Fが点Vで接続しており、点Vの次数=2の場合: Expr(E) = 積(Expr(E), Expr(F))として、辺Fを縮約した後のグラフについて求めます。
Pythonで実行してみる
クラス定義をします。
python3
from itertools import combinations, product
from collections import namedtuple
Union = namedtuple('Union', 'l r') # 和
Produ = namedtuple('Produ', 'l r') # 積
Combi = namedtuple('Combi', 'e') # 組
class Edge:
def __init__(self, u, v, e):
self.u = u
self.v = v
self.e = e
def __repr__(self):
return '<%s %s %s>'%(self.u, self.v, self.e)
class Graph:
def __init__(self, num_nodes, edges):
self.nodes = [[] for _ in range(num_nodes)]
self.edges = []
for i, (u, v) in enumerate(edges):
self.edges.append(Edge(u, v, chr(97 + i)))
self.nodes[u].append(i)
self.nodes[v].append(i)
def __repr__(self):
return str(self.edges)
def spanning_tree(self):
res = Graph._reduct(self.nodes.copy(), self.edges.copy())
return sorted(Graph._expand(res))
@staticmethod
def _reduct(nodes, edges):
if not edges:
return '' if len(nodes) == 1 else None
for i, e in enumerate(edges): # 自己ループ
if e.u == e.v:
Graph._erase(nodes, edges, i)
return Produ(l=Combi(e=e.e), r=Graph._reduct(nodes, edges))
for con in nodes: # 次数=1
if len(con) == 1:
e = edges[con[0]]
Graph._erase(nodes, edges, con[0])
return Produ(l=e.e, r=Graph._reduct(nodes, edges))
for con in nodes: # 次数=2
if len(con) == 2:
e = edges[con[0]]
edges[con[0]] = Edge(e.u, e.v, Produ(l=edges[con[0]].e,
r=edges[con[1]].e))
Graph._shrink(nodes, edges, con[1])
return Graph._reduct(nodes, edges)
e = edges[0]
nodes2, edges2 = nodes.copy(), edges.copy()
Graph._erase(nodes, edges, 0)
Graph._shrink(nodes2, edges2, 0)
return Union(l=Produ(l=Combi(e=e.e), r=Graph._reduct(nodes, edges)),
r=Produ(l=e.e, r=Graph._reduct(nodes2, edges2)))
@staticmethod
def _erase(nodes, edges, k):
for a, con in enumerate(nodes):
nodes[a] = [b if b < k else b-1 for b in con if b != k]
del edges[k]
@staticmethod
def _shrink(nodes, edges, k):
e = edges[k]
dn = max(e.u, e.v)
sn = e.u+e.v-dn
nodes[sn] = nodes[sn] + nodes[dn]
for a, con in enumerate(nodes):
nodes[a] = [b if b < k else b-1 for b in con if b != k]
for a, ed in enumerate(edges):
u = sn if ed.u == dn else ed.u if ed.u < dn else ed.u-1
v = sn if ed.v == dn else ed.v if ed.v < dn else ed.v-1
edges[a] = Edge(u, v, ed.e)
del edges[k]
del nodes[dn]
@staticmethod
def _expand(ex):
if ex is None:
return set()
elif isinstance(ex, str):
return set(ex) if ex else {''}
elif isinstance(ex, Combi):
exe = Graph._expand(ex.e)
return set.union(*(set(''.join(s) for s in
combinations(e, len(e)-1)) for e in exe))
exl = Graph._expand(ex.l)
exr = Graph._expand(ex.r)
if isinstance(ex, Union):
return exl.union(exr)
return {''.join(sorted((i+j))) for i, j in product(exl, exr)}
三角グラフで試してみます。
python3
g = Graph(3, [(0,1), (1,2), (2,0)])
print(g.spanning_tree())
>>>
['ab', 'ac', 'bc']
4点の完全グラフで試してみます。
python3
g = Graph(4, [(0,1), (1,2), (2,3), (3,0), (0,2), (1,3)])
print(g.spanning_tree())
>>>
['abc', 'abd', 'abf', 'acd', 'ace', 'acf', 'ade', 'aef',
'bcd', 'bce', 'bde', 'bdf', 'bef', 'cdf', 'cef', 'def']
ちなみに、このPythonは85行ですが、Cで書くと500行で、C#で書くと330行ほどでした。
以上
-
辺を縮約するとは、その辺を長さ0にして、両端の点を1つに変える操作です。 ↩