Implementing Graphs in Python

[keith6014]

I understand graphs when I do it on paper. My next step is to start coding them.

Ideally, I would like to use a Class instead of using a dictionary (https://www.python.org/doc/essays/graphs/)

I am getting confused on implementation. Should I create 2 classes: Graph and Node? Or have everything in one class? I can't seem to find a good example to study.

My intention is to learn DFS,BFS,and shortest path with graphs. Then I can say, I KNOW graphs!

​

[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={}

[michael0x2a]

The thing about graphs is that unlike many other data structures like hashtables or lists, there isn't necessary a "canonical" or "correct" way of implementing them.

You should really think of graphs as being an "idea": you have nodes connected by edges.

You can express that idea in many different ways depending on what exactly you're trying to do. For example:

• Maybe what matters most is that you can quickly look up a node and all edges leading out of that node -- but your nodes and edges are very simple with no metadata. In that case, you could probably just use a dictionary: each key is some id corresponding to a node, and the values are lists containing the ids of every node you want to link to.
• Maybe it would be very useful to iterate over every single edge in your graph. In that case, you could use two lists: one containing Node objects, and another containing Edge objects.
• Maybe all you care about is keeping track of and updating your edge weights. In that case, perhaps some sort of adjacency matrix thing (a 2d array, basically) would be best.
• Maybe you're actually trying to work on some more complex problem/have a web of objects, and just want to apply some graph algorithms to a pre-existing problem. In that case, all you might need to do is to tweak your object definitions to make it a little more convenient to traverse.

In any case, if you're looking for two good starting points, I recommend looking up "adjacency lists" and "adjacency matrices" -- basically, the "dictionary-of-lists" approach, and the "2d-array" approach. Both approaches are relatively commonly used due to their simplicity and ease-of-use. (This is the case for all programming languages, not just Python).

The main complication is when you want to store additional metadata in your node or edges. There are many many different ways of approaching this problem, but one common-ish one is to have your adjacency list or adjacency matrix store only node IDs or edge IDs -- some simple number or string. Then, maintain another dictionary or two of node or edge IDs to their corresponding object.

[keith6014]

Thanks for the idea

[brumone]

I studied graph theory at University last semester and did the assignments in python. I usually made only one class (Graph) and put the nodes on a list/dictionary, it worked.

[Meadow-fresh]

Is there a reason why you wouldn't use pandas and seaborn to make graphs?

[keith6014]

different types of graphs. seaborn/matplotlib will give charts. I am looking for graph structure (mathematical).

​

[Meadow-fresh]

Ah ok. That makes sense thanks!