Package: dec_graphs

Decontractible Graphs are recursively defined graphs that can be used to represent graphs which nodes can be decomposed into smaller graphs. This module provides classes to represent decontractible graphs, its nodes and edges as independent objects called supernodes and superedges, respectively, and some algorithms to work with them.

Class: DecGraph

class DecGraph(dict_V=None, dict_E=None)

Bases: object

A decontractible graph is a directed graph where each node represents a graph and each edge represents a non-empty set of edges between the nodes represented by the tail and the nodes represented by the head of the edge. Nodes of a decontractible graph are called supernodes and edges are called superedges.

More formally, a decontractible graph is a quadruple G = (V, E, dec_V, dec_E) where

• V is a set of supernodes

• E, subset of V x V, is a set of directed superedges

• dec_V is a function that assigns to each supernode v in V a decontractible graph dec_V(v) = G_v

• dec_E is a function that assigns to each superedge e in E a set of superedges dec_E(e) = E_e, such that for each superedge e = (v, w) in E, v is a supernode in G_v and w is a supernode in G_w

This implementation of the decontractible graph uses independent classes for supernodes and superedges and associates to each supernode and superedge an attribute dec that is, respectively, a decontractible graph representing the supernode and a set of superedges representing the superedge.

The decontractible graph is internally represented as a directed graph where nodes are the keys of the supernodes and edges are the keys of the superedges. The actual supernode and superedge objects are stored in the dictionaries V and E of the decontractible graph, respectively, that map the keys to the corresponding objects.

Parameters:

• dict_V (Dict[Any, Supernode]) –

• dict_E (Dict[Any, Superedge]) –

V

A dictionary that maps the keys of supernodes to the supernodes in the decontractible graph.

Type:

Dict[Any, Supernode]

E

A dictionary that maps the keys of superedges to the superedges in the decontractible graph.

Type:

Dict[Any, Superedge]

See also

Supernode, Superedge

Examples

A decontractible graph can be created as follows, creating its supernodes and superedges directly:

from multilevelgraphs.dec_graphs import DecGraph, Supernode, Superedge
dec_graph = DecGraph()
n1 = Supernode(1)
n2 = Supernode(2)
e = Superedge(n1, n2)
dec_graph.add_node(n1)
dec_graph.add_node(n2)
dec_graph.add_edge(e)

Or can be created from a NetworkX directed graph using the natural_transformation static method from the MultiLevelGraph class. In the following example, an equivalent decontractible graph is created:

import networkx as nx
from multilevelgraphs import MultiLevelGraph
nx_graph = nx.DiGraph()
nx_graph.add_edges_from([(1, 2)])
dec_graph = MultiLevelGraph.natural_transformation(nx_graph)

In both cases the created supernodes and superedges will have an empty decontraction.

Once the decontractible graph is created, specific supernodes and superedges can be accessed through the V and E attributes. In the following example, a new supernode is added to both decontractible graphs n1.dec and n2.dec, then a new superedge between the two new subnodes is added to the decontraction of the superedge with key (1,2):

subnode_1 = Supernode(3)
subnode_2 = Supernode(4)
dec_graph.V[1].dec.add_node(subnode_1)
dec_graph.V[2].dec.add_node(subnode_2)
dec_graph.E[(1, 2)].dec.add(Superedge(subnode_1, subnode_2))

Superedges added to supernodes decontractions must have their tail and head supernodes included in the decontractions:

subnode_3 = Supernode(5)
subnode_4 = Supernode(6)
dec_graph.V[1].dec.add_node(subnode_3)
dec_graph.V[1].dec.add_node(subnode_4)
dec_graph.V[1].dec.add_edge(Superedge(subnode_3, subnode_4))

Note that supernodes must have a unique key relative to the decontractible graph where they are directly included, so a supernode with key 1 can host a supernode with key 1 in its decontraction.

__init__(dict_V=None, dict_E=None)

Initializes a decontractible graph with the given supernodes and superedges described by V and E dictionaries, that map the keys of supernodes and superedges to the corresponding objects. A shallow copy of the given dictionaries is made, so changes in the original dictionaries will not affect the decontractible graph.

If no supernodes and superedges are given, an empty decontractible graph is created.

Parameters:

• dict_V (Dict[Any, Supernode] | None) – the dictionary of supernodes

• dict_E (Dict[Any, Superedge] | None) – the dictionary of superedges

