# Graph representation implementation

Posted on

Problem

I wanted to represent graphs in Python, and wrote the following class. I don’t care about values associated with nodes or the weights of the connections between them, simply the connections between nodes.

Is this a good enough implementation? Or is there a significantly better way?

``````class Graph:
def __init__(self, nodes):
self.array_representation = [[] for _ in range(nodes)]

def directly_connected(self, node_1, node_2):
# Predicate, checks if the two nodes are connected by one edge
return node_2 in self.array_representation[node_1]

def connect(self, node_1, node_2):
# Draws an edge between the node at node_1 and the node at node_2
self.array_representation[node_1].append(node_2)
self.array_representation[node_2].append(node_1)
``````

Solution

If your graph becomes big (or rather if a node has many connections), `node_2 in self.array_representation[node_1]` might take a long time, because `in` is O(n) for lists. Therefore I would use a set for the connections of a node. You don’t even needed to change a lot:

``````class Graph:

def __init__(self, nodes):
self.connections = [set() for _ in range(nodes)]

def directly_connected(self, node_1, node_2):
"""Predicate, checks if the two nodes are connected by one edge"""
return node_2 in self.connections[node_1]

def connect(self, node_1, node_2):
"""Draws an edge between the node at node_1 and the node at node_2"""
``````

And while I was at it, I promoted your comments to proper docstrings. Now you can do `help(Graph.connect)` in an interactive session.

I also changed the name of the internal representation to `self.connections`.

The business logic of graphs is mathematical in nature. As implemented the `Graph` class does not directly reflect the underlying mathematics. Poor mapping between code and graph mathematics is not uncommon even for graph implementations in well regraded text books and online tutorials.

## Mathematics

A graph `G` is defined as a set of nodes or vertices `V = {v1, v2...vn}` and a bag of edges `E = {e1, e2, ...em}`. The only relation between edges and vertices is that for each edge `e` between vertices `u` and `v` both `u` and `v` must be members of `V`.

### Dependencies

Mathematically, a set of vertices `V` is independent of the set of edges `E`. Two different graphs `G1` and `G2` can be defined across the same set of vertices based solely on the difference between two sets of edges `E1` and `E2`.

`````` G1 = V, E1
G2 = V, E2
``````

Nodes are necessarily properties of Edges. Edges are not properties of nodes.
Edges are [ properties | fields | objects ] of a graph. The dependencies are:

`````` Graph <- Edges
Graph <- Nodes
Edge  <- Node, Node
``````

## An Minimal Implementation

This code does not attempt to be particularly Pythonic. It attempts to reflect the underlying mathematics in an object based manner.

``````from collections import Counter

class Graph:
E = Counter()
V = set()

def remove_node(self, node):
self.V.remove(node)

if self.exists_node(node_1) and self.exists_node(node_2):
edge = str(node_1) + '_' + str(node_2)
self.E[edge]+=1

def remove_edge(self, node_1, node_2):
edge = str(node_1) + '_' + str(node_2)
if self.E[edge] > 0:
self.E[edge]-=1
else:
self.E[edge] = 0

def exists_edge(self, node_1, node_2):
edge_1 = str(node_1) + '_' + str(node_2)
return self.E[edge_1] > 0

def exists_node(self, node):
return node in self.V
``````

The `Graph` class maintains the nodes as a set in order to provide set semantics. It uses `collection.Counter` to maintain a bag of edges as recommended by the Python documentation. The implementation of undirectional edges is left as an exercise.

Building on Ben Rudgers answer above, I would change some small things. Storing the edge as string seems odd, so I changed it to a namedtuple. Naming the internal variables to something more readable. Raising an error on adding an edge with unknown nodes, instead of ignoring it.

I also added the directly_connected() and connected() methods the OP is asking for.

``````from collections import namedtuple

Edge = namedtuple('Edge', ['node_1', 'node_2'])

class Graph:
edges = set()
nodes = set()

def remove_node(self, node):
self.nodes.remove(node)

if self.exists_node(node_1) and self.exists_node(node_2):
else:
msg = 'Either {} or {} are not registered nodes!'
msg = msg.format(node_1, node_2)
raise KeyError(msg)

def remove_edge(self, node_1, node_2):
self.edges.remove(Edge(node_1, node_2))

def exists_edge(self, node_1, node_2):
return Edge(node_1, node_2) in self.edges

def exists_node(self, node):
return node in self.nodes

def directly_connected(self, node_1, node_2):
return self.exists_edge(node_1, node_2,)

def connected(self, node_1, node_2):
if self.directly_connected(node_1, node_2):
return True

for edge in self.edges:
if edge.node_1 == node_1:
return self.connected(edge.node_2, node_2)

return False

g = Graph()
``````A -> C Directly connected:  False