Monday 20 February 2017

Graphs in Python

In one of the post from series Python Data Structures I promised, that graphs come to the family, so here they are.
Design, I decided to adjacency list implementation, as underlying data structures there are: a list of vertices and list of lists (list of adjacent vertices for any given). I could have used a symbol table (more operation), but decided to keep things as simple as possible (graph algorithms are complicted on its own). A sample of code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
# Simple graph API in Python, implementation uses adjacent lists.
# look also here:
# Classes: Graph, Depth_first_search, Depth_first_paths
# Usage:
# Creating new graph: gr1 = Graph(v) - creates new
# graph with no edges and v vertices;

# Search object: gr2 = Depth_first_search(graph, vertex) -
# creates search object,
# gr2.marked_vertex(vertex) - returns true if
# given vertex is reachable from source(above)

# Path object: gr3 = Depth_first_paths(graph, vertex)-
# creates a new path object,
# gr3.has_path(vertex) - thee same as above
# gr3.path_to(vertex) - returns path from source vertex (to the given)
from collections import deque


class Graph:
    """Class graph, creates a graph - described by integers - number
    of vertices - V : v0, v1, ..., v(V-1)"""

    def __init__(self, v_in):
        """constructor -  takes number of vertices and creates a graph
         with no edges (E = 0) and an empty adjacent lists of vertices"""
        self.V = v_in
        self.E = 0
        self.adj = []
        for i in range(v_in):
            self.adj.append([])

    def V(self):
        """returns number of vertices"""
        return self.V

    def E(self):
        """returns number of edges"""
        return self.E

    def add_edge(self, v, w):
        """adds an edge to the graph, takes two integers (two vertices)
         and creates an edge v,w - by modifying appropriate adjacent lists """
        self.adj[v].append(w)
        self.adj[w].append(v)
        self.E += 1

    def adj_list(self, v):
        """Takes an integer - a graph vertex and returns the adjacency lists of it"""
        return self.adj[v]

    def __str__(self):
        """to string method, prints the graph"""
        s = str(self.V) + " vertices, " + str(self.E) + " edges\n"
        for v in range(self.V):
            s += str(v) + ": "
            for w in self.adj[v]:
                s += str(w) + " "
            s += "\n"
        return s


class Depth_first_search:
    """class depth forst search, creates an object,
    constructor takes graph and a vertex"""

    def __init__(self, gr_obj, v_obj):
        self.marked = [False] * gr_obj.V
        self.cnt = 0
        self.__dfs(gr_obj, v_obj)

    def __dfs(self, gr, v):
        """private depth first search, proceed recursively,
        mutates marked - marks the all possible to reach
         from given (v) vertices; also mutates cnt - number of visited vert"""
        self.marked[v] = True
        self.cnt += 1
        for w in gr.adj_list(v):
            if self.marked[w] == False:
                self.__dfs(gr, w)

    def marked_vertex(self, w):
        """Takes an integer - a graph vertex and returns True if it's reachable
        from vertex v (source)"""
        return self.marked[w]

    def count(self):
        """returns number of visited verticles
        (from given in the constructor vertex)"""
        return self.cnt

Why I did it in the java style? (Additional classes to given graph opertions) Primarly to avoid set and mutate global variables (in that case cnt in class Depth_first_search, I don't know how to solve it using function no object :/), also there is lots of graph tasks and operatons, and, imo, this approach is more clear (Did I really write this?:)). There are  going to be updates on this definitely! Code obviously, also on github. Thanks, till the next time!

No comments: