Graphs
Table of Contents
Introduction
This is a starter post for an introduction to Graphs.
Imports and Setup
Imports
# python
from __future__ import annotations
from collections import defaultdict
from enum import Enum
# pypi
from attrs import define
Constants
class Color(Enum):
WHITE = 1
GRAY = 2
BLACK = 3
INFINITY = float("inf")
A Vertex Implementation
Note to future self: the default setting for attrs.define makes the object to unhashable, to make it hashable by object identity pass in eq=False otherwise trying to add the object to a set will raise an error.
@define(eq=False)
class Vertex:
"""A single node in a graph
Args:
identifier: something to identify the node
color: the 'discovery' state of the node
distance: The number of edges to the root
predecessor: The 'parent' of the node in a tree
"""
identifier: int
color: Enum=Color.WHITE
distance: float=INFINITY
predecessor: Vertex=None
def __str__(self) -> str:
return (f"{self.identifier}: {self.color}, "
f"distance: {self.distance}, predecessor: {self.predecessor}")
A Graph Implementation
class Graph:
"""A graph implementation
"""
def __init__(self) -> None:
self._adjacent = None
self._vertices = None
return
Adjacencies
The book uses an adjacency linked list, but I'll assume that there will be only one edge between each pair of vertices and use a dictionary with sets of adjacent nodes instead.
@property
def adjacent(self) -> defaultdict:
"""The dictionary of adjacent vertices"""
if self._adjacent is None:
self._adjacent = defaultdict(set)
return self._adjacent
@adjacent.setter
def adjacent(self, new_adjacent: dict) -> None:
"""Sets the dictionary of adjacent vertices (converting to default dict)
Note:
This expects the new_adjacent to be a dict of node: set of nodes
"""
if type(new_adjacent) is not defaultdict:
new_new_adjacent = defaultdict(set)
for key, nodes in new_adjacent.items():
new_new_adjacent[key] = nodes
new_adjacent = new_new_adjacent
self._adjacent = new_adjacent
return
Vertices
The representation we're using is an adjacency list, but sometimes you need to traverse the vertices. So I'm going to make an alias to the adjacency list keys, in the assumption that every node in the graph is a key in the dict. This might not be true in a directed graph, so I'll have to revisit it later.
@property
def vertices(self) -> set:
"""The vertices in this graph"""
if self._vertices is None:
self._vertices = set()
return self._vertices
Add Item
def add(self, node_1: Vertex, node_2: Vertex) -> None:
"""Add edge
Warning:
This assumes an undirected graph, change it for a directed graph
Args:
node_1: node on one end of the edge
node_2: Node on the other end of the edge
"""
self.vertices.add(node_1)
self.vertices.add(node_2)
self.adjacent[node_1].add(node_2)
self.adjacent[node_2].add(node_1)
return
Getitem
def __getitem__(self, key):
"""Get the list from the adjacencies dict
Args:
key: vertex whose list we want
"""
return self.adjacent[key]
Testing
# pypi
from expects import be, contain, equal, expect
# software under test
from bowling.data_structures.graphs import graph
from bowling.data_structures.graphs.graph import Color, Graph, Vertex
v = Vertex(1)
expect(v.color).to(be(Color.WHITE))
g = Graph()
v2 = Vertex(2)
v3 = Vertex(3)
g.add(v, v2)
g.add(v, v3)
expect(g.adjacent.keys()).to(contain(v, v2))
expect(g.adjacent[v]).to(contain(v2))
expect(g[v2]).to(contain(v))
expect(g[v3]).to(contain(v))
expect(g[v3]).not_to(contain(v2))
