algorithm - 2つのグラフを部分的に比較する方法

Question

たとえば、これら2つのグラフは、完全に部分的に一致していると見なされます。

0-1

1-2

2-3

3-0

と

0-1

1-2

これら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による記事で言及されているアルゴリズムが1つあります。

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