Some terminology
Let X be an abs. We call an element of X a simplex.
\begin{definition}: the vertices of X, written V, are the set of all points in at least one element of X. Writing this formally: $V = \bigcup \limits _{S \in X}S$$. \end{definition}\begin{definition} If $\sigma$ is a simplex, and $\tau$ is a subset of $\sigma$, then we say that $\tau$ is a face of $\sigma$ or that $\sigma$ is a coface of $\tau$ and denote this by $\tau \le \sigma$. \end{definition}Definition: If \sigma \in X then the dimension of \sigma is |\sigma|-1.
Definition: If \sigma \in X and the only coface of \sigma is itself, then we call \sigma a maximal simplex.
Notice that an abs is completely determined by its set of maximal simplices.
Representation in Python
We want a convenient way to represent and generate these objects. Firstly we want to create one from a list of maximal simplices given as lists of integers. Secondly we want to map the (co)face relations, and enable us to easily iterate over simplices of a given dimension.
So stage one will be unwrapping the maximal simplices into simplices, placing them in a tree. Stage two will be filling in the face relations, representing the abs as a Hasse diagram, where each node represents a simplex.
Which Data structures?
based on http://www.math.cornell.edu/~levine/18.312/alg-comb-lecture-11.pdf, see this book https://books.google.it/books?id=9sfSCQAAQBAJ&pg=PA248&lpg=PA248&dq=hasse+diagram+simplicial+complex&source=bl&ots=k0RxMv8KK4&sig=UE5vIFvwdF9EO6XIzJcKpAzqopw&hl=it&sa=X&ved=0ahUKEwjor6TF_pzWAhVJBMAKHTx8D7gQ6AEIWzAH#v=onepage&q=hasse%20diagram%20simplicial%20complex&f=false
How to visualize?
Enanche jupyter utilities:
The following is based on the excellent blog: https://triangleinequality.wordpress.com. Python igraph is interfaced only for plotting purposes and the module tigraph is used as basis for the Simplicial class.
In [35]:
# Tigraph from https://triangleinequality.wordpress.com
# -*- coding: utf-8 -*-
import numpy as np
import igraph as ig
import functools
class BasicNode: #should be interfaced to from a graph object
def __init__(self, content=None, labels=None):
self.content = content
self.incident_edges =set([])
self.incident_outward_edges=set([])
self.incident_inward_edges=set([])
self.label=None
def add_edge(self,Edge):
self.incident_edges.add(Edge)
if Edge.source()==self:
self.incident_outward_edges.add(Edge)
else:
self.incident_inward_edges.add(Edge)
def remove_edge(self,Edge):
self.incident_edges.discard(Edge)
def get_neighbors(self):
neighbors = [Edge.ends for Edge in self.incident_edges]
unique_neighbors = list(set(reduce(lambda x,y: x+y, neighbors)))
if [self, self] not in neighbors: #checks for a loop
unique_neighbors.remove(self)
return set(unique_neighbors)
def get_targets(self):
#targets = set([Edge.target() for Edge in self.incident_outward_edges])
targets = set(map(lambda x: x.target(), self.incident_outward_edges))
return targets
def get_sources(self):
#sources = set([Edge.source() for Edge in self.incident_inward_edges])
sources = set(map(lambda x: x.source(), self.incident_inward_edges))
return sources
def add_label(self, label):
self.label =label
def remove_label(self, label):
self.label=None
class BasicEdge: #should be interfaced to from a graph object
def __init__(self, content=None, ends=[], labels=None):
self.content = content
self.ends = ends
if labels is None:
self.labels=set([])
else:
self.labels=labels
def source(self):
return self.ends[0]
def target(self):
return self.ends[1]
def add_label(self, label):
self.labels.add(label)
def remove_label(self, label):
self.labels.discard(label)
def update_up(class_method):
def inner(self, *args, **kwargs):
method_name = class_method.func_name
class_method(self, *args, **kwargs)
for Supergraph in self.supergraphs:
getattr(Supergraph, method_name)(*args, **kwargs)
return inner
def update_up_down(class_method):
def inner(self, *args, **kwargs):
method_name = class_method.func_name
if class_method(self, *args, **kwargs):
for Supergraph in self.supergraphs:
getattr(Supergraph, method_name)(*args, **kwargs)
for Subgraph in self.subgraphs:
getattr(Subgraph, method_name)(*args, **kwargs)
return inner
class Graph(object):
def __init__(self, vertices=None, edges=None, Vertex=BasicNode, Edge=BasicEdge):
if edges == None:
edges = []
self.edges=set(edges)
if vertices == None:
vertices = []
self.vertices=vertices
self.vertex_dict = {}
self.edges_dict={}
self.Vertex = Vertex
self.Edge = Edge
def create_vertex(self, *args, **kwargs):
self.vertices.append(self.Vertex(*args, **kwargs))
def create_vertices(self, no_create):
for i in range(no_create):
self.create_vertex()
def add_vertex(self, Vertex):
self.vertices.append(Vertex)
def create_edge(self, ends):
NewEdge=self.Edge(ends=ends)
self.edges.add(NewEdge)
for Vertex in ends:
Vertex.add_edge(NewEdge)
def remove_edge(self, Edge):
self.edges.discard(Edge)
def get_incident_edges(self, Vertex):
incident_edges = Vertex.incident_edges
return incident_edges
def remove_vertex(self, Vertex):
edges_to_remove = self.get_incident_edges(Vertex)
for Edge in edges_to_remove:
self.remove_edge(Edge)
self.vertices.remove(Vertex)
def get_vertex_neighbors(self, Vertex):
neighbors = Vertex.get_neighbors()
return neighbors
def get_degree(self, Vertex):
return len(self.get_incident_edges(Vertex))
def get_number_vertices(self):
return len(self.vertices)
def get_number_edges(self):
return len(self.edges)
def get_adjacency_matrix(self):
#adj_list = map(lambda x: self.get_adjacency_list_of_vertex(x), self.vertices)
adj_list = list(map(lambda x: self.get_adjacency_list_of_vertex(x), self.vertices))
adj_mat = np.array(adj_list)
return adj_mat
def get_adjacency_matrix_as_list(self):
return self.get_adjacency_matrix().tolist()
def set_adjacency_list(self, adj_list):
self.vertices=[]
self.edges=[]
def is_in(self,vertex_or_edge):
if (vertex_or_edge in self.edges) or (vertex_or_edge in self.vertices):
return True
else:
return False
def get_incident_outward_edges(self,Vertex):
return Vertex.incident_outward_edges
def get_incident_inward_edges(self,Vertex):
return Vertex.incident_inward_edges
def get_vertex_targets(self, Vertex):
targets = Vertex.get_targets()
return targets
def get_vertex_sources(self, Vertex):
sources = Vertex.get_sources()
return sources
def add_vertex_label(self, vertex, label):
self.vertex_dict[label] = vertex
vertex.add_label(label)
def get_vertex(self,label):
if label in self.vertex_dict.keys():
return self.vertex_dict[label]
def get_vertex_label(self, vertex):
labels = vertex.get_labels()
labels = labels & self.vertex_dict.keys()
labels = filter(lambda x: self.get_vertex[x]==vertex,labels)
def remove_vertex_label(self, label):
vertex=self.vertex_dict.pop(label, 'Not Found')
if vertex == 'Not Found':
return
else:
vertex.remove_label(label)
def add_edge_label(self, edge, label):
self.edge_dict[label] = edge
edge.add_label(label)
def get_edge(self,label):
if label in self.edge_dict.keys():
return self.edge_dict[label]
else:
return None
def get_edge_label(self, edge):
labels = edge.get_labels()
labels = filter(lambda x: self.get_edge[x]==edge,labels)
def remove_edge_label(self, label):
edge=self.edge_dict.pop(label, 'Not Found')
if edge == 'Not Found':
return
else:
edge.remove_label(label)
class UnDirGraph(Graph, object):
def get_adjacency_list_of_vertex(self, Vertex):
N = self.get_number_vertices()
adj_list= [0 for x in range(N)]
incident_edges = self.get_incident_edges(Vertex)
for Edge in incident_edges:
ends = Edge.ends
if ends[0] != Vertex:
index = self.vertices.index(ends[0])
else:
index = self.vertices.index(ends[1])
adj_list[index] += 1
return adj_list
def set_adjacency_matrix(self, adj_mat):
shape = np.shape(adj_mat)
if shape[0] != shape[1]:
print('Wrong shape, expecting square matrix.')
return
n = shape[0]
self.vertices=[]
self.edges=set([])
self.create_vertices(n)
for row in range(n):
Source = self.vertices[row]
for col in range(row+1):
no_edges = adj_mat[row, col]
Target = self.vertices[col]
for Edge in range(no_edges):
self.create_edge(ends=[Source, Target])
def plot(self):
A = self.get_adjacency_matrix_as_list()
g = ig.Graph.Adjacency(A, mode='undirected')
for vertex in self.vertices:
if vertex.label !=None:
#print vertex.label
index=self.vertices.index(vertex)
g.vs[index]['label']=vertex.label
# layout = g.layout("rt", root=0)
visual_style = {}
visual_style["vertex_size"] = 20
visual_style["vertex_label_angle"]=0
visual_style["vertex_label_dist"] =1
#layout.rotate(180)
ig.plot(g, margin=60, **visual_style)
class DirGraph(Graph):
def get_adjacency_list_of_vertex(self, Vertex):
N = self.get_number_vertices()
adj_list= [0 for x in range(N)]
incident_edges = self.get_incident_outward_edges(Vertex)
for Edge in incident_edges:
target = Edge.target()
index = self.vertices.index(target)
adj_list[index] += 1
return adj_list
def set_adjacency_matrix(self, adj_mat):
shape = np.shape(adj_mat)
if shape[0] != shape[1]:
print('Wrong shape, expecting square matrix.')
return
n = shape[0]
self.vertices=[]
self.edges=set([])
self.create_vertices(n)
for row in range(n):
for col in range(n):
no_edges = adj_mat[row, col]
Source = self.vertices[row]
Target = self.vertices[col]
for Edge in range(no_edges):
self.create_edge(ends=[Source, Target])
def get_vertex_targets(self, Vertex):
targets = Vertex.get_targets()
return targets
def get_vertex_sources(self, Vertex):
sources = Vertex.get_sources()
return sources
def plot(self):
A = self.get_adjacency_matrix_as_list()
g = ig.Graph.Adjacency(A)
for vertex in self.vertices:
if vertex.label !=None:
index=self.vertices.index(vertex)
g.vs[index]['label']=vertex.label
g.vs[index]['label_dist']=2
layout = g.layout("circle")
ig.plot(g)
#This is a wrapper to a class definition, deciding whether to inherit
#from DirGraph or UnDirGraph at runtime. It can be initialised by
#number of vertices or the number of edges.
def return_linear_class(directed=False):
if directed:
base=DirGraph
else:
base=UnDirGraph
class Linear(base, object):
def __init__(self, number_vertices=0, number_edges=0, **kwargs):
super(Linear, self).__init__(**kwargs)
self.linear_generate(number_vertices, number_edges)
def linear_generate(self,number_vertices, number_edges):
if (not number_edges ==0) and (not number_vertices==0):
if not number_vertices == number_edges+1:
print('Number of edges and vertices incompatible!')
return
else:
self.number_vertices=number_vertices
elif not number_edges==0:
self.number_vertices = number_edges +1
else:
self.number_vertices = number_vertices
self.create_vertices(self.number_vertices)
for index in range(self.number_vertices -1):
Source = self.vertices[index]
Target = self.vertices[index+1]
self.create_edge([Source, Target])
return Linear
#instantiates the Linear class
def create_linear(directed=False, number_vertices=0, number_edges=0,**kwargs):
linear = return_linear_class(directed)(number_vertices, number_edges,**kwargs)
return linear
#Class definition wrapper to dynamically inherti from DirGraph or UnDirGraph.
#Also has a composition from Linear, to create a cycle it joins the ends
#of a linear graph.
def return_cycle_class(directed=False):
if directed:
base = DirGraph
else:
base = UnDirGraph
class Cycle(base, object):
def __init__(self, number_vertices=0, number_edges=0, **kwargs):
super(Cycle, self).__init__(**kwargs)
if (not number_edges==0) and (not number_vertices==0):
if not number_edges == number_vertices:
print('Numbers of edges and vertices incompatible!')
return
elif not number_edges ==0:
number_vertices = number_edges
Linear_part = create_linear()
Linear_part.linear_generate(number_vertices, number_edges-1)
self.vertices = Linear_part.vertices
self.edges = Linear_part.edges
self.cycle_generate(number_vertices)
def cycle_generate(self, number_vertices):
Target = self.vertices[0]
Source = self.vertices[number_vertices-1]
self.create_edge(ends=[Source, Target])
return Cycle
def create_cycle(directed=False, number_vertices=0, number_edges=0, **kwargs):
cycle = return_cycle_class(directed)(number_vertices, number_edges, **kwargs)
return cycle
class Complete(UnDirGraph, object):
def __init__(self,number_vertices=0, **kwargs):
super(Complete, self).__init__(**kwargs)
self.create_vertices(no_create=number_vertices)
ends=[]
for Source in self.vertices:
for Target in self.vertices:
if [Source,Target] not in ends:
if not Source == Target:
self.create_edge(ends=[Source,Target])
ends.append([Source,Target])
ends.append([Target, Source])
def return_tree_class(directed=False):
if directed:
base = DirGraph
else:
base = UnDirGraph
class Tree(base, object):
def __init__(self, **kwargs):
super(Tree, self).__init__(**kwargs)
self.leaves=set([])
self.find_leaves()
def is_leaf(self, vertex):
if self.get_degree(vertex) == 1:
return True
elif self.get_number_vertices() ==1:
return True
else:
return False
def set_root(self, vertex):
if vertex in self.vertices:
self.remove_vertex_label('Root')
self.add_vertex_label(vertex, label='Root')
def get_root(self):
return self.get_vertex('Root')
def find_leaves(self):
self.leaves = set(filter(self.is_leaf,self.vertices))
return [leaf for leaf in self.leaves]
return Tree
def create_tree(directed=False, **kwargs):
tree = return_tree_class(directed)(**kwargs)
return tree
def return_nary_tree_class(directed=False):
base = return_tree_class(directed)
class NaryRootedTree(base,object):
def __init__(self, N=0, **kwargs):
super(NaryRootedTree, self).__init__(**kwargs)
self.N = N
def split_vertex(self, vertex):
if vertex in self.leaves:
children = [self.Vertex() for i in range(self.N)]
vertex.children = children
self.leaves.discard(vertex)
for Child in children:
self.add_vertex(Child)
self.leaves.add(Child)
Child.parent=vertex
self.create_edge(ends=[vertex, Child])
def fuse_vertex(self, vertex):
self.leaves.add(vertex)
try:
children=vertex.children
except AttributeError:
return
if children==None:
return
for child in children:
self.fuse_vertex(child)
self.leaves.discard(child)
self.remove_vertex(child)
child.parent = None
vertex.children = None
def create_full_n_level(self, n):
self.vertices =[]
self.edges =set([])
self.create_vertex()
self.set_root(self.vertices[0])
for level in range(n):
leaves=self.find_leaves()
for Leaf in leaves:
self.split_vertex(Leaf)
def get_descendants(self, node, desc=set({})):
try:
children=node.children
except AttributeError:
node.children=None
if children != None:
for child in children:
desc = desc.union(set({child}))
desc= desc.union(self.get_descendants(child))
return desc
else:
return desc
return NaryRootedTree
def create_nary_tree(directed=False, N=0,**kwargs):
nary_tree = return_nary_tree_class(directed)(N, **kwargs)
return nary_tree
In [2]:
import igraph as ig
class Simplex(BasicNode, object):
def __init__(self, vertices, **kwargs):
super(Simplex, self).__init__(**kwargs)
self.vertices = vertices
self.faces=[]
self.cofaces=[]
self.dimension = len(self.vertices)-1
#These are used for initializing the complex:
self._cfaces =[]
self._children={}
self.__parent = None
class SimplicialComplex(return_tree_class(), object):
def __init__(self, maximal_simplices, Vertex=Simplex, **kwargs):
super(SimplicialComplex, self).__init__(Vertex=Vertex, **kwargs)
self.maximal_simplices = maximal_simplices
self.dimension = max(map(len,self.maximal_simplices))-1
self.n_simplex_dict={} #Keeps track of simplexes by dimension.
for i in range(-1,self.dimension+1):
self.n_simplex_dict[i]=[]
#Create the empty set 'root' of the structure.
self.create_simplex([])
self.set_root(self.vertices[0])
self.vertices[0].label=str([])
#Initialize complex from maximal simplices
for ms in self.maximal_simplices:
self.add_maximal_simplex(ms)
def create_simplex(self, vertices):
self.create_vertex(vertices)
vertex = self.vertices[-1]
self.n_simplex_dict[vertex.dimension].append(self.vertices[-1])
#It is convienient for the simplex to know its index for later on
#when we create 'vectors' of simplices.
index = len(self.n_simplex_dict[vertex.dimension])-1
vertex.index=index
vertex.label=str(vertices)
def create_child(self, simplex, vertex):
#This method creates a new simplex which is an immediate coface to the argument
#simplex. It does so by appending the new vertex to the old simplex's vertices.
#_cfaces keeps track of which of the simplex's cofaces have already been added.
if vertex in simplex._cfaces:
return
simplex._cfaces.append(vertex)
child_vertices=[v for v in simplex.vertices]
child_vertices.append(vertex)
self.create_simplex(child_vertices)
child=self.vertices[-1]
child._parent=simplex
simplex._children[vertex]=child
self.leaves.add(child)
self.create_edge(ends=[simplex, child])
simplex.cofaces.append(child)
child.faces.append(simplex)
def add_maximal_simplex(self,vertices, simplex=None, first=True):
#We start at the root.
if first:
simplex = self.get_root()
if len(vertices)>=1: #Condition to terminate recursion.
for index in range(len(vertices)):
vertex = vertices[index]
self.create_child(simplex, vertex)
self.add_maximal_simplex(simplex=simplex._children[vertex],
vertices=vertices[index+1:],
first=False)
def plot(self,margin=60):
A = self.get_adjacency_matrix_as_list()
print(A)
g = ig.Graph.Adjacency(A, mode='undirected')
print(g)
# for vertex in self.vertices:
# if vertex.label !=None:
# #print vertex.label
# index=self.vertices.index(vertex)
# g.vs[index]['label']=vertex.label
#The layout is designed for trees, so we tell it to set the empty set as the root.
#layout = g.layout("rt", root=0)
#layout = g.layout("kk")
#visual_style = {}
#visual_style["vertex_size"] = 20
#visual_style["vertex_label_angle"]=3
#visual_style["vertex_label_dist"] =1
#We want the root at the bottom of the plot.
#layout.rotate(180)
#ig.plot(g, layout=layout, margin=margin, **visual_style)
return g
#ig.plot(g, layout=layout)
In [3]:
%matplotlib inline
import cairo
# Why it doesn't plot from within function in Jupyter?
from igraph import plot
def test(n):
maximal_simplices = [list(range(n))]
Sn = SimplicialComplex(maximal_simplices)
g =Sn.plot()
test(4)
plot(g, layout='rt')
In [4]:
from igraph import Graph
class Tree(Graph, object):
"""
vertex = vertex index (note that the index may change, if this turn out to be an issue vertex= vertex attribute)
"""
def __init__(self, **kwargs):
super(Tree, self).__init__(**kwargs)
self.leaves=set([])
self.find_leaves()
def is_leaf(self, vertex):
"""Class method: check if vertex is a leaf
Note:
The root is not usually considered a leaf, http://mathworld.wolfram.com/TreeLeaf.html, whereas here the
root is considered a leaf.
Args:
param1: vertex index.
Returns:
True if successful, False otherwise.
"""
if self.degree(vertex) == 1:
return True
elif self.vcount() ==1:
return True
else:
return False
def set_root(self, vertex):
if vertex in [v.index for v in self.vs]:
g.vs[0]['Root']=g.vs[0]['name']
del g.vs[0]['name']
def get_root(self):
return self.vs.select(name_eq="Root")
def find_leaves(self):
self.leaves = set(filter(self.is_leaf, [v.index for v in self.vs]))
return [leaf for leaf in self.leaves]
In [5]:
t = Tree()
t.add_vertices(3)
print(t.is_leaf(2))
t.add_edge(1,2)
print([x.index for x in t.vs])
print(t.is_leaf(2))
print(t.find_leaves())
In [6]:
#class Simplex(tig.BasicNode, object):
from igraph import Vertex, Graph
class Simplex(Vertex, object):
def __init__(self, vertices, **kwargs):
super(Simplex, self).__init__(**kwargs)
self.vertices = vertices
self.faces=[]
self.cofaces=[]
self.dimension = len(self.vertices)-1
#These are used for initializing the complex:
self._cfaces =[]
self._children={}
self.__parent = None
In [33]:
class SimplicialComplex(Tree, object): #to be implemented on top of igraph
def __init__(self, maximal_simplices, Ver=Simplex, **kwargs):
super(SimplicialComplex, self).__init__(**kwargs)
self.vertices = self.vs
self.maximal_simplices = maximal_simplices
self.dimension = max(map(len,self.maximal_simplices))-1
self.n_simplex_dict={} #Keeps track of simplexes by dimension.
for i in range(-1,self.dimension+1):
self.n_simplex_dict[i]=[]
#Create the empty set 'root' of the structure.
self.create_simplex([])
self.set_root(self.vertices[0])
self.vertices[0].label=str([])
#Initialize complex from maximal simplices
for ms in self.maximal_simplices:
self.add_maximal_simplex(ms)
def create_simplex(self, vertices):
self.add_vertices(vertices)
vertex = self.vertices[-1]
self.n_simplex_dict[vertex.dimension].append(self.vertices[-1])
#It is convienient for the simplex to know its index for later on
#when we create 'vectors' of simplices.
index = len(self.n_simplex_dict[vertex.dimension])-1
vertex.index=index
vertex.label=str(vertices)
def create_child(self, simplex, vertex):
#This method creates a new simplex which is an immediate coface to the argument
#simplex. It does so by appending the new vertex to the old simplex's vertices.
#_cfaces keeps track of which of the simplex's cofaces have already been added.
if vertex in simplex._cfaces:
return
simplex._cfaces.append(vertex)
child_vertices=[v for v in simplex.vertices]
child_vertices.append(vertex)
self.create_simplex(child_vertices)
child=self.vertices[-1]
child._parent=simplex
simplex._children[vertex]=child
self.leaves.add(child)
self.create_edge(ends=[simplex, child])
simplex.cofaces.append(child)
child.faces.append(simplex)
def add_maximal_simplex(self,vertices, simplex=None, first=True):
#We start at the root.
if first:
simplex = self.get_root()
if len(vertices)>=1: #Condition to terminate recursion.
for index in range(len(vertices)):
vertex = vertices[index]
self.create_child(simplex, vertex)
self.add_maximal_simplex(simplex=simplex._children[vertex],
vertices=vertices[index+1:],
first=False)
In [34]:
s = SimplicialComplex([list(range(3))])
In [22]:
def test(n):
maximal_simplices = [list(range(n))]
Sn = SimplicialComplex(maximal_simplices)
Sn.plot()
Sn.update_adjacency()
Sn.plot()
test(4)
In [ ]:
In [ ]: