कैसे आंशिक रूप से दो रेखांकन

Question

उदाहरण के लिए तुलना करने के लिए, इन दो रेखांकन एक आदर्श आंशिक मैच माना जाता है - 0

और

0 - 1

+०१२३५१६४१०

1 - 2

इन दोनों खराब मिलान

0 माना जाता है - 1

1 - 2

2 - 3

3 - 0

और

0 - 1

1 - 2

2 - 0

संख्या उन नोड्स पूरी तरह से कर सकते हैं मैच के बीच संबंध के रूप में मैच के लिए, जब तक जरूरत नहीं है।

Answer 1

इस subgraph समाकृतिकता समस्या है: http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

वहाँ एक एल्गोरिथ्म Ullmann की वजह से लेख में वर्णित है।

उलमैन का एल्गोरिदम गहराई-पहली खोज का विस्तार है। possible_assignments[i] = range(0,graph.n_vertices)

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 

बुनियादी एल्गोरिथ्म के लिए,: एक गहराई-पहले खोज इस तरह काम करेगा। यही है, सभी शिखर एक संभावना है।

Ullmann संभावनाओं को सीमित करने से यह बुनियादी एल्गोरिथ्म लागू होता है:

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 

विचार यह है कि अगर नोड subgraph की मैं संभवतः के लिए प्रत्येक नोड एक्स उस नोड के निकट है ग्राफ के नोड j, तो मेल खा सकते हैं मैं उपग्राफ में, ग्राफ़ में नोड जे के नजदीक नोड वाई ढूंढना संभव है। यह प्रक्रिया सबसे पहले स्पष्ट हो सकती है, क्योंकि हर बार जब हम एक संभावित असाइनमेंट को खत्म करते हैं, तो इससे अन्य संभावित असाइनमेंट समाप्त हो सकते हैं, क्योंकि वे परस्पर निर्भर हैं।

अंतिम एल्गोरिथ्म तो है:

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