I am coding graph objects (vertex, edge, graph) in Python. I have a random_graph method which takes a list of vertices, and for each pair of vertices it places an edge between them with probability p. I have a is_connected method which returns whether or not a graph is connected.
I want to know the probability that a graph will be connected, given that it has n vertices and used probability p for random generation. This can be found without code, but I want to also calculate this experimentally with code, by generating a bunch of random graphs and seeing how many of them are connected.
Everything seems to work fine when I do this once: create a random graph and then check if it is connected. For example, I run the file over and over with probability 0.95 and every time it tells me the graph is connected, as it should with high probability. The problem is that when I put this same code into a loop to run it many times, the behavior changes. When in a loop, the (0-indexed) 3rd and 9th iteration print out that the graph is not connected.
Below is all my code, including play.py in both forms (non-loop which works and loop which gives the weird behavior):
*****
play.py (non-loop, works)
*****
from vertex import SimpleVertex
from edge import SimpleEdge
from graph import SimpleGraph
vertices = []
for i in xrange(10):
vertices.append(SimpleVertex('v'+str(i), i))
g = SimpleGraph.random_graph(vertices, p=1)
res = g.breadth_first_search(vertices[0])
print 'g is connected:'
print g.is_connected()
*****
play.py (loop, weird behavior)
*****
from vertex import SimpleVertex
from edge import SimpleEdge
from graph import SimpleGraph
for j in range(10):
vertices = []
for i in xrange(10):
vertices.append(SimpleVertex('v'+str(i), i))
g = SimpleGraph.random_graph(vertices, p=1)
res = g.breadth_first_search(vertices[0])
print 'g is connected:'
print g.is_connected()
*****
edge.py
*****
class SimpleEdge(object):
"""
Base class for edges of graphs with no concept of direction
"""
def __init__(self, v1, v2):
if v1 == v2:
raise Exception("Cannot make edge from " + str(v1) + " to itself.")
self.vertices = {v1, v2}
def __str__(self):
vertices = list(self.vertices)
return "Edge(%s, %s)" % (vertices[0], vertices[1])
def __eq__(self, other):
return self.vertices == other.vertices
*****
vertex.py
*****
from edge import SimpleEdge
class SimpleVertex(object):
"""
Base class for vertices of graphs with no concept of direction
"""
def __init__(self, name='', vid=None):
self.name = name
self.vid = vid if vid is not None else id(self)
self.edges = []
def __str__(self):
display = self.name if self.name else self.vid
return "Vertex(%s)" % display
def __eq__(self, other):
return self.vid == other.vid
def has_edge(self, edge):
""" Checks if a certain edge already exists on this vertex """
return edge in self.edges
def add_edge(self, other):
""" Adds an edge from this vertex to another vertex """
edge = SimpleEdge(self, other)
if self.has_edge(edge) or other.has_edge(edge):
raise Exception(str(edge) + " already exists.")
self.edges.append(edge)
other.edges.append(edge)
return edge
def neighbors(self):
""" List of vertices adjacent to this vertex """
neighbors = []
for edge in self.edges:
vertices = edge.vertices
for vertex in vertices:
if vertex != self:
neighbors.append(vertex)
return neighbors
def degree(self):
""" Number of neighbors this vertex has """
return len(self.neighbors())
def breadth_first_search(self, goal=None):
""" Beginning at this vertex, perform breadth-first search to find the
distance, in edges, to either some goal vertex or all vertices
reachable from this vertex """
vertex_queue = [(self, 0)]
seen_so_far = set([self])
dists = {}
# handle each vertex until there are no vertices left to check
while vertex_queue:
next_vertex, current_dist = vertex_queue.pop(0)
# if searching for a specific vertex, check if this is it
if goal is not None and next_vertex == goal:
return current_dist
# if this is the first time seeing this vertex, store its dist
if next_vertex not in dists:
dists[next_vertex] = current_dist
# put this vertex's neighbors onto the back of the queue
new_dist = current_dist + 1
for n in next_vertex.neighbors():
if n not in seen_so_far:
vertex_queue.append((n, new_dist))
seen_so_far.add(n)
# if searching for a specific vertex, it was not reachable
if goal is not None:
return -1
return dists
*****
graph.py
*****
from edge import SimpleEdge, DirectedEdge
import random
class SimpleGraph(object):
""" Base class for graphs with no concept of direction """
def __init__(self):
self.vertices = set()
self.edges = set()
def __str__(self):
vertices_str = ", ".join([str(vertex) for vertex in self.vertices])
edges_str = ", ".join([str(edge) for edge in self.edges])
return "Vertices: %s\nEdges: %s" % (vertices_str, edges_str)
def num_vertices(self):
""" Number of vertices in this graph """
return len(self.vertices)
def num_edges(self):
""" Number of edges in this graph """
return len(self.edges)
def has_vertex(self, vertex):
""" Checks if a certain vertex already exists in this graph """
return vertex in self.vertices
def has_edge(self, edge):
""" Checks if a certain edge already exists in this graph """
return edge in self.edges
def add_vertex(self, vertex):
""" Adds a vertex to this graph """
if vertex.degree():
raise Exception(str(vertex) + " has neighbors.")
if self.has_vertex(vertex):
raise Exception(str(vertex) + " already exists.")
self.vertices.add(vertex)
return vertex
def add_edge(self, v1, v2):
""" Adds an edge between two vertices in this graph """
edge = SimpleEdge(v1, v2)
if self.has_edge(edge):
raise Exception(str(edge) + " already exists.")
self.edges.add(v1.add_edge(v2))
return edge
def average_degree(self):
""" Average number of neighbors vertices in this graph have """
if not self.num_vertices:
return 0
return 2.0 * self.num_edges() / self.num_vertices()
@classmethod
def random_graph(cls, vertices, p=0.5):
""" Generate a graph using a set of vertices where each pair of vertices
has some probability of having an edge between them """
graph = cls()
for v1 in vertices:
graph.add_vertex(v1)
for v2 in graph.vertices:
if v1 > v2 and random.random() < p:
graph.add_edge(v1, v2)
return graph
@classmethod
def complete_graph(cls, vertices):
""" Generate a graph with all possible edges using a set of vertices """
return cls.random_graph(vertices, p=1.0)
def breadth_first_search(self, start, goal=None):
""" Beginning at some vertex, perform breadth-first search to find the
distance, in edges, to either some goal vertex or all vertices """
# perform breadth-frist search starting from the specified vertex
result = start.breadth_first_search(goal)
if goal is not None:
return result
# for all the unreachable vertices, add them to the result
for vertex in self.vertices:
if vertex not in result:
result[vertex] = -1
return result
def is_connected(self):
""" Checks if this graph has a path from any vertex to any other
vertex """
dists = self.breadth_first_search(list(self.vertices)[0])
return all([dists[dist] >= 0 for dist in dists])
1and dump all the generated graphs. Now take a look at what graph's3and9were and why they aren't connected.classes?