グラフ：ワイルドカードを含むノードのリストを使用してサブグラフを見つける

Question

次の問題に名前が付いていますが、それを解決するアルゴリズムはありますか？ ： グラフ、有向かのいずれかで与えられ、

1. 正確なノードのリスト、または
2. によって与えられる仕様を満たすすべてのパスを見つけます '*？これはちょうど「任意のノードまたは全くノード」、または
3. 示す「* {N}」「どれ連続接続されたノード」

例を示し

A -> B -> *? -> D which results in ABXD and ABYD and ABD etc. 

または

A -> *{1} -> D -> *? -> E which results in ABXDZE and ABYDZE and ABDZE etc. etc. 

おかげ

P.S. RやperlやCでこれを行うグラフライブラリを知っている人はいますか？

Answer 1

た：

1. 問題は、2つのノード間の長さNのすべてのパスを見つけることです。サイクルは除外されます。
2. は、edgelistとしてデータを読み込みます。 （ノードの名前は一意とみなされます）
3. ノード名のハッシュテーブル（またはboostとstl、C++のunordered_map）をキーとして作成し、値としてハッシュテーブルを作成します。
4. この2番目のハッシュテーブルには、最初のノードがキーとするすべてのノードが含まれます。
例えば

A->B 
A->C 
B->D 
C->E 
E->D 

ためのPerl表記で入力されたデータを保持して得られたデータ構造は、「edgelist」などのすべてのデータに読み出した後、次のようになり

：

my %hash = (
'A' => {'B' => 1, 'C' => 1}, 
'B' => {'D' => 1}, 
'C' => {'E' => 1}, 
'E' => {'D' => 1}, 
); 

知見場合ノードのペアは直接接続されています（perl）としておおよそ行えます：

sub search { 
    my ($from,$to) = @_; 
    if($to eq '*'){ return defined($x=$hash{$from}) ? [keys $hash{$from}] : [] } 
    return defined($x=$hash{$from}) && defined($x{$to}) ? [$to] : [] 
} 

上記の関数には、$ toを '*'に設定することによって、ノードが接続されているすべてのノードを返す手段があります。戻り値は、$ fromパラメーターに直接接続されたノードの配列参照です。

2つのノード間のパスを検索するには、上記の関数を再帰的に使用する必要があります。

sub path { 
    my ($from,$to, $hops, $save_results) = @_; 
    if($hops < 0){ return 0 } 
    $results = search($from, '*'); 
    if("".@$results == 0){ return 0 } 
    $found = 0; 
    foreach $result (@$results){ 
     $a_node = new Tree::Nary($result); 
     if(path($result, $to, $hops-1, $a_node) == 1){ 
      $save_results->insert($save_results, -1, $a_node); 
      $found = 1; 
     } 
    } 
    return $found; 

}

深さがあまりない場合には（すなわち、$は< 6ホップ？）ので、[原文のまま]スタックオーバーフローの再帰を使用しても大丈夫です。

最も難しいのは、結果を読み取って各パスのノードを抽出することです。多くの審議の後、私は結果を格納するためにTree :: Nary（n-aryツリー）を使うことに決めました。すべてのパスを抽出するために

 |-> B -> D 
A -> |-> C -> E -> D 

は、実行します：

1. は、各リーフノードから
2. スタートは、その親を経由して逆方向に移動するすべてのリーフノードを見つける終わりに、私たちは以下のツリーを持っていますルートノードに追加し、ノード名を保存します。

上記はperlを使用して実装されていますが、ハッシュテーブルにboost :: unordered_mapを使用してC++でも行っています。私はまだC++コードにツリー構造を追加していません。

結果：3281415エッジと18601個のユニークノードの場合、PerlはA - > '*' - > '*' - > Bを見つけるのに3分かかります。準備ができたらC++コードのアップデートを提供します。

Answer 2

私はそのための任意のライブラリを知らないが、次の2つの部分でこれを分離することがあります。

• あなたが

探しているものを見つけるために

アルゴリズムを解析し、ユーザーのクエリを構文解析、私はあなたがする必要があるものを見つけることができます（ライブラリの解析や自己のものを使用）

私はあなたが特別な構造を定義することをお勧めします（リンクされたリストのような）クエリーを表します。各要素は、実ノード、xノード数、または無制限ノード数のいずれかを表すことができます。

アルゴリズムの唯一の問題は、無限数または限られた数の中間ノードを使用して、ノードAからノードBまでのすべてのパスを見つけることです。これは、動的プログラミング、またはDFSやBFSなどの検索アルゴリズムを使用して行うことができます。私は最後にやった