49415


仕様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次元


CC BY-SA 4.0
2018-10-17T15:07:36.373
49392
2018-10-31T13:28:55.453
2018-10-31T13:28:55.453
17199
17199
question
アルゴリズム グラフ理論
線分群から、閉図形の数を数える方法を教えて下さい。


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

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

オイラーの定理は、頂点の数を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だと、平面と違ってどの経路が内側かがわからないので省く方法はないように思います。


CC BY-SA 4.0
2018-10-18T11:14:47.220
49415
2018-10-20T05:14:08.077
2018-10-20T05:14:08.077
15171
15171
49392
answer


例3は単純ミスということなんで、とりあえず再帰的に総当たりをするためのアルゴリズムを示しておきます。「特に言語にこだわりません」と言いつつ、アルゴリズムの記述にSwiftを使うなんて想定している人はいないでしょうが、こちらが一番使い慣れているものなのでご容赦を。

まずはデータ構造の準備

[code]

    //点を表す構造体
    struct Point: Hashable {
        var x: Int
        var y: Int
    }
    
    //線分を表す構造体
    struct Line: Hashable {
        var p1: Point
        var p2: Point
    
        //入力データを書きやすくするためのイニシャライザ
        init(_ p1: (x: Int, y: Int), _ p2: (x: Int, y: Int)) {
            self.p1 = Point(x: p1.x, y: p1.y)
            self.p2 = Point(x: p2.x, y: p2.y)
        }
    
        //補助メソッド: 線分をたどった隣側の点
        func next(to: Point) -> Point {
            if to == self.p1 {return p2}
            if to == self.p2 {return p1}
            fatalError("Invalid line used")
        }
    }
    
    //閉路を表す構造体
    struct ClosedPath: Hashable {
        var start: Point //始点(結果を表示しやすくするためだけに使っている)
        var path: [Line] //閉路に含まれるすべての線分
        let lineSet: Set<Line> //同一性判定用
    
        //初期化, pathは必ず閉路を表していないといけない
        init(start: Point, path: [Line]) {
            self.start = start
            self.path = path
            self.lineSet = Set(path)
        }
    
        //
        //線分の集合が等しければ同一の閉図形と判定する
        //
        func hash(into hasher: inout Hasher) {
            self.lineSet.hash(into: &hasher)
        }
        static func == (lhs: ClosedPath, rhs: ClosedPath) -> Bool {
            return lhs.lineSet == rhs.lineSet
        }
    }
    
[/code]

重複を防ぐために集合型を多用しているので、そのために`Hashable`なんてものが出てきてますが、`Set`(や`Dictionary`のキー)に使うためのおまじないくらいに思ってください。

上記の構造体を使うと、「閉路」探索は次のように書けます。

[code]

    //閉路探索
    func findClosedPaths(lines: [Line]) -> Set<ClosedPath> {
        //結果は重複を防ぐため集合型で持つ
        var result: Set<ClosedPath> = []
    
        //前処理:ある頂点から辿れる線分を全部リストアップしておく
        var availablePaths: [Point: Set<Line>] = [:]
        for line in lines {
            availablePaths[line.p1] = (availablePaths[line.p1] ?? []).union([line])
            availablePaths[line.p2] = (availablePaths[line.p2] ?? []).union([line])
        }
    
        //関数型プログラミング的には美しくないが、現在の状態を再帰処理関数の外に持っておく
        var currentPath: [Line] = [] //現在までの経路
        var visitedLines: Set<Line> = [] //訪問済みの線分
    
        //深さ優先探索用の内部関数
        func searchClosedPath(start: Point, current: Point) {
            //currentから辿れる未訪問の線分について繰り返し
            for nextLine in availablePaths[current]! where !visitedLines.contains(nextLine){
                currentPath.append(nextLine)
                //その線分をたどった時の次の点を求める
                let nextPoint = nextLine.next(to: current)
                if nextPoint == start {
                    //ゴール(==始点)に達していたら現在の経路を結果に追加して終了
                    result.insert(ClosedPath(start: start, path: currentPath))
                } else {
                    //まだなら再帰的に探索
                    visitedLines.insert(nextLine)
                    searchClosedPath(start: start, current: nextPoint)
                    visitedLines.remove(nextLine)
                }
                currentPath.removeLast()
            }
        }
    
        //線分に含まれる全ての点について繰り返す
        for start in availablePaths.keys {
            searchClosedPath(start: start, current: start)
        }
    
        return result
    }
    
[/code]

詳細はコメントを参照してください。内部関数やそこから参照されている変数類を外出しすれば、リスト型(可変長配列)、集合型、辞書型(Hash,
HashMap)のある言語なら移植は容易だと思います。

