Simple Python GUI application to explore the differential of a given simple, undirected graph.
def determine_neighbourhood(edges, vertices, target_vertices=[]):
neighbourhood = []
for v in target_vertices:
for e in edges:
if v in e:
adjacent_vertex = vertices[vertices.index(e[(e.index(v)+1)%2])]
if adjacent_vertex not in target_vertices and adjacent_vertex not in neighbourhood:
neighbourhood.append(adjacent_vertex)
return neighbourhood
def calculate_all_subsets(vertices):
subsets = []
for n in range(1,len(vertices)+1):
for c in combinations(vertices, n):
subsets.append(c)
return subsets
def calculate_differentials(matrix):
vertices = determine_vertices(matrix)
edges = determine_edges(matrix, vertices)
graph_differential = None
subsets = calculate_all_subsets(vertices)
differential_groups = {}
for s in subsets:
this_neighbourhood = len(determine_neighbourhood(edges, vertices, s))
this_differential = this_neighbourhood-len(s)
if this_differential not in differential_groups:
differential_groups[this_differential] = [s]
else:
if differential_groups != {}:
differential_groups[this_differential].append(s)
if graph_differential == None or graph_differential < this_differential:
graph_differential = this_differential
return (vertices, edges, differential_groups, graph_differential)