Package: contraction_schemes¶

Abstract Class: ContractionScheme¶

class ContractionScheme(supernode_attr_function=None, superedge_attr_function=None, c_set_attr_function=None)[source]¶

Bases: ABC

An abstract class for contraction schemes. A contraction scheme is a layer of a multilevel graph that defines how the nodes and edges of the graph are contracted into supernodes and superedges, respectively. More formally, a contraction scheme is a contraction function fc defined on the domain of decontractible graphs and codomain of contracted decontractible graphs, which, given a decontractible graph G, returns a new decontractible graph G’ that is a contraction of G.

Along with the definition of the contraction function, provided by the method contraction_function, a contraction scheme should define methods to update the contracted decontractible graph according to the changes in the lower level decontractible graph. Those methods are _update_added_node, _update_removed_node, _update_added_edge and _update_removed_edge.

When a contraction scheme is constructed, it can be initialized with attribute functions for supernodes, superedges and component sets. These functions produce a dictionary of key-value pairs that are used to assign attributes to the supernodes and superedges of the produced contracted decontractible graph, as well as to the component sets tracked by the component set table of the contraction scheme.

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]]) –

level¶

the level of the contraction scheme in the multilevel graph. Automatically set by the multilevel graph when the contraction scheme is added to it.

Type:: Optional[int]

dec_graph¶

the contracted decontractible graph produced by this contraction scheme.

Type:: Optional[DecGraph]

component_sets_table¶

the component set table of this contraction scheme, that tracks the current state of the component sets recognized by the contraction scheme.

Type:: Optional[CompTable]

supernode_table¶

a dictionary that maps the bijection between sets of component sets and the supernodes of the contracted decontractible graph produced by this contraction scheme.

Type:: Dict[FrozenSet[ComponentSet], Supernode]

update_quadruple¶

a quadruple of four sets that tracks the changes in the supernodes and superedges of the contracted decontractible graph. Used as a buffer to store the changes to send to the immediate upper level of the multilevel graph the contraction scheme is part of.

Type:: UpdateQuadruple

Examples

Let CliquesContractionScheme and SCCsContractionScheme be sample contraction scheme implementations, they can be used to define a multilevel graph as follows:

from multilevelgraphs import MultilevelGraph, SCCsContractionScheme, CliquesContractionScheme
import networkx as nx

nx_graph = nx.DiGraph()
nx_graph.add_edges_from([(1, 2), (2, 3), (3, 1)])

scheme_1 = CliquesContractionScheme()
scheme_2 = SCCsContractionScheme()
ml_graph = MultilevelGraph(nx_graph, [scheme_1, scheme_2])

The definition of the contraction scheme could also include attribute functions for supernodes, superedges and component sets:

scheme = SCCsContractionScheme(
    supernode_attr_function= lambda n: {'size': len(n)},
    superedge_attr_function= lambda e: {'weight': sum([edge['weight'] for edge in e.edges()])},
    c_set_attr_function= lambda c_set: {'size': len(c_set)}
)

__init__(supernode_attr_function=None, superedge_attr_function=None, c_set_attr_function=None)[source]¶

Initializes a contraction scheme based on the contraction function defined for this 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

_add_edge_in_superedge(tail_key, head_key, edge)[source]¶

Adds the given edge to the superedge in the decontractible graph of this contraction scheme having the given tail and head keys. If no such superedge is in the graph, it is added, and the quadruple is updated accordingly.

Parameters:

tail_key (Any) – the key of the tail supernode of the superedge
head_key (Any) – the key of the head supernode of the superedge
edge (Superedge) – the edge to add

_make_dec_graph(dec_table, dec_graph)[source]¶

Constructs a decontractible graph from the given decontractible graph and the table containing the mapping between nodes and their set of contraction sets.

Parameters:

dec_table (CompTable) – a table of contraction sets
dec_graph (DecGraph) – the decontractible graph to be contracted

Return type:

DecGraph

_remove_edge_in_superedge(tail_key, head_key, edge)[source]¶

Removes the given edge from the superedge in the decontractible graph of this contraction scheme having the given tail and head keys. If the superedge decontraction set becomes empty, it is removed from the graph, and the quadruple is updated accordingly.

Parameters:

tail_key (Any) – the key of the tail supernode of the superedge
head_key (Any) – the key of the head supernode of the superedge
edge (Superedge) – the edge to remove

abstract _update_added_edge(edge)[source]¶

Updates the structure of the decontractible graph of this contraction scheme according to the addition of the given superedge at the immediate lower level.