add_edge(superedge)

Adds a superedge to the decontractible graph. If the superedge has a tail and head the key of which are already in the graph as an edge, it will not be added again. If the supernodes of the superedge to be added are not included in the decontractible graph, rises a ValueError.

Parameters:

superedge (Superedge) – the superedge to be added

add_node(supernode)

Adds a supernode to the decontractible graph. If the supernode has a key that is already in the graph, it will not be added again.

Parameters:

supernode (Supernode) – the supernode to be added

complete_decontraction()

Returns the complete decontraction of this decontractible graph. The complete decontraction of a decontractible graph is the decontractible graph obtained by expanding all supernodes and superedges into the supernodes and superedges they represent.

If all supernodes and superedges in this decontractible graph have an empty decontraction, an empty decontractible graph is returned. Otherwise, if at least one supernode or superedge has a non-empty decontraction, the complete decontraction will contain all supernodes and superedges in those non-empty decontractions.

Returns:

the complete decontraction of this decontractible graph

Return type:

DecGraph

deepcopy(supernode_memo=None)

Returns a deep copy of this decontractible graph. Supernodes and superedges in the decontractible graph are recursively deep copied as well as their decontractions and default attributes. Values of custom attributes of supernodes and superedges are not deep copied.

The supernode parameter is used in the recursive calls to indicate the supernode that this decontractible graph is contracted into, and should not be used in the call to this method.

Parameters:

supernode_memo (Supernode | None) – the supernode that this decontractible graph is contracted into

Returns:

a deep copy of this decontractible graph

degree(node)

Returns the degree of a supernode in the decontractible graph, which is the number of superedges that have the supernode as tail or head.

Parameters:

node (Supernode) – the supernode to get the degree

Returns:

the degree of the supernode

Return type:

int

edges()

Returns the set of superedges in the decontractible graph.

Returns:

the set of superedges in the decontractible graph

Return type:

Set[Superedge]

edges_keys()

Returns the set of keys of superedges in the decontractible graph.

Returns:

the set of keys of superedges in the decontractible graph

Return type:

Set

forward_star(node)

Returns the forward star of a supernode in the decontractible graph, which is the set of supernodes m such that there is an edge from the given supernode to m in the decontractible graph.

Parameters:

node (Supernode) – the supernode to get the forward star

Returns:

the forward star of the supernode

Return type:

Set[Supernode]

graph(ref=False, attr=False)

Returns this decontractible graph as a simple directed graph with simple nodes and edges. If ref is True, the returned graph is a reference to this decontractible graph structure and changes in the returned graph will affect the original decontractible graph structure. If attr is True, nodes in the returned graph will carry the same attributes as the original decontractible graph supernodes. Note that setting ref to True will always return a graph with no attributes in the nodes, regardless of the value of the attr parameter.

Parameters:

• ref (bool) – If True, the returned graph is a view of the decontractible graph.

• attr (bool) – If True, the returned graph nodes have the same attributes as in the original decontractible graph.

Returns:

the corresponding NetworkX directed graph

Return type:

DiGraph

height()

Returns the height of the decontractible graph, as the maximum height among supernodes in this graph, where the height of a supernode is the height of the decontractible graph represented by the supernode.

Returns:

the height of the decontractible graph

Return type:

int

in_edges(node)

Returns the set of superedges that have the given supernode as head in the decontractible graph.

Parameters:

node (Supernode) – the supernode to get the in edges

Returns:

the set of superedges that have the given supernode as head

Return type:

Set[Superedge]

induced_subgraph(nodes)

Returns the induced decontractible subgraph of this decontractible graph by the given set of supernodes. The induced subgraph of a graph on a subset of nodes N is the graph with nodes N and edges from G which have both ends in N. If the set of supernodes keys is not entirely included in the decontractible graph, only the supernodes that are included in the decontractible graph will be considered.

Parameters:

• self – the decontractible graph

• nodes (Iterable[Supernode]) – the set of supernodes to induce the subgraph

Returns:

the induced subgraph

Return type:

DecGraph

induced_subgraph_from_keys(nodes_keys)

Returns the induced decontractible subgraph of this decontractible graph by the given set of supernodes keys. The induced subgraph of a graph on a subset of nodes N is the graph with nodes N and edges from G which have both ends in N. If the set of supernodes keys is not entirely included in the decontractible graph, only the supernodes keys that are included in this decontractible graph will be considered.

