我有两个Python文件.我生成了两个NetworkX图,只是遍历了文件的AST.我想判断一下--是否有一个图的子图与另一个图同构?

100

whiletest.py

a= 10
while(a <= 0):
    if a == 5:
        print(a)
        a += 1
print("exited")

whiletestchanged.py

a= 10
# ANBD
'''
Test Someting
'''
while(a <= 0): #   print("a is:", a)    
    if a == 5:   # if a is 5, then break  
        print(a) 
    a += 1
    # a += 1 
print("exited")

100

class GetNXgraphFromAST(ast.NodeVisitor):
    def __init__(self):
        self.stack = []
        self.graph = nx.Graph()

    def generic_visit(self, stmt):
        node_name = stmt
        parent_name = None

        if self.stack:
            parent_name = self.stack[-1]

        self.stack.append(node_name)
        self.graph.add_node(node_name)

        if parent_name:
            self.graph.add_edge(node_name, parent_name)

        super(self.__class__, self).generic_visit(stmt)
        self.stack.pop()

100

whiletest.png

enter image description here

whiletestchanged.png

enter image description here

100

nodesoriginal = ast.parse(srcOriginal)
nodesbackport = ast.parse(srcBackport)
OriginalNXGraphIni = GetNXgraphFromAST()
BackportNXGraphIni = GetNXgraphFromAST()
OriginalNXGraphIni.visit(nodesoriginal) 
BackportNXGraphIni.visit(nodesbackport)
OriginalNXGraph = OriginalNXGraphIni.graph
BackportNXGraph = BackportNXGraphIni.graph

isomorphicSUbGraphs = isomorphism.GraphMatcher(OriginalNXGraph, BackportNXGraph)
for subGraph in isomorphicSUbGraphs.subgraph_isomorphisms_iter():
    subGraph = subGraph
    break 

但它没有检测到任何子同构图.我犯了什么错误吗?事先感谢您在这方面的帮助.

推荐答案

下面的代码接受两个Python源字符串,判断是否存在同构子图,然后打印结果:

import ast
import collections

def tree_attrs(tree):
   #extract AST node's attributes for matching later
   return (t:=type(tree)).__name__, \
    {a:getattr(tree, a) for a in t._fields if not isinstance(getattr(tree, a), 
                                                        (ast.AST, list))}, \
    [i for i in t._fields if isinstance(getattr(tree, i), (ast.AST, list))]
    
def build_graph(tree, d1, d2, p = []):
   #recursively build subgraph from a starting AST node
   #potential child nodes can be discovered by checking d1 and d2
   if str(attrs:=tree_attrs(tree)) in d2 and \
      any(p == p1[-1*len(p):] or not p for _, p1 in d2[str(attrs)]):
      ast_attrs = {}
      for i in attrs[2]:
         if isinstance(v:=getattr(tree, i), list):
            ast_attrs[i] = [result for j in v if (result:=build_graph(j, d1, d2, p+[type(tree).__name__])) is not None]
         elif (result:=build_graph(v, d1, d2, p+[type(tree).__name__])) is not None:
            ast_attrs[i] = result
      return type(tree)(**attrs[1], **ast_attrs, **{i:getattr(tree, i, 0) 
             for i in type(tree)._attributes})   

def walk(tree, p = []):
   #get all AST nodes from the .py source, along with its ancestor hierarchy
   yield tree, p
   for i in tree._fields:
     if isinstance(v:=getattr(tree, i), list):
       for j in v:
          yield from walk(j, p + [type(tree).__name__])
     elif isinstance(v, ast.AST):
        yield from walk(v, p + [type(tree).__name__])

def subgraphs(s1, s2):
   #build AST node lookup from both .py sources
   #these lookups are later used to find valid children for any given AST node
   d1, d2 = collections.defaultdict(list), collections.defaultdict(list)
   for i, p in walk(ast.parse(s1)):
      d1[str(tree_attrs(i))].append((i, p))
   for i, p in walk(ast.parse(s2)):
      d2[str(tree_attrs(i))].append((i, p))
   return [build_graph(i, d1, d2) for i in ast.walk(ast.parse(s1))]
   
def valid_py_subgraphs(sub_g):
   result = []
   for i in sub_g:
      try:
         if (r:=ast.unparse(i)):
            result.append(r)
      except: pass
   return result

s1 = """
a= 10
while(a <= 0):
    if a == 5:
        print(a)
        a += 1
print("exited")
"""
s2 = """a= 10
# ANBD
'''
Test Someting
'''
while(a <= 0): #   print("a is:", a)    
    if a == 5:   # if a is 5, then break  
        print(a) 
    a += 1
    # a += 1 
print("exited")"""
sub_g = valid_py_subgraphs(subgraphs(s1, s2))
print(bool(sub_g))
print('='*20)
for i in sub_g:
  print(i)
  print('-'*20)

示例输出:

True
====================
a = 10
while a <= 0:
    if a == 5:
        print(a)
print('exited')
--------------------
a = 10
--------------------
while a <= 0:
    if a == 5:
        print(a)
--------------------
print('exited')
--------------------
a
--------------------
10
--------------------
a <= 0
--------------------
if a == 5:
    print(a)
--------------------
print('exited')
--------------------
a += 1
--------------------
print(a)
--------------------
...

s3 = """
def main(a, b, c):
    return [i for i in range([3, 4])]
"""
s4 = """
def main(a, b, n = 10):
   return [i for i in range([1, 2, 3])]
"""
sub_g = valid_py_subgraphs(subgraphs(s3, s4))
print(bool(sub_g))
for i in sub_g:
  print(i)
  print('-'*20)

示例输出:

True
====================
def main(a, b):
    return [i for i in range([3])]
--------------------
a, b
--------------------
return [i for i in range([3])]
--------------------
a
--------------------
b
--------------------
[i for i in range([3])]
--------------------
 for i in range([3])
--------------------
i
--------------------
range([3])
--------------------
range
--------------------
[3]
--------------------
3
--------------------
...

s5 = """
def test(a:int, b:str) -> None:
   x += 1
"""
s6 = """
for i in range(10):
   print(i)
"""
sub_g = valid_py_subgraphs(subgraphs(s5, s6))
print(bool(sub_g))

输出:

False

Python相关问答推荐

python中csv. Dictreader. fieldname的类型是什么?'

我对这个简单的异步者的例子有什么错误的理解吗?

如何在GEKKO中使用复共轭物

Seaborn散点图使用多个不同的标记而不是点

类型对象';敌人';没有属性';损害';

一维不匹配两个数组上的广义ufunc

仅取消堆叠最后三列

有没有一种方法可以根据不同索引集的数组从2D数组的对称子矩阵高效地构造3D数组?

如何删除剪裁圆的对角线的外部部分

Pandas 数据框自定义排序功能

GEKKO中若干参数的线性插值动态优化

如何定义一个将类型与接收该类型的参数的可调用进行映射的字典?

Wagail:当通过外键访问索引页时,如何过滤索引页的子项

对齐多个叠置多面Seborn CAT图

用考克斯回归的生存分析系列的真值是模棱两可的.

收到Firebase推送通知时,电话不会震动

如何在JAX中训练具有多输出(向量值)损失函数的梯度下降模型?

使用Pandas 遍历词典

加快滚动总和计算速度?

如何使用libclang';S Python绑定获取返回类型和参数类型的完全限定名?