Imagine you have a network — like a map of interconnected computers or transit stations — and you're interested in finding groups of these points where none are directly linked together. We call such groups "independent sets." Traditionally, researchers have looked at these groups and at the ones that can’t have any more points added without breaking that no-connection rule, which we call maximal independent sets.
In my project, I'm taking this idea a step further by focusing on what's known as an Order-k Maximal Independent Set (MIS). Specifically, I'm looking at the case where k=3. What this means is that the group is so well-chosen that if you try to add or remove up to three points, you'll never be able to make a larger valid group that still follows the rule of no direct connections. It’s a way to measure how optimal or stable a group is against small disruptions.
I study these resilient groups within a particular type of network called a Lattice-Torus Product Graph, which is like a grid that's allowed to wrap around itself in as many directions as dimensions compose it. These complex networks are great models for real-world systems like communication networks or transportation grids.
By counting and analyzing these Order-3 MISs, my work aims to uncover new insights into the hidden symmetries and structural effects of these networks. Ultimately, understanding these robust configurations could help us design more efficient and reliable systems in everyday applications—from keeping our communication networks stable to ensuring that transportation systems can handle disruptions.
from itertools import product
def generate_cartesian_product(paths, cycles):
dimensions = cycles + paths
is_cycle = [True] * len(cycles) + [False] * len(paths)
all_nodes = list(product(*(range(d) for d in dimensions)))
graph = {node: [] for node in all_nodes}
for node in all_nodes:
for dim, (length, cycle_flag) in enumerate(zip(dimensions, is_cycle)):
if cycle_flag: # Cycle: wrap around
prev_node = list(node)
next_node = list(node)
prev_node[dim] = (node[dim] - 1) % length
next_node[dim] = (node[dim] + 1) % length
graph[node].append(tuple(prev_node))
graph[node].append(tuple(next_node))
else: # Path: no wrap-around
if node[dim] > 0:
prev_node = list(node)
prev_node[dim] -= 1
graph[node].append(tuple(prev_node))
if node[dim] < length - 1:
next_node = list(node)
next_node[dim] += 1
graph[node].append(tuple(next_node))
return graph
def count_maximal_independent_sets(graph):
def is_order_3_maximal(graph, independent_set):
#Maximal check
for node in graph:
if node not in independent_set:
if all(neighbor not in independent_set for neighbor in graph[node]):
return False
for vertex_to_remove in independent_set:
candidate_set = independent_set - {vertex_to_remove}
forbidden_vertices = set(candidate_set) | {neighbor for v in candidate_set for neighbor in graph[v]}
potential_additions = [v for v in graph if v not in forbidden_vertices]
for v1 in range(len(potential_additions)):
for v2 in range(v1 + 1, len(potential_additions)):
extended_set = candidate_set | {potential_additions[v1], potential_additions[v2]}
if is_independent_set(graph, extended_set):
return False
return True
def is_independent_set(graph, independent_set):
for node in independent_set:
for neighbor in graph[node]:
if neighbor in independent_set:
return False
return True
def dfs(remaining_nodes, current_set):
if not remaining_nodes:
return 1 if is_order_3_maximal(graph, current_set) else 0
node = remaining_nodes[0]
rest = remaining_nodes[1:]
# Include node
include_set = current_set | {node}
include_rest = [n for n in rest if n not in graph[node]]
count_with_node = dfs(include_rest, include_set)
# Exclude node
count_without_node = dfs(rest, current_set)
return count_with_node + count_without_node
nodes = list(graph.keys())
result = dfs(nodes, set())
return result
def input_list(prompt):
user_input = input(prompt)
if not user_input.strip():
return []
return [int(item.strip()) for item in user_input.split(',')]
# ------------------- #
while True:
print("------------------------------")
print("Enter the size of each Path and Cycle Graph. Separate the elements by commas.")
paths = input_list("Enter the path graphs: ")
cycles = input_list("Enter the cycle graphs: ")
graph = generate_cartesian_product(paths, cycles)
result = count_maximal_independent_sets(graph)
print("------------------------------")
print("Cycles:",cycles)
print("Paths:",paths)
print("Number of Order-3 Maximal Independent Sets:", result)
# ------------------- #
for summ in range(4,20):
print("--------------------------------------------------------")
for np in range(2,summ-1):
print("testing (",str(np),",",str(summ-np),") for lattices, cylinders, torus")
if(np>=2 and summ-np>=2):
graph1 = generate_cartesian_product([np,summ-np],[])
result1 = count_maximal_independent_sets(graph1)
print("\tfinished (",str(np),",",str(summ-np),") Latti:",result1)
else:
print("\tfinished (",str(np),",",str(summ-np),") Latti: ERR NiR")
if(np>=2 and summ-np>=3):
graph2 = generate_cartesian_product([np], [summ-np])
result2 = count_maximal_independent_sets(graph2)
print("\tfinished (",str(np),",",str(summ-np),") PC Cy:",result2)
else:
print("\tfinished (",str(np),",",str(summ-np),") PC Cy: ERR NiR")
if(np>=3 and summ-np>=3):
graph3 = generate_cartesian_product([],[np,summ-np])
result3 = count_maximal_independent_sets(graph3)
print("\tfinished (",str(np),",",str(summ-np),") Torus:",result3)
else:
print("\tfinished (",str(np),",",str(summ-np),") Torus: ERR NiR")
print("Finished!")