68 lines
2.0 KiB
Python
68 lines
2.0 KiB
Python
def build_graph(node_list):
|
|
"""
|
|
Build a graph where:
|
|
- Each graph starts with a node containing `0`.
|
|
- Nodes are connected if they share a common value, except `0` cannot connect to another `0`.
|
|
"""
|
|
graph = {}
|
|
|
|
# Parse nodes
|
|
parsed_nodes = [tuple(map(int, node.split('/'))) for node in node_list]
|
|
|
|
# Build adjacency list
|
|
for node1 in parsed_nodes:
|
|
for node2 in parsed_nodes:
|
|
# Skip if both nodes contain `0`
|
|
if node1 == node2 or (0 in node1 and 0 in node2):
|
|
continue
|
|
|
|
# Add edge if they share a common value
|
|
if node1[0] == node2[0] or node1[1] == node2[1] or node1[0] == node2[1] or node1[1] == node2[0]:
|
|
graph.setdefault(node1, []).append(node2)
|
|
graph.setdefault(node2, []).append(node1)
|
|
|
|
return graph
|
|
|
|
def find_paths(graph, start, visited=None, path=None):
|
|
"""
|
|
Recursively find all paths starting from a given node.
|
|
Ensures that each node is visited only once per path.
|
|
"""
|
|
if visited is None:
|
|
visited = set()
|
|
if path is None:
|
|
path = []
|
|
|
|
visited.add(start)
|
|
path.append(start)
|
|
|
|
# Print the current path
|
|
#print(" \--".join(f"{node[0]}/{node[1]}" for node in path))
|
|
|
|
# Explore neighbors
|
|
for neighbor in graph.get(start, []):
|
|
if neighbor not in visited:
|
|
find_paths(graph, neighbor, visited.copy(), path.copy())
|
|
return path
|
|
|
|
def main():
|
|
# Input list of nodes
|
|
nodes = [
|
|
"0/2", "2/2", "2/3", "3/4", "3/5", "0/1", "10/1", "9/10"
|
|
]
|
|
|
|
# Build the graph
|
|
graph = build_graph(nodes)
|
|
results = []
|
|
# Find and print all paths for each subgraph starting with a `0` node
|
|
zero_nodes = [node for node in graph if 0 in node]
|
|
for start in zero_nodes:
|
|
print(f"Starting from {start[0]}/{start[1]}:")
|
|
tmp = find_paths(graph, start)
|
|
results.append(tmp)
|
|
|
|
print(results)
|
|
|
|
if __name__ == "__main__":
|
|
main()
|