そのままだと結果が見辛くなるので、少しばかりごそごそ。

[code]

    /*
     * 表示整形用
     */
    extension Point: CustomStringConvertible {
        var description: String {
            return String(format: "[%2d,%2d]", x, y)
        }
    }
    extension Line: CustomStringConvertible {
        var description: String {
            return "\(p1)-\(p2)"
        }
    }
    extension ClosedPath: CustomStringConvertible {
        var description: String {
            var currPoint = start
            var points: [Point] = []
            for line in path {
                points.append(currPoint)
                currPoint = line.next(to: currPoint)
            }
            return points.map {$0.description}.joined(separator: "-")
        }
    }
    func prettyPrintInput(lines: [Line]) {
        for (index, line) in lines.enumerated() {
            let heading = index == 0 ? "input  : " : "         "
            print("\(heading)線分\(index+1) \(line)")
        }
    }
    func prettyPrintOutput(closedPaths: Set<ClosedPath>) {
        print("output : 閉図形の数=\(closedPaths.count)")
        for closedPath in closedPaths {
            print("       :   \(closedPath)")
        }
    }
    func showClosedPaths(title: String, lines: [Line]) {
        print(title)
        prettyPrintInput(lines: lines)
        let result = findClosedPaths(lines: lines)
        prettyPrintOutput(closedPaths: result)
        print()
    }
    
[/code]

出来合いのパッケージなら内部で全部やってくれることを自前でやらないといけないので、ちょっと長くなりますが、メインの閉路探索については再帰処理の典型例なので、しっかり頭の中でトレースしていけばイメージはつかめるかと思います。

では実行。

[code]

    /*
     * 実行
     */
    showClosedPaths(title: "例1", lines: [
        Line(( 0, 0), (10, 0)),
        Line((10, 0), ( 0,10)),
        Line(( 0,10), ( 0, 0)),
        Line((-5, 0), (-5,10)),
    ])
    showClosedPaths(title: "例2(8の字の形:1つとします)", lines: [
        Line(( 0, 0), (10,10)),
        Line((10,10), (10, 0)),
        Line((10, 0), ( 0,10)),
        Line(( 0,10), ( 0, 0)),
        Line((-5, 0), (-5,10)),
    ])
    showClosedPaths(title: "例3(▽△)", lines: [
        Line(( 0, 0), ( 5, 5)),
        Line(( 5, 5), ( 0,10)),
        Line((10, 0), ( 0, 0)),
        Line(( 5, 5), (10, 0)),
        Line((10, 0), (10,10)),
        Line((10,10), ( 5, 5)),
    ])
    showClosedPaths(title: "例5(▽△)", lines: [
        Line(( 0, 0), ( 5, 5)),
        Line(( 5, 5), ( 0,10)),
        Line(( 0,10), ( 0, 0)),
        Line(( 5, 5), (10, 0)),
        Line((10, 0), (10,10)),
        Line((10,10), ( 5, 5)),
    ])
    
[/code]

結果です。

>
[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]-[ 0,10]-[10, 0]
>  
>     例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
>            :   [10,10]-[ 0, 0]-[ 0,10]-[10, 0]
>  
>     例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 : 閉図形の数=3
>            :   [10,10]-[10, 0]-[ 0, 0]-[ 5, 5]
>            :   [10,10]-[10, 0]-[ 5, 5]
>            :   [ 0, 0]-[10, 0]-[ 5, 5]
>  
>     例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 : 閉図形の数=3
>            :   [10,10]-[10, 0]-[ 5, 5]
>            :   [10,10]-[10, 0]-[ 5, 5]-[ 0,10]-[ 0, 0]-[ 5, 5]
>            :   [ 0, 0]-[ 0,10]-[ 5, 5]
>  
[/code]

例5が例3とは別の理由で3つ出てきています。これは

[code]

    ▽     ▽
       △  △
    
[/code]

を別の閉路として捉えているためです。単に「閉路」と言った場合、同じ点を2度通っても良いのでこのような結果になります。(上のコードでは、経路としては別ものでも、同じ「閉図形」になるものは一つと数えるようにしています。)

同じ点を2度通らない場合を「単純閉路」と言います。上記のコードを単純閉路用に書き換えたものがこちら。

