質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.34%

VBAによる部分グラフ同型判定プログラムについて

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 708

teratailist

score 4

 前提・実現したいこと

あるグラフの隣接行列A1とあるグラフの隣接行列A2がわかっているとして

A1 = P * A2T * PT    (Tは転置)

を満たす置換行列(各行各列に1が一つ、それ以外が0の行列)Pが存在するかどうか調べるプログラムを作成したいです。

置換行列Pが存在すれば、A2はA1に含まれる部分グラフだということまでわかったのですが、

Pの求め方がわからなくて困っています。

下のソースは置換行列Pが存在する場合の行列をA1とA2に設定しています。

ご教授願います。

よろしくお願いいたします。

 該当のソースコード

Option Explicit

Sub main()
    Dim A1
    Dim A2

    A1 = [{0,1,1,1,1,0,0,0,0,0,0;1,0,0,0,0,1,0,0,0,0,0;1,0,0,0,0,0,1,1,1,0,0;1,0,0,0,0,0,0,0,0,0,0;1,0,0,0,0,0,0,0,0,0,0;0,1,0,0,0,0,0,0,0,2,1;0,0,1,0,0,0,0,0,0,0,0;0,0,1,0,0,0,0,0,0,0,0;0,0,1,0,0,0,0,0,0,0,0;0,0,0,0,0,2,0,0,0,0,0;0,0,0,0,0,1,0,0,0,0,0}]
    A2 = [{0,1,0,0,0;1,0,1,0,0;0,1,0,2,1;0,0,2,0,0;0,0,1,0,0}]

    ' 置換行列Pが存在すれば、Pありと出力
    If SubgraphHomotyping(A1, A2) = True Then
        Debug.Print "Pあり"
    Else
        Debug.Print "Pなし"
    End If
End Sub

' 置換行列Pが存在するか判定する処理(存在すればTrue, 存在しなければFalse)
Function SubgraphHomotyping(A1 As Variant, A2 As Variant) As Boolean

    ' 処理をここに記述

    If Pが存在する Then
        SubgraphHomotyping = True
    Else
        SubgraphHomotyping = False
    End If

End Function
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

+1

http://www-erato.ist.hokudai.ac.jp/lecture2013/docs/washio2.pdf

こんなPDFを眺めてみました。p.7にある部分グラフ同型判定のところを見ますとNP完全問題とありました。p.9以降に様々な具体的手法が紹介されていますね。

p.9にUllmannの方法として「一定の約束事(行や列の順列など)で重複なく置換行列Pを生成する」と有りますが、この方法ではNP完全問題をまともに解く(有り得る様々なPを想定してしらみつぶしに調べてゆく)ということのように思えました。しかしこのページ以降に置換行列Pの大きさをしぼれそうな様々な手法が書かれていますね。

いずれにせよ少なくとも重複なく置換行列Pを生成するという論理が必要と思います。A1の大きさと重みありの個数を見ますと、まともに有り得る置換行列の全ての組み合わせを探索しても9!×2 = 725760となりますので素朴に総当たりしても(ご質問にある規模の問題なら)時間的には大丈夫な気がします。
(追記:最大30x30を想定しておられるとのことでまともに全探索するアプローチでは不十分と思いました)


追記:VBAではありませんが、ご要望があったので全探索をするPythonコードを参考までに挙げておきます。
適当に書いたままなのであまりよいコードではありませんが。

import numpy as np
import functools
import operator

A1=[
    [0,1,1,1,1,0,0,0,0,0,0],
    [1,0,0,0,0,1,0,0,0,0,0],
    [1,0,0,0,0,0,1,1,1,0,0],
    [1,0,0,0,0,0,0,0,0,0,0],
    [1,0,0,0,0,0,0,0,0,0,0],
    [0,1,0,0,0,0,0,0,0,2,1],
    [0,0,1,0,0,0,0,0,0,0,0],
    [0,0,1,0,0,0,0,0,0,0,0],
    [0,0,1,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,2,0,0,0,0,0],
    [0,0,0,0,0,1,0,0,0,0,0]
]
A2 = [
    [0,1,0,0,0],
    [1,0,1,0,0],
    [0,1,0,2,1],
    [0,0,2,0,0],
    [0,0,1,0,0]
]

A1 = np.array(A1, dtype=np.uint8)
A2 = np.array(A2, dtype=np.uint8)