Parameters:

• self – the decontractible graph

• nodes_keys (Set) – the set of supernodes keys to induce the subgraph

Returns:

the induced subgraph

Return type:

DecGraph

nodes()

Returns the set of supernodes in the decontractible graph.

Returns:

the set of supernodes in the decontractible graph

Return type:

Set[Supernode]

nodes_keys()

Returns the set of keys of supernodes in the decontractible graph.

Returns:

the set of keys of supernodes in the decontractible graph

Return type:

Set

order()

Returns the order of the decontractible graph, as the number of supernodes in this graph.

Returns:

the order of the decontractible graph

Return type:

int

out_edges(node)

Returns the set of superedges that have the given supernode as tail in the decontractible graph.

Parameters:

node (Supernode) – the supernode to get the out edges

Returns:

the set of superedges that have the given supernode as tail

Return type:

Set[Superedge]

remove_edge(superedge)

Removes a superedge from the decontractible graph. If the superedge has a tail and head the key of which are not in the graph as an edge, rise a KeyError.

Parameters:

superedge (Superedge) – the superedge to be removed

remove_node(supernode)

Removes a supernode from the decontractible graph. All edges that have the supernode as tail or head in this decontractible graph will be removed as well. If the supernode has a key which is not in the graph, rise a KeyError.

Parameters:

supernode (Supernode) – the supernode to be removed

reverse_star(node)

Returns the reverse star of a supernode in the decontractible graph, which is the set of supernodes m such that there is an edge from m to the given supernode in the decontractible graph.

Parameters:

node (Supernode) – the supernode to get the reverse star

Returns:

the reverse star of the supernode

Return type:

Set[Supernode]

Class: Supernode

class Supernode(key, level=None, dec=None, component_sets=None, supernode=None, **attr)

Bases: object

A supernode is a node of a decontractible graph that represents another decontractible graph.

A supernode can be considered as an independent element which brings some information about the context where it is included. This information is stored in the attributes of the supernode.

Parameters:

• level (int) –

• dec (DecGraph) –

• component_sets (FrozenSet) –

• supernode (Supernode | None) –

key

the unique identifier of the supernode in the decontractible graph

Type:

Any

level

the level this supernode belongs to in a multilevel graph, if any

Type:

Optional[int]

dec

the decontractible graph represented by this supernode

Type:

DecGraph

component_sets

the set of component sets that this supernode represents in the contraction scheme it was created from, if any

Type:

FrozenSet

supernode

the supernode that this supernode is contracted into, if any

Type:

Optional[Supernode]

attr

a dictionary of custom attributes and values to be added to the supernode

Type:

Dict[str, Any]

Examples

A supernode can be created indicating a key of any type and any other optional attribute, that are typically automatically initialized when the supernode is created by structures like MultiLevelGraph. Custom attributes, as ‘weight’, for instance, can be added to the supernode as follows:

from multilevelgraphs.dec_graphs import Supernode
supernode = Supernode(key=1, level=0, weight=10)

While the default supernode attributes are accessed with the . notation, custom attributes can be accessed and assigned with the [] notation:

print(supernode.level) # 0
print(supernode['weight']) # 10
supernode['weight'] = 20
print(supernode['weight']) # 20

__init__(key, level=None, dec=None, component_sets=None, supernode=None, **attr)

Initializes a supernode.

Parameters:

• key – an immutable value representing the key label of the supernode. It is used to identify the supernode in the decontractible graph and should be unique in the decontractible graph where the supernode resides.

• level (int | None) – the level this supernode belongs to in a multilevel graph, if any

• dec (DecGraph | None) – the decontractible graph represented by this supernode

• supernode (Supernode | None) – the supernode that this supernode into

• attr – a dictionary of custom attributes to be added to the supernode

• component_sets (FrozenSet | None) –

add_edge(edge_for_adding)

Adds a superedge to the decontractible graph represented by this supernode.

If the superedge has a tail and head the key of which are already in the graph as an edge, it will not be added again.

Parameters:

edge_for_adding (Superedge) – the edge to be added

add_node(supernode)

Adds a supernode to the decontractible graph represented by this supernode. If the supernode has a key that is already in the graph, it will not be added again. If this supernode belongs to a multilevel graph, the level of the supernode to be added must be one less than the level of this supernode.

Parameters:

supernode (Supernode) – the supernode to be added

