NAC Colorings

Module related to the NAC-coloring search.

This implementation is based on https://github.com/Lastaapps/bc_thesis_code. Before you try to optimize this code, please check out the original implementation first.

algorithms

This module implements various approaches for NAC-coloring search.

Made in a generic way to also support Cartesian NAC-coloring in the future.

pyrigi.graph._flexibility.nac.algorithms.NAC_colorings_cycles(graph, classes_ids, class_to_edges, is_NAC_coloring_routine)

Implementation of the naive algorithm improved by using cycles.

Parameters:

• graph (Graph) – The graph to search on.

• classes_ids (list[int]) – List of classes IDs.

• class_to_edges (list[list[tuple[int, int]]]) – Mapping from class ID to its edges.

• is_NAC_coloring_routine (Callable[[Graph, tuple[Collection[tuple[int, int]], Collection[tuple[int, int]]]], bool]) – Used to check if the coloring is NAC-coloring or Cartesian NAC-coloring.

Return type:

Iterable[tuple[Collection[tuple[int, int]], Collection[tuple[int, int]]]]

pyrigi.graph._flexibility.nac.algorithms.NAC_colorings_naive(graph, class_ids, class_to_edges, is_NAC_coloring_routine)

Naive implementation of the basic NAC-coloring search algorithm.

Parameters:

• graph (Graph) – The graph to search on.

• class_ids (list[int]) – List of classes IDs.

• class_to_edges (list[list[tuple[int, int]]]) – Mapping from class ID to its edges.

• is_NAC_coloring_routine (Callable[[Graph, tuple[Collection[tuple[int, int]], Collection[tuple[int, int]]]], bool]) – Used to check if the coloring is NAC-coloring or Cartesian NAC-coloring.

Yields:

All colorings satisfying `is_NAC_coloring_routine.`

Return type:

Iterable[tuple[Collection[tuple[int, int]], Collection[tuple[int, int]]]]

pyrigi.graph._flexibility.nac.algorithms.NAC_colorings_subgraphs(graph, class_ids, class_to_edges, is_NAC_coloring_routine, seed, split_strategy='neighbors', merge_strategy='linear', preferred_chunk_size=5)

Return NAC-colorings by splitting to subgraphs.

This version of the algorithm splits the graph into subgraphs and finds NAC-colorings for each of them. The subgraphs are then merged, and new colorings are reevaluated until we reach the original graph again.

Parameters:

• graph (Graph) – The original graph.

• class_ids (list[int]) – List of classes IDs.

• class_to_edges (list[list[tuple[int, int]]]) – List of edges for each class.

• is_NAC_coloring_routine (Callable[[Graph, tuple[Collection[tuple[int, int]], Collection[tuple[int, int]]]], bool]) – The function to check if a coloring is a NAC-coloring.

• seed (int) – Random seed used by some strategies.

• split_strategy (Literal['none', 'neighbors', 'neighbors_degree']) – The strategy to split the graph into subgraphs.

• merge_strategy (Literal['linear', 'shared_vertices']) – The strategy to merge the subgraphs.

• preferred_chunk_size (int) – The preferred size of the chunks.

Return type:

Iterable[tuple[Collection[tuple[int, int]], Collection[tuple[int, int]]]]

check

The module checks if the given coloring is a NAC-coloring. The algorithm is based on Lemma 6.

pyrigi.graph._flexibility.nac.check.is_NAC_coloring(graph, coloring)

Check if the coloring given is a NAC-coloring by using algorithm described in Lemma 6.

The algorithm checks if all the edges are in the same component. This is an internal implementation, so some properties like injectivity are not checked for performance reasons - we only search for the cycles.

Parameters:

• graph (Graph)

• coloring (tuple[Collection[tuple[int, int]], Collection[tuple[int, int]]] | dict[str, Collection[tuple[int, int]]]) – The coloring to check if it is a NAC coloring.

Return type:

bool

core

The module contains functions for converting from and to NAC-mono classes represented by bit masks to sets of edges representing a NAC-coloring.

pyrigi.graph._flexibility.nac.core.IntEdge

Represents a NAC-coloring. Meant for internal use only as frozenset() should be exposed to the user instead. Tuple is faster for internal use.

alias of tuple[int, int]

pyrigi.graph._flexibility.nac.core.NAC_colorings_with_non_surjective(graph, colorings)

Add monochromatic colorings to the iterator of NAC-colorings.

Return type:

Iterable[tuple[Collection[tuple[int, int]], Collection[tuple[int, int]]]]

Parameters:

• graph (Graph)

• colorings (Iterable[tuple[Collection[tuple[int, int]], Collection[tuple[int, int]]]])

class pyrigi.graph._flexibility.nac.core.SubgraphColorings(colorings, subgraph_mask)

Bases: NamedTuple

