Package: contraction_schemes_impl

Class: CliquesContractionScheme

class CliquesContractionScheme(supernode_attr_function=None, superedge_attr_function=None, c_set_attr_function=None, reciprocal=False)

Bases: EdgeBasedContractionScheme

An edge-based contraction scheme defined by the contraction function by cliques. According to this scheme, two nodes are in the same component set if they are part of the same maximal clique, and two nodes are part of the same supernode if they are part of the same set of maximal cliques. In this scheme there is a one-to-one correspondence between supernodes and distinct non-empty sets of component sets.

In a decontractible (directed) graph, a clique is a subset of nodes of a graph such that every two distinct nodes are adjacent. A maximal clique is a clique that is not a subset of any other clique.

The reciprocal attribute of the scheme determines how two nodes are considered adjacent: if True, two nodes are adjacent if there is an edge between them in both directions in the original graph, otherwise, two nodes are adjacent if there is an edge between them in at least one direction in the original graph.

Parameters:

• supernode_attr_function (Callable[[Supernode], Dict[str, Any]]) –

• superedge_attr_function (Callable[[Superedge], Dict[str, Any]]) –

• c_set_attr_function (Callable[[Set[Supernode]], Dict[str, Any]]) –

• reciprocal (bool) –

_reciprocal

boolean value that determines how two nodes are considered adjacent in the original graph

Type:

bool

__init__(supernode_attr_function=None, superedge_attr_function=None, c_set_attr_function=None, reciprocal=False)

Initializes a contraction scheme based on the contraction function by cliques. In a decontractible (directed) graph, a clique is a subset of nodes of a graph such that every two distinct nodes are adjacent. A maximal clique is a clique that is not a subset of any other clique. The reciprocal parameter determines how two nodes are considered adjacent: if True, two nodes are adjacent if there is an edge between them in both directions in the original graph, otherwise, two nodes are adjacent if there is an edge between them in at least one direction in the original graph.

Parameters:

• supernode_attr_function (Callable[[Supernode], Dict[str, Any]] | None) – a function that returns the attributes to assign to each supernode of this scheme

• superedge_attr_function (Callable[[Superedge], Dict[str, Any]] | None) – a function that returns the attributes to assign to each superedge of this scheme

• c_set_attr_function (Callable[[Set[Supernode]], Dict[str, Any]] | None) – a function that returns the attributes to assign to each component set of this scheme

• reciprocal (bool) – if True, two nodes are considered adjacent if there is an edge between them in both directions

clone()

Instantiates and returns a new contraction scheme with the same starting attributes as this one, such as attribute functions and others based on the implementation. The new contraction scheme does not preserve any information about the contraction sets or the decontractible graph of the clones one.

This method is used internally by the multilevel graph to create new contraction schemes based on their construction parameters and preserve their encapsulation.

Returns:

a new contraction scheme with the same starting attributes as this one

component_sets_table: CompTable | None

contract(dec_graph)

Modifies the state of this contraction scheme constructing a decontractible from the given decontractible graph according to this contraction scheme.

Parameters:

dec_graph (DecGraph) – the decontractible graph to be contracted

Returns:

the contracted decontractible graph

Return type:

DecGraph

contraction_function(dec_graph)

Returns component set table for the given decontractible graph according to this contraction scheme. The component set table is a mapping between nodes and their corresponding collection of component sets the node is part of, according to the contraction scheme.

The returned component set table should provide a covering of the nodes of the decontractible graph, where each node appears as the key of a row of the table, and all the sets of component sets provided as values should be non-empty.

All the component sets tracked by the table should also be distinct in terms of their contained supernodes.

Parameters:

dec_graph (DecGraph) – the decontractible graph to be contracted

Return type:

CompTable

contraction_name()

Returns the name of the contraction scheme. The name should be unique among all the implementations of the ContractionScheme class. The name of the contraction scheme is used as part of the key for each supernode in the decontractible graph of this contraction scheme.

Returns:

the name of the contraction scheme

Return type:

str

dec_graph: DecGraph | None

invalidate()

Marks the decontractible graph of this contraction scheme as invalid, that is, it has not been contracted or is not up-to-date with the changes in the lower level decontractible graph.

is_valid()

Returns whether the decontractible graph of this contraction scheme is valid, that is, it has been contracted and is up-to-date with the changes in the lower level decontractible graph.

Returns:

True if the decontractible graph is valid, False otherwise

level: int | None

supernode_table: Dict[FrozenSet[ComponentSet], Supernode]

update(update_quadruple)

Updates the structure of the decontractible graph of this contraction scheme according to the given update quadruple, indicating the changes in the supernodes and superedges of the decontractible graph at the immediate lower level.

Parameters:

update_quadruple (UpdateQuadruple) – the update quadruple indicating the changes in the lower level decontractible graph

Returns:

the updated decontractible graph of this contraction scheme

Return type:

DecGraph

update_attr()

Updates the attributes of the supernodes, superedges and component sets of this contraction scheme.

update_quadruple: UpdateQuadruple

Class: CyclesContractionScheme

class CyclesContractionScheme(supernode_attr_function=None, superedge_attr_function=None, c_set_attr_function=None, maximal=True)

Bases: DecontractionEdgeBasedContractionScheme

A contraction scheme based on the contraction function by simple cycles. According to this scheme, two nodes are in the same component set if they are part of the same simple cycle among all distinct simple cycles in the graph, and two nodes are part of the same supernode if they are part of the same set of simple cycles. In this scheme there is a one-to-one correspondence between supernodes and distinct non-empty sets of component sets.

In a decontractible (directed) graph, a simple cycle, or elementary circuit, is a closed path where no node appears twice. Two simple cycles are distinct if they are not cyclic permutations of each other. A maximal simple cycle is a simple cycle that is not a subset of any other simple cycle.

The maximal attribute of the scheme determines whether only maximal simple cycles are considered.

Parameters:

• supernode_attr_function (Callable[[Supernode], Dict[str, Any]]) –

• superedge_attr_function (Callable[[Superedge], Dict[str, Any]]) –

• c_set_attr_function (Callable[[Set[Supernode]], Dict[str, Any]]) –

• maximal (bool) –

_maximal

boolean value that determines whether only maximal simple cycles are considered

Type:

bool

__init__(supernode_attr_function=None, superedge_attr_function=None, c_set_attr_function=None, maximal=True)

Initializes a contraction scheme based on the contraction function by simple cycles. 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. A maximal simple cycle is a simple cycle that is not a subset of any other simple cycle.

Parameters:

• supernode_attr_function (Callable[[Supernode], Dict[str, Any]] | None) – a function that returns the attributes to assign to each supernode of this scheme

• superedge_attr_function (Callable[[Superedge], Dict[str, Any]] | None) – a function that returns the attributes to assign to each superedge of this scheme

• c_set_attr_function (Callable[[Set[Supernode]], Dict[str, Any]] | None) – a function that returns the attributes to assign to each component set of this scheme

• maximal (bool) – if True, only maximal simple cycles are considered

clone()

Instantiates and returns a new contraction scheme with the same starting attributes as this one, such as attribute functions and others based on the implementation. The new contraction scheme does not preserve any information about the contraction sets or the decontractible graph of the clones one.

This method is used internally by the multilevel graph to create new contraction schemes based on their construction parameters and preserve their encapsulation.

Returns:

a new contraction scheme with the same starting attributes as this one

component_sets_table: CompTable | None

contract(dec_graph)

Modifies the state of this contraction scheme constructing a decontractible from the given decontractible graph according to this contraction scheme.

Parameters:

dec_graph (DecGraph) – the decontractible graph to be contracted

Returns:

the contracted decontractible graph

Return type:

DecGraph

contraction_function(dec_graph)

Returns component set table for the given decontractible graph according to this contraction scheme. The component set table is a mapping between nodes and their corresponding collection of component sets the node is part of, according to the contraction scheme.

The returned component set table should provide a covering of the nodes of the decontractible graph, where each node appears as the key of a row of the table, and all the sets of component sets provided as values should be non-empty.

All the component sets tracked by the table should also be distinct in terms of their contained supernodes.

Parameters:

dec_graph (DecGraph) – the decontractible graph to be contracted

Return type:

CompTable

contraction_name()

Returns the name of the contraction scheme. The name should be unique among all the implementations of the ContractionScheme class. The name of the contraction scheme is used as part of the key for each supernode in the decontractible graph of this contraction scheme.

Returns:

the name of the contraction scheme

Return type:

str

static cycle_search(graph, path)

Parameters:

• graph (Graph) –

• path (list) –

Return type:

Generator

dec_graph: DecGraph | None

invalidate()

Marks the decontractible graph of this contraction scheme as invalid, that is, it has not been contracted or is not up-to-date with the changes in the lower level decontractible graph.

is_valid()

Returns whether the decontractible graph of this contraction scheme is valid, that is, it has been contracted and is up-to-date with the changes in the lower level decontractible graph.

Returns:

True if the decontractible graph is valid, False otherwise

level: int | None

set_decontracted_graph()

Sets the complete decontraction of the graph of this scheme. This method is used to lazily set the decontracted graph during the update procedures.

supernode_table: Dict[FrozenSet[ComponentSet], Supernode]

update(update_quadruple)