Parameters:: edge (Superedge) – the superedge added to the lower level decontractible graph

abstract _update_added_node(node)[source]¶

Updates the structure of the decontractible graph of this contraction scheme according to the addition of the given supernode at the immediate lower level.

The new added supernode should be immediately assigned to a new supernode in the decontractible graph of this contraction scheme. Temporary supernodes created in this method should not be tracked by the supernode table of this scheme.

Parameters:: node (Supernode) – the supernode added to the lower level decontractible graph

_update_graph()[source]¶: Updates the structure of the decontractible graph of this contraction scheme according to the changes in the component sets tracked by the component sets table.

abstract _update_removed_edge(edge)[source]¶

Updates the structure of the decontractible graph of this contraction scheme according to the removal of the given superedge at the immediate lower level.

Parameters:: edge (Superedge) – the superedge removed from the lower level decontractible graph

abstract _update_removed_node(node)[source]¶

Updates the structure of the decontractible graph of this contraction scheme according to the removal of the given supernode at the immediate lower level.

Parameters:: node (Supernode) – the supernode removed from the lower level decontractible graph

abstract clone()[source]¶

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

contract(dec_graph)[source]¶

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

abstract contraction_function(dec_graph)[source]¶

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

abstract contraction_name()[source]¶

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

invalidate()[source]¶: 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()[source]¶

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

update(update_quadruple)[source]¶

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()[source]¶: Updates the attributes of the supernodes, superedges and component sets of this contraction scheme.

Abstract Class: EdgeBasedContractionScheme¶

class EdgeBasedContractionScheme(supernode_attr_function=None, superedge_attr_function=None, c_set_attr_function=None)[source]¶

Bases: ContractionScheme, ABC

An abstract class for edge-based contraction schemes. An EdgeBasedContractionScheme is a ContractionScheme where two supernodes being part of the same connected component is a necessary condition for them to be part of the same component set. In other words, in an edge-based contraction scheme, if a single node has no incident edges, it must reside in a singleton component set. Examples of edge-based contraction schemes are the SCCs, Cycles and Cliques contraction schemes, where component sets are formed based on the connection between supernodes. Example of non-edge-based contraction schemes are the independent sets contraction scheme, where component sets are formed based on the absence of edges between supernodes.

This abstract class provides implementations for two of the update procedures defined in the ContractionScheme class: _update_added_node and _update_removed_node. The other update procedures, _update_added_edge and _update_removed_edge, are abstract and should be implemented by the subclasses as they depend on the specific contraction scheme.

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)[source]¶

Initializes a contraction scheme based on the contraction function defined for this 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

abstract clone()[source]¶

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

abstract contraction_function(dec_graph)[source]¶

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

abstract contraction_name()[source]¶

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¶

Abstract Class: DecontractionEdgeBasedContractionScheme¶

class DecontractionEdgeBasedContractionScheme(supernode_attr_function=None, superedge_attr_function=None, c_set_attr_function=None)[source]¶

Bases: EdgeBasedContractionScheme, ABC

An abstract class for edge-based contraction schemes which make use of the complete decontraction of its graph in the update algorithms.

This abstract class enriches the implementations of two of the update procedures defined in the ContractionScheme class: _update_added_node and _update_removed_node. The other update procedures, _update_added_edge and _update_removed_edge, are abstract and should be implemented by the subclasses as they depend on the specific contraction scheme. The _add_edge_to_decontraction and _remove_edge_from_decontraction methods of this class can be used to update the complete decontraction of the graph during the update procedures _update_added_edge and _update_removed_edge respectively.

Class: CompTable¶

class CompTable(sets=None, maximal=False)[source]¶

Bases: object

A component set table is a data structure associated with a particular layer of a multilevel graph that represents a covering of nodes at the immediate lower level and stores the information regarding which nodes are currently in which set of nodes.

This data structure can be used as a dictionary where the keys are the nodes and the values are the sets of component set of nodes to which they belong.

Parameters:

sets (Iterable[ComponentSet]) –
maximal (bool) –

modified¶

the set of nodes whose component sets have been modified in the rows of this table since the last update

Type:: Set[Supernode]

__init__(sets=None, maximal=False)[source]¶

Initializes a component set table with the given set of component sets of nodes. The given set should be a covering of the nodes of a decontractible graph, and all the component sets should be distinct in terms of their contained supernodes. In case the maximal parameter is set to True, the table will only track the maximal sets of nodes among the given component sets.

Parameters:

