6
\$\begingroup\$

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?

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.