4

①有向グラフが木構造か木構造でないかの判定方法を教えて下さい。
②rootは入力ですか

よろしくお願いします。

(参考)DOT言語
https://ja.wikipedia.org/wiki/DOT%E8%A8%80%E8%AA%9E
(参考)WebGraphviz is Graphviz in the Browser
http://www.webgraphviz.com/

(判定)
有向グラフが木構造
digraph graphname {a -> b -> c;b -> d; }

有向グラフが木構造とならない
digraph graphname {a -> b -> c;b -> d;c ->d}

2 件の回答 2

4

ライブラリ・ツール

  • PyDotPluspydot にはDOT言語をパースしてグラフ構造を構築する能力があります。
  • NetworkXは内部的にPyDotPlusを利用する事が出来て、作ったグラフ構造に対して木構造か判定する is_tree という関数も持っています。
  • Any Python Tree Data (anytree) は木構造の操作に特化したライブラリです。
  • Graphviz の出力形式には plainjson がありますので、 dot コマンドでこれらの形式に変換し、パースで楽をする方法もあります。
    (私の手元の環境では json は非サポートでした。コンパイルオプションなどに依存するのかも知れません)

木構造の判定

判定方法は大まかに、

  • グラフ構造を構築した後、一気に探索してチェックする方法
  • ノード間の接続が行なわれる都度、その接続が木構造として許されるかチェックする方法

の二つに分けられるかと思います。
前者は 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 -Tplainplain 形式にしています。

2
  • 有向グラフにおける森がよくわからないのですが { a -> b; a -> c; d -> b; d -> c; } は森ですか?
    – nekketsuuu
    Commented 2017年5月11日 2:16
  • @nekketsuuu 森の判定に補足しましたが、字数もあり少しだけにしました。 まだ疑問がありましたら、新しい質問として投稿していただくのがよいと思います。 間違いの指摘や、正確な説明をして下さる方がいらっしゃるかも知れませんし。
    – mjy
    Commented 2017年5月14日 2:38
4

最初に無向木の場合を説明して、それから有向木の場合の説明をします。

(無向)木とは「連結でループがないグラフ」のことなので、これをチェックすれば良いです。つまり、与えられたグラフを適当な頂点から探索することで連結性を確かめ、さらに深さ優先探索などで閉路があるかチェックすれば良いです(実はこれらは同時にできます)。

有向木の場合、どういう定義で有向木と言っているのかを確認してください。向きを消したときに木になっているだけで良いのなら、上と同じアルゴリズムで有向木かどうかを判定できます。根となりうる頂点がどこか気になるなら、入次数が0の頂点を探せば良いです。根から葉に向かって有向路があることを要求する(根付き有向木)なら、根となりうる頂点から探索を始め、辺の向きを気にしながら探索すると良いです。

また、実際にプログラムを動かすにはDOT言語を解釈する部分(字句解析、構文解析)も必要になるかと思います。この部分は自作しても良いですし、Pythonならgraphvizというパッケージを使うのも良いと思います (ドキュメントにサンプルコードが載っています)。 graphviz パッケージはグラフ上を走査するには向いていなさそうなので、mjyさんの回答にあるように pydotplusNetworkX をご使用ください。以下 Python 3 と pydotplus を使って DOT ファイルを読み込むサンプルコードです。

  • sample.dot

    graph samplegraph {
          a -- b -- c;
          b -- d;
    }
    
  • sample.py

    import pydotplus
    
    dotfile = open('sample.dot', 'r')
    graph = pydotplus.parser.parse_dot_data(dotfile.read())
    dotfile.close()
    
    print(graph.to_string())
    
  • 実行結果

    $ python sample.py 
    graph samplegraph {
    a -- b;
    b -- c;
    b -- d;
    }
    
2
  • モジュール graphviz にはDOT言語をパースする機能があるのでしょうか? こちらの質問 につながっているようなので、出来るか出来ないかだけでも明記しておくと親切かと思います。
    – mjy
    Commented 2017年5月14日 2:41
  • @mjy ご指摘ありがとうございます。すっかり忘れていて申し訳ありません。追記いたしました。
    – nekketsuuu
    Commented 2017年7月7日 21:54

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。