Represents a subgraph and all its NAC-coloring colorings.

Parameters:

• colorings (Iterable[int])

• subgraph_mask (int)

colorings: Iterable[int]

Alias for field number 0

subgraph_mask: int

Alias for field number 1

pyrigi.graph._flexibility.nac.core.can_have_NAC_coloring(graph)

Return if the graph may have a NAC-coloring.

Use equivalence from [GLS19, Thm 3.1] that a graph has a NAC-colorings if and only if it has a flexible realization. For a flexible realization, the upper bound on the number of edges in a graph is known [GLS19, Thm 4.7].

Definitions

• NAC-coloring

• Flexibility

• Realization

Parameters:

graph (Graph) – A connected graph with at least one edge.

Return type:

bool

pyrigi.graph._flexibility.nac.core.coloring_from_mask(ordered_class_ids, class_to_edges, mask, allow_mask=None)

Convert a mask representing a red-blue edge coloring.

Parameters:

• ordered_class_ids (list[int]) – List of class IDs that the mask’s bits point into.

• class_to_edges (list[list[set[Hashable] | tuple[Hashable, Hashable] | list[Hashable]]]) – Mapping from class ID to its edges.

• mask (int) – Bit mask pointing into ordered_class_ids, 1 means the first and 0 the second set of edges.

• allow_mask (int | None) – Mask allowing only some class. Used for subgraphs.

Return type:

tuple[Collection[tuple[int, int]], Collection[tuple[int, int]]]

pyrigi.graph._flexibility.nac.core.create_bitmask_for_class_graph_cycle(graph, class_to_edges, cycle, local_ordered_class_ids=None)

Create a bit mask (template) matching classes in the cycle and a mask matching classes of the cycle such that if they are the only class with the other color, an almost cycle exists.

Tuple (template, valid) is returned: template is a bit mask representing the cycle, and valid is a bit mask representing classes of the cycle such that if they are the only class with the other color, an almost cycle exists.

Parameters:

• graph (Graph)

• class_to_edges (Callable[[int], list[tuple[int, int]]]) – Mapping from class to its edges. The method __getitem__() can also be passed.

• cycle (tuple[int, ...]) – A cycle in the class graph.

• local_ordered_class_ids (set[int] | None) – It can be used if the given graph is a subgraph of the original graph and class_to_edges also represents the original graph.

Return type:

tuple[int, int]

pyrigi.graph._flexibility.nac.core.mask_matches_templates(templates, mask, subgraph_mask)

Check the given coloring represented by mask for any almost cycle that can be found by the given cycle templates.

Parameters:

• templates (list[tuple[int, int]]) – List of cycle templates and allow masks generated by create_bitmask_for_class_graph_cycle().

• mask (int) – Bit mask representing the coloring.

• subgraph_mask (int) – Bit mask representing the subgraph.

Return type:

Return `True if an almost cycle was found.`

pyrigi.graph._flexibility.nac.core.mask_to_vertices(ordered_class_ids, class_to_edges, subgraph_mask)

Return vertices in the original graph that are incident to edges in classes of the subgraph.

Return type:

set[int]

Parameters:

• ordered_class_ids (list[int])

• class_to_edges (list[list[tuple[int, int]]])

• subgraph_mask (int)

pyrigi.graph._flexibility.nac.core.vertices_of_classes(class_ids, class_to_edges)

Obtain vertices corresponding to edges of the given NAC-mono classes.

Return type:

set[int]

Parameters:

• class_ids (list[int])

• class_to_edges (list[list[tuple[int, int]]])

cycle_detection

This module contains code related to finding cycles that should correspond to NAC-mono classes.

pyrigi.graph._flexibility.nac.cycle_detection.find_cycles(graph, subgraph_class_IDs, class_to_edges, per_class_limit=2)

For each edge, find all the cycles among NAC-mono classes of length at most five (length is the number of classes it spans).

Not all the returned cycles are guaranteed to be actual cycles as this may create cycles that enter and exit a class at the same vertex.

Parameters:

• graph (Graph) – Input graph.

• subgraph_class_IDs (Collection[int]) – Classes of the subgraph.

• class_to_edges (Collection[Collection[tuple[int, int]]]) – A list of edges for each class.

• per_class_limit (int) – The maximum number of a cycle to be returned per class.

Return type:

set[tuple[int, ...]]

existence

This module checks whether a graph can have a NAC-colorings.

pyrigi.graph._flexibility.nac.existence.has_NAC_coloring_checks(graph)

Return whether the graph has a NAC-coloring.

Implementation of has_NAC_coloring, but without falling back to single_NAC_coloring. May be used before an exhaustive search that would not find anything anyway.

Definitions

• NAC-coloring

Parameters:

graph (Graph) – The graph to check.

Return type:

bool | None

facade

