Advertisement
Guest User

Untitled

a guest
Apr 21st, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.22 KB | None | 0 0
  1. import string
  2. import random
  3.  
  4. class Graph:
  5.     def __init__(self, initial_data = None):
  6.         if initial_data is None:
  7.             initial_data = {}
  8.         self.graph = initial_data
  9.  
  10.     def add_node(self,point):
  11.         self.graph[point] = set()
  12.  
  13.     def add_edge(self,points):
  14.         if points[1] not in self.graph[points[0]] and points[1] in self.graph:
  15.             print(f"Adding edge from {points[0]} to {points[1]}")
  16.             self.graph[points[0]].add(points[1])
  17.         else:
  18.             print("Cannot add edge")
  19.  
  20.     def nodes(self):
  21.         return [x for x in self.graph]
  22.  
  23.     def edges(self):
  24.         return [(k, v if v != set() else None) for k,v in self.graph.items()]
  25.  
  26.     def generate_random(self, size):
  27.         possible_keys = string.ascii_lowercase
  28.         for x in range(size):
  29.             try:
  30.                 random_choice = random.choice([x for x in possible_keys if x not in self.graph])
  31.             except IndexError:
  32.                 break
  33.             if random_choice not in self.graph:
  34.                 self.add_node(random_choice)
  35.  
  36.         for y in self.graph:
  37.             random_choice = random.choice([x for x in self.graph if x != y])
  38.             if random_choice not in self.graph[y]:
  39.                 self.add_edge([y, random_choice])
  40.                 if random.random() > 0.5:
  41.                     random_choice = random.choice([x for x in self.graph if x != y])
  42.                     if random_choice not in self.graph[y] and random_choice != y:
  43.                         self.add_edge([y, random_choice])
  44.  
  45.     def explore(self):
  46.         traversed = []
  47.         def traverse(point):
  48.             if point not in traversed:
  49.                 print(f"going from {point} to {self.graph[point]}")
  50.                 traversed.append(point)
  51.                 for x in self.graph[point]:
  52.                     traverse(x)
  53.         while traversed != list(self.graph):
  54.             try:
  55.                 random_choice = random.choice([x for x in self.graph if x not in traversed])
  56.                 traverse(random_choice)
  57.             except IndexError:
  58.                 break
  59.  
  60.  
  61.  
  62.  
  63.  
  64. my_graph = Graph()
  65.  
  66.  
  67. my_graph.generate_random(12)
  68. print(my_graph.nodes())
  69. print(my_graph.edges())
  70. my_graph.explore()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement