Simple Graph in Python

Question

Just the beginning of graphs API in Python:

# Simple graph API in Python, implementation uses adjacent lists.
# 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)


class Graph:
    """class graph"""
    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):
        """void, adds an edge to the graph"""
        self.adj[v].append(w)
        self.adj[w].append(v)
        self.E += 1

    def adj_list(self, v):
        """returns the adjacency lists of the vertex v"""
        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):
        """void 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):
        """returns True if given vertex (w) is reachable
        from vertex v"""
        return self.marked[w]

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

class Depth_first_paths:
    """class depth first paths, solves
    single paths problem: given graph and a vertex (source vertex), find
    a path to another vertex."""

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

    def __dfs(self, gr, v):
        """void recursive depth first search, mutates array marked,
        mutates counter (cnt), and creates a path (filling an array     edge_to)"""
        self.marked[v] = True
        for w in gr.adj_list(v):
            if self.marked[w] == False:
                self.edge_to[w] = v
                self.__dfs(gr, w)

    def has_path(self, v):
    """returns true if there is a path from the source
    vertex to the given, else false"""
    return self.marked[v]

    def path_to(self, v):
        """returns path from source to the given vertex"""
        if self.has_path(v) == False:
            return None
        path = []
        x = v
        while x != self.s:
            path.insert(0, x)
            x = self.edge_to[x]
        path.insert(0, self.s)
        return path

I've used classes not function because there is no need for global variables. How do you think build the rest graph algorithms on it?

Answer 1

I've reviewed your code and I can make the following remarks. I'm only going to review the Graph class for now so lets start:

class Graph:
    """class graph"""

Here the comment is redundant. We know its a Graph and we know its a class. Also note for completeness I like to write class Graph(object)

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

Again the comment is redundant We know its a constructor and what it initializes. However as you may notice the real problem here is not the comment but what it describes. Those V, E, v_in parameters are too short and do not mean anything. If I were to read the method body and not the class name I wouldn't be able to understand that they denote Vertices and Edges. So a better name for them would be vertices, edges and input_vertices. Note that we use lowercase names for class properties.

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

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

More redundant notes as we know they return something. However the method names are wrong. Why V and E? And why do they return a number? I would suspect to return a list or an Object that I can query. A better name would be again vertices and edges.

def add_edge(self, v, w):
    """void, adds an edge to the graph"""
    self.adj[v].append(w)
    self.adj[w].append(v)
    self.E += 1

def adj_list(self, v):
    """returns the adjacency lists of the vertex v"""
    return self.adj[v]

That's not too bad although I would remove the void remark and add a better explanation about the input assumptions. For example what happens if do add_edge(set((1,2,3)), frozenset((4,5,6)))? Traceback error. So its better to specify that it assumes the input is integers.

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

Ok nothing wrong here. I would only rename s to output or response so that I understand the meaning.

In general I would say to try to keep the names consistent and meaningful so a reader will not have to guess whats going on.

Answer 2

You should embrace the builtin types Python provides for you. I will show you how you can replace every method in your class with functions based on those. First __init__ becomes:

def create_graph(vertices):
    return {v:set() for v in vertices}

Used like this: G = create_graph([1, 2, 3]) Then def V(self): is just len(G). E becomes

def edge_count(G):
    return sum(len(v) for v in G.values()) / 2

add_edge becomes

def add_edge(G, f, t):
    G[f].add(t)
    G[t].add(f)

adj_list is just G[v]. __str__ is also very easy to replace.

Your Depth_first_search makes a class out of what should be a function. It can be implemented like this:

def dfs(G, at, visited = None):
    if visited is None:
        visited = set()
    yield at
    visited.add(at)
    for neighbour in G[at]:
        if neighbour not in visited:
            for at in dfs(G, neighbour, visited):
                yield at

And used like this to print all nodes found in a graph:

for at in dfs(G, 1):
    print(at)

The problem of finding a path between two graphs can then be expressed as:

def path_to(G, at, to, sofar = None, visited = None):
    if sofar is None:
        sofar = []
    sofar.append(at)
    if visited is None:
        visited = set()
    visited.add(at)
    if at == to:
        return sofar
    for neighbour in G[at]:
        if neighbour not in visited:
            res = path_to(G, neighbour, to, sofar, visited)
            if res:
                return res
    return None

print(path_to(G, 1, 10))