pyrigi.graph._flexibility.nac.facade.NAC_colorings(graph, algorithm='default', use_cycles_optimization=True, use_blocks_decomposition=True, mono_class_type='triangle-extended', seed=42)

Find all NAC-colorings of the graph.

Definitions

• NAC-coloring

Parameters:

• graph (Graph)

• algorithm (str) – The algorithm to use. The options are "naive" for the naive approach and "subgraphs" for the subgraphs decomposition approach, see Computations. Strategies can be specified for the subgraphs algorithm as follows: "subgraphs-<split_strategy>-<merging_strategy>-<subgraphs_size>". Split strategies are none, neighbors, and neighbors_degree, merging strategies are linear and shared_vertices. The default strategy is "subgraphs-neighbors-linear-5".

• use_cycles_optimization (bool) – Use cycles optimization for the given algorithm. This is always enabled for subgraphs strategies.

• use_blocks_decomposition (bool) – If enabled, the graph is first decomposed into blocks, and NAC-colorings are found for each block (2-vertex connected component) separately and then combined.

• mono_class_type (str) – The type of NAC-mono classes to use. The options are "edges" (each edge is a NAC-mono class), "triangle" for triangle-connected components, or "triangle-extended" (default) for triangle-extended classes.

• seed (int | None) – The seed to use for randomization.

Return type:

Iterable[tuple[list[set[Hashable] | tuple[Hashable, Hashable] | list[Hashable]], list[set[Hashable] | tuple[Hashable, Hashable] | list[Hashable]]]]

pyrigi.graph._flexibility.nac.facade.has_NAC_coloring(graph, algorithm='default', use_cycles_optimization=True, mono_class_type='triangle-extended', seed=42)

Return if the graph has a NAC-coloring.

Same as single_NAC_coloring(), but no certificate of existence is provided.

See NAC_colorings() for parameter descriptions.

Return type:

bool

Parameters:

• graph (Graph)

• algorithm (str)

• use_cycles_optimization (bool)

• mono_class_type (str)

• seed (int | None)

Definitions

• NAC-coloring

pyrigi.graph._flexibility.nac.facade.single_NAC_coloring(graph, algorithm='default', use_cycles_optimization=True, mono_class_type='triangle-extended', seed=42)

Return a single NAC-coloring.

If no NAC-coloring exists, None is returned. Some polynomial time checks are run. If they fail, an exhaustive search is run.

See NAC_colorings() for parameter descriptions.

Return type:

tuple[list[set[Hashable] | tuple[Hashable, Hashable] | list[Hashable]], list[set[Hashable] | tuple[Hashable, Hashable] | list[Hashable]]] | None

Parameters:

• graph (Graph)

• algorithm (str)

• use_cycles_optimization (bool)

• mono_class_type (str)

• seed (int | None)

Definitions

• NAC-coloring

mono_classes

This module is responsible for finding triangle-connected components and NAC-mono classes.

class pyrigi.graph._flexibility.nac.mono_classes.MonoClassType(value)

Bases: Enum

Represents approaches for finding NAC-mono classes of different types - single edges, triangle-connected components, and triangle-extended classes.

Suggested Improvement

Make from_string more fancy.

EDGES = 'edges'

Corresponds to triangle-connected components.

TRI_CONNECTED = 'triangle'

Corresponds to hattriangle-extended classes.

TRI_EXTENDED = 'triangle-extended'

static from_string(class_name)

Return type:

MonoClassType

Parameters:

class_name (str)

pyrigi.graph._flexibility.nac.mono_classes.find_mono_classes(graph, class_type=MonoClassType.TRI_EXTENDED)

Find NAC-mono classes based on the type given.

First, all the classes of triangle equivalence are found. Then these are optionally extended to larger NAC-mono classes as described in [LL24].

An ID of a NAC-mono class corresponds to its index in a list of all NAC-mono classes. A mapping from edges to their class ID is returned together with a list of NAC-mono classes where the index corresponds to the class ID.

Parameters:

• class_type (MonoClassType) – Type of NAC-mono classes

• graph (Graph)

Return type:

tuple[dict[set[Hashable] | tuple[Hashable, Hashable] | list[Hashable], int], list[list[set[Hashable] | tuple[Hashable, Hashable] | list[Hashable]]]]

search

This module is the starting point for the NAC-colorings search. The main entry point is the function pyrigi.graph._flexibility.nac.search.NAC_colorings_impl(). The given graph is relabeled if the vertices are not integers from 0 to N-1.

Then the algorithm argument is parsed and either the Naive algorithm (_NAC_colorings_naive) or the subgraph decomposition algorithm (_NAC_colorings_subgraphs) is chosen. The strategies are then chosen depending on the given parameters.

The main pair of the search uses only a bit mask representing the coloring and converts it back to NAC-coloring once a check is needed.