def genp():
    # Pを次々に生成するジェネレーター
    # Pは5 x 11とする。1の場所は11個の中から5個選ぶ
    # itertools.permutationsを使えば単純にできるがあえて原始的に実装
    # 組み合わせはTC1 = 11 * 10 * 9 * 8 * 7
    S1 = [i for i in range(11, 6, -1)]
    TC1 = functools.reduce(operator.mul, S1)

    for tc1 in range(TC1):
        i1 = iii(S1, tc1)
        a = np.zeros((5, 11), dtype=np.uint8)
        for i in range(5):
            # print(f'i2[i]={i2[i]}, i1[i]={i1[i]}')
            a[i, i1[i]] = 1
        yield a

def iii(ss, t):
    # t番目の組み合わせのインデックスを生成
    i = [i for i in range(ss[0])]
    r = []
    for s in ss:
        j = t % s
        # print(f'j={j} i={i}')
        r.append(i[j])
        del i[j]
        t //= s
    return r

def main():
    count = 1
    g = genp()
    for p in g:
        A3 = p.dot(A1).dot(p.T)
        if np.all(A2 == A3):
            print(f'number of trials = {count}')
            print('p=')
            print(p)
            break
        count += 1
        # 探索の進捗具合の確認用
        if count % 10000 == 0:
            print(f'count={count}')

if __name__ == '__main__':
    main()


(Python 3.6.5)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/11 14:57

    しかし、まずは例にあげている11*5の置換行列を求めるプログラムをVBAで作ろうと思います。

    ところで、ご提示いただいたpythonコードのiii関数
    t //= s
    はどういう処理ですか?

    キャンセル

  • 2018/05/11 15:00

    t = t \ s
    です。すみませんがこのレベルの質問はご容赦ください。pythonの指導になってしまいます。それは本サイトで本来すべきことではないと思います。

    キャンセル

  • 2018/05/11 15:57

    申し訳ありません。
    以降気を付けます。
    お陰様でおおよそ理解できました。

    キャンセル

check解決した方法

0

お世話になっております。

ご提示いただいたpythonコードを参考に、VBAでも欲しい動作を得ることができました。
ご協力いただいた皆様ありがとうございました。

Option Explicit

Sub main()
    Dim A1  '(1 To 11, 1 To 11)
    Dim A2  '(1 To 5, 1 To 5)
    Dim A3  '(1 To 5, 1 To 5)
    Dim MatT
    Dim MatX
    Dim A1N As Integer
    Dim A2n As Integer
    Dim i, j As Long
    Dim P() As Integer
    Dim prm As Long
    Dim count As Long
    Dim count_ As Long
    Dim i1
    Dim prmttn

    A1 = [{0,1,1,1,1,0,0,0,0,0,0;1,0,0,0,0,1,0,0,0,0,0;1,0,0,0,0,0,1,1,1,0,0;1,0,0,0,0,0,0,0,0,0,0;1,0,0,0,0,0,0,0,0,0,0;0,1,0,0,0,0,0,0,0,2,1;0,0,1,0,0,0,0,0,0,0,0;0,0,1,0,0,0,0,0,0,0,0;0,0,1,0,0,0,0,0,0,0,0;0,0,0,0,0,2,0,0,0,0,0;0,0,0,0,0,1,0,0,0,0,0}]
    A2 = [{0,1,0,0,0;1,0,1,0,0;0,1,0,2,1;0,0,2,0,0;0,0,1,0,0}]

    A1N = 11
    A2n = 5

    ReDim P(1 To A1N, 1 To A2n)

    count = 0

    ' 11 * 5のあらゆる置換行列を生成・探索
    prmttn = Permutation(A1N, A2n)
    For prm = 1 To prmttn
        i1 = iii(prm, A1N, A2n)

        ' 11 * 5のゼロ行列を生成
        For i = 1 To A1N
            For j = 1 To A2n
                P(i, j) = 0
            Next j
        Next i

        ' 置換行列の1の要素を設定
        For i = 1 To A2n
            P(i1(i), i) = 1
        Next i

        ' PT * A1 * P (5 * 5)を計算
        MatT = MatrixT(P)
        MatX = MatrixCross(MatT, A1)
        A3 = MatrixCross(MatX, P)

        ' A2, A3を比較して、一致する要素をカウント
        count_ = 0
        For i = 1 To A2n
            For j = 1 To A2n
                If A2(i, j) = A3(i)(j) Then
                    count_ = count_ + 1
                End If
            Next j
        Next i
        ' A2, A3の要素がすべて一致すれば、"Pあり"と表示
        If count_ = A2n * A2n Then
            Debug.Print count
            Debug.Print "Pあり"

            Exit For
        End If

        count = count + 1

        ' 探索の進捗状況の確認
        If count Mod 10000 = 0 Then
            Debug.Print count
        End If

    Next prm

