topobench.transforms.liftings.graph2combinatorial.graph_induced_cc module#

GraphInducedCC lifting of graphs to combinatorial complexes.

class CombinatorialComplex(cells=None, ranks=None, graph_based=False, **kwargs)#

Bases: ColoredHyperGraph

Class for Combinatorial Complex.

A Combinatorial Complex (CCC) is a triple $CCC = (S, X, rk)$ where: - $S$ is an abstract set of entities, - $X$ a subset of the power set of $S$, and - $rk$ is the a rank function that associates for every set x in X a rank, a positive integer.

The rank function $rk$ must satisfy $x subseteq y$ then $rk(x) leq rk(y)$. We call this condition the CCC condition.

A CCC is a generalization of graphs, hypergraphs, cellular and simplicial complexes.

Mathematical Example:

Let $S = {1, 2, 3, 4}$ be a set of abstract entities. Let $X = {{1, 2}, {1, 2, 3}, {1, 3}, {1, 4}}$ be a subset of the power set of $S$. Let rk be the ranking function that assigns the length of a set as its rank, i.e. $rk({1, 2}) = 2$, $rk({1, 2, 3}) = 3$, etc.

Then, $(S, X, rk)$ is a combinatorial complex.

Parameters:

cellsCollection, optional: A collection of cells to add to the combinatorial complex.
ranksCollection, optional: When cells is an iterable or dictionary, ranks cannot be None and it must be iterable/dict of the same size as cells.
graph_basedbool, default=False: When true rank 1 edges must have cardinality equals to 1.
**kwargskeyword arguments, optional: Attributes to add to the complex as key=value pairs.

Attributes:

complexdict: A dictionary that can be used to store additional information about the complex.

Raises:

TypeError: If cells is not given as an Iterable.
ValueError: If input cells is not an instance of HyperEdge when rank is None. If input HyperEdge has None rank when rank is specified. If cells and ranks do not have an equal number of elements.

Examples

Define an empty combinatorial complex:

>>> CCC = tnx.CombinatorialComplex()

Add cells to the combinatorial complex:

>>> CCC = tnx.CombinatorialComplex()
>>> CCC.add_cell([1, 2], rank=1)
>>> CCC.add_cell([3, 4], rank=1)
>>> CCC.add_cell([1, 2, 3, 4], rank=2)
>>> CCC.add_cell([1, 2, 4], rank=2)
>>> CCC.add_cell([1, 2, 3, 4, 5, 6, 7], rank=3)

__init__(cells=None, ranks=None, graph_based=False, **kwargs)#

Initialize a new instance of the Complex class.

Parameters:

**kwargskeyword arguments, optional: Attributes to add to the complex as key=value pairs.

add_cell(cell, rank=None, **attr)#

Add a single cells to combinatorial complex.

Parameters:

cellhashable, iterable or HyperEdge: If hashable the cell returned will be empty.
rankint: Rank of the cell.
**attrkeyword arguments, optional: Attributes to add to the cell as key=value pairs.

add_cells_from(cells, ranks=None)#

Add cells to combinatorial complex.

Parameters:

cellsiterable of hashables: For hashables the cells returned will be empty.
ranksiterable or int, optional: When iterable, len(ranks) == len(cells).

add_node(node, **attr)#

Add a node to a CCC.

Parameters:

nodeHashable: The node to add to this combinatorial complex.
**attrkeyword arguments, optional: Attributes to add to the node as key=value pairs.

adjacency_matrix(rank, via_rank, s=1, index=False)#

Sparse weighted s-adjacency matrix.

Parameters:

rank, via_rankint: Two ranks for skeletons in the input combinatorial complex.
sint, default=1: Minimum number of edges shared by neighbors with node.
indexbool, default=False: Whether to return the indices of the rows and columns of the adjacency matrix.

Returns:

indiceslist: List identifying the rows and columns of the adjacency matrix with the cells of the combinatorial complex. Only returned if index is True.
adjacency_matrixscipy.sparse.csr.csr_matrix: The adjacency matrix of this combinatorial complex.

Examples

>>> CCC = tnx.CombinatorialComplex()
>>> CCC.add_cell([1, 2], rank=1)
>>> CCC.add_cell([3, 4], rank=1)
>>> CCC.add_cell([1, 2, 3, 4], rank=2)
>>> CCC.add_cell([1, 2, 4], rank=2)
>>> CCC.add_cell([1, 2, 3, 4, 5, 6, 7], rank=3)
>>> CCC.adjacency_matrix(0, 1)

clone()#

Return a copy of the simplex.

The clone method by default returns an independent shallow copy of the simplex and attributes. That is, if an attribute is a container, that container is shared by the original and the copy. Use Python’s copy.deepcopy for new containers.

Returns:

CombinatorialComplex: A copy of this combinatorial complex.

coadjacency_matrix(rank, via_rank, s=1, index=False)#

