How to partially compare two graphs

Question

For example, these two graphs are considered an ideal partial match:

0 - 1

12

2 - 3

thirty

and

0 - 1

12

These two are considered a bad coincidence.

0 - 1

12

2 - 3

thirty

and

0 - 1

12

20

The numbers should not match if the connection between these nodes can perfectly match.

Answer 1

This is a subgraph isomorphism problem: http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

There is one algorithm mentioned in the article due to Ullman.

Ullman's algorithm is an extension of the depth search. Depth search will work as follows:

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 

For the main algorithm, possible_assignments[i] = range(0,graph.n_vertices) . That is, all the vertices are possible.

Ullmann extends this basic algorithm, 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 

The idea is that if the node i of the subgraph can correspond to the node j of the graph, then for each node x adjacent to node i in the subgraph, it should be possible to find the node y adjacent to node j on the graph. This process helps more than it may be obvious at first, because every time we eliminate a possible assignment, it can lead to the elimination of other possible assignments, since they are interdependent.

The final algorithm:

 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