有沒有一種簡單的方法可以用蠻力演算法計算兩個圖的圖編輯距離？

在不使用 networkx 內置函式的情況下，是否有一種簡單的蠻力演算法可以計算G1和之間的圖形編輯距離G2？

我在網上搜索，但我只能找到很難的最優解

uj5u.com熱心網友回復：

這是一個非常低效的程序，但它確實解決了問題。這個想法是從“編輯圖”進行類似 Dijkstra 的最短路徑搜索，其中編輯圖中的節點表示圖，兩個節點之間有一條邊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回傳作為輸入圖鄰居的一組不同圖（直到同構）。如果 x 可以通過 1 次編輯從 y 獲得（反之亦然），則兩個圖 x,y 是鄰居。

uj5u.com熱心網友回復：

根據 Juan Carlos Ramirez 的回復（他給出了演算法的偽代碼），我終于實作了我期待的丑陋的 brutforce 演算法。正如對話中提到的，它只處理小圖，因為復雜性是指數級的。以下 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 以顯示您想要的

標籤：

上一篇：獲取深度嵌套物件中鍵的值

下一篇：內回圈的時間復雜度