Compute the coadjacency matrix of self.

Parameters:

rank, via_rankint: Two ranks for skeletons in the input combinatorial complex , such that r>k.
sint, default=1: Minimum number of edges shared by neighbors with node.
indexbool, default=False: Whether to return the indices of the rows and columns of the coadjacency matrix.

Returns:

indiceslist: List identifying the rows and columns of the coadjacency matrix with the cells of the combinatorial complex. Only returned if index is True.
coadjacency_matrixscipy.sparse.csr.csr_matrix: The coadjacency matrix of this combinatorial complex.

dirac_operator_matrix(weight=None, index=False)#

Compute dirac operator matrix of self.

Parameters:

weightstr, optional: The name of the cell attribute to use as weights for the dirac operator matrix. If None, the matrix is binary.
indexbool, default=False: If True, return will include a dictionary of all cells in the complex uid.

Returns:

scipy.sparse.csr.csc_matrix | tuple[dict, dict, scipy.sparse.csc_matrix]: The dirac operator matrix, if index is False; otherwise, row_indices, col_indices : dict List identifying rows and columns of the dirac operator matrix. Only returned if index is True. dirac_matrix : scipy.sparse.csr.csc_matrix The dirac operator matrix of this combinatorial complex.

Examples

>>> CCC = tnx.CombinatorialComplex()
>>> CCC.add_cell([1, 2, 3, 4], rank=2)
>>> CCC.add_cell([1, 2], rank=1)
>>> CCC.add_cell([2, 3], rank=1)
>>> CCC.add_cell([1, 4], rank=1)
>>> CCC.add_cell([3, 4, 8], rank=2)
>>> CCC.dirac_operator_matrix()

get_cell_attributes(name, rank=None)#

Get node attributes from graph.

Parameters:

namestr: Attribute name.
rankint: Restrict the returned attribute values to cells of a specific rank.

Returns:

dict: Dictionary of attributes keyed by cell or k-cells if k is not None.

Examples

>>> G = nx.path_graph(3)
>>> CCC = tnx.CombinatorialComplex(G)
>>> d = {
...     (1, 2): {"color": "red", "attr2": 1},
...     (0, 1): {"color": "blue", "attr2": 3},
... }
>>> CCC.set_cell_attributes(d)
>>> cell_color = CCC.get_cell_attributes("color")
>>> cell_color[frozenset({0, 1})]
'blue'

get_node_attributes(name)#

Get node attributes.

Parameters:

namestr: Attribute name.

Returns:

dict[Hashable, Any]: Dictionary mapping each node to the value of the given attribute name.

Examples

>>> G = nx.path_graph(3)
>>> CCC = tnx.CombinatorialComplex(G)
>>> d = {0: {"color": "red", "attr2": 1}, 1: {"color": "blue", "attr2": 3}}
>>> CCC.set_node_attributes(d)
>>> CCC.get_node_attributes("color")
{0: 'red', 1: 'blue'}

>>> G = nx.Graph()
>>> G.add_nodes_from([1, 2, 3], color="blue")
>>> CCC = tnx.CombinatorialComplex(G)
>>> nodes_color = CCC.get_node_attributes("color")
>>> nodes_color[1]
'blue'

incidence_matrix(rank, to_rank=None, incidence_type='up', weight=None, sparse=True, index=False)#

Compute incidence matrix for the CCC between rank and to_rank skeleti.

Parameters:

rank, to_rankint: For which rank of cells to compute the incidence matrix.
incidence_type{“up”, “down”}, default=”up”: Whether to compute the up or down incidence matrix.
weightbool, default=False: The name of the cell attribute to use as weights for the incidence matrix. If None, all cell weights are considered to be one.
sparsebool, default=True: Whether to return a sparse or dense incidence matrix.
indexbool, default=False: Whether to return the indices of the rows and columns of the incidence matrix.

Returns:

row_indices, col_indicesdict: Dictionary assigning each row and column of the incidence matrix to a cell.
incidence_matrixscipy.sparse.csr.csr_matrix: The incidence matrix.

number_of_cells(cell_set=None)#

Compute the number of cells in cell_set belonging to the CCC.

Parameters:

cell_setiterable of HyperEdge, optional: If None, then return the number of cells.

Returns:

int: The number of cells in cell_set belonging to this combinatorial complex.

number_of_nodes(node_set=None)#

Compute the number of nodes in node_set belonging to the CCC.

Parameters:

node_setiterable of Entities, optional: If None, then return the number of nodes in the CCC.

Returns:

int: The number of nodes in node_set belonging to this combinatorial complex.

order()#

Compute the number of nodes in the CCC.

Returns:

int: The number of nodes in this combinatorial complex.

remove_cell(cell)#

Remove a single cell from CCC.

Parameters:

cellhashable or RankedEntity: The cell to remove from this combinatorial complex.

Notes

Deletes reference to cell from all of its nodes. If any of its nodes do not belong to any other cells the node is dropped from self.

