ライブラリ・ツール
木構造の判定
判定方法は大まかに、
- グラフ構造を構築した後、一気に探索してチェックする方法
- ノード間の接続が行なわれる都度、その接続が木構造として許されるかチェックする方法
の二つに分けられるかと思います。
前者は nekketsuuu さんの回答 が詳しいですね。
後者の場合、親子関係のエッジの作成が試みられる度に、
- 子になるノードに既に祖先があってはならない(その時点では根でなければいけない)
- 子になるノードが親になるノードの根であってはならない
の2点をチェックします。
グラフ中に木として不正な構造が無いならば、エッジは常に根の数だけノードより少ないです。
よって、森(お互いに接続されていない部分があり、根が複数ある)かどうかは、
# 成り立つならば森
エッジの総数 < (ノードの総数 - 1)
で判定出来ます。
(以上は Wikipedia に出ている絵を見て適当に考えた事ですので、実用に供するには精査が必要です)
例: NetworkX の利用
NetworkX と、PyDotPlus のインストールが必要です。
# Ubuntu の場合
$ sudo apt install python3-networkx
$ sudo apt install python3-pydotplus
コード:
#!/usr/bin/python3
import networkx
def check(dot_file):
graph = networkx.nx_pydot.read_dot(dot_file)
return networkx.is_tree(graph)
if __name__ == "__main__":
import sys
is_tree = check(sys.stdin)
print("Yes, 木構造です" if is_tree else "No, 木構造ではありません")
exit(0 if is_tree else 1)
複数のグラフがある場合や、グラフがノードを持たない場合はエラーになります。
実行:
$ ./is_tree_by_nx.py <tree.dot
Yes, 木構造です
例: エッジ毎の判定
上で説明した逐次的な方法です。
DOT言語で定義されたグラフを構築する事はせず、各ノードは自分の根を特定するのに必要な情報だけを保持します。
DOT言語のパースには、dot
コマンドの plain
形式による出力 を利用します。
コード:
#!/usr/bin/python3
class Node():
def __init__(self, name):
self._name = name
self._latest_root = self
def __repr__(self):
return "<Node('{}')>".format(self._name)
def is_root(self):
return self._latest_root is self
def search_root(self):
if not self._latest_root.is_root():
self._latest_root = self._latest_root.search_root()
return self._latest_root
def connect_child(self, child):
if not child.is_root():
return (False,
"{child} は既に根ではなく、祖先を持っているので、"
"新たに {self} の子になる事は出来ません".format(**locals()))
elif child is self.search_root():
return (False,
"{child} は {self} の祖先(根)なので、"
"{self} の子になる事は出来ません".format(**locals()))
else:
child._latest_root = self.search_root()
return True, ""
def check(dot_plain_file):
nodes = {}
graphs = 0
edges = 0
for line in dot_plain_file:
words = line.split()
if not len(words):
continue
command = words[0]
if command == "node":
node_name = words[1]
nodes[node_name] = Node(node_name)
elif command == "edge":
edges += 1
parent = nodes[words[1]]
child = nodes[words[2]]
ok, msg = parent.connect_child(child)
if not ok:
return False, msg
elif command == "graph":
graphs += 1
if graphs > 1:
raise Exception("入力データ中に複数のグラフがあります")
# debug: print node list
for node in nodes.values():
print(" #{}: root={}".format(node, node.search_root()))
if edges < len(nodes) - 1:
return False, "複数の木構造を含んでいます(森)"
else:
return True, "nodes={}, edges={}, root={}".format(
len(nodes),
edges,
nodes[node_name].search_root() if len(nodes) else "")
if __name__ == "__main__":
import sys
is_tree, msg = check(sys.stdin)
print("Yes, 木構造です:" if is_tree else "No, 木構造ではありません:", msg)
exit(0 if is_tree else 1)
グラフがノードを持たない場合も木構造と見なしています。
複数のグラフがある場合はエラーにしています。
実行:
$ dot -Tplain tree.dot |./is_tree.py
#<Node('a')>: root=<Node('a')>
#<Node('d')>: root=<Node('a')>
#<Node('c')>: root=<Node('a')>
#<Node('b')>: root=<Node('a')>
Yes, 木構造です: nodes=4, edges=3, root=<Node('a')>
$ dot -Tplain not_tree.dot |./is_tree.py
No, 木構造ではありません: <Node('d')> は既に根ではなく、祖先を持っているので、新たに <Node('c')> の子になる事は出来ません
dot -Tplain
で plain
形式にしています。