Undirected Graph with edge data (python)

graph.py

# Undirected Graph ADT with edge data stored as adj_vertices dict for each Vertex
# The key to each edge is a nomalized tuple of the vertex ids ordered from low to high
# edge id (eid) for v1, v2  is (v1,v2) or (v2,v1) such that the first tuple item is less than second


def edge_id(v1,v2):  # normalize key v1,v2 to tuple (v_low,v_hi)
    return (v1, v2) if v1 <= v2 else (v2, v1)

class Vertex(object):

    def __init__(self, vid, **data):
        self.id = vid
        self.adj_vertices = []  # list of edge object references
        self.data = data  # other data

    def __repr__(self):
        return self.id.__repr__() + self.data.__repr__()


class Graph(object):
    """ Graph implements undirected graph with edge and vertex extra data"""

    def __init__(self):
        self.vertices = {}  # vid : Vertex obj
        self.edges = {}  # key is vid1,vid2: Edge dict of key/values, including eid
        
    def add_vertex(self, vid, **data):
        if vid in self.vertices:
            v = self.vertices[vid]
        else:
            v = Vertex(vid, **data)
            self.vertices[vid] = v
        return v
        
    def add_edge(self, v1_id, v2_id, **data):
        v1 = self.add_vertex(v1_id)
        v2 = self.add_vertex(v2_id)
        eid = edge_id(v1_id, v2_id)
        if eid not in self.edges:
            self.edges[eid] = { 'eid':eid, **data}
            v1.adj_vertices.append(v2)  # add both sides for undirected graph
            v2.adj_vertices.append(v1)
            
    def edge_exists(self,v1_id,v2_id):
        eid = edge_id(v1_id, v2_id)
        return eid in self.edges


def bfs(g, vid_start):
    v = g.vertices[vid_start]
    v.data['distance'] = 0
    v.data['pred'] = None
    visited = { vid_start } # will add and pop and check if in
    done = set()

    while len(visited) > 0:
        x = g.vertices[visited.pop()]

        for v in x.adj_vertices:
            if (v.id not in visited and v.id not in done):
                visited.add(v.id)
                v.data['distance'] = x.data['distance'] + 1
                v.data['pred'] = x
        done.add(x.id)

if __name__ == '__main__':
    g = Graph()
    g.add_edge(1,2, color='blue')
    g.add_edge(2,1)
    g.add_edge(2,3)
    g.add_edge(2,3)
    g.add_edge(1,3)
    g.add_vertex(6)
    g.add_edge(1,4)
    g.add_edge(4,6)
    g.add_vertex(9,color='green')
    g.add_edge(3,9)

    for v in g.vertices.values():
        print(v, "\n   ", v.adj_vertices)

    for eid in g.edges.values():
        print(eid)

    print("bfs from 1")
    bfs(g,1)

    for v in g.vertices.values():
        print(v, "\n   ", v.adj_vertices)

    print("done")

Undirected Graph that allows edge data as well as vertex data in python

edges are stored in dict with key as a tuple of the two vertex ids in order from lowest to highest