deepcopy(supernode=None)

Returns a deep copy of this supernode. The decontractible graph represented by this supernode is recursively deep copied as well.

Note that the component_sets attribute is simply copied by reference, due to strict dependency with the contraction scheme the node comes from. Therefore, component sets in the component_sets attribute should not be changed.

Parameters:

supernode (Supernode | None) – the reference to the supernode that this supernode is contracted into

Returns:

the deep copy of this supernode

height()

Returns the height of this supernode as the height of the decontractible graph represented by this supernode. This is equivalent to the height of the hierarchy tree of supernodes contracted into this supernode. If this node belongs to a multilevel graph, the height of the supernode is the level where the supernode is located in the multilevel graph.

Returns:

the height of the decontractible graph

Return type:

int

is_in_multi_level_graph()

Returns True if this supernode belongs to a multilevel graph, False otherwise.

Returns:

True if this supernode belongs to a multilevel graph, False otherwise

Return type:

bool

remove_edge(edge_for_removal)

Removes a superedge from the decontractible graph represented by this supernode.

If the superedge has a tail and head the key of which are not in the graph as an edge, rise a KeyError.

Parameters:

edge_for_removal (Superedge) – the superedge to be removed

remove_node(supernode)

Removes a supernode from the decontractible graph represented by this supernode.

If the supernode has a key which is not in the graph, rise a KeyError.

Parameters:

supernode (Supernode) – the supernode to be removed

size()

Returns the number of 0-height supernodes this supernode represents. This number is the amount of leaf supernodes in the hierarchy tree of supernodes contracted into this supernode.

Return type:

int

update(**attr)

Update the supernode attributes with the given attributes.

Parameters:

attr – the attributes to be added to the supernode

Class: Superedge

class Superedge(tail, head, level=None, dec=None, **attr)

Bases: object

A superedge is an edge of a decontractible graph that represents a set of superedges between the supernodes in the decontraction of the tail and the head of the superedge.

Parameters:

• tail (Supernode) –

• head (Supernode) –

• level (int) –

• dec (Set[Superedge]) –

tail

the supernode that is the tail of the superedge

Type:

Supernode

head

the supernode that is the head of the superedge

Type:

Supernode

level

the level this superedge belongs to in a multilevel graph, if any

Type:

Optional[int]

dec

the set of superedges represented by this superedge

Type:

Set[Superedge]

attr

a dictionary of custom attributes and values to be added to the superedge

Type:

Dict[str, Any]

Examples

A superedge can be created indicating the reference to the tail and head supernodes objects and any other optional attribute, that are typically automatically initialized when the supernode is created by structures like MultiLevelGraph. Custom attributes, as ‘weight’, for instance, can be added to the superedge as follows:

from multilevelgraphs.dec_graphs import Supernode, Superedge
supernode_1 = Supernode(key=1, level=0)
supernode_2 = Supernode(key=2, level=0)
superedge = Superedge(tail=supernode_1, head=supernode_2, level=0, weight=10)

While the default supernode attributes are accessed with the . notation, custom attributes can be accessed and assigned with the [] notation:

print(superedge.level) # 0
print(superedge['weight']) # 10
superedge['weight'] = 20
print(superedge['weight']) # 20

__init__(tail, head, level=None, dec=None, **attr)

Initializes a superedge.

Parameters:

• tail (Supernode) – the supernode that is the tail of the superedge

• head (Supernode) – the supernode that is the head of the superedge

• level (int | None) – the level this superedge belongs to in a multilevel graph, if any

• dec (Set[Superedge] | None) – the set of superedges represented by this superedge

• attr – a dictionary of custom attributes to be added to the superedge

add_edge(superedge)

Adds a superedge to the superedge set represented by this superedge. If the superedge has a tail and head the key of which are already in the set, it will not be added again.

Parameters:

superedge (Superedge) – the superedge to be added

deepcopy(v_copies=None)

Returns a deep copy of this superedge. The set of superedges represented by this superedge is recursively deep copied.

The deep copied supernodes dictionary of the decontractible graph where this superedge resides must be passed as a parameter to this method in order to create the deep copy of the superedges in the set.

Parameters:

v_copies (Dict | None) – a dictionary of supernode copies to be used in the recursive calls

Returns:

the deep copy of this superedge

height()