sets (Iterable[ComponentSet] | None) – the covering of nodes
maximal (bool) – if True, only maximal sets of nodes are stored

add_maximal_set(c_set, check_subsets=True)[source]¶

Adds the given component set to the table only if it is maximal among the sets already tracked in the table. If the given component is added to the table, sets already tracked in the table that are subsets of the given component set are removed.

When the check_subset flag is set to False, this method does not check for subsets of the given component set to remove in the table while adding it. For this reason this option should only be used for a performance gain purposes when it is guaranteed that the given component set is not a subset of any other component set in the table.

A component set is maximal if it is not a subset of any other component set in the table. Rows of the table that are modified due to the possible addition and removals are tracked in the modified set.

Parameters:

c_set (ComponentSet) – the component set to add
check_subsets (bool) – if True, the method does not check for subsets of the given component set to remove

add_non_maximal_set(c_set)[source]¶

Adds the given component set to the table tracked sets. If the given component set is already in the table according to its key, nothing happens. Note that component sets with the same set of nodes and different keys are considered distinct and no distinct component sets with different set of nodes should be added to the same table. Rows of the table that are modified due to the addition of the given component set are tracked in the modified set.

Parameters:: c_set (ComponentSet) – the component set to add

add_set(c_set, maximal=False)[source]¶

Adds the given component set to the table tracked sets. The method behaves differently depending on the maximal parameter:

When maximal is set to False: if the given component set is already in the table according to its key, nothing happens. Note that component sets with the same set of nodes and different keys are considered distinct and no distinct component sets with different set of nodes should be added to the same table. Rows of the table that are modified due to the addition of the given component set are tracked in the modified set.
When maximal is set to True: adds the given component set to the table only if it is maximal among the sets already tracked in the table. If the given component is added to the table, sets already tracked in the table that are subsets of the given component set are removed. A component set is maximal if it is not a subset of any other component set in the table. Rows of the table that are modified due to the possible addition and removals are tracked in the modified set.

Parameters:

c_set (ComponentSet) – the component set to add
maximal (bool) – if True, only maximal sets of nodes are stored and maintained

add_singletons(id_function)[source]¶

Creates and adds to this table singleton component sets for all the nodes that are not in any component set among the tracked sets. Note that only the nodes that have been tracked as modified are considered for this operation, since having empty set of component sets for a node is not a valid state in this table outside the update procedure of a contraction scheme.

Parameters:: id_function (Callable[[], int]) – the function to generate unique identifiers for the new component sets

get_all_c_sets()[source]¶

Returns all the unique component sets tracked in this table.

Returns:: all the unique component sets tracked in this table
Return type:: Set[ComponentSet]

items()[source]¶

keys()[source]¶

Return type:: Iterable[Supernode]

remove_set(c_set)[source]¶

Removes the given component set from the table tracked sets. If the given component set is not in the table, nothing happens. Rows of the table that are modified due to the removal of the given component set are tracked in the modified set.

Parameters:: c_set (ComponentSet) – the component set to remove

values()[source]¶

Return type:: Iterable[Set[ComponentSet]]

Class: ComponentSet¶

class ComponentSet(key, supernodes=None, **attr)[source]¶

Bases: object

A ComponentSet is a set of supernodes that are part of the same component according to a certain contraction scheme. For instance, a componentSet could be representing a clique or a circuit, depending on which contraction scheme created it.

Note that, in general, a supernode can be part of multiple ComponentSets in some contraction schemes, while in others, like the SCCs contraction scheme, a supernode can only be part of one ComponentSet at a time. In any case, nodes in the same supernode must share the same component sets where they are part of according to the contraction scheme at the immediate upper level. The set of component sets associated to a supernode is, therefore, the set of component sets that each of its nodes share.

Parameters:

key (Any) –
supernodes (Set[Supernode]) –

key¶

the unique identifier of the component set in its contraction scheme

Type:: Any

Examples

A ComponentSet can be treated as a set of supernodes, for instance:

from multilevelgraphs import ComponentSet, Supernode
c1 = ComponentSet(1, {Supernode(1), Supernode(2)})
c1.add(Supernode(3))
for supernode in c1:
    print(supernode)

A ComponentSet can also have attributes that may be calculated during the contraction process:

from multilevelgraphs import MultilevelGraph, SCCsContractionScheme
import networkx as nx
nx_graph = nx.DiGraph()
nx_graph.add_edges_from([(1, 2, {'weight': 25}), (2, 3, {'weight': 20}), (3, 1, {'weight': 10})])
scheme = SCCsContractionScheme(c_set_attr_function=lambda c_set: sum([node['weight'] for node in c_set]))
ml_graph = MultilevelGraph(nx_graph, [scheme])
c1 = next(iter(ml_graph.get_component_sets(1)))
c1['weight'] # 55
c1['double_wight'] = c1['weight'] * 2

