Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import string
- import random
- class Graph:
- def __init__(self, initial_data = None):
- if initial_data is None:
- initial_data = {}
- self.graph = initial_data
- def add_node(self,point):
- self.graph[point] = set()
- def add_edge(self,points):
- if points[1] not in self.graph[points[0]] and points[1] in self.graph:
- print(f"Adding edge from {points[0]} to {points[1]}")
- self.graph[points[0]].add(points[1])
- else:
- print("Cannot add edge")
- def nodes(self):
- return [x for x in self.graph]
- def edges(self):
- return [(k, v if v != set() else None) for k,v in self.graph.items()]
- def generate_random(self, size):
- possible_keys = string.ascii_lowercase
- for x in range(size):
- try:
- random_choice = random.choice([x for x in possible_keys if x not in self.graph])
- except IndexError:
- break
- if random_choice not in self.graph:
- self.add_node(random_choice)
- for y in self.graph:
- random_choice = random.choice([x for x in self.graph if x != y])
- if random_choice not in self.graph[y]:
- self.add_edge([y, random_choice])
- if random.random() > 0.5:
- random_choice = random.choice([x for x in self.graph if x != y])
- if random_choice not in self.graph[y] and random_choice != y:
- self.add_edge([y, random_choice])
- def explore(self):
- traversed = []
- def traverse(point):
- if point not in traversed:
- print(f"going from {point} to {self.graph[point]}")
- traversed.append(point)
- for x in self.graph[point]:
- traverse(x)
- while traversed != list(self.graph):
- try:
- random_choice = random.choice([x for x in self.graph if x not in traversed])
- traverse(random_choice)
- except IndexError:
- break
- my_graph = Graph()
- my_graph.generate_random(12)
- print(my_graph.nodes())
- print(my_graph.edges())
- my_graph.explore()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement