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

Question

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

我在网上搜索过，也只能找到硬最优解

Answer 1

这是一个非常低效的过程，但它确实解决了问题。这个想法是从“编辑图”中进行 Dijkstra-like shortest-path 搜索，编辑图中的节点代表图，两个节点之间有一条边 G_a, G_b 在编辑图表中，如果存在从 G_a 到 G_b 的编辑。请注意，您将需要一个函数 is_isomorphic(Gx,Gy) 来测试 Gx 和 Gy 是否是同构图（您可以通过检查所有节点排列来检查，同样非常昂贵）。

寻找最短编辑距离的算法如下：

initialize: current_node as  G1,
            visited_nodes as G1,
            current_minimum_cost_dictionary={G1:0}
            #overload == for Graph Class so that G==F iff is_isomorphic(G,F)
while G2 not in visited nodes:
    cost = current_minimum_cost_dictionary[G2]
    neighbor_graphs_set = calculate_distinct_neighbor_nodes(current_node)
        for graph in neighbor_graphs_set:
            if graph not in visited_nodes:
                visited_nodes.push(graph)
                current_minimum_cost_dictionary[graph] = cost + 1
            else:
                current_minimum_cost_dictionary[graph] = min(cost + 1, current_minimum_cost_dictionary[graph])
    #set current_node to the Graph with the minimum value in current_minimum_cost
return current_minimum_cost_dictionary(G2)

calculate_distinct_neighbor_nodes returns 与输入图相邻的一组不同的图（直到同构）。如果可以通过 1 次编辑（反之亦然）从 y 获得 x，则两个图 x，y 是邻居。

Answer 2

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

networkx（用于图形操作）
algorithmx（图形二维渲染）

  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以显示您想要的那个

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

Is there an easy way to calculate the graph edit distance of two graphs with a brut force algorithm?

python

algorithm

graph

networkx