6

無向グラフ上で単純なサイクルを形成するすべてのパスを返すアルゴリズムを作成するのに問題があります。

最初に、頂点Aから始まるすべてのサイクルを検討しています。これは、以下のグラフの場合です。

A、B、E、G、F
A、B、E、D、F
A、B、C、D、F
A、B、C、D、E、G、F

追加のサイクルは

B、C、D、E
F、D、E、G

しかし、これらは、たとえば、同じアルゴリズムを再度呼び出すことによって見つけることができますが、それぞれBとDから開始します。

グラフを以下に示します-

ここに画像の説明を入力してください

私の現在のアプローチは、次のルールに従いながら、Aのすべてのネイバー、次にネイトボーのネイバーなどを訪問して、Aから可能なすべてのパスを構築することです。

  • 複数のネイバーが存在するたびに、フォークが検出され、Aからの新しいパスが作成されて探索されます。

  • 作成されたパスのいずれかが元の頂点にアクセスする場合、そのパスはサイクルです。

  • 作成されたパスのいずれかが同じ頂点に2回アクセスした場合（Aとは異なる）、パスは破棄されます。

  • 考えられるすべてのパスが探索されるまで続けます。

私は現在、同じサイクルが複数回検出されるのを回避しようとして問題を抱えています。新しいネイバーがすでに別の既存のパスの一部であるかどうかを調べて、2つのパスを組み合わせて（独立している場合）、サイクル。

私の質問は次のとおりです。私はこの問題を解決するために正しい/より良い/より単純なロジックに従っていますか？

コメントありがとうございます

4

2 に答える 2

4

他の質問に対する@eminsenayの回答に基づいて、Johnsonのアルゴリズムを実装するweb_at_normalisiert_dot_deからFrankMeyerによって開発されたelementaryCyclesライブラリを使用しました。

ただし、このライブラリは有向グラフ用であるため、次の項目にいくつかのルーチンを追加しました。

  • JGraphT無向グラフ（Meyerのlibが必要）から隣接行列を作成します
  • 長さ2のサイクルを回避するために、結果をフィルター処理します
  • Meyerのlibは有向グラフ用であり、各無向サイクルは2つの有向サイクル（各方向に1つ）であるため、繰り返されるサイクルを削除します。

コードは

package test;

import java.util.*;

import org.jgraph.graph.DefaultEdge;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.graph.SimpleGraph;


public class GraphHandling<V> {

private UndirectedGraph<V,DefaultEdge>     graph;
private List<V>                         vertexList;
private boolean                         adjMatrix[][];

public GraphHandling() {
    this.graph             = new SimpleGraph<V, DefaultEdge>(DefaultEdge.class);
    this.vertexList     = new ArrayList<V>();
}

public void addVertex(V vertex) {
    this.graph.addVertex(vertex);
    this.vertexList.add(vertex);
}

public void addEdge(V vertex1, V vertex2) {
    this.graph.addEdge(vertex1, vertex2);
}

public UndirectedGraph<V, DefaultEdge> getGraph() {
    return graph;
}

public List<List<V>>     getAllCycles() {
    this.buildAdjancyMatrix();

    @SuppressWarnings("unchecked")
    V[] vertexArray                 = (V[]) this.vertexList.toArray();
    ElementaryCyclesSearch     ecs     = new ElementaryCyclesSearch(this.adjMatrix, vertexArray);

    @SuppressWarnings("unchecked")
    List<List<V>>             cycles0    = ecs.getElementaryCycles();

    // remove cycles of size 2
    Iterator<List<V>>         listIt    = cycles0.iterator();
    while(listIt.hasNext()) {
        List<V> cycle = listIt.next();

        if(cycle.size() == 2) {
            listIt.remove();
        }
    }

    // remove repeated cycles (two cycles are repeated if they have the same vertex (no matter the order)
    List<List<V>> cycles1             = removeRepeatedLists(cycles0);

    for(List<V> cycle : cycles1) {
        System.out.println(cycle);    
    }


    return cycles1;
}

private void buildAdjancyMatrix() {
    Set<DefaultEdge>     edges        = this.graph.edgeSet();
    Integer             nVertex     = this.vertexList.size();
    this.adjMatrix                     = new boolean[nVertex][nVertex];

    for(DefaultEdge edge : edges) {
        V v1     = this.graph.getEdgeSource(edge);
        V v2     = this.graph.getEdgeTarget(edge);

        int     i = this.vertexList.indexOf(v1);
        int     j = this.vertexList.indexOf(v2);

        this.adjMatrix[i][j]     = true;
        this.adjMatrix[j][i]     = true;
    }
}
/* Here repeated lists are those with the same elements, no matter the order, 
 * and it is assumed that there are no repeated elements on any of the lists*/
private List<List<V>> removeRepeatedLists(List<List<V>> listOfLists) {
    List<List<V>> inputListOfLists         = new ArrayList<List<V>>(listOfLists);
    List<List<V>> outputListOfLists     = new ArrayList<List<V>>();

    while(!inputListOfLists.isEmpty()) {
        // get the first element
        List<V> thisList     = inputListOfLists.get(0);
        // remove it
        inputListOfLists.remove(0);
        outputListOfLists.add(thisList);
        // look for duplicates
        Integer             nEl     = thisList.size();
        Iterator<List<V>>     listIt    = inputListOfLists.iterator();
        while(listIt.hasNext()) {
            List<V>     remainingList     = listIt.next();

            if(remainingList.size() == nEl) {
                if(remainingList.containsAll(thisList)) {
                    listIt.remove();    
                }
            }
        }

    }

    return outputListOfLists;
}

}
于 2013-01-13T15:44:11.203 に答える
3

和音のないサイクルを見つけたいという理由でこれに答えていますが、和音のあるサイクルを見つけるように変更できます。

この問題は、2 つの頂点 s と t の間のすべての (包含) 最小パスを見つけることになります。

  • すべてのトリプレット (v,s,t) について:
    • v,s,t のいずれかが三角形を形成する場合、それを出力して次のトリプレットに進みます。
    • それ以外の場合は、s と t を除く v とその隣接を削除し、すべての st-path を列挙します。

すべての st-path を見つけることは、動的計画法によって行うことができます。

于 2013-01-04T15:02:40.517 に答える