一種子圖匹配裝置，用于在大規(guī)模圖中查找出與帶環(huán)圖匹配的子圖，包括：生成樹模塊、匹配模塊、判斷模塊以及集合模塊。生成樹模塊根據(jù)最小生成樹算法找到帶環(huán)圖的生成樹；匹配模塊自底向上對(duì)數(shù)據(jù)圖進(jìn)行生成樹匹配，尋找與生成樹匹配的樹Li（i>=1）；判斷模塊判斷所述樹Li的評(píng)分函數(shù)值與缺失邊數(shù)之和是否大于等于預(yù)設(shè)值，若是，則判斷模塊判斷樹Li能否擴(kuò)展為帶環(huán)圖；集合模塊還在所述樹Li的評(píng)分函數(shù)值與缺失邊數(shù)之和大于等于預(yù)設(shè)值時(shí)將所述集合V中前固定值個(gè)匹配圖輸出。

1.一種子圖匹配裝置，用于在大規(guī)模圖中查找出與帶環(huán)圖匹配的
子圖，包括：
生成樹模塊，用于根據(jù)最小生成樹算法找到所述帶環(huán)圖的生成樹；
匹配模塊，用于自底向上對(duì)數(shù)據(jù)圖進(jìn)行生成樹匹配，尋找與生成樹
匹配的樹Li；
判斷模塊，用于判斷所述樹Li的評(píng)分函數(shù)值與缺失邊數(shù)之和是否大
于等于預(yù)設(shè)值，其中，所述判斷模塊還用于在所述樹Li的評(píng)分函數(shù)值與
缺失邊數(shù)之和小于預(yù)設(shè)值時(shí)判斷所述樹Li能否擴(kuò)展為帶環(huán)圖；
集合模塊，用于在樹Li能擴(kuò)展為帶環(huán)圖時(shí)將所述樹Li擴(kuò)展為匹配
圖，并存入集合V中，其中，所述集合模塊還用于將所述集合V中的匹
配圖按照權(quán)重從小到大來排序，所述判斷模塊還用于判斷集合V中匹配
圖的個(gè)數(shù)是否大于等于固定值，且在集合V中匹配圖的個(gè)數(shù)大于等于固
定值時(shí)將所述預(yù)設(shè)值設(shè)為第固定值個(gè)匹配圖的權(quán)重；
其中，所述集合模塊還用于在所述樹Li的評(píng)分函數(shù)值與缺失邊數(shù)之
和大于等于預(yù)設(shè)值時(shí)將所述集合V中前固定值個(gè)匹配圖輸出。
2.如權(quán)利要求1所述的子圖匹配裝置，其特征在于，所述集合模
塊在所述樹Li不能擴(kuò)展為帶環(huán)圖時(shí)丟棄樹Li。
3.如權(quán)利要求1所述的子圖匹配裝置，其特征在于，評(píng)分函數(shù)為：
s c o r e ( M Q ) = Σ ( X ; Y ) ∈ E ( Q ) C ( X ; Y ) d i s t ( u ; v ) ]]>
其中u，v∈M_Q，M_Q是查詢圖Q在數(shù)據(jù)圖G_D中的匹配圖，
(X；Y)＝(λ^-1(u)；λ^-1(v))為查詢圖Q中的邊，C(X；Y)為與查詢邊(X；Y)關(guān)
聯(lián)的系數(shù)，dist(u；v)表示頂點(diǎn)u和v的最短路徑的距離值。
4.如權(quán)利要求1所述的子圖匹配裝置，其特征在于，所述匹配模
塊包括：
分解子模塊，用于將所述生成樹自頂向下分解為只有邊的子樹；
判斷子模塊，用于判斷子樹生長(zhǎng)后形成的樹是否為I型子樹，所述
I型子樹為葉子節(jié)點(diǎn)無兄弟的樹；
尋找子模塊，用于在所述子樹生長(zhǎng)后形成的樹為I型子樹時(shí)在所述
數(shù)據(jù)圖中尋找所述子樹的根結(jié)點(diǎn)到葉子節(jié)點(diǎn)的最優(yōu)結(jié)果，放入pTable中，
其中，所述尋找子模塊還用于將所述pTable中權(quán)重值最小的數(shù)據(jù)放入
sTable中，并刪除pTable中權(quán)重值最小的數(shù)據(jù)，所述判斷子模塊還用于
判斷所述子樹是否為最后一棵子樹；
輸出子模塊，用于在所述子樹是最后一棵子樹時(shí)將所述sTable的內(nèi)
容作為所述生成樹的一個(gè)匹配的樹Li。
5.如權(quán)利要求4所述的子圖匹配裝置，其特征在于，所述尋找子
模塊還用于在所述子樹生長(zhǎng)后形成的樹不為I型子樹時(shí)在所述數(shù)據(jù)圖中
尋找所述子樹的兄弟節(jié)點(diǎn)之間的最優(yōu)結(jié)果，放入pTable中。
6.如權(quán)利要求4所述的子圖匹配裝置，其特征在于，所述分解子
模塊還用于在所述子樹不是最后一棵子樹時(shí)將所述子樹作為葉子節(jié)點(diǎn)。
7.一種子圖匹配的方法，用于在大規(guī)模圖中查找出與帶環(huán)圖匹配
的子圖，其特征在于，所述方法包括以下步驟：
根據(jù)最小生成樹算法找到所述帶環(huán)圖的生成樹；
自底向上對(duì)數(shù)據(jù)圖進(jìn)行生成樹匹配，尋找與生成樹匹配的樹Li；
判斷所述樹Li的評(píng)分函數(shù)值與缺失邊數(shù)之和是否大于等于預(yù)設(shè)值；
若所述樹Li的評(píng)分函數(shù)值與缺失邊數(shù)之和小于預(yù)設(shè)值，則判斷所述
樹Li能否擴(kuò)展為帶環(huán)圖；
若所述樹Li能擴(kuò)展為帶環(huán)圖，則將所述樹Li擴(kuò)展為匹配圖，并存
入集合V中；
將所述集合V中的匹配圖按照權(quán)重從小到大來排序；
判斷所述集合V中匹配圖的個(gè)數(shù)是否大于等于固定值；
若所述集合V中匹配圖的個(gè)數(shù)大于等于固定值，則將所述預(yù)設(shè)值設(shè)
為第固定值個(gè)匹配圖的權(quán)重，其中，若所述樹Li的評(píng)分函數(shù)值與缺失邊
數(shù)之和大于等于預(yù)設(shè)值，則將所述集合V中前固定值個(gè)匹配圖輸出。
8.如權(quán)利要求7所述的子圖匹配的方法，其特征在于，還包括以
下步驟：
若所述樹Li不能擴(kuò)展為帶環(huán)圖時(shí)，則丟棄樹Li。
9.如權(quán)利要求7所述的子圖匹配的方法，其特征在于，所述評(píng)分
函數(shù)為：
s c o r e ( M Q ) = Σ ( X ; Y ) ∈ E ( Q ) C ( X ; Y ) d i s t ( u ; v ) ]]>
其中u，v∈M_Q，M_Q是查詢圖Q在數(shù)據(jù)圖G_D中的匹配圖，
(X；Y)＝(λ^-1(u)；λ^-1(v))為查詢圖Q中的邊，C(X；Y)為與查詢邊(X；Y)關(guān)
聯(lián)的系數(shù)，dist(u；v)表示頂點(diǎn)u和v的最短路徑的距離值。
10.如權(quán)利要求7所述的子圖匹配的方法，其特征在于，步驟“自底
向上對(duì)數(shù)據(jù)圖進(jìn)行生成樹匹配，尋找與生成樹匹配的樹Li”包括以下步
驟：
將所述生成樹自頂向下分解為只有邊的子樹；
判斷子樹生長(zhǎng)后形成的樹是否為I型子樹，所述I型子樹為葉子節(jié)
點(diǎn)無兄弟的樹；
若所述子樹生長(zhǎng)后形成的樹為I型子樹，則在所述數(shù)據(jù)圖中尋找所
述子樹的根結(jié)點(diǎn)到葉子節(jié)點(diǎn)的最優(yōu)結(jié)果，放入pTable中；
將所述pTable中權(quán)重值最小的數(shù)據(jù)放入sTable中，并刪除pTable
中權(quán)重值最小的數(shù)據(jù)；
判斷所述子樹是否為最后一棵子樹；
若所述子樹為最后一棵子樹時(shí)將所述sTable的內(nèi)容作為所述生成樹
的一個(gè)匹配的樹Li。
11.如權(quán)利要求10所述的子圖匹配的方法，其特征在于，步驟“自
底向上對(duì)數(shù)據(jù)圖進(jìn)行生成樹匹配，尋找與生成樹匹配的樹Li”還包括以
下步驟：
若所述子樹生長(zhǎng)后形成的樹不為I型子樹，則在所述數(shù)據(jù)圖中尋找
所述子樹的兄弟節(jié)點(diǎn)之間的最優(yōu)結(jié)果，放入pTable中。
12.如權(quán)利要求10所述的子圖匹配的方法，其特征在于，步驟“自
底向上對(duì)數(shù)據(jù)圖進(jìn)行生成樹匹配，尋找與生成樹匹配的樹Li”還包括以
下步驟：
若所述子樹不是最后一棵子樹，則將所述子樹作為葉子節(jié)點(diǎn)。