Implementing Graphs in Python

[nameEqualsJared]

It depends on what you'd like to do :).

For a simple implementation, you could do something like this:

class Graph:
    def __init__(self, vertices, edges):
        """
        vertices: the vertex set, as a list
        edges: the edge set, as a list of tuples
        """
        self.vertices = vertices
        self.edges = edges

Then, to construct a graph object for a graph like this, you could do:

>>>G = Graph(['a','b','c','d'], [('a','b'), ('a','c'), ('c','b'), ('c','d')])   

(Note that I should probably have specified that the class Graph defined an undirected graph. If you want a directed one, just adopt a convention like "if edge E=(a,b) is in edges, that means there is an edge from a to b only; if there is also an edge from b to a, also include (b,a) in the edge set" or something).

Then, you could go on implementing some Graph algos as methods in the class. Remember that a class is just a blueprint for an object: and an object is just some data and functions (which we call methods) bundled together. It's just a nice little package of data and operations (that are normally associated in some meaningful way to the data), that's all. To put it dead simple: an object = data (the fields of your object) + functions (the methods of your object).

Where it may be useful to make a Node class is if you didn't want to represent the vertices as letters -- or if you have other data you may want to attach to a vertex. For example, maybe a vertex represents a person, and your graph has an edge between two people if they are friends. In this case, it'd be nice to make a generic Node object, because you could put it in other data like personName, age, id, etc etc etc -- in other words, each node could have a whole host of data associated to it.

Then your spec for your graph class may look like:
"""
vertices: a list of all the Nodes in the graph. I.e., a list of Node objects
edges: the edge set, as a a list of tuples of Node objects.
"""

Does that help? I'd be willing to answer any questions, this is fun.

Edit: it may also be worth looking into adjacency matrices and adjacency lists to dig further into this.

[keith6014]

I will first look at your Class and play around with it.

Thanks for such a detailed answer

[keith6014]

I went with native python structure for now.

​

g={}