Without using the networkx built-in function, is there an easy brut force algorithm that calculates the graph edit distance between G1 and G2?

I searched on the Internet, but I could only find hard optimal solutions

CodePudding user response：

Here is a very inefficient process, but it does solve the problem. The idea will be to do a Dijkstra-like shortest-path search from the "edit graph", where the nodes in the edit graph represent Graphs, there is an edge between two nodes G_a, G_b in an edit graph if there is an edit that takes G_a to G_b. Note, you will need you will need a function is_isomorphic(Gx,Gy) which tests whether Gx and Gy are isomorphic graphs (which you can check by checking all the node permutations, again very costly).

The algorithm to find shortest edit distance would be as follows:

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 the set of distinct graphs (up to isomorphism)that are neighbors of the input graph. two graphs x,y are neighbors if x can be obtained from y by 1 edit (or viceversa).

CodePudding user response：

According to Juan Carlos Ramirez reply (who gave a pseudo code of the algorithm), I finally implemented the ugly brutforce algorithm I was expecting. As mentionned in the conversation, it only deals with small graphs as the complexity is exponential. The following Python code uses:

1. networkx (for graph manipulation)
2. algorithmx (for graph 2D-rendering)

  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

Uncomment canvas1/canvas2 to display the one you want