線分群から、閉図形の数を数える方法を教えて下さい。


仕様1:2次元  
仕様2:線分と線分の交差は、気にしません。  
目的:輪(環)がいくつあるか知りたい。

[code]

    例1
    input  : 線分1 [ 0, 0], [10, 0]
             線分2 [10, 0], [ 0,10]
             線分3 [ 0,10], [ 0, 0]
             線分4 [-5, 0], [-5,10]
    output : 閉図形の数=1
           :  [0,0],[10,0],[ 0,10]
    
    例2(8の字の形:1つとします)
    input  : 線分1 [ 0, 0], [10,10]
             線分2 [10,10], [10, 0]
             線分3 [10, 0], [ 0,10]
             線分4 [ 0,10], [ 0, 0]
             線分5 [-5, 0], [-5,10]
    output : 閉図形の数=1
           :  [0,0],[10,10],[10,0],[0,10]
    
    例3(▽△)
    input  : 線分1 [ 0, 0], [ 5, 5]
             線分2 [ 5, 5], [ 0,10]
             線分3 [10, 0], [ 0, 0]
             線分4 [ 5, 5], [10, 0]
             線分5 [10, 0], [10,10]
             線分6 [10,10], [ 5, 5]
    output : 閉図形の数=2
           :  [0,0],[ 5, 5],[ 0,10]
           :  [5,5],[10, 0],[10,10]
    
    例4(閉図形と閉図形の重なりはOKです)
    
[/code]

①タイトルで意味が通じますか？正式名称があれば教えて下さい。検索語が思いつきませんでした。  
②特に言語にこだわりません。おすすめのページがあれば教えて下さい。  
よろしくお願いします。

2018-10-19A----------------------------------------------------------------  
〉例3では[ 0, 0]-[10, 0]-[10,10]-[ 5, 5]なんて閉路もあるようなんですが、  
申し訳ありません。  
例3の線分3 [10, 0], [ 0, 0]は、[ 0,10], [ 0, 0]でした。正しいものを、  
例5としました。

[code]

    例5(▽△)
    input  : 線分1 ( 0, 0),( 5, 5),
             線分2 ( 5, 5),( 0,10),
             線分3 ( 0,10),( 0, 0),
             線分4 ( 5, 5),(10, 0),
             線分5 (10, 0),(10,10),
             線分6 (10,10),( 5, 5)
    output : 閉図形の数=2
           : (0,0),( 5, 5),( 0,10)
           : (5,5),(10, 0),(10,10)
    
[/code]

例3は、想定していませんでした。

〉検索語が思いつきませんでした。  
hamiltonian-pathで検索

2018-10-19B----------------------------------------------------------------  
〉PythonでNetworkXを使って  
2次元のままのデータで、できました。  
例3は、イメージとして、=2ですね。  
例5は、残念ながら閉図形の数=1でした。  
edges = [((0, 0), (5, 5)), ((5, 5), (0,10)),((10, 0), (0, 0)),((5, 5), (10,
0)), ((10, 0), (10,10)),((10,10), (5, 5))]

〉内側かはかは、わからないので  
(5,5)から(10,0)へのルート3通ありました。

〉閉路の検出と同じ  
座標をナンバリングしたら、別世界ですか?  
例3について、NetworkXは,1次元でできるかチャレンジしてみます。  
00→1,100→2,1010→3,55→4,010→5  
(00,55)(55,010),(100,00)(55,100)(100,1010)(1010,55)  
(1,4) (4,5) (2,1) (4,2) (2,3) (3,4) :1次元




**平面グラフとしての回答**

質問が平面グラフということであれば、オイラーの定理を使って領域の数を求めることができます。平面グラフというのは頂点以外の点で辺が交差しないように平面に書けるようなグラフです。

オイラーの定理は、頂点の数をv、辺の数をe、領域の数をfとすると以下の関係が成立します。

[code]

    v - e + f = 2
    
[/code]

その定理を使って、Pythonで`NetworkX`を使用したコードは次のようになります。

