Graph Data Structure

1. Vertex
   A vertex is the most basic part of a graph and it is also called a node. Throughout we'll call it note. A vertex may also have additional information and we'll call it as payload.
2. Edge
   An edge is another basic part of a graph, and it connects two vertices/ Edges may be one-way or two-way. If the edges in a graph are all one-way, the graph is a directed graph, or a digraph. The picture shown above is not a digraph.
3. Weight
   Edges may be weighted to show that there is a cost to go from one vertex to another. For example in a graph of roads that connect one city to another, the weight on the edge might represent the distance between the two cities or traffic status.
4. Graph
   A graph can be represented by $G$ where $G=(V,E)$. $V$ is a set of vertices and $E$ is a set of edges. Each edge is a tuple $(v,w)$ where $w,v \in V$. We can add a third component to the edge tuple to represent a weight. A subgraph $s$ is a set of edges $e$ and vertices $v$ such that $e \in E$ and $v \in V$.

   The picture above shows a simple weighted graph and we can represent this graph as the set of six vertices

   $$V = \{a, b, c, d, e, f\}$$

   and the set of nine edges:

   $$E = \{(a,b,7),(a,c,9),(a,f,14),(b,d,15),(b,c,10),(c,d,11),(c,f,2),(d,e,6),(e,f,9)\}$$
5. Path
   A path in a graph is a sequence of vertices that are connected by edges. We usually define a path as $w_1, w_2,..., w_n$ such that $(w_i, w_{i+1}) \in E$ for all $1 \le i \le n-1$. The unweighted path length is the number of edges in the path $(n-1)$. The weighted path length is the sum of the weights of all the edges in the path. For example in the picture above, the path from $a$ to $e$ is the sequence of vertices $(a, c, d, e)$. The edges are $\{(a, c, 9), (c, d, 11), (d, e, 6)\}$.
6. Cycle
   A cycle in a directed graph is a path that starts and ends at the same vertex. A graph with no cycles is called an acyclic graph. A directed graph with no cycles is called a directed acyclic graph or a DAG.

In the code, we create two classes: Graph, which holds the master list of vertices, and Vertex, which represents each vertex in the graph:

class Vertex:
    def __init__(self, node):
        self.id = node
        self.adjacent = {}

    def __str__(self):
        return str(self.id) + ' adjacent: ' + str([x.id for x in self.adjacent])

    def add_neighbor(self, neighbor, weight=0):
        self.adjacent[neighbor] = weight

    def get_connections(self):
        return self.adjacent.keys()  

    def get_id(self):
        return self.id

    def get_weight(self, neighbor):
        return self.adjacent[neighbor]

class Graph:
    def __init__(self):
        self.vert_dict = {}
        self.num_vertices = 0

    def __iter__(self):
        return iter(self.vert_dict.values())

    def add_vertex(self, node):
        self.num_vertices = self.num_vertices + 1
        new_vertex = Vertex(node)
        self.vert_dict[node] = new_vertex
        return new_vertex

    def get_vertex(self, n):
        if n in self.vert_dict:
            return self.vert_dict[n]
        else:
            return None

    def add_edge(self, frm, to, cost = 0):
        if frm not in self.vert_dict:
            self.add_vertex(frm)
        if to not in self.vert_dict:
            self.add_vertex(to)

        self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost)
        self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost)

    def get_vertices(self):
        return self.vert_dict.keys()

if __name__ == '__main__':

    g = Graph()

    g.add_vertex('a')
    g.add_vertex('b')
    g.add_vertex('c')
    g.add_vertex('d')
    g.add_vertex('e')
    g.add_vertex('f')

    g.add_edge('a', 'b', 7)  
    g.add_edge('a', 'c', 9)
    g.add_edge('a', 'f', 14)
    g.add_edge('b', 'c', 10)
    g.add_edge('b', 'd', 15)
    g.add_edge('c', 'd', 11)
    g.add_edge('c', 'f', 2)
    g.add_edge('d', 'e', 6)
    g.add_edge('e', 'f', 9)

    for v in g:
        for w in v.get_connections():
            vid = v.get_id()
            wid = w.get_id()
            print '( %s , %s, %3d)'  % ( vid, wid, v.get_weight(w))

    for v in g:
        print 'g.vert_dict[%s]=%s' %(v.get_id(), g.vert_dict[v.get_id()])

The Vertex class uses a dictionary (adjacent) to keep track of the vertices to which it is connected, and the weight of each edge. The Vertex constructor initializes the id, which is usually a string, and the adjacent dictionary. The add_neighbor() method is used add a connection from this vertex to another. The get_connections() method returns all of the vertices in the adjacency list. The get_weight() method returns the weight of the edge from this vertex to the vertex passed as a parameter.

The Graph class contains a dictionary(vert-dict) that maps vertex names to vertex objects, and we can see the output by the __str__() method of Vertex class:

g.vert_dict[a]=a adjacent: ['f', 'c', 'b']

Graph also provides methods for adding vertices to a graph and connecting one vertex to another. The get_vertices() method returns the names of all of the vertices in the graph. Also, we have the __iter__() method to make it easy to iterate over all the vertex objects in a particular graph. Together, the two methods allow us to iterate over the vertices in a graph by name, or by the objects themselves.

In main(), we created six vertices laebled 'a' through 'f'. Then we displayed the vertex dictionary. Notice that for each key 'a' through 'f' we have created an instance of a Vertex. Next, we add the edges that connect the vertices together. Finally, a nested loop verifies that each edge in the graph is properly stored.

Output:

( a , f,  14)
( a , c,   9)
( a , b,   7)
( c , f,   2)
( c , a,   9)
( c , b,  10)
( c , d,  11)
( b , a,   7)
( b , c,  10)
( b , d,  15)
( e , f,   9)
( e , d,   6)
( d , c,  11)
( d , e,   6)
( d , b,  15)
( f , a,  14)
( f , c,   2)
( f , e,   9)
g.vert_dict[a]=a adjacent: ['f', 'c', 'b']
g.vert_dict[c]=c adjacent: ['f', 'a', 'b', 'd']
g.vert_dict[b]=b adjacent: ['a', 'c', 'd']
g.vert_dict[e]=e adjacent: ['f', 'd']
g.vert_dict[d]=d adjacent: ['c', 'e', 'b']
g.vert_dict[f]=f adjacent: ['a', 'c', 'e']