Updates the structure of the decontractible graph of this contraction scheme according to the given update quadruple, indicating the changes in the supernodes and superedges of the decontractible graph at the immediate lower level.

Parameters:

update_quadruple (UpdateQuadruple) – the update quadruple indicating the changes in the lower level decontractible graph

Returns:

the updated decontractible graph of this contraction scheme

Return type:

DecGraph

update_attr()

Updates the attributes of the supernodes, superedges and component sets of this contraction scheme.

update_quadruple: UpdateQuadruple

Class: SCCsContractionScheme

class SCCsContractionScheme(supernode_attr_function=None, superedge_attr_function=None, c_set_attr_function=None)

Bases: EdgeBasedContractionScheme

A contraction scheme based on the contraction function by strongly connected components. According to this scheme, two nodes are in the same component set and supernode if they are part of the same strongly connected component in the decontractible graph. In this scheme there is a one-to-one correspondence between supernodes and component sets.

A strongly connected component (SCC) of a decontractible (directed) graph is the node set of a maximal subgraph in which there is a path between every pair of nodes.

Parameters:

• supernode_attr_function (Callable[[Supernode], Dict[str, Any]]) –

• superedge_attr_function (Callable[[Superedge], Dict[str, Any]]) –

• c_set_attr_function (Callable[[Set[Supernode]], Dict[str, Any]]) –

__init__(supernode_attr_function=None, superedge_attr_function=None, c_set_attr_function=None)

Initializes a contraction scheme based on the contraction function by strongly connected components. A strongly connected component (SCC) of a decontractible (directed) graph is the node set of a maximal subgraph in which there is a path between every pair of nodes.

For this contraction scheme, there is a one-to-one correspondence between the strongly connected components of the decontractible graph and the component sets of the contraction scheme.

Parameters:

• supernode_attr_function (Callable[[Supernode], Dict[str, Any]] | None) – a function that returns the attributes to assign to each supernode of this scheme

• superedge_attr_function (Callable[[Superedge], Dict[str, Any]] | None) – a function that returns the attributes to assign to each superedge of this scheme

• c_set_attr_function (Callable[[Set[Supernode]], Dict[str, Any]] | None) – a function that returns the attributes to assign to each component set of this scheme

clone()

Instantiates and returns a new contraction scheme with the same starting attributes as this one, such as attribute functions and others based on the implementation. The new contraction scheme does not preserve any information about the contraction sets or the decontractible graph of the clones one.

This method is used internally by the multilevel graph to create new contraction schemes based on their construction parameters and preserve their encapsulation.

Returns:

a new contraction scheme with the same starting attributes as this one

component_sets_table: CompTable | None

contract(dec_graph)

Modifies the state of this contraction scheme constructing a decontractible from the given decontractible graph according to this contraction scheme.

Parameters:

dec_graph (DecGraph) – the decontractible graph to be contracted

Returns:

the contracted decontractible graph

Return type:

DecGraph

contraction_function(dec_graph)

Returns component set table for the given decontractible graph according to this contraction scheme. The component set table is a mapping between nodes and their corresponding collection of component sets the node is part of, according to the contraction scheme.

The returned component set table should provide a covering of the nodes of the decontractible graph, where each node appears as the key of a row of the table, and all the sets of component sets provided as values should be non-empty.

All the component sets tracked by the table should also be distinct in terms of their contained supernodes.

Parameters:

dec_graph (DecGraph) – the decontractible graph to be contracted

Return type:

CompTable

contraction_name()

Returns the name of the contraction scheme. The name should be unique among all the implementations of the ContractionScheme class. The name of the contraction scheme is used as part of the key for each supernode in the decontractible graph of this contraction scheme.

Returns:

the name of the contraction scheme

Return type:

str

dec_graph: DecGraph | None

invalidate()

Marks the decontractible graph of this contraction scheme as invalid, that is, it has not been contracted or is not up-to-date with the changes in the lower level decontractible graph.

is_valid()

Returns whether the decontractible graph of this contraction scheme is valid, that is, it has been contracted and is up-to-date with the changes in the lower level decontractible graph.

Returns:

True if the decontractible graph is valid, False otherwise

level: int | None

supernode_table: Dict[FrozenSet[ComponentSet], Supernode]

update(update_quadruple)

Updates the structure of the decontractible graph of this contraction scheme according to the given update quadruple, indicating the changes in the supernodes and superedges of the decontractible graph at the immediate lower level.

Parameters:

update_quadruple (UpdateQuadruple) – the update quadruple indicating the changes in the lower level decontractible graph

Returns:

the updated decontractible graph of this contraction scheme

Return type:

DecGraph

update_attr()

Updates the attributes of the supernodes, superedges and component sets of this contraction scheme.

update_quadruple: UpdateQuadruple