# Graph representation implementation

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)


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.

• Using a frozenset as the keys to the bag of edges instead of building the string might be an easy way to implement the unidirectional edges and be maybe faster. Dec 9 '16 at 7:38
• @graipher I don't disagree. I'd probably be inclined to model an undirected graph with pairs of edges because I don't know how too model a directed graph using frozenset in a straightforward way. I have a bias toward fewer data structures and would rather have two sets of functions that operate on one data structure than two data structures. But that's just opinion. Dec 9 '16 at 13:57

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

• There are all kinds of ways to implement E. The important goal, for me, is to abstract over the implementation details by working at a higher level. This allows the implementation to be changed if profiling or coding standards indicate such a change is warranted. In regard to adding an edge that does not exist, I felt that crashing the program was inconsistent mathematical abstractions. It also seemed a bit extreme given that the most likely way of handling would boil down ignoring it and proceeding with input. If I were to do something about it, I'd probably write to a log. Dec 12 '16 at 17:28