delta_graphs.py

from pymwp import DeltaGraph

DeltaGraph

DeltaGraph(*init_nodes: Optional[Union[Monomial, NODE]], degree: int = 3)

Delta Graph is a dictionary representing a weighted graph of tuples of deltas (also referenced here as a monomial_list, a list of Monomials without its scalar). We will often refer to tuple of deltas as simple node, but a node with length!

Nodes are "sorted" by this length in order to be compared by chunks of same size.

Weight of edge represents the index where the nodes differ.

We use tuple because we want them to be hashable (as key in dictionary).

Example

                      ↓
n1 = ((0,1), (0,2), (0,3), (0,4))
n2 = ((0,1), (0,2), (1,3), (0,4))

in our graph will have:

n1 <---- 3 ----> n2

or

size = 4   ↓
graph_dict[4][n1][n2] = 3

The graph is symmetric:

graph_dict[4][n2][n1] = 3

This representation will help us simplify the evaluation by removing redundant/irrelevant choices/paths.

Attributes:

Name	Type	Description
graph_dict	dict	Dictionary of nodes.
degree	int	Graph degree.

Create a Delta Graph.

Parameters:

Name	Type	Description	Default
*init_nodes	Optional[Union[Monomial, NODE]]	Initial list of monomials or nodes.	()
degree	int	Degree of a full node.	3

Example

Create an empty delta graph

dg = DeltaGraph()

Create delta graph with some initial nodes from monomials.

dg = DeltaGraph(mono1, mono2)

from_monomial

from_monomial(monomial: Monomial) -> None

Add monomial's deltas to the delta graph.

Parameters:

Name	Type	Description	Default
monomial	Monomial	monomial	required

fusion

fusion() -> None

Eliminates cliques of same label in a delta graph.

Example

m1 = ((0, 1), (0, 2))
m2 = ((0, 1), (1, 2))
m3 = ((0, 1), (2, 2), (0, 3))
m4 = ((0, 1), (2, 2), (1, 3))
m5 = ((0, 1), (2, 2), (2, 3))

Delta graph:

  m1 -- 2 -- m2
  m3 -- 3 -- m4
   ⟍         |
      3      3
        ⟍    |
          ⟍  |
            m5

Looks for cliques (size default 3) at each index.
=> Graph will simplify to: ((0,1)).

insert_edge

insert_edge(node1: NODE, node2: NODE, label: int) -> None

Add an edge of label label between node1 and node2 If one node does not exist, it's created

Symmetry is also added in the graph.

Parameters:

Name	Type	Description	Default
node1	NODE	first node	required
node2	NODE	second node	required
label	int	label over the edge	required

insert_node

insert_node(node: NODE) -> None

Insert a node into the graph.

If a node is already in the graph do nothing. Else compare it with all nodes of same size with node_diff.

Parameters:

Name	Type	Description	Default
node	NODE	tuple to insert in the graph	required

is_full

is_full(node: NODE, size: int, index: int) -> bool

Check for cliques of same label.

Example

n3 = ((0, 1), (2, 2), (0, 3))
n4 = ((0, 1), (2, 2), (1, 3))
n5 = ((0, 1), (2, 2), (2, 3))

node = n4
size = 3
index = 3
degree = 3

n3 -- 3 -- n4
 ⟍         |
    3       3
      ⟍    |
        ⟍  |
          n5

return True

Parameters:

Name	Type	Description	Default
node	NODE	check for clique around that graph node.	required
size	int	size of nodes or graph "level".	required
index	int	index where to find clique.	required

Returns:

Type	Description
bool	True if there is a clique.

node_diff staticmethod

node_diff(
    node1: NODE, node2: NODE, index: Optional[int] = None
) -> Tuple[bool, int]

Compares two nodes of the same length.

The return value is a tuple representing the result of comparison (boolean) and an index.

The result is True, if and only if both lists differ only on one element regarding the same index. The second return value is the index of the corresponding delta.

Parameters:

Name	Type	Description	Default
node1	NODE	first monomial list	required
node2	NODE	second monomial list	required
index	Optional[int]	index with to check number of diff	None

Returns:

Name	Type	Description
diff	bool	boolean True if the lists differ of one element
i	int	the index of the delta which differs

remove_index staticmethod

remove_index(node: NODE, index: int) -> NODE

Remove delta with given index.

Example

remove index 4:
((0, 2), (1, 3), (2, 4))  ->  ((0, 2), (1, 3))

Parameters:

Name	Type	Description	Default
node	NODE	monomial list	required
index	int	index to remove	required

Returns:

Type	Description
NODE	a new tuple without deltas with index index

remove_node

remove_node(node: NODE, index: int) -> None

Remove given node and neighbors connected with same label.

Also removes edges/labels connected to the node (they no longer exist).