pyrigi.graph._flexibility.nac.search.NAC_colorings_impl(graph, algorithm, use_cycles_optimization, use_blocks_decomposition, mono_class_type, seed)

Find all NAC-colorings of the given graph.

Parameters:

• algorithm (Union[str, Literal['naive', 'subgraphs']]) – The algorithm to use. The options are "naive" for the naive approach and "subgraphs" for the subgraphs decomposition approach. Strategies can be specified for the subgraphs algorithm as follows: "subgraphs-<split_strategy>-<merging_strategy>-<subgraphs_size>". Split strategies are none, neighbors, and neighbors_degree, merging strategies are linear and shared_vertices. See docs for further details.

• use_cycles_optimization (bool) – Use cycles optimization for the given algorithm. This is always enabled for subgraphs strategies.

• use_blocks_decomposition (bool) – If enabled, graph is first decomposed into blocks, and NAC-colorings are found for each block (2-vertex connected component) separately and then combined.

• mono_class_type (MonoClassType) – The type of NAC-mono classes to use.

• seed (int | None) – The seed to use for randomization.

• graph (Graph)

Yields:

All :prf:ref:`NAC-colorings for a given graph.`

Return type:

Iterable[tuple[Collection[tuple[int, int]], Collection[tuple[int, int]]]]

Suggested improvements

Allow running polynomial checks for NAC-coloring existence on startup. Reference subgraphs algorithm. Evaluate if the copy is needed at the beginning of run function.

single

This module holds functions related to whether a graph can have a NAC-coloring.

pyrigi.graph._flexibility.nac.single.has_NAC_coloring_impl(graph, algorithm, use_cycles_optimization, mono_class_type, seed)

Return whether the graph has a NAC-coloring.

Same as pyrigi.graph._flexibility.nac.single.single_NAC_coloring_impl(), but the certificate may not be created. Polynomial time checks are used.

Definitions

• NAC-coloring

Parameters:

• graph (Graph) – The graph to check.

• algorithm (str | Literal['naive', 'subgraphs'])

• use_cycles_optimization (bool)

• mono_class_type (MonoClassType)

• seed (int | None)

Return type:

bool

pyrigi.graph._flexibility.nac.single.single_NAC_coloring_impl(graph, algorithm, use_cycles_optimization, mono_class_type, seed, _is_first_check=True)

Find a single NAC-coloring if it exists.

Polynomial time existence checks are run to determine whether a NAC-coloring exists. If they fail, an exhaustive search is run and halted after some NAC-coloring is found.

Definitions

• NAC-coloring

Parameters:

• algorithm (Union[str, Literal['naive', 'subgraphs']]) – The algorithm used in case we need to fall back to exhaustive search.

• use_cycles_optimization (bool) – Use cycles optimization for the given algorithm. This is always enabled for subgraphs strategies.

• mono_class_type (MonoClassType) – The type of NAC-mono classes to use. The options are "edges" (each edge is a NAC-mono class), "triangle" for triangle-connected components, or "triangle-extended" (default) for

• seed (int | None) – The seed to use in case we need to fall back to exhaustive search.

• _is_first_check (bool) – Internal parameter, do not change! Skips some checks already performed in has_NAC_coloring.

• graph (Graph)

Return type:

tuple[Collection[tuple[int, int]], Collection[tuple[int, int]]] | None

strategies

pyrigi.graph._flexibility.nac.strategies.linear(colorings_merge_wrapper, all_epochs)

Merge all subgraphs linearly.

Return type:

list[SubgraphColorings]

Parameters:

• colorings_merge_wrapper (Callable[[SubgraphColorings, SubgraphColorings], SubgraphColorings])

• all_epochs (list[SubgraphColorings])

pyrigi.graph._flexibility.nac.strategies.shared_vertices(class_to_edges, ordered_class_ids, colorings_merge_wrapper, all_epochs)

Merge subgraphs by preferring pairs where with more shared vertices

Return type:

list[SubgraphColorings]

Parameters:

• class_to_edges (list[list[tuple[int, int]]])

• ordered_class_ids (list[int])

• colorings_merge_wrapper (Callable[[SubgraphColorings, SubgraphColorings], SubgraphColorings])

• all_epochs (list[SubgraphColorings])

pyrigi.graph._flexibility.nac.strategies.subgraphs_strategy_neighbors(graph, class_ids, class_to_edges, chunk_sizes, use_degree, seed)

Split graph into subgraphs by neighbors. For algorithm description, see documentation.

Parameters:

• graph (Graph) – The original graph.

• class_ids (list[int]) – List of available classes IDs.

• class_to_edges (list[list[tuple[int, int]]]) – List of edges for each class.

• chunk_sizes (Sequence[int]) – List of chunk sizes.

• seed (int | None) – Random seed used to split equal decisions.

• use_degree (bool)

Return type:

list[int]