[code]

    import networkx as nx
    
    def count_regions(edges):
        G = nx.Graph(edges)
        r = 0
        # 今回の質問では繋がっていない頂点があるので、繋がっているグループ毎に計算
        for component in nx.connected_components(G):
            H = G.subgraph(component)
            r += H.number_of_edges() - H.number_of_nodes() + 1
        return r
    
    edges = [((0, 0), (10, 0)), ((10, 0), (0, 10)), ((0, 10), (0, 0)), ((-5, 0), (-5, 10))]
    print(count_regions(edges))
    edges = [((0, 0), (10,10)), ((10,10), (10, 0)),((10, 0), (0,10)), ((0,10), (0, 0)), ((-5, 0), (-5,10))]
    print(count_regions(edges))
    edges = [((0, 0), (5, 5)), ((5, 5), (0,10)),((10, 0), (0, 0)),((5, 5), (10, 0)), ((10, 0), (10,10)),((10,10), (5, 5))]
    print(count_regions(edges))
    
[/code]

これで、質問にあるものと同じ答になります。

質問が平面グラフであれば、

> ①タイトルで意味が通じますか？正式名称があれば教えて下さい。検索語が思いつきませんでした。

は、次のようなタイトルにするのがいいと思います。

平面グラフで、線分群から閉じた領域の数を求める方法

**単純閉路の問題としての回答**

Pythonで`NetworkX`を使って単純閉路を求めるという方法であれば、以下のようなコードで求めることができます。

NetworkXドキュメント
[networkx.algorithms.cycles.simple_cycles](https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.cycles.simple_cycles.html)

