To conclude this short bit on graphs (see Part 1, and Part 2) lets look at a sample implementation I've created in Python. Note that this targets the 2.x version of the language, but I believe it would run OK in Python 3 (except for print statements vs function maybe).

This particular implementation has the following properties:

• It's directed.
• It's unweighted (no edge can specify a weight).
• It supports cyclic nodes.

To view the full source yourself, check it out here on BitBucket.

First, lets describe the nodes themselves a bit, in GraphNode.py. Nodes in this graph have the following functionality:

• Can add neighbors (nodes that it can reach).
• Can check if a node is reachable (adjacent).
• Can be iterated on (for searching - Use typical Python iterator syntax).
• Can be printed (and show the values it's connected to).

This is effectively a container for a list of GraphNodes. Check the BitBucket site to see how it's written.

Next, and more interestingly, is the implementation of Graph.py. Features the Graph object supports include:

• Adding a new value.
• Marking two values adjacent.
• Checking if two values are adjacent.
• Determining a path between the two nodes.
• Finding all the paths between a value and the nodes it can reach.

Adding a new value is as simple as appending to a collection of nodes:

def add(self, value):
    node = GraphNode(value)
    self.__nodes__[value] = node

Marking and checking nodes for adjacency follows this simple pattern: - Get both nodes - If both nodes exist, optionally perform an operation - Return if both nodes existed

For example:

def mark_adjacent(self, x, y):
    x_node = self.__nodes__[x]
    y_node = self.__nodes__[y]

    if x_node and y_node:
        x_node.add_neighbor(y_node)

    return x_node and y_node

Finally, finding a path between two values x and y involves a fairly straightforward function. Prior to running the algorithm, the function verified both values exist within the graph. If they do, the following recursive algorithm is applied:

• If the current node being viewed has already been visited, the path cannot continue from here (cyclic node).
• Otherwise, mark the node as visited.
• Appending the current node to the path.
• If the current node is the end node, return true.
• Otherwise, recursively search all adjacent nodes to the current node until a path is found
• If the ending node is not found on the recursive step, remove the topmost node from the path and return false.

The algorithm in code is listed below. Note that this is not the method that should be called, but rather the Graph.path(x, y) function instead. Graph.path(x, y) will call this function if it is required to.

def __path_helper__(self, start, end, cur, path):
    if cur.visited:
        return False

    cur.visited = True
    path.append(cur)

    if cur != end:
        for neighbor in cur:
            if self.__path_helper__(start, end, neighbor, path):
                return True

        if path:
            path.pop()
            return False
    else:
        return True

There's lots left to be desired in this code, but this is a simple example of what a graph may look like in code. There are tons of variants on the implementation of graphs, but all of the fundamental operations remain the same throughout implementations.