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

Question

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

Answer 1

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