remove_cells(cell_set)#

Remove cells from CCC.

Parameters:

cell_setiterable of hashables: The cells to remove from this combinatorial complex.

remove_node(node)#

Remove node from cells.

This also deletes any reference in the nodes of the CCC. This also deletes cell references in higher ranks for the particular node.

Parameters:

nodehashable or HyperEdge: The node to remove from this combinatorial complex.

remove_nodes(node_set)#

Remove nodes from cells.

This also deletes references in combinatorial complex nodes.

Parameters:

node_setan iterable of hashables: The nodes to remove from this combinatorial complex.

remove_singletons()#

Construct new CCC with singleton cells removed.

Returns:

CombinatorialComplex: A copy of this combinatorial complex with singleton cells removed.

set_cell_attributes(values, name=None)#

Set cell attributes.

Parameters:

valuesdict: Dictionary of cell attributes to set keyed by cell name.
namestr, optional: Attribute name.

Examples

After computing some property of the cell of a combinatorial complex, you may want to assign a cell attribute to store the value of that property for each cell:

>>> CCC = tnx.CombinatorialComplex()
>>> CCC.add_cell([1, 2, 3, 4], rank=2)
>>> CCC.add_cell([1, 2, 4], rank=2)
>>> CCC.add_cell([3, 4], rank=2)
>>> d = {(1, 2, 3, 4): "red", (1, 2, 3): "blue", (3, 4): "green"}
>>> CCC.set_cell_attributes(d, name="color")
>>> CCC.cells[(3, 4)]["color"]
'green'

If you provide a dictionary of dictionaries as the second argument, the entire dictionary will be used to update edge attributes:

>>> G = nx.path_graph(3)
>>> CCC = tnx.CombinatorialComplex(G)
>>> d = {
...     (1, 2): {"color": "red", "attr2": 1},
...     (0, 1): {"color": "blue", "attr2": 3},
... }
>>> CCC.set_cell_attributes(d)
>>> CCC.cells[(0, 1)]["color"]
'blue'
3

Note that if the dict contains cells that are not in self.cells, they are silently ignored.

singletons()#

Return a list of singleton cell.

A singleton cell is a node of degree 0.

Returns:

list: A list of cells uids.

Examples

>>> CCC = tnx.CombinatorialComplex()
>>> CCC.add_cell([1, 2], rank=1)
>>> CCC.add_cell([3, 4], rank=1)
>>> CCC.add_cell([9], rank=0)
>>> CCC.singletons()
[frozenset({9})]

skeleton(rank, level='equal')#

Skeleton of the CCC.

Parameters:

rankint: The rank of the skeleton.
levelstr, default=”equal”: Level of the skeleton.

Returns:

list of HyperEdge: The skeleton of the CCC.

property cells#

Object associated with self._cells.

Returns:

HyperEdgeView: Returns all the present cells in the combinatorial complex along with their rank.

property nodes#

Object associated with self.elements.

Returns:

NodeView: Returns all the nodes of the combinatorial complex.

property shape#

Return shape.

This is: (number of cells[i], for i in range(0,dim(CCC)) )

Returns:

tuple of ints: Shape of the CC object.

class Graph2CombinatorialLifting(**kwargs)#

Bases: GraphLifting

Abstract class for lifting graphs to combinatorial complexes.

Parameters:

**kwargsoptional: Additional arguments for the class.

__init__(**kwargs)#

class GraphTriangleInducedCC(**kwargs)#

Bases: Graph2CombinatorialLifting

Lift graph to combinatorial complexes.

Parameters:

**kwargsoptional: Additional arguments for the class.

__init__(**kwargs)#

lift_topology(data)#

Lift the topology of a graph to a combinatorial complex.

Parameters:

datatorch_geometric.data.Data: The input data to be lifted.

Returns:

dict: The lifted topology.

class combinations(iterable, r)#

Bases: object

Return successive r-length combinations of elements in the iterable.

combinations(range(4), 3) –> (0,1,2), (0,1,3), (0,2,3), (1,2,3)

class defaultdict#

Bases: dict

defaultdict(default_factory=None, /, […]) –> dict with default factory

The default factory is called without arguments to produce a new value when a key is not present, in __getitem__ only. A defaultdict compares equal to a dict with the same items. All remaining arguments are treated the same as if they were passed to the dict constructor, including keyword arguments.

__init__(*args, **kwargs)#

copy() → a shallow copy of D.#

default_factory#: Factory for default value called by __missing__().

build_paths(overlap_pairs)#

Find overlapint sequesnces.

Parameters:

overlap_pairslist: List of pairs of overlapping triangles.

Returns:

list: List of sequences of overlaping triangles.

find_overlapping_paths(lists)#

Find ovelaping triabgles and their seuqences.

Parameters:

listslist: List of triangles.

Returns:

list: List of sequences of overlaping triangles.