python - 有没有一种简单的方法可以用蛮力算法计算两个图的图编辑距离？

Question

在不使用networkx内置函数的情况下，是否有一种简单的暴力算法可以计算G1和G2之间的图形编辑距离？

网上查了一下，只能找到硬最优解

Answer 1

根据Juan Carlos Ramirez的回复(他给出了算法的伪代码)，我终于实现了我所期待的丑陋的暴力算法。正如对话中提到的，它只处理小图，因为复杂性是指数级的。以下Python代码使用:

1. networkx(用于图形操作)
2. algorithmx(用于图形 2D 渲染)

  from networkx.classes.function import nodes
  
  import algorithmx
  import networkx as nx
  from algorithmx.networkx import add_graph
  
  canvas1 = algorithmx.jupyter_canvas()
  canvas2 = algorithmx.jupyter_canvas()
  # Create a directed graph
  G1 = nx.Graph()
  G2 = nx.Graph()
  
  # G1.add_edges_from([(1, 2), (7, 4), (2, 7),(3, 7)])
  # G2.add_edges_from([(1, 2), (3, 4), (2, 3), (3, 5)])
  
  G1.add_edges_from([(1, 2), (5, 4), (2, 5),(3, 5)])
  G2.add_edges_from([(1, 2), (3, 4), (2, 3), (3, 1)])
  
  
  
  def graph_distance(G1, G2):
    tmp_graphs = []
    next_graphs = [G1]
    dist = 0
    nId = 1000
  
    while 1:
      print(dist)
      for graph in next_graphs:
        if nx.is_isomorphic(graph, G2): # Check isomorphism for each built graph
          return dist
  
  
        new_graph = graph.copy()
        new_graph.add_node(len(graph.nodes))
        tmp_graphs.append(new_graph) # Add one vertex (that will be connected to the rest of the graph in the next iterations)
  
        graph_copy = graph.copy()
        for node in graph.nodes : # Add edge
          for newNeighbour in graph.nodes :
            if not graph.has_edge(node, newNeighbour):
              new_graph = graph.copy()
              new_graph.add_edge(node, newNeighbour)
              tmp_graphs.append(new_graph)
        
        for node in graph.nodes : # Delete edge
          for newNeighbour in graph.nodes:
            if graph.has_edge(node, newNeighbour):
              new_graph = graph.copy()
              new_graph.remove_edge(node, newNeighbour)
              tmp_graphs.append(new_graph)
            
        for node in graph.nodes : # Delete vetex
          new_graph = graph.copy()
          new_graph.remove_node(node)
          tmp_graphs.append(new_graph)
  
      dist+=1
      next_graphs = tmp_graphs
      tmp_graphs = []
      
      
   
        
  print("Graph edit distance is:",graph_distance(G1, G2))
  add_graph(canvas1, G1)
  add_graph(canvas2, G2)

  canvas1
  # canvas2

取消canvas1/canvas2的注释以显示您想要的