graph.py

graph.py

def edgesFunc(G):
	if callable(G):
		return G
	items = _itemsFunc(G)
	return lambda v: items(G[v])


# (list of dictionaries)
def bgraph(x, dicttype=dict):
	# by number of vertices
	if isinstance(x, int):
		return [dicttype() for i in range(x)]

	# from dicts
	elif _is_dict_graph(x):
		return [dicttype(r) for r in x]

	# from "matrix"
	else:
		# ignore zeros (make no edges)
		return [dicttype(_enumerateNonZero(r)) for r in x]

def dgraph(x):
	return bgraph(x, dgraph_dict)

# (list of lists)
def mgraph(x):
	# by number of vertices
	if isinstance(x, int):
		return [[0]*x for i in range(x)]

	# from dicts
	elif _is_dict_graph(x):
		n = len(x)
		return [_setItems([0]*n, r.items()) for r in x]

	# from "matrix"
	else:
		return [list(r) for r in x]


def _enumerateNonZero(x):
	return ((i, v) for i, v in enumerate(x) if v != 0)

def _setItems(D, items):
	for k, v in items:
		D[k] = v
	return D


_setDictItem = dict.__setitem__

class dgraph_dict(dict):
	__slots__=()

	def __getitem__(self, k):
		return self.get(k, 0)

	def __setitem__(self, k, v):
		if v != 0:
			_setDictItem(self, k, v)
		else:
			self.pop(k, None)


def _is_dict_graph(G):
	return isinstance(G[0], dict) if G else False

def _itemsFunc(G):
	return dict.items if _is_dict_graph(G) else _enumerateNonZero


def dot(A, B, C=None):
	if C is None:
		C = mgraph(len(A))

	if B and type(B[0]) is dict:
		B = dgraph(B)

	V = range(len(A))
	items = _itemsFunc(A)
	for i, Ai, Ci in zip(V, A, C):
		for j in V:
			Ci[j] = sum(Aik * B[k][j] for k, Aik in items(Ai))

	return C

# A and B have to be symetric
def sdot(A, B, C=None):
	if C is None:
		C = mgraph(len(A))

	if _is_dict_graph(B):
		if _is_dict_graph(A):
			_sdotDD(A, B, C)
		else:
			_sdotXM(B, A, C)
	else:
		_sdotXM(A, B, C)

	return C

def _sdotXM(A, B, C):
	n = len(B)
	items = _itemsFunc(A)
	for i, Ai in enumerate(A):
		for j in range(i, n):
			Bj = B[j]
			s = sum(Aik * Bj[k] for k, Aik in items(Ai))
			C[i][j] = s
			C[j][i] = s

def _sdotDD(A, B, C):
	n = len(B)
	for i, Ai in enumerate(A):
		for j in range(i, n):
			Bj = B[j]
			if len(Ai) < len(Bj):
				s = sum(Ai[k] * Bj[k] for k in Ai if k in Bj)
			else:
				s = sum(Ai[k] * Bj[k] for k in Bj if k in Ai)
			C[i][j] = s
			C[j][i] = s