如何部分比较两个图形

Question

例如，这两个图被认为是完美的部分匹配：

0 - 1

1 - 2

2 - 3

3 - 0

和

0 - 1

1 - 2

这两者被认为是一个糟糕的匹配

0 - 1

1 - 2

2 - 3

3 - 0

和

0 - 1

1 - 2

2 - 0

这些

数字不必匹配，只要这些节点之间的关系可以完全匹配即可。

Answer 1

这是子图同构问题： http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

由于 Ullmann，文章中提到了一种算法。

Ullmann算法是深度优先搜索的扩展。 深度优先搜索的工作方式如下：

def search(graph,subgraph,assignments):
  i=len(assignments)
  # Make sure that every edge between assigned vertices in the subgraph is also an
  # edge in the graph.
  for edge in subgraph.edges:
    if edge.first<i and edge.second<i:
      if not graph.has_edge(assignments[edge.first],assignments[edge.second]):
        return False
  # If all the vertices in the subgraph are assigned, then we are done.
  if i==subgraph.n_vertices:
    return True
  # Otherwise, go through all the possible assignments for the next vertex of
  # the subgraph and try it.
  for j in possible_assignments[i]:
    if j not in assignments:
      assignments.append(j)
      if search(graph,subgraph,assignments):
        # This worked, so we've found an isomorphism.
        return True
      assignments.pop()
def find_isomorphism(graph,subgraph):
  assignments=[]
  if search(graph,subgraph,assignments):
    return assignments
  return None

对于基本算法，possible_assignments[i] = range(0,graph.n_vertices) . 也就是说，所有顶点都是可能的。

Ullmann 通过缩小可能性来扩展此基本算法：

def update_possible_assignments(graph,subgraph,possible_assignments):
  any_changes=True
  while any_changes:
    any_changes = False
    for i in range(0,len(subgraph.n_vertices)):
      for j in possible_assignments[i]:
        for x in subgraph.adjacencies(i):
          match=False
          for y in range(0,len(graph.n_vertices)):
            if y in possible_assignments[x] and graph.has_edge(j,y):
              match=True
          if not match:
            possible_assignments[i].remove(j)
            any_changes = True

这个想法是，如果子图的节点 i 可能与图的节点 j 匹配，那么对于子图中与节点 i 相邻的每个节点 x，必须能够找到与图中节点 j 相邻的节点 y。 这个过程比最初显而易见的更有帮助，因为每次我们消除可能的赋值时，这都可能导致其他可能的赋值被消除，因为它们是相互依赖的。

最终的算法是：

def search(graph,subgraph,assignments,possible_assignments):
  update_possible_assignments(graph,subgraph,possible_assignments)
  i=len(assignments)
  # Make sure that every edge between assigned vertices in the subgraph is also an
  # edge in the graph.
  for edge in subgraph.edges:
    if edge.first<i and edge.second<i:
      if not graph.has_edge(assignments[edge.first],assignments[edge.second]):
        return False
  # If all the vertices in the subgraph are assigned, then we are done.
  if i==subgraph.n_vertices:
    return True
  for j in possible_assignments[i]:
    if j not in assignments:
      assignments.append(j)
      # Create a new set of possible assignments, where graph node j is the only 
      # possibility for the assignment of subgraph node i.
      new_possible_assignments = deep_copy(possible_assignments)
      new_possible_assignments[i] = [j]
      if search(graph,subgraph,assignments,new_possible_assignments):
        return True
      assignments.pop()
    possible_assignments[i].remove(j)
    update_possible_assignments(graph,subgraph,possible_assignments)
def find_isomorphism(graph,subgraph):
  assignments=[]
  possible_assignments = [[True]*graph.n_vertices for i in range(subgraph.n_vertices)]
  if search(graph,subgraph,assignments,possible_assignments):
    return assignments
  return None