Python - checking if graph is connected - unexpected loop behavior

Question

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])

Answer 1

Your comparison of v1 and v2 in SimpleGraph.random_graph is comparing based upon the id of the class, which is probably not what you want. Adding the following method to SimpleVertex fixes the problem:

def __lt__(self, other):
    return self.vid < other.vid