[code]

    //単純閉路探索
    func findSimpleClosedPaths(lines: [Line]) -> Set<ClosedPath> {
        //結果は重複を防ぐため集合型で持つ
        var result: Set<ClosedPath> = []
    
        //前処理:ある頂点から辿れる線分を全部リストアップしておく
        var availablePaths: [Point: Set<Line>] = [:]
        for line in lines {
            availablePaths[line.p1] = (availablePaths[line.p1] ?? []).union([line])
            availablePaths[line.p2] = (availablePaths[line.p2] ?? []).union([line])
        }
    
        //関数型プログラミング的には美しくないが、現在の状態を再帰処理関数の外に持っておく
        var currentPath: [Line] = [] //現在までの経路
        var visitedLines: Set<Line> = [] //訪問済みの線分
        var visitedPoints: Set<Point> = [] //訪問済みの点
    
        //深さ優先探索用の内部関数
        func searchClosedPath(start: Point, current: Point) {
            //currentから辿れる未訪問の線分について繰り返し
            for nextLine in availablePaths[current]! where !visitedLines.contains(nextLine){
                currentPath.append(nextLine)
                //その線分をたどった時の次の点を求める
                let nextPoint = nextLine.next(to: current)
                if nextPoint == start {
                    //ゴール(==始点)に達していたら現在の経路を結果に追加して終了
                    result.insert(ClosedPath(start: start, path: currentPath))
                } else if !visitedPoints.contains(nextPoint) {
                    //まだなら再帰的に探索
                    visitedPoints.insert(current)
                    visitedLines.insert(nextLine)
                    searchClosedPath(start: start, current: nextPoint)
                    visitedLines.remove(nextLine)
                    visitedPoints.remove(current)
                }
                currentPath.removeLast()
            }
        }
    
        //線分に含まれる全ての点について繰り返す
        for start in availablePaths.keys {
            searchClosedPath(start: start, current: start)
        }
    
        return result
    }
    
[/code]

で実行。

[code]

    /*
     * 表示整形用
     */
    func showSimpleClosedPaths(title: String, lines: [Line]) {
        print(title)
        prettyPrintInput(lines: lines)
        let result = findSimpleClosedPaths(lines: lines)
        prettyPrintOutput(closedPaths: result)
        print()
    }
    
    /*
     * 実行
     */
    showSimpleClosedPaths(title: "例1", lines: [
        Line(( 0, 0), (10, 0)),
        Line((10, 0), ( 0,10)),
        Line(( 0,10), ( 0, 0)),
        Line((-5, 0), (-5,10)),
    ])
    showSimpleClosedPaths(title: "例2(8の字の形:1つとします)", lines: [
        Line(( 0, 0), (10,10)),
        Line((10,10), (10, 0)),
        Line((10, 0), ( 0,10)),
        Line(( 0,10), ( 0, 0)),
        Line((-5, 0), (-5,10)),
    ])
    showSimpleClosedPaths(title: "例3(▽△)", lines: [
        Line(( 0, 0), ( 5, 5)),
        Line(( 5, 5), ( 0,10)),
        Line((10, 0), ( 0, 0)),
        Line(( 5, 5), (10, 0)),
        Line((10, 0), (10,10)),
        Line((10,10), ( 5, 5)),
    ])
    showSimpleClosedPaths(title: "例5(▽△)", lines: [
        Line(( 0, 0), ( 5, 5)),
        Line(( 5, 5), ( 0,10)),
        Line(( 0,10), ( 0, 0)),
        Line(( 5, 5), (10, 0)),
        Line((10, 0), (10,10)),
        Line((10,10), ( 5, 5)),
    ])
    
[/code]

結果。

>
[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]-[ 0,10]-[10, 0]
>  
>     例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
>            :   [10,10]-[ 0, 0]-[ 0,10]-[10, 0]
>  
>     例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 : 閉図形の数=3
>            :   [10,10]-[10, 0]-[ 0, 0]-[ 5, 5]
>            :   [10,10]-[10, 0]-[ 5, 5]
>            :   [ 0, 0]-[10, 0]-[ 5, 5]
>  
>     例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
>            :   [10,10]-[10, 0]-[ 5, 5]
>            :   [ 0, 0]-[ 0,10]-[ 5, 5]
>  
[/code]

例3までの結果は「閉路」と同じですが、例5では結果が2個になっています。同じ点を2度通るような経路は省かれているためです。

結果だけが欲しいのであれば出来合いのパッケージで良いでしょうが、再帰処理による総当たりの良い練習問題になりますので、ご自身の得意な言語で実装しなおしてみることをお勧めします。

(注)Swiftの実行ができちゃうという人は試してもらうとわかるんですが、点や閉路の表示順が実行するたびに変化します。これは現在のSwift(4.2)の仕様です。


CC BY-SA 4.0
2018-10-19T12:27:10.107
49460
2018-10-19T12:27:10.107
13972
49392
answer