Javaグラフクラスの間接接続テストを実装します

Question

グラフデータ構造を表すためにJavaでクラスを書いています。これは、無向の非加重グラフに固有のものであり、その目的は主にエッジテスト用です（ノードAは、直接または間接的にノードBに接続されています）。

間接的な方法の実装を支援する必要があります。以下のコードでは、この方法のみにコメントしただけで、コードがAs-ISをコンパイルするように虚偽を返しています。

私はアルゴリズムを思いつくのに少し時間を費やしましたが、これよりも単純なものを見つけることができないようです。

• 最初に直接接続をテストします
• ノードAからノードBへの直接接続が存在しない場合：
  • すべてのエッジについて、私はノードAに接続しました：
    • エッジA-> iを含む新しいグラフを作成します
    • ノードIとB間の間接接続の新しいグラフをテストする

擬似コードまたは実際のJavaコードのいずれかを回答で歓迎します。これが私が持っているコードです：

class Graph {

    // This is for an undirected, unweighted graph
    // This implementation uses an adjacency matrix for speed in edge testing 

    private boolean[][] edge;
    private int numberOfNodes;

    public Graph(int numNodes) {

        // The indices of the matrix will not be zero-based, for clarity,
        // so the size of the array will be increased by 1.

           edge = new boolean[numNodes + 1][numNodes + 1];
           numberOfNodes = numNodes;
    }

    public void addEdge(int a, int b) {
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                edge[a][b] = true;
                edge[b][a] = true;
            }
        }
    }

    public void removeEdge(int a, int b) {
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                edge[a][b] = false;
                edge[b][a] = false;
            }
        }
    }

    public boolean directEdgeTest(int a, int b) {

        // if node a and node b are directly connected, return true 

        boolean result = false;
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                if (edge[a][b] == true) {
                    result = true;
                }
            }
        }
        return result;
    }

    public boolean indirectEdgeTest(int a, int b) {

        // if there exists a path from node a to node b, return true 

            // implement indirectEdgeTest algorithm here.

            return false;
    }
}

Answer 1

私は彼または彼女の答えをメリトンを称賛しますが、私はそのアイデアをJavaクラスとユニットテストについてコーディングしたので、誰もが再利用可能なコードを探している場合に備えて、ここで別の答えを提供しています。

メリトンに感謝します。直接エッジテストとパステストを区別することが重要であり、特定のタイプのテストにより適したグラフのさまざまな実装があることに同意します。パステストの場合、隣接するリストは隣接マトリックス表現よりもはるかに効率的であるようです。

以下の私のコードはおそらくそれほど効率的ではありませんが、今のところは私の問題を解決しています。誰かが提案する改善がある場合は、お気軽にお問い合わせください。

コンパイルする：Javac Graph.java

実行する：Java GraphTest

class Graph {

    private java.util.ArrayList<Node> nodeList;
    private int numberOfNodes;

    public Graph(int size) {
        nodeList = new java.util.ArrayList<Node>(size + 1);
        numberOfNodes = size;

        for (int i = 0; i <= numberOfNodes; i++) {
            nodeList.add(new Node());
        }
    }

    public void addEdge(int a, int b) {
        if (a >= 1 && a <= numberOfNodes) {
            if (b >= 1 && b <= numberOfNodes) {
                nodeList.get(a).addNeighbour(nodeList.get(b));
                nodeList.get(b).addNeighbour(nodeList.get(a));
            }
         }
    }

    public void walk(Node origin, java.util.Set<Node> visited) {
        for (Node n : origin.getNeighbours()) {
            if (!visited.contains(n)) {
                visited.add(n);
                walk(n, visited);
            }
        }
    }

    public boolean hasPath(Node origin, Node target) {
        java.util.Set<Node> reachables = new java.util.HashSet<Node>();
        walk(origin, reachables);
        return reachables.contains(target);
    }

    public boolean hasPath(int a, int b) {

        java.util.Set<Node> reachables = new java.util.HashSet<Node>();
        Node origin = nodeList.get(a);
        Node target = nodeList.get(b);
        walk(origin, reachables);
        return reachables.contains(target);       
    }
}

class Node {

    private java.util.Set<Node> neighbours;

    public Node() {
        neighbours = new java.util.HashSet<Node>();
    }

    public void addNeighbour(Node n) {
        neighbours.add(n);
    }

    public java.util.Set<Node> getNeighbours() {
        return neighbours;
    }
}

class GraphTest {

    private static Graph g;

    public static void main(String[] args) {

        g = new Graph(6);

        g.addEdge(1,5);
        g.addEdge(4,1);
        g.addEdge(4,3);
        g.addEdge(3,6);

        printTest(1, 2);
        printTest(1, 4); 
        printTest(6, 1);   
    }

    public static void printTest(int a, int b) {

        System.out.print("Are nodes " + a + " and " + b + " connected?");
        if (g.hasPath(a, b)) {
            System.out.println(" YES.");
        } else {
            System.out.println(" NO.");
        }
    }
}

Answer 2

えーと、そのアプローチは恐ろしく非効率的に聞こえます。これはどうですか：

void walk(Node orgin, Set<Node> visited) {
    for (Node n : origin.neighbours) {
        if (!visited.contains(n)) {
            visited.add(n);
            walk(n, visited);
        }
    }
}


boolean hasPath(Node origin, Node target) {
    Set<Node> reachables = new HashSet<Node>();
    walk(origin, reachables);
    return reachables.contains(target);
}

また、スパースグラフでノードの近隣を効率的に反復することはできないため、グラフトラバーサルに隣接するマトリックスを使用することは疑わしいものです。

その方法が頻繁に使用され、グラフがめったに変化しない場合、分解を行うことでクエリをスピードアップできます 接続された領域 前もって、それが属する領域を各ノードに保存します。次に、同じ領域に属している場合、2つのノードが接続されます。

編集：グラフを最適に表現する方法を明確にする。直接エッジテストでは、隣接マトリックスが推奨されます。パステストの場合、領域への分解はです。後者は、グラフが変化するときに最新の状態を保つために些細なことではありませんが、文献にはこれにはアルゴリズムがある場合があります。あるいは、隣接リストはグラフトラバーサルとパステストに使用可能ですが、接続領域への分解を直接記録するよりも効率が低いままです。また、隣接セットを使用して、スパースグラフのより効率的な隣接反復と一定のエッジテストと組み合わせることもできます。

情報を冗長に保存することもできます。各種類のクエリに対して、調整された個別のデータ構造を維持することもできます。

Answer 3

ソリューションは機能しますが、より良い解決策は、ルート「A」ノードからスパニングツリーを構築することです。これにより、特定のエッジのみが欠落している複数のサブグラフの代わりに、最終的に考慮すべきツリーが1つしかありません。

一度 アイデアを取得します, 、あなたがそれをどのように実装するかはあなた次第です。合理的な方法でアルゴリズムを実装できると仮定すると、接続を検索するために1つのツリーのみが必要である必要があります。