java - jar ファイルのグラフ同形

Question

私は *.jar ファイルとグラフの同形を扱っています。2 つの *.jar ファイル間のグラフ同型性をチェックしたいと考えています。このためのpythonまたはrubyのライブラリはありますか。私はigraphまたは何でそれを行うことができますか?

ありがとう。

Answer 1

これは、あなたが求めていると私が理解していることを行うための基礎として、NetworkX 同形チェックを使用する取り組みです...

たとえば、こちらのメソッドを使用して、2 つの jar ファイルの内容を含むテキスト ファイルを作成するとします。

このコードは、2 つの jar ファイルをロードし、グラフを NetworkX にロードします。ここでの例は、各パス名に 2 つのレベルのみで単純化されていますが、一般的な原則は同じままです... いくつかのサンプル コンテンツを投稿すると、get_edges()関数を微調整して、より深いレベルのネストを処理できます。

import networkx as nx
from networkx.algorithms import isomorphism

# Contents of two jar files listed, as in
# http://java.sun.com/developer/Books/javaprogramming/JAR/basics/view.html
jar1 = '''a/g
a/h
a/i
b/g
b/h
b/j
c/g
c/i
c/j
d/h
d/i
d/j'''

jar2 = '''1/2
2/3
3/4
4/1
5/6
6/7
7/8
8/5
1/5
2/6
3/7
4/8'''

def get_edges(jar):
    nodes = set( jar.replace('\n', '/').split('/') )
    nodes = dict( zip(nodes, range(len(nodes)) ) )
    edges = [ edge.split('/') for edge in jar.split('\n') ]
    edges = [ (nodes[ edge[0] ],nodes[ edge[1] ]) for edge in edges ]
    return edges

if __name__ == '__main__':
    G1 = nx.Graph()
    G1.add_edges_from( get_edges(jar1) )

    G2 = nx.Graph()
    G2.add_edges_from( get_edges(jar2) )
    print 'Edges from jar1: ', G1.edges()
    print 'Edges from jar2: ', G2.edges()

    GM = isomorphism.GraphMatcher(G1,G2)
    print 'Isomorphic: ', GM.is_isomorphic()
    print 'Mapping between the two jars: ', GM.mapping

これは次のように表示されます。

Edges from jar1:  [(0, 4), (0, 5), (0, 6), (1, 4), (1, 5), (1, 7), (2, 4), (2, 6), (2, 7), (3, 5), (3, 6), (3, 7)]
Edges from jar2:  [(0, 2), (0, 3), (0, 4), (1, 2), (1, 4), (1, 5), (2, 6), (3, 6), (3, 7), (4, 7), (5, 6), (5, 7)]
Isomorphic:  True
Mapping between the two jars:  {0: 0, 1: 1, 2: 6, 3: 7, 4: 2, 5: 4, 6: 3, 7: 5}

お役に立てれば。