Make undirected graph from adjacency list

Question

I'm trying to make an undirected graph from an adjacency list to practice the Karger's Min Cut algorithm. The following is my code

class Vertex(object):
    '''Represents a vertex, with the indices of edges
       incident on it'''
    def __init__(self,name,edgeIndices=[]):
        self.name = name
        self.edgeIndices = edgeIndices
    def getName(self):
        return self.name
    def addEdge(self,ind):
        self.edgeIndices.append(ind)
    def getEdges(self):
        return self.edgeIndices
    def __eq__(self,other):
        return self.name == other.name

class Edge(object):
    '''Represents an edge with the indices of its endpoints''' 
    def __init__(self,ends):
        self.ends = ends
    def getEnds(self):
        return self.ends
    def __eq__(self,other):
        return (self.ends == other.ends)\
               or ((self.ends[1],self.ends[0]) == other.ends)

class Graph(object):
    def __init__(self,vertices,edges):
        self.edges = edges
        self.vertices = vertices

def createGraph(filename):
    '''Input: Adjacency list
       Output: Graph object'''
    vertices = []
    edges = []
    with open(filename) as f:
        for line in f:
            elements = line.split()
            newVert = Vertex(elements[0])
            if newVert not in vertices:
                vertices.append(newVert)

            for verts in elements[1:]:
                otherVert = Vertex(verts)
                if otherVert not in vertices:
                    vertices.append(otherVert)
                end1 = vertices.index(newVert)
                end2 = vertices.index(otherVert)
                newEdge = Edge((end1,end2))
                if newEdge not in edges:
                    edges.append(newEdge)
                newVert.addEdge(edges.index(newEdge))
    return Graph(vertices,edges)

Suppose the adjacency list is as follows with vertices represented by integers

1 -> 2,3,4
2 -> 1,3
3 -> 1,2,4
4 -> 1,3

In total, this graph will have five edges, so the length of list holding indices of edges a vertex is associated with can't more than 5 long.

For instance, I expect the vertex '2' to have indices of just two edges, i.e. edges with vertices 1 and 3. Instead, what I get is [0, 1, 2, 3, 0, 2, 1, 3]. I need help to figure out what is going wrong.

Answer 1

First error comes from the Vertex init. When passing a list as default argument, Python instantiates it once, and share this instance with all future instances of Vertex. Pass None, and use a local list if no list is given.

class Vertex(object):
    def __init__(self,name,edgeIndices=None):
        self.name = name
        self.edgeIndices = edgeIndices if edgeIndices else []

In the createGraph method, when the vertex already exists in the graph you need to use it. See the added else: newVert = ... You also seem to have an issue with the ligne splitting. See the iteration over elements[2].split(',').

def createGraph(filename):
    '''Input: Adjacency list
       Output: Graph object'''
    vertices = []
    edges = []
    with open(filename) as f:
        for line in f:
            elements = line.split()
            newVert = Vertex(elements[0])
            if newVert not in vertices:
                vertices.append(newVert)
            else:
                newVert = vertices[vertices.index(newVert)]

            for verts in elements[2].split(','):
                otherVert = Vertex(verts)
                if otherVert not in vertices:
                    vertices.append(otherVert)
                end1 = vertices.index(newVert)
                end2 = vertices.index(otherVert)
                newEdge = Edge((end1,end2))
                if newEdge not in edges:
                    edges.append(newEdge)
                newVert.addEdge(edges.index(newEdge))
    return Graph(vertices,edges)

As a side note, I would try to use a dict to store the vertices (and edges) and do the lookup. List.index is used a lot, and you may create a lot of objects for nothing.

Answer 2

I would recommend to take a look at Dict, OrderedDict, Linked List based graph implementations. The are far more effective then based on lists and indexes. To make you code work you can do the following:

Change a Vertex to avoid issue described in previous answer:

class Vertex(object):
    def __init__(self,name, edgeIndices=None):
        self.name = name
        self.edgeIndices = edgeIndices or []     

Let the graph do some work:

class Graph(object):
    def __init__(self):
        self.edges = []
        self.vertices = []

    def add_vertex(self, name):
        vertex = Vertex(name)
        if vertex not in self.vertices:
            self.vertices.append(vertex)

    def add_edge(self, *names):
        self._add_vertices(names)
        edge = self._add_edge(names)
        self._update_vertices_links(edge, names)

    def get_vertex_index(self, name):
        vertex = Vertex(name)
        return self.vertices.index(vertex)

    def get_vertex(self, name):
        return self.vertices[self.get_vertex_index(name)]

    def _update_vertices_links(self, edge, names):
        for name in names:
            vertex = self.get_vertex(name)
            vertex.addEdge(self.edges.index(edge))

    def _add_edge(self, names):
        edge = Edge((self.get_vertex_index(names[0]), self.get_vertex_index(names[1])))
        if edge not in self.edges:
            self.edges.append(edge)
        return edge

    def _add_vertices(self, names):
        for name in names:
            self.add_vertex(name)

    def __repr__(self):
        return "Vertices: %s\nEdges: %s" % (self.vertices, self.edges)

Create Graph:

def createGraph(filename):
    with open(filename) as f:
        graph = Graph()
        for line in f:
            elements = line.strip().split()
            graph.add_vertex(elements[0])
            for element in elements[2].split(","):
                graph.add_edge(elements[0], element)
    return graph

Run it:

graph = createGraph('input.txt')
print graph

Output for your input:

Vertices: [<Name:1 Edges:[0, 1, 2]>, <Name:2 Edges:[0, 3]>, <Name:3 Edges:[1, 3, 4]>, <Name:4 Edges:[2, 4]>]
Edges: [(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)]