The two most well-know representations:
- adjacency lists
- adjacency matrices
+ Adjacency Lists
list/array or set
a, b, c, d, e, f, g, h = range(8)
N = [
{b: 2, c: 3, d: 4, e: 1, f: 5}, # a
{c, e}, # b
{d}, # c
...
]
or
N = {
'a': set('bcdef'), # or 'bcdef' - use string instead of set, lower overhead but only useful for iteration only use cases
'b': set('ce'),
...
}
+ Adjacency Matrices
Instead of listing all neighbors for each node, have a row (an array) with one position for each possible (that is, one for each node in the graph), and store a value, such as True or False. The simplest implementation is achieved using nested lists.
a, b, c, d, e, f, g, h = range(8)
# a b c d e f g h
N = [
[0,1,1,1,1,1,0,0], # a
[0,0,1,0,1,0,0,0], # b
[0,0,0,1,0,0,0,0], # c
[0,0,0,0,1,0,0,0], # d
[0,0,0,0,0,1,0,0], # e
[0,0,1,0,0,0,1,1], # f
[0,0,0,0,0,1,0,1], # g
[0,0,0,0,0,1,1,0] # h
]
# check neighborhood membership
N[a]
# Degree
sum(N[f])
- Useful properties for adjacency matrices
- the diagonal is all false (0) if we don't allow the self-loops
- the adjacency matrix for an undirected graph will be symmetric
- use weight instead of True/False for weighted graph
- use infinite weight for nonexistent edges for practical reasons
- or use illegal weight values such as None or -1
a, b, c, d, e, f, g, h = range(8)
inf = float('inf')
W = [
[0, 2, 1, 3, 4, inf, inf], #a
...
]
>>> W[a] < inf
# Neighborhood membership
True
>>> W[c][e] < inf
# Neighborhood membership
False
>>> sum(1 for w in W[a] if w < inf) - 1 # Degree
5
- special purpose arrays with numpy
N = np.zeros([10, 10])
2. Implement Trees
- could represent that tree with lists of lists, like this:
>>> T[0][1]
'b'
>>> T[2][1][0]
'e'
- A Binary Tree Class
def __init__(self, left, right):
self.left = left
self.right = right
You can use the Tree class like this:
>>> t = Tree(Tree("a", "b"), Tree("c", "d"))
>>> t.right.left
'c'
- A Multiway Tree Class
- A common way of implementing trees, especially in languages that don’t have built-in lists, is the “first child, next sibling” representation. Here, each tree node has two “pointers,” or attributes referencing other nodes, just like in the binary tree case. However, the first of these refers to the first child of the node, while the second refers to its next sibling, as the name implies. In other words, each tree node refers to a linked list of siblings (its children), and each of these siblings refers to a linked list of its own.
- A common way of implementing trees, especially in languages that don’t have built-in lists, is the “first child, next sibling” representation. Here, each tree node has two “pointers,” or attributes referencing other nodes, just like in the binary tree case. However, the first of these refers to the first child of the node, while the second refers to its next sibling, as the name implies. In other words, each tree node refers to a linked list of siblings (its children), and each of these siblings refers to a linked list of its own.
def __init__(self, kids, next=None):
self.kids = self.val = kids
self.next = next
>>> t = Tree(Tree("a", Tree("b", Tree("c", Tree("d")))))
>>> t.kids.next.next.val
'c'
===
THE BUNCH PATTERN [This pattern isn’t useful only when building trees, of course. You could use it for any situation where you’d want a flexible object whose attributes you could set in the constructor.]
When prototyping or even finalizing data structures such as trees, it can be useful to have a flexible class that
will allow you to specify arbitrary attributes in the constructor. In these cases, the Bunch pattern (named by Alex
Martelli in the Python Cookbook) can come in handy. There are many ways of implementing it, but the gist of it is
the following:
class Bunch(dict):
def __init__(self, *args, **kwds):
super(Bunch, self).__init__(*args, **kwds)
self.__dict__ = self
- There are several useful aspects to this pattern. First, it lets you create and set arbitrary attributes by supplying them as command-line arguments:
>>> x.name
'Jayne Cobb'
- Second, by subclassing dict , you get lots of functionality for free, such as iterating over the keys/attributes or easily checking whether an attribute is present. Here’s an example:
>>> t = T(left=T(left="a", right="b"), right=T(left="c"))
>>> t.left
{'right': 'b', 'left': 'a'}
>>> t.left.right
'b'
>>> t['left']['right']
'b'
>>> "left" in t.right
True
>>> "right" in t.right
False