问题描述
例如，这两个图形被认为是完美的部分匹配
For example, these two graphs is considered to be a perfect partial match:
0 - 1
1 - 2
2 - 3
3 - 0
和
0 - 1
1 - 2
这两个被认为是一个糟糕的比赛
These two are considered a bad match
0 - 1
1 - 2
2 - 3
3 - 0
和
0 - 1
1 - 2
2 - 0
的数字不具有匹配的，只要这些节点之间的关系可以完美匹配
The numbers don't have to match, as long as the relation between those nodes can perfectly match.
推荐答案
这是子图同构问题：http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem
目前由于乌尔曼在文章中提到的一种算法。
There is one algorithm mentioned in the article due to Ullmann.
乌尔曼的算法是一个深度优先搜索的扩展。深度优先搜索将像这样的工作：
Ullmann's algorithm is an extension of a depth-first search. A depth-first search would work like this:
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_isomporhism(graph,subgraph):
assignments=[]
if search(graph,subgraph,assignments):
return assignments
return None
有关的基本算法， possible_assignments [I] =范围（0，graph.n_vertices）。也就是说，所有的顶点是一种可能性。
For the basic algorithm, possible_assignments[i] = range(0,graph.n_vertices). That is, all the vertices are a possibility.
乌尔曼通过缩小的可能性扩展了这个基本算法：
Ullmann extends this basic algorithm by narrowing the possibilities:
def update_possible_assignements(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，然后为每一个节点x即相邻节点i的子图，它有可能找到一个节点y表示相邻到节点j的曲线图。这个过程有助于多于威力第一是显而易见的，因为每次我们消除一个可能的分配，这可能会导致其他可能的分配来消除，因为它们是相互依存
The idea is that if node i of the subgraph could possibly match node j of the graph, then for every node x that is adjacent to node i in the subgraph, it has to be possible to find a node y that is adjacent to node j in the graph. This process helps more than might first be obvious, because each time we eliminate a possible assignment, this may cause other possible assignments to be eliminated, since they are interdependent.
最后的算法则：
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_isomporhism(graph,subgraph):
assignments=[]
possible_assignments = [[True]*graph.n_vertices for i in range(subgraph.n_vertices)]
if search(graph,subgraph,asignments,possible_assignments):
return assignments
return None
这篇关于如何部分比较两个图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！