__init__(key, supernodes=None, **attr)[source]¶

Initialize a ComponentSet with a key, a set of supernodes and optional attributes.

Parameters:

key (Any) – the unique identifier of the component set in its contraction scheme
supernodes (Set[Supernode] | None) – the supernodes that are part of the component set
attr – the key-values pairs attributes of the component set

add(value)[source]¶

copy()[source]¶

Return type:: ComponentSet

deepcopy(supernodes_dict)[source]¶

Returns a deep copy of the component set where the supernodes are replaced by the supernodes in the given dictionary having the same keys.

Parameters:: supernodes_dict (Dict[Any, Supernode]) – the dictionary of supernodes to replace the supernodes in the component set
Returns:: a deep copy of the component set with the new supernodes
Return type:: ComponentSet

discard(value)[source]¶

update(**attr)[source]¶

Class: UpdateQuadruple¶

class UpdateQuadruple(v_plus=None, v_minus=None, e_plus=None, e_minus=None)[source]¶

Bases: object

A quadruple of sets of supernodes and superedges that represent an update in the decontractible graph of a contraction scheme and tracks the changes in the supernodes and superedges of the decontractible graph that are not yet considered by higher level contraction schemes.

The sets are:

v_plus : the supernodes tha have been added to the decontractible graph
v_minus : the supernodes that have been removed from the decontractible graph
e_plus : the superedges that have been added to the decontractible graph
e_minus : the superedges that have been removed from the decontractible graph

The update quadruple is managed in order to maintain itself minimal, that is, v_plus and v_minus are disjoint and e_plus and e_minus are disjoint.

Parameters:

v_plus (Iterable[Supernode]) –
v_minus (Iterable[Supernode]) –
e_plus (Iterable[Superedge]) –
e_minus (Iterable[Superedge]) –

__init__(v_plus=None, v_minus=None, e_plus=None, e_minus=None)[source]¶

Parameters:

v_plus (Iterable[Supernode] | None) –
v_minus (Iterable[Supernode] | None) –
e_plus (Iterable[Superedge] | None) –
e_minus (Iterable[Superedge] | None) –

add_e_minus(superedge)[source]¶

Adds a superedge to the set of superedges that have been removed. If the superedge is in the set of superedges that have been added, it is removed from that set instead.

Parameters:: superedge (Superedge) – the superedge to add

add_e_plus(superedge)[source]¶

Adds a superedge to the set of superedges that have been added. If the superedge is in the set of superedges that have been removed, it is removed from that set instead.

Parameters:: superedge (Superedge) – the superedge to add

add_v_minus(supernode)[source]¶

Adds a supernode to the set of supernodes that have been removed. If the supernode is in the set of supernodes that have been added, it is removed from that set instead.

Parameters:: supernode (Supernode) – the supernode to add

add_v_plus(supernode)[source]¶

Adds a supernode to the set of supernodes that have been added. If the supernode is in the set of supernodes that have been removed, it is removed from that set instead.

Parameters:: supernode (Supernode) – the supernode to add

clear()[source]¶: Clears the update quadruple, removing all supernodes and superedges from its four sets.

property e_minus: Set[Superedge]¶: Returns a copy of the set of superedges that have been removed. :return: a copy of the set of superedges that have been removed

property e_plus: Set[Superedge]¶: Returns a copy of the set of superedges that have been added. :return: a copy of the set of superedges that have been added

has_updates()[source]¶

Returns True if there are any supernodes or superedges in any of the sets of the update quadruple, False otherwise. :return: True if there are any supernodes or superedges in the update quadruple

Return type:: bool

property v_minus: Set[Supernode]¶: Returns a copy of the set of supernodes that have been removed. :return: a copy of the set of supernodes that have been removed

property v_plus: Set[Supernode]¶: Returns a copy of the set of supernodes that have been added. :return: a copy of the set of supernodes that have been added

Package: contraction_schemes¶

Abstract Class: ContractionScheme¶

Abstract Class: EdgeBasedContractionScheme¶

Abstract Class: DecontractionEdgeBasedContractionScheme¶

Class: CompTable¶

Class: ComponentSet¶

Class: UpdateQuadruple¶

MultiLevelGraphs

Navigation

Related Topics