[code]

    import networkx as nx
    
    def count_simple_cycles(edges):
        G = nx.Graph(edges)
        H = G.to_directed()
        n = H.number_of_edges()
        simple_cycles = list(nx.simple_cycles(H))
        print(simple_cycles)
        return (len(simple_cycles) - n // 2) // 2
    
    edges = [((0, 0), (10, 0)), ((10, 0), (0, 10)), ((0, 10), (0, 0)), ((-5, 0), (-5, 10))]
    print(count_simple_cycles(edges))
    edges = [((0, 0), (10,10)), ((10,10), (10, 0)),((10, 0), (0,10)), ((0,10), (0, 0)), ((-5, 0), (-5,10))]
    print(count_simple_cycles(edges))
    edges = [((0, 0), (5, 5)), ((5, 5), (0,10)),((10, 0), (0, 0)),((5, 5), (10, 0)), ((10, 0), (10,10)),((10,10), (5, 5))]
    print(count_simple_cycles(edges))
    
[/code]

この結果は、以下のようになります。

[code]

    [[(-5, 0), (-5, 10)], [(10, 0), (0, 10), (0, 0)], [(10, 0), (0, 10)], [(10, 0), (0, 0), (0, 10)], [(10, 0), (0, 0)], [(0, 0), (0, 10)]]
    1
    [[(-5, 0), (-5, 10)], [(10, 0), (0, 10), (0, 0), (10, 10)], [(10, 0), (0, 10)], [(10, 0), (10, 10)], [(10, 0), (10, 10), (0, 0), (0, 10)], [(0, 0), (0, 10)], [(0, 0), (10, 10)]]
    1
    [[(0, 0), (10, 0), (10, 10), (5, 5)], [(0, 0), (10, 0), (5, 5)], [(0, 0), (10, 0)], [(0, 0), (5, 5), (10, 10), (10, 0)], [(0, 0), (5, 5), (10, 0)], [(0, 0), (5, 5)], [(10, 0), (10, 10), (5, 5)], [(10, 0), (10, 10)], [(10, 0), (5, 5), (10, 10)], [(10, 0), (5, 5)], [(0, 10), (5, 5)], [(5, 5), (10, 10)]]
    3
    
[/code]

なお、例3では、コメントにあるように、単純閉路だと、[(0, 0), (10, 0), (10, 10), (5,
5)]という閉路も含まれてきます。このような閉路の中に路があるものを省く必要があるのかどうかという問題はありますが、Graphだと、平面と違ってどの経路が内側かがわからないので省く方法はないように思います。




**平面グラフとしての回答**

質問が平面グラフということであれば、オイラーの定理を使って領域の数を求めることができます。平面グラフというのは頂点以外の点で辺が交差しないように平面に書けるようなグラフです。

オイラーの定理は、頂点の数をv、辺の数をe、領域の数をfとすると以下の関係が成立します。

[code]

    v - e + f = 2
    
[/code]

その定理を使って、Pythonで`NetworkX`を使用したコードは次のようになります。

[code]

    import networkx as nx
    
    def count_regions(edges):
        G = nx.Graph(edges)
        r = 0
        # 今回の質問では繋がっていない頂点があるので、繋がっているグループ毎に計算
        for component in nx.connected_components(G):
            H = G.subgraph(component)
            r += H.number_of_edges() - H.number_of_nodes() + 1
        return r
    
    edges = [((0, 0), (10, 0)), ((10, 0), (0, 10)), ((0, 10), (0, 0)), ((-5, 0), (-5, 10))]
    print(count_regions(edges))
    edges = [((0, 0), (10,10)), ((10,10), (10, 0)),((10, 0), (0,10)), ((0,10), (0, 0)), ((-5, 0), (-5,10))]
    print(count_regions(edges))
    edges = [((0, 0), (5, 5)), ((5, 5), (0,10)),((10, 0), (0, 0)),((5, 5), (10, 0)), ((10, 0), (10,10)),((10,10), (5, 5))]
    print(count_regions(edges))
    
[/code]

これで、質問にあるものと同じ答になります。

質問が平面グラフであれば、

> ①タイトルで意味が通じますか？正式名称があれば教えて下さい。検索語が思いつきませんでした。

は、次のようなタイトルにするのがいいと思います。

平面グラフで、線分群から閉じた領域の数を求める方法

**単純閉路の問題としての回答**

Pythonで`NetworkX`を使って単純閉路を求めるという方法であれば、以下のようなコードで求めることができます。

NetworkXドキュメント
[networkx.algorithms.cycles.simple_cycles](https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.cycles.simple_cycles.html)

[code]

    import networkx as nx
    
    def count_simple_cycles(edges):
        G = nx.Graph(edges)
        H = G.to_directed()
        n = H.number_of_edges()
        simple_cycles = list(nx.simple_cycles(H))
        print(simple_cycles)
        return (len(simple_cycles) - n // 2) // 2
    
    edges = [((0, 0), (10, 0)), ((10, 0), (0, 10)), ((0, 10), (0, 0)), ((-5, 0), (-5, 10))]
    print(count_simple_cycles(edges))
    edges = [((0, 0), (10,10)), ((10,10), (10, 0)),((10, 0), (0,10)), ((0,10), (0, 0)), ((-5, 0), (-5,10))]
    print(count_simple_cycles(edges))
    edges = [((0, 0), (5, 5)), ((5, 5), (0,10)),((10, 0), (0, 0)),((5, 5), (10, 0)), ((10, 0), (10,10)),((10,10), (5, 5))]
    print(count_simple_cycles(edges))
    
[/code]

この結果は、以下のようになります。

[code]

    [[(-5, 0), (-5, 10)], [(10, 0), (0, 10), (0, 0)], [(10, 0), (0, 10)], [(10, 0), (0, 0), (0, 10)], [(10, 0), (0, 0)], [(0, 0), (0, 10)]]
    1
    [[(-5, 0), (-5, 10)], [(10, 0), (0, 10), (0, 0), (10, 10)], [(10, 0), (0, 10)], [(10, 0), (10, 10)], [(10, 0), (10, 10), (0, 0), (0, 10)], [(0, 0), (0, 10)], [(0, 0), (10, 10)]]
    1
    [[(0, 0), (10, 0), (10, 10), (5, 5)], [(0, 0), (10, 0), (5, 5)], [(0, 0), (10, 0)], [(0, 0), (5, 5), (10, 10), (10, 0)], [(0, 0), (5, 5), (10, 0)], [(0, 0), (5, 5)], [(10, 0), (10, 10), (5, 5)], [(10, 0), (10, 10)], [(10, 0), (5, 5), (10, 10)], [(10, 0), (5, 5)], [(0, 10), (5, 5)], [(5, 5), (10, 10)]]
    3
    
[/code]

なお、例3では、コメントにあるように、単純閉路だと、[(0, 0), (10, 0), (10, 10), (5,
5)]という閉路も含まれてきます。このような閉路の中に路があるものを省く必要があるのかどうかという問題はありますが、Graphだと、平面と違ってどの経路が内側かがわからないので省く方法はないように思います。

