34537


①有向グラフが木構造か木構造でないかの判定方法を教えて下さい。  
②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}


CC BY-SA 3.0
2017-05-06T07:47:20.330
34481
2018-10-20T10:17:07.643
2018-10-20T10:17:07.643
17199
17199
question
python アルゴリズム graphviz dot グラフ理論
DOT言語の有向グラフが木構造か木構造でないかの判定方法を教えて下さい。


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

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

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

また、実際にプログラムを動かすにはDOT言語を解釈する部分（字句解析、構文解析）も必要になるかと思います。この部分は自作しても良いですし、
~~Pythonなら[`graphviz`](https://pypi.python.org/pypi/graphviz)というパッケージを使うのも良いと思います
([ドキュメントにサンプルコードが載っています](https://graphviz.readthedocs.io/en/stable/manual.html#using-
raw-dot))。~~ `graphviz`
パッケージはグラフ上を走査するには向いていなさそうなので、[mjyさんの回答](https://ja.stackoverflow.com/a/34537/19110)にあるように
[`pydotplus`](https://pypi.python.org/pypi/pydotplus) や
[NetworkX](http://networkx.github.io/) をご使用ください。以下 Python 3 と `pydotplus` を使って
DOT ファイルを読み込むサンプルコードです。

  * sample.dot
[code]     graph samplegraph {

          a -- b -- c;
          b -- d;
    }
    
[/code]

  * sample.py
[code]     import pydotplus

    
    dotfile = open('sample.dot', 'r')
    graph = pydotplus.parser.parse_dot_data(dotfile.read())
    dotfile.close()
    
    print(graph.to_string())
    
[/code]

  * 実行結果
[code]     $ python sample.py

    graph samplegraph {
    a -- b;
    b -- c;
    b -- d;
    }
    
[/code]


CC BY-SA 3.0
2017-05-06T14:17:35.350
34490
2017-07-07T22:25:43.317
2017-07-07T22:25:43.317
19110
19110
34481
answer


## ライブラリ・ツール

  * [PyDotPlus](https://github.com/carlos-jenkins/pydotplus)や [pydot](https://github.com/erocarrera/pydot) にはDOT言語をパースしてグラフ構造を構築する能力があります。
  * [NetworkX](https://github.com/networkx/networkx)は内部的にPyDotPlusを利用する事が出来て、作ったグラフ構造に対して木構造か判定する [`is_tree`](http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.tree.recognition.is_tree.html#is-tree) という関数も持っています。
  * [Any Python Tree Data (`anytree`)](http://anytree.readthedocs.io/en/latest/) は木構造の操作に特化したライブラリです。
  * [Graphviz の出力形式](http://www.graphviz.org/doc/info/output.html)には `plain` や `json` がありますので、 `dot` コマンドでこれらの形式に変換し、パースで楽をする方法もあります。  
（私の手元の環境では `json` は非サポートでした。コンパイルオプションなどに依存するのかも知れません）

## 木構造の判定

判定方法は大まかに、

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

の二つに分けられるかと思います。  
前者は [nekketsuuu さんの回答](https://ja.stackoverflow.com/a/34490/3054) が詳しいですね。

後者の場合、親子関係のエッジの作成が試みられる度に、

  * 子になるノードに既に祖先があってはならない（その時点では根でなければいけない）
  * 子になるノードが親になるノードの根であってはならない

の2点をチェックします。

グラフ中に木として不正な構造が無いならば、エッジは常に根の数だけノードより少ないです。  
よって、森（お互いに接続されていない部分があり、根が複数ある）かどうかは、

[code]

    # 成り立つならば森
    エッジの総数 < (ノードの総数 - 1)
    
[/code]

で判定出来ます。

（以上は [Wikipedia](https://en.wikipedia.org/wiki/Tree_\(data_structure\))
に出ている絵を見て適当に考えた事ですので、実用に供するには精査が必要です）

## 例: NetworkX の利用

NetworkX と、PyDotPlus のインストールが必要です。

[code]

    # Ubuntu の場合
    $ sudo apt install python3-networkx
    $ sudo apt install python3-pydotplus
    
[/code]

コード:

[code]

    #!/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)
    
[/code]

複数のグラフがある場合や、グラフがノードを持たない場合はエラーになります。

実行:

[code]

    $ ./is_tree_by_nx.py <tree.dot 
    Yes, 木構造です
    
[/code]

## 例: エッジ毎の判定

上で説明した逐次的な方法です。  
DOT言語で定義されたグラフを構築する事はせず、各ノードは自分の根を特定するのに必要な情報だけを保持します。  
DOT言語のパースには、[`dot` コマンドの `plain` 形式による出力
](http://www.graphviz.org/doc/info/output.html) を利用します。

コード:

[code]

    #!/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)
    
[/code]

グラフがノードを持たない場合も木構造と見なしています。  
複数のグラフがある場合はエラーにしています。

実行:

[code]

    $ 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')> の子になる事は出来ません
    
[/code]

`dot -Tplain` で `plain` 形式にしています。


CC BY-SA 3.0
2017-05-08T02:25:44.640
34537
2017-05-14T02:34:28.553
2017-05-14T02:34:28.553
3054
3054
34481
answer