Returns the height of this superedge as the maximum height of the superedges represented by this superedge. This is equivalent to the height of the hierarchy tree of superedges contracted into this superedge. If this edge belongs to a multilevel graph, the height of the superedge is the level where the superedge is located in the multilevel graph, and coincides with the level of the tail and head supernode. The height of a superedge having an empty set of superedges is 0.

Returns:

the height of this superedge

Return type:

int

is_in_multi_level_graph()

Returns True if this superedge belongs to a multilevel graph, False otherwise.

Returns:

True if this superedge belongs to a multilevel graph, False otherwise

Return type:

bool

remove_edge(superedge)

Removes a superedge from the superedge set represented by this superedge. If the superedge is not in the set, rise a KeyError.

Parameters:

superedge (Superedge) – the superedge to be removed

size()

Returns the number of 0-height superedges this superedge represents. This number is the amount of leaf superedges in the hierarchy tree of superedges contracted into this superedge.

Return type:

int

update(**attr)

Update the superedge attributes with the given attributes.

Parameters:

attr – the attributes to be added to the superedge

Module: Algorithms

maximal_cliques(dec_graph, reciprocal=False)

Enumerates all the maximal cliques in the given decontractible graph as a list of sets of supernodes. The cliques are calculated on the undirected version of the given decontractible graph, obtained by keeping only edges that appear in both directions in the original digraph or not, depending on the value of the reciprocal parameter.

The implementation is based on the NetworkX library. More precisely, cliques are found using the non-recursive version of Bron-Kerbosch algorithm (1973) [1], as adapted by Tomita, Tanaka and Takahashi (2006) [2] and discussed in Cazals and Karande (2008) [3].

Parameters:

• dec_graph (DecGraph) – the decontractible graph

• reciprocal (bool) – If True, cliques are calculated on the undirected version of the given decontractible graph containing only edges that appear in both directions in the original decontractible graph.

Returns:

the set of maximal cliques as sets of supernodes

Return type:

set

References

[1]

Bron, C. and Kerbosch, J. “Algorithm 457: finding all cliques of an undirected graph”. Communications of the ACM 16, 9 (Sep. 1973), 575–577. <http://portal.acm.org/citation.cfm?doid=362342.362367 >

[2]

Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi, “The worst-case time complexity for generating all maximal cliques and computational experiments”, Theoretical Computer Science, Volume 363, Issue 1, Computing and Combinatorics, 10th Annual International Conference on Computing and Combinatorics (COCOON 2004), 25 October 2006, Pages 28–42 <https://doi.org/10.1016/j.tcs.2006.06.015 >

[3]

Cazals, F. and Karande, C. “A note on the problem of reporting maximal cliques”, Theoretical Computer Science, Volume 407, Issues 1–3, 6 November 2008, Pages 564–568, <https://doi.org/10.1016/j.tcs.2008.05.010 >

simple_cycles(dec_graph)

Enumerates all the simple cycles in the given decontractible graph as a set of list of supernodes. A simple cycle, or elementary circuit, is a closed path where no node appears twice. In a decontractible (directed) graph, two simple cycles are distinct if they are not cyclic permutations of each other.

The implementation is based on the NetworkX library. More precisely, simple cycles are found using a nonrecursive, iterator/generator version of Johnson’s algorithm [4], enhanced by some well-known preprocessing techniques that restrict the attention to strongly connected components of the graph.

Parameters:

dec_graph (DecGraph) – The decontractible graph.

Returns:

An iterator of simple cycles as tuples of supernodes.

Return type:

set

References

[4]

Johnson D. B. , “Finding all the elementary circuits of a directed graph,” SIAM Journal on Computing, vol. 4, no. 1, pp. 77-84, 1975. https://doi.org/10.1137/0204007

strongly_connected_components(dec_graph)

Enumerates all the strongly connected components in the given decontractible graph as a set of sets of supernodes. A strongly connected component (SCC) of a decontractible (directed) graph is a maximal subgraph in which there is a path between every pair of nodes.

The implementation is based on the NetworkX library. More precisely, the SCCs are found using the Kosaraju’s algorithm [5].

Parameters:

dec_graph (DecGraph) – the decontractible graph

Returns:

The set of strongly connected components as sets of supernodes

Return type:

set

References

[5]

Sharir M. , “A strong-connectivity algorithm and its applications in data flow analysis”, Computers & Mathematics with Applications, 1981 - Elsevier. https://doi.org/10.1016/0898-1221(81)90008-0