同じ構造を判断するプログラム

[mint]

困っています。
ノードとリンクからなる２つのグラフ(グラフAはグラフBの部分グラフ)を比較して、グラフAに対応するグラフBのID番号を出力するC言語プログラムを書きたいと考えています。各ノードにはラベルが貼ってあります。

グラフの情報としては、
グラフA:（２つのノードと１辺のリンクから成る）
label_A[0]=2;label_A[1]=4;
ID番号とは、配列の要素番号に対応します。
それと接続関係の情報、ノード間にリンクがある場合に１としています・
E[0][0]=0;E[0][1]=1;E[1][0]=1;E[1][1]=0;

グラフB：（３つのノードと３辺のリンクから成る)
label_B[0]=4;label_B[1]=8;label_B[2]=2;
E[0][0]=0;E[0][1]=1;[0][2]=1;E[1][0]=1;E[1][1]=0;E[1][2]=1;E[2][0]=1;E[2][1]=1;E[2][2]=0;

分かりづらくすみません。つまり、グラフAに対応するグラフBはノードID番号０と２となり、出力したいのはこの０と２です。
この作業が出来るプログラムを教えていただけないでしょうか。よろしくお願いします。

各グラフのイメージとしては、次のような感じです。
グラフA:
２ - ４

グラフB：
４ - ８ - ２
|______|

[ゆーずぃ]

この場合接続関係の情報は一切関係がない気がするのですが…

forの２重ループで、label_A == label_B[j]の時だけjの値を出力してください。これだけです。

因みに
for(i){
for(j){
}
}
とします

まぁ、これだと要素番号が順不同になっちゃうので、それを後でソートするなりは好きにしてください。

[mint]

返信ありがとうございます。

本当は、グラフ構造が少し複雑で、次のようになっています。これだと、接続関係を考慮しないと、同じラベル２でも、どちらのラベル２のIDが欲しいのか分からない状況です。実際に欲しいIDは、グラフBの左から1,3,4番目となります。この作業が出来るプログラムを書いて頂けると助かります。よろしくお願いします。

グラフA：
５－２－１

グラフB：
５－２－２－１
|______|

[ゆーずぃ]

なるほど、接続関係の読み方をようやく理解しました。
そこで質問なのですが、例２のグラフＡ、Ｂ
(
グラフＡ:５ー２ー１
グラフＢ:５ー２ー２ー１
)
の場合、接続情報はどうなりますか？最初の例だけだと接続情報とグラフのユニークな関係が判断できないので(^_^;)

[mint]

例２のグラフを最初の例と同じ感じで表現すると、次のようになります。
各ラベルと接続関係を行列で表現します。

グラフA:（3つのノードと2辺のリンクから成る）
label_A[]={5,2,1};
なお、ID番号は左から0,1,2です。
E_B[][]=
{{0,1,0},
{1,0,1},
{0,1,0}};

グラフB：(４つのノードと４辺から成る）
label_B[]={5,2,2,1};
ID番号は、左から、0,1,2,3です。
E[][]＝
{{0,1,1,0},
{1,0,1,0},
{1,1,0,1},
{0,0,1,0}};

[たいちう]

グラフAのノード数は決まっていないのですよね？
上限を設けて良いならば比較的簡単です。
グラフAのラベルに重複がないならもっと簡単。
アルゴリズムは、こんな感じで。

１．グラフA、Bともに、ラベル順にソートする。

２．グラフAの各ラベル毎と同じラベルが、
グラフBにいくつあるか数える。
65503の例の場合は、(1, 2, 5) : (1, 2, 1)となる。

３．全ての組み合わせを生成
上の例の場合、1 * 2 * 1通りチェックすれば良い。

４．グラフBの部分集合のリンクの有無が、
Aと完全に一致すれば答。
Aのノード数が3ならば、Bのリンクの配列の対応する3 * 3の部分が、
Aの配列と完全に一致すると言う事。


まず、Aのノード数が3に固定で、ラベルの重複が無い場合の
プログラムを作ってみてはいかがでしょうか？
Bのノード数には制限なしで。
ラベルはソート済みにしておいてもいいでしょう。

それができたら、未ソートのグラフ。

次にAのノード数を5以下とする場合。
ここまでは殆どプログラミングの手間だけの問題かと。
（以降に比べると）

次はAのノード数の制限をなくす場合。
上手に再帰で作るのが一番簡単だと思います。
（再帰が使いこなせないとかなり難しそう）

最後に、Aのラベルの重複を許した場合。
「全ての組み合わせを生成」の部分が少しやっかいになります。


どこまでできそうですか？
少しずつ作っていけば、イメージも固まっていくんじゃないでしょうか。

# グラフ理論は勉強したことが無いのでわかりませんが、
# もっとエレガントな解法があるかもしれませんね。

[mint]

ご回答ありがとうございます。グラフAも最終的にはラベルの重複があるので、がんばらないといけなそうです。

まず、１と２は出来そうです。４も、３ができたら出来そうです。
３の、全ての組み合わせの作り方が思いつきません。組み合わせとして、ソートしたIDの配列を作ろうと思ったのですが。
こんなイメージです。
AとBそれぞれ、ソートしたラベルとそのIDが以下のようになっているとして、
A：
ラベル=[1,2,5]
ID=[2,1,0]
B:
ラベル=[1,2,2,5]
ID=[3,1,2,0]
組み合わせの配列をkumi[][]として(「全組み合わせ数×グラフAのラベル数」の行列です)、
kumi[0][3,1,0],kumi[1][3,2,0]の２通りがあるという表現です。
この配列を作ろうと思うのですが、どのように作ったら良いですか？

[たいちう]

> まず、Aのノード数が3に固定で、ラベルの重複が無い場合の
> プログラムを作ってみてはいかがでしょうか？

それでは、↑の条件で、2まで作ってください。
2までできたということを表示できるようにしてくださいね。

[たいちう]

一応書いておくと、私はプログラムを書くつもりはありませんよ（少なくとも今のところは）。
あなたが一歩ずつ進むためのアドバイスをさせてもらいたいと思っています。
いつでもすぐに返信できるわけでもないので、
私に合わせていると完成までに長期間かかる可能性もあります。
更に私が書いた方法よりも簡単なアルゴリズムがあるかもしれません。

私はスルーされても一向に構いませんので、
事情によっては他の回答者を待つというのも良いかもしれません。
（老婆心ながらマルチポストなどは注意してください）