End Sub

' 行列同士の掛け算
Function MatrixCross(ByVal m1, ByVal m2)
    Dim ans
    Dim i, j, k
    Dim sum_

    ans = CreateMatrix(UBound(m1), UBound(m2, 2))
    For i = 1 To UBound(ans)
        For j = 1 To UBound(ans(2))
            sum_ = 0
            For k = 1 To UBound(m1(2))
                sum_ = sum_ + m1(i)(k) * m2(k, j)
            Next k
            ans(i)(j) = sum_
        Next j
    Next i
    MatrixCross = ans

End Function

' 行列の転置
Function MatrixT(ByVal m)
    Dim ans
    Dim i, j

    ans = CreateMatrix(UBound(m, 2), UBound(m))
    For i = 1 To UBound(ans)
        For j = 1 To UBound(ans(2))
            ans(i)(j) = m(j, i)
        Next j
    Next i
    MatrixT = ans

End Function

' 任意サイズの行列を作成
Function CreateMatrix(ByVal row_size, ByVal col_size)
    Dim ans, row
    Dim i

    ans = Array()
    ReDim ans(1 To row_size)
    For i = 1 To row_size
        row = Array() ' 新しいオブジェクトのインスタンス代入
        ReDim row(1 To col_size)
        ans(i) = row
    Next i

    CreateMatrix = ans

End Function

' t番目の組合せのインデックスを生成
Function iii(ByVal t As Long, A1N As Integer, A2n As Integer)
    Dim i()
    ReDim i(0 To A1N - 1)
    Dim r()
    Dim k As Integer
    Dim j As Integer
    Dim count As Integer
    count = 0

    ' i = 1 ~ A1N
    For k = 0 To A1N - 1
        i(k) = k + 1
    Next k

    ReDim r(1)
    For k = A1N To A1N - A2n + 1 Step -1
        count = count + 1
        j = t Mod k
        ReDim Preserve r(count)
        r(count) = i(j)
        Call ArrayRemove(i, j)
        t = t \ k

    Next k

    iii = r

End Function

' 配列の要素の削除
Sub ArrayRemove(ByRef TargetArray, ByVal deleteIndex As Integer)
    Dim i As Integer

    '削除したい要素以降の要素を前につめて上書きコピー
    For i = deleteIndex To UBound(TargetArray) - 1
        TargetArray(i) = TargetArray(i + 1)
    Next i

    '最後の要素を削除
    ReDim Preserve TargetArray(UBound(TargetArray) - 1)

End Sub

' 順列(nPk)の計算
Function Permutation(n, k)
    Dim i
    Dim nPk

    nPk = 1
    For i = n - k + 1 To n
        nPk = nPk * i
    Next i

    Permutation = nPk

End Function

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

ご提示のコードを動かそうとしましたが、
A1 = [{0,1,1・・・ の処理で既に動きませんが?

このコードはあなたが作ったものですか?
それとも、何かの宿題ですか?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/10 13:48 編集

    申し訳ありません。
    テキストファイルでコードを書いて、動作の確認をせずにあげてしまいました。
    宿題ではなく、自分で作成したものです。
    コードを修正しておきます。

    キャンセル

  • 2018/05/10 14:26 編集

    コメント欄には修正コード載せなくていいですよ。
    コメントが見づらくなっちゃうんで。

    あと、↓の判定で、「ElseIf ・・・ = False Then」は、
    「Else」でいいのでは?
    (2回処理する必要、無いですよね?)
    If SubgraphHomotyping(A1, A2) = True Then
    Debug.Print "Pあり"
    ElseIf SubgraphHomotyping(A1, A2) = False Then
    Debug.Print "Pなし"
    End If

    ※「If Pが存在する Then」の箇所も同様

    キャンセル

  • 2018/05/10 14:36

    ご回答いただきありがとうございます。

    その通りです。
    修正しておきます。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.34%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る