core package

Subpackages

Submodules

core.connect_cycle_cover module

core.cycle_cover module

core.cycle_cover.add_cycle_in_order(cycle_cover, cycle, cycle_end)[source]

Adds a cycle to the cycle cover in order. The order is based on the last two elements of the cycle. The last element should be the smallest and then the second to last element should be the smallest.

Parameters:

  • cycle_cover (list[list[tuple[int, ...]]]) – The cycle cover to add the cycle to. The depth of the list is undefined and depends on the cycle cover.

  • cycle (list[list[tuple[int, ...]]]) – The cycle to add.

  • cycle_end (tuple[int, int]) – The last two elements of the cycle. The last element should be the largest.

Returns:

The cycle cover with the added cycle.

Return type:

list[list[tuple[int, …]]]

Raises:

AssertionError – If the cycle is empty.

core.cycle_cover.generate_all_even_cycle_cover(sig, naive_glue=False)[source]

Generates the disjoint cycle cover on the non-stutter permutations for the given signature sig according to the Theorem by Verhoeff.

Theorem: When the arity is at least 3 and at most one k i is odd, the neighbor-swap graph of non-stutter permutations admits a disjoint cycle cover, that is, a set of vertex-disjoint cycles that visit all permutations exactly once.

This handles the case where all elements are even. This is done by fixing the trailing two elements and then generating the cycle cover for the remaining signature.

Parameters:

  • sig (tuple[int, ...]) – The signature of the permutations. Must have at least one element.

  • naive_glue (bool, optional) – If the disjoint cycle cover should be naively glued. Defaults to False.

Returns:

The cycle cover for the given signature sig.

Every list of tuples is a cycle in the cycle cover. The tuples are permutations. The lists do not have a defined depth since they can consist of cycle covers themselves. But the depth is at least 2.

Return type:

list[list[tuple[int, …]]]

core.cycle_cover.odd_odd_1_cycle(sig)[source]

Generates a cycle for the odd-odd-1 case. It uses the waveTopRowOddOddOne function to transform the odd-odd subcase into a cycle.

Parameters:

sig (tuple[int, ...]) – The signature of the permutations. Must be of structure odd-odd-1.

Returns:

The cycle for the odd-odd-1 case.

Return type:

list[tuple[int, …]]

core.cycle_cover.even_2_1_cycle(k)[source]

Generates a Hamiltonian cycle for the even-2-1 case.

Parameters:

k (int) – Value for even or k_0.

Returns:

The cycle for the even-odd-1 case.

Return type:

list[tuple[int, …]]

core.cycle_cover.even_odd_1_cycle(sig, distinct_ends=True)[source]

Generates a cycle for the even-odd-1 case. This is a cycle that contains two parallel cycles that are isomorphic to each other.

Parameters:

  • sig (tuple[int, ...]) – The signature of the permutations. Must be of structure even-odd-1 or odd-even-1.

  • distinct_ends (bool, optional) – If the ends of the cutnodes should be distinct. Defaults to True.

Returns:

The cycle for the even-odd-1 case.

Return type:

list[tuple[int, …]]

core.cycle_cover.even_1_1_1_cycle(sig)[source]

Generates a cycle for the even-1-1-1 case. This is a cycle that contains three paths that are glued to one Hamiltonian cycle in two parts. First two nodes are removed from each path to be added to the Hamiltonian cycle. The Hamiltonian cycle is then glued to the rest of the paths (which is a cycle).

Parameters:

sig (tuple[int, ...]) – The signature of the permutations. Must be of structure even-1-1-1.

Returns:

The Hamiltonian cycle for the even-1-1-1 case.

Return type:

list[tuple[int, …]]

core.cycle_cover.even_2_1_1_cycle(sig)[source]

Generates a Hamiltonian cycle for the (even, 2, 1, 1) signature. This is a cycle has two subgraphs that only have a Hamiltonian path.

Parameters:

sig (tuple[int, ...]) – The signature of the permutations. Must be of structure (even, 2, 1, 1).

Returns:

The Hamiltonian cycle for the (even, 2, 1, 1) signature.

Return type:

list[tuple[int, …]]

core.cycle_cover.two_odd_rest_even_cycle_cover(sig, naive_glue=False)[source]

Generates the disjoint cycle cover on the permutations for the given signature sig. This handles the case where there are two odd elements and the rest are even. This is done by fixing the trailing element or trailing two elements if the trailing element is odd to incorporate stutter permutations. For more explanation, see the master thesis.

Parameters:

  • sig (tuple[int, ...]) – The signature of the permutations. Must have at least one element.

  • naive_glue (bool, optional) – If the naive glue method should be used. Defaults to False.

Returns:

The disjoint cycle cover for the given signature sig. The first list contains the disjoint cycle cover for the permutations where the last element is even. The second list contains the disjoint cycle cover for the permutations where the last element is odd.

Return type:

tuple[list[list[tuple[int, …]]], list[list[tuple[int, …]]]]

core.cycle_cover.two_odd_rest_even_cycle(sig, naive_glue=False)[source]

Generates a Hamiltonian cycle for the given signature sig where there are two odd elements and the rest are even. This uses the disjoint cycle cover generated by the two_odd_rest_even_cycle_cover function to generate the Hamiltonian cycle. The individual cycles are connected by cross edges to form the Hamiltonian cycle.

Parameters:

  • sig (tuple[int, ...]) – The signature of the permutations. Must have two odd occurring colors.

  • naive_glue (bool, optional) – If the naive glue method should be used. Defaults to False.

Returns:

The Hamiltonian cycle for the given signature sig.

Return type:

list[tuple[int, …]]

core.cycle_cover.generate_cycle_cover(sig, naive_glue=False)[source]

Generates the disjoint cycle cover on the non-stutter permutations for the given signature sig according to the Theorem by Verhoeff.

Theorem: When the arity is at least 3 and at most one k i is odd, the neighbor-swap graph of non-stutter permutations admits a disjoint cycle cover, that is, a set of vertex-disjoint cycles that visit all permutations exactly once.

This is split into several cases below. Note that Even-1-1 and Odd-1-1 form a cycle together:

  • Arity 1: The cycle is a single node of 0’s.

  • Arity 2: The cycle is a single cycle of 0’s and 1’s. Using Verhoeff’s binary theorem.

  • Even-1-1: A path from c = 1 2 0^k0 to d = 0 2 1 0^(k0-1). Does not contain a cycle.

  • Odd-1-1: The cycle from 1 0^k0 2 to 0 1 0^(k0-1) 2.

  • Odd-2-1: A path from a = 1 2 0^{k0} 1 to b = 0 2 1 0^{k0-1} 1. (Also contains a cycle by Stachowiak’s theorem)

  • Even-2-1: A cycle formed by the path from Even-1-1 and Odd-2-1.

  • All-but-one-even: Forms cycles by fixing the trailing element. (uses Stachowiak’s Lemma 11 for the two-or-more-odd case)

  • All-even: Forms cycles by fixing the trailing two elements.

  • Two-or-more-odd: Stachowiak’s theorem gives us a cycle on this graph.

Parameters:

  • sig (tuple[int, ...]) – The signature of the permutations. Must have at least one element.

  • naive_glue (bool, optional) – Whether to use naive gluing or not. Defaults to False.

Returns:

The cycle cover for the given signature sig.

Every list of tuples is a cycle in the cycle cover. The tuples are permutations. The lists do not have a defined depth since they can consist of cycle covers themselves. But the depth is at least 2.

Return type:

list[list[tuple[int, …]]]

Raises:

ValueError – If the signature is empty.

References

  • Tom Verhoeff. The spurs of D. H. Lehmer: Hamiltonian paths in neighbor-swap graphs of permutations. Designs, Codes, and Cryptography, 84(1-2):295-310, 7 2017.

  • Stachowiak G. Hamilton Paths in Graphs of Linear Extensions for Unions of Posets. Technical report, 1992

core.cycle_cover.get_subsigs_and_cross_edges(sig, naive_glue=False)[source]

Generates the subsignatures, cross edges, and trailing colors for the given signature sig. This is used to visualize the cycle cover for the given signature.

Parameters:

  • sig (tuple[int, ...]) – The signature of the permutations. Must have at least one element.

  • naive_glue (bool, optional) – Whether to use naive gluing or not. Defaults to False.

Returns:

The subsignatures, cross edges, and colors trailing each subsignature for the given signature sig.

Return type:

tuple[list[tuple[int, …]], list[tuple[tuple[int, …], tuple[int, …]]], list[tuple[int, …]]]

core.cycle_cover.get_connected_cycle_cover(sig, naive_glue=False)[source]

Computes the a cycle on the non-stutter permutations for a given signature. If the signature is odd-2-1, the connected cycle cover is computed using lemma 11 by Stachowiak. Otherwise Verhoeff’s cycle cover theorem is used to generate the cycle cover and that is then connected using the connect_cycle_cover function.

Parameters:

  • sig (tuple[int, ...]) – The signature for which the cycle on non-stutter permutations needs to be computed.

  • naive_glue (bool, optional) – If the naive gluing method should be used. Defaults to False.

Returns:

The connected cycle cover as a list of tuples, where each tuple represents a permutation.

Return type:

list[tuple[int, …]]

Raises:

AssertionError – If the generated cycle cover by Verhoeff’s theorem is empty.

References

  • Tom Verhoeff. The spurs of D. H. Lehmer: Hamiltonian paths in neighbor-swap graphs of permutations. Designs, Codes, and Cryptography, 84(1-2):295-310, 7 2017.

  • Stachowiak G. Hamilton Paths in Graphs of Linear Extensions for Unions of Posets. Technical report, 1992

core.lehmer_paths module

core.lehmer_paths.order_path_to_stutter_start(path, stutters)[source]

If the path is a cycle; order the cycle to make the start node adjacent to a stutter. If the path is not a cycle; just return the original path.

Parameters:

  • path (list[tuple[int, ...]]) – The path to order.

  • stutters (list[tuple[int, ...]]) – The stutters to incorporate.

Returns:

The ordered path.

Return type:

list[tuple[int, …]]

core.lehmer_paths.incorporate_stutters(sig)[source]

Creates a cycle/path on the non-stutter permutations and then incorporates the stutters to create a Lehmer cycle/path. See the Notes for which signatures result in a path instead of a cycle.

Parameters:

sig (tuple[int, ...]) – The input signature.

Returns:

The list of tuples representing the valid cycle/path on non-stutter permutations with the stutters incorporated.

Return type:

list[tuple[int, …]]

Note

Some signatures do not result in a cycle but in a path, the signatures that result in a path are:

  • Even-1 or odd-1 (Linear neighbor-swap graphs)

  • Odd-odd

  • Odd-even / even-odd

  • Even-1-1

core.permute module

core.permute.main()[source]

Helper tool to find Lehmer paths in neighbor-swap graphs.

This function takes command line arguments to perform various operations on a given permutation signature. It has various options:

  • Visualize the NetworkX neighbor swap graph (–graph)

  • Compute permutations using Rivertz’s algorithm (–rivertz)

  • Find paths using Lehmer’s algorithm (–lehmer). Here we can also automatically recognize stutters as spurs (–auto-spur)

  • Color the nodes in the Lehmer Path (–color), note that –graph must be enabled. This automatiaclly enables –lehmer.

  • Enable verbose mode (–verbose), here extra information will be printed in the console.

The input permutation signature is a comma-separated list of integers. (e.g. 4,2,1)

Command Line Arguments:

  • -s, --signature: Input permutation signature (comma separated) (required)

  • -v, --verbose: Enable verbose mode

  • -l, --lehmer: Compute the path using Lehmer’s algorithm

  • -a, --auto-spur: Automatically recognize stutters as spurs in Lehmer’s algorithm

  • -g, --graph: Show the NetworkX neighbor swap graph

  • -c, --color: Color the nodes in the Hamiltonian Path based on Lehmer’s algorithm

  • -r, --rivertz: Compute the permutations with Rivertz’s algorithm

Returns:

None

Raises:

ValueError – If the input signature is invalid

core.stachowiak module

core.stachowiak.main()[source]

This script uses Stachowiak’s theorems to find Hamiltonian cycles in neighbor-swap graphs.

Parameters:

  • -s – Input permutation signature (comma separated, without spaces)

  • --signature – Input permutation signature (comma separated, without spaces)

  • -v – Enable verbose mode, False by default

  • --verbose – Enable verbose mode, False by default

  • -p – Show the even and odd counts of all permutations

  • --parities – Show the even and odd counts of all permutations

Returns:

Prints whether the result is a Hamiltonian path or cycle in the neighbor-swap graph. If verbose mode is enabled, it also prints the resulting path.

Raises:

  • ValueError – If the signature is empty.

  • ValueError – If the signature contains negative values.

References

  • Stachowiak G. Hamilton Paths in Graphs of Linear Extensions for Unions of Posets. Technical report, 1992

core.stachowiak.lemma2_cycle(chain_p, case_2_1=True)[source]

This function generates the cycles of Lemma 2. If the length of the chain_p is even the last two nodes are discarded as in the lemma. Defaults to case 2.1 of Lemma 2. If the case_2_1 variable is set to False, the cycle will be as in case 2.2. The discarded nodes are:

  • d_p = (01 l^p, 10 l^p) for case 2.1

  • d_p’ = (l^p 01, l^p 10) for case 2.2

Parameters:

  • chain_p (tuple[int, ...]) – The chain of p elements in the lemma

  • case_2_1 (bool, optional) –

    Whether the case is 2.1 or 2.2. Defaults to True.

    • True ==> Case 2.1 with all d_i paths.

    • False ==> Case 2.2 with all d_i’ paths.

Returns:

The cycle of all d_i or d_i’ paths. If the length of chain_p is even, d_p or d_p’ is discarded respectively to the input for case_2_1.

Return type:

list[tuple[int, …]]

core.stachowiak.lemma2_extended_path(chain_p, case_2_1=True)[source]

Extends the cycle of Lemma 2 with the last two elements in case chain_p is even. If the length of chain_p is odd, then the cycle is returned. Defaults to case 2.1 of Lemma 2. If the case_2_1 variable is set to False, the path will be as in case 2.2.

If chain_p is even, the two nodes which are appended to the path are;

  • d_p = (01 l^p, 10 l^p) for case 2.1

  • d_p’ = (l^p 01, l^p 10) for case 2.2

Parameters:

  • chain_p (tuple[int, ...]) – The chain of p elements in the lemma.

  • case_2_1 (bool, optional) –

    Whether the case is 2.1 or 2.2. Defaults to True.

    • True ==> Case 2.1 with all d_i paths.

    • False ==> Case 2.2 with all d_i’ paths.

Returns:

The cycle of all d_i or d_i’ paths extended with the two nodes that are left out if the length of chain_p is even.

  • d_i=[0l^{p-i} 1 l^i, l0l^{p-i-1} 1 l^i, …, l^{p-i} 01 l^i, l^{p-i} 10 l^i, …, 1 l^{p-i} 0 l^i]

  • d_i’=[l^i 1 l^{p-i} 0, l^i 1 l^{p-i-1} 0 l, …, l^{i} 10 l^{p-i}, l^i 01 l^{p-i}, …, l^i 0 l^{p-i} 1]

Return type:

list[tuple[int, …]]

core.stachowiak.lemma7(sig)[source]

Computes Lemma 7 by Stachowiak: The graph G=GE( (0|1) (k^q|l^p) ) contains a Hamilton cycle for every p, q > 0.

Parameters:

sig (tuple[int, ...]) – The signature of the graph in the form (1, 1, q, p). The elements are of colors 0, 1, 2, 3 (so color 2 occurs q times and 3 occurs p times).

Returns:

A Hamiltonian cycle of the form (0|1) (k^q|l^p)

Return type:

list[tuple[int, …]]

core.stachowiak.lemma8(sig)[source]

The graph G=GE( ((0|1) k^q) | l^p) ) contains a Hamilton cycle for every p, q > 0

Parameters:

sig (tuple[int, ...]) – The signature of the neighbor-swap graph; 1, 1, q, p. We assume the first two elements are of colors 0 and 1 and occur once. The second two elements are of colors 2 and 3 and occur q and p times respectively.

Returns:

A Hamiltonian cycle of the form GE((0|1) k^q) | l^p)

Return type:

list[tuple[int, …]]

core.stachowiak.lemma9(sig)[source]

The graph G=GE( (k^r (0|1) k^s) | l^p) ) contains a Hamilton cycle for every p, r+s > 0.

Parameters:

sig (tuple[int, ...]) –

The signature of the neighbor-swap graph; (1, 1, r, s, p). We assume:

  • The first two elements are of colors 0 and 1 respectively and occur once.

  • The second two elements are of color 2 and occur r and s times respectively.

  • The fourth element is of color 3 and occurs p times.

Returns:

A Hamiltonian cycle of the form GE( (k^r (0|1) k^s) | l^p) )

Return type:

list[tuple[int, …]]

core.stachowiak.lemma10(sig)[source]

Computes Lemma 10 by Stachowiak: If q = |Q| > 2, Q is even and GE(Q) contains a Hamiltonian path and p > 0 then GE(Q|l^p) has a Hamiltonian cycle. Here Q is two elements in the signature that form a Hamiltonian path of even length and p is the third element.

Parameters:

sig (tuple[int, ...]) – The signature of the graph; Q is the first two elements, p is the third. Q is of length 2, its colors are 0 and 1. It contains a Hamiltonian path. p is the third element of sig and has color 2 and occurs p times.

Returns:

A Hamiltonian cycle in the neighbor-swap graph of the form GE(Q|l^p)

Return type:

list[tuple[int, …]]

Raises:

AssertionError – If the signature is not well-formed. The first two elements must be able to form a Hamiltonian path of even length > 2.

core.stachowiak.lemma11(sig)[source]

Finds a Hamiltonian cycle in a graph using Lemma 11 from Stachowiak’s paper: If q = |Q| > 2, p = |P| > 0 and GE(Q) has an even number of vertices and contains a Hamiltonian path then GE(Q|P) has a Hamiltonian cycle.

Parameters:

sig (tuple[int, ...]) – A signature of a neighbor-swap graph where at least two elements form a Hamiltonian path of even length > 2. These two elements are set to the front of the signature using a recursive call. Note that this can also be three elements if the first two are 1 (using Lemma 2). Or at least 3 elements that occur once (using Steinhaus-Johnson-Trotter algorithm). The rest of the signature is processed using Stachowiak’s lemmas.

Returns:

A Hamiltonian cycle in the neighbor-swap graph of the form GE(Q|P). Q is this Hamiltonian path and P is the rest of the signature

Return type:

list[tuple[int, …]]

Raises:

  • ValueError – If the signature is empty.

  • ValueError – There are no elements that can form a Hamiltonian path.

Notes

  • If q = |Q| > 2, p = |P| > 0 and GE(Q) has an even number of vertices and contains a Hamiltonian path, then GE(Q|P) has a Hamiltonian cycle.

  • The function first checks the length of the signature and handles special cases where the signature has only one or two elements.

  • If the signature is not ordered well, it transforms the signature and recursively calls the function with the transformed signature. The order is well when the first two elements are the largest odd numbers.

  • If the first two elements in the signature can form a cycle (more than two permutations), it uses Verhoeff’s Theorem to find the cycle.

  • If the first 3 (or more) elements are 1, it uses the Steinhaus-Johnson-Trotter algorithm to get the Hamiltonian cycle.

  • If the third element in the signature is not 0, it uses Stachowiak’s Lemma 2 to find a Hamiltonian path in GE(Q|l^{sig[2]}).

  • Finally, it iterates over the remaining elements in the signature and calls the helper function _lemma10_helper to extend the cycle.

References

  • Stachowiak G. Hamilton Paths in Graphs of Linear Extensions for Unions of Posets. Technical report, 1992

  • Tom Verhoeff. The spurs of D. H. Lehmer: Hamiltonian paths in neighbor-swap graphs of permutations. Designs, Codes, and Cryptography, 84(1-2):295-310, 7 2017. (Used to find Hamiltonian cycles in binary neighbor-swap graphs.)

core.steinhaus_johnson_trotter module

class core.steinhaus_johnson_trotter.SteinhausJohnsonTrotter[source]

Bases: object

Class representing the Steinhaus-Johnson-Trotter algorithm for generating permutations.

The Steinhaus-Johnson-Trotter algorithm is an algorithm for generating all permutations of a given set of elements.

References

  • From https://www.geeksforgeeks.org/johnson-trotter-algorithm/. This Code is Contributed by Prasad Kandekar (prasad264).

  • Hugo Steinhaus. One Hundred Problems In Elementary Mathematics. Dover, New York, 1979.

  • Selmer M. Johnson. Iterative Solution of Linear Systems of Functional Equations. Technical Report 2, 1962.

      1. Trotter. Algorithm 115: Perm. Communications of the ACM, 5(8):434-435, 8 1962

LEFT_TO_RIGHT = True

The direction of the mobile element to move left to right.

Type:

bool

RIGHT_TO_LEFT = False

The direction of the mobile element to move right to left.

Type:

bool

searchArr(a, n, mobile)[source]

Search for the given mobile element in the array.

Parameters:

  • a (list[int]) – The array to search in.

  • n (int) – The length of the array.

  • mobile (int) – The mobile element to search for.

Returns:

The index of the mobile element in the array, if found.

Return type:

int

Raises:

ValueError – If the mobile element is not found in the array.

getMobile(a, dir, n)[source]

Returns the largest mobile element in the given permutation.

Parameters:

  • a (list[int]) – The permutation of numbers.

  • dir (list[bool]) – The direction of each element in the permutation.

  • n (int) – The length of the permutation.

Returns:

The largest mobile element in the permutation.

Return type:

int

get_sjt_permutations(n)[source]

Generate permutations using the Steinhaus-Johnson-Trotter algorithm.

Parameters:

n (int) – The number of elements in the permutation.

Returns:

A list of permutations generated using the Steinhaus-Johnson-Trotter algorithm.

Return type:

list[tuple[int, …]]

core.verhoeff module

core.verhoeff.HpathNS(k0, k1)[source]

Computes a Hamiltonian path in the neighbor-swap graph on the non-stutter permutations for the given signature. If k0 and k1 are both even, the path is a Hamiltonian cycle.

Parameters:

  • k0 (int) – Number of 0s in the signature.

  • k1 (int) – Number of 1s in the signature.

Returns:

A Hamiltonian path in the neighbor-swap graph G(0^k_0|1^(k_1)).

Return type:

list[tuple[int, …]]

References

  • Tom Verhoeff. The spurs of D. H. Lehmer: Hamiltonian paths in neighbor-swap graphs of permutations. Designs, Codes, and Cryptography, 84(1-2):295-310, 7 2017.

core.visualization module

core.visualization.visualize(dict_graph, dict_inv)[source]

Visualizes a graph based on the given dictionary adjacency matrix.

The inversion dictionary is used to determine the position of each node in the visualization. The number of inversions of a node is represented by the number of elements that appear out of order in the permutation. Two elements are considered out of order if the left element is strictly greater than the right element (the elements are not necessarily adjacent).

Parameters:

  • dict_graph (dict[str, set[str]]) – A dictionary representing the graph, where each key is a node and the corresponding value is a set of adjacent nodes.

  • dict_inv (dict[tuple, int]) – A dictionary mapping nodes to their respective number of inversions.

Returns:

A tuple containing the graph object and a dictionary of edge colors.

Return type:

tuple[nx.Graph, dict]

core.visualization.find_path_colors(edge_colors, graph, cli_args, signature)[source]

Determines the colors of a Lehmer path in a neighbor-swap graph. The Lehmer path is computed using the lehmer_path function. Uses whether the CLI arguments specify coloring or not. If coloring is enabled, the nodes and edges are colored based on the Lehmer path (possibly with spurs). If coloring is disabled, the nodes and edges are colored based on whether they are spurs or not.

Parameters:

  • edge_colors (dict) – A dictionary representing which edges are colored red (because they are in the Lehmer path), or black (rest). The keys are tuples of nodes and the values are the color of the edge.

  • graph (nx.Graph) – The networx graph to find the coloring for.

  • cli_args (Namespace) – Command-line arguments. Contains the color flag, which activates coloring of the Lehmer path if True.

  • signature (list[int]) – The signature of the permutations (for the Lehmer path)

Returns:

A tuple containing the nodes and edges colors as lists of strings where the strings represent the colors. The order of the colors corresponds to the order of the nodes and edges in the graph.

Return type:

tuple[list[str], list[str]]

core.visualization.plot_graph(graph, n_color, e_color)[source]

Plot a graph using NetworkX and Matplotlib.

Parameters:

  • graph (nx.Graph) – The graph to be plotted.

  • n_color (list[str]) – List of colors for nodes. The order corresponds to the order of the nodes in the graph.

  • e_color (list[str]) – List of colors for edges. The order corresponds to the order of the edges in the graph.

Return type:

None

Returns:

None

core.visualization.point_to_line_distance(x, y, x1, y1, x2, y2)[source]

Calculates the shortest distance between a point (x, y) and a line segment defined by two points (x1, y1) and (x2, y2). We will say that the click is close to the edge if the distance is less than 0.01.

Parameters:

  • x (float) – The x-coordinate of the clicked point.

  • y (float) – The y-coordinate of the clicked point.

  • x1 (float) – The x-coordinate of the first point defining the line segment.

  • y1 (float) – The y-coordinate of the first point defining the line segment.

  • x2 (float) – The x-coordinate of the second point defining the line segment.

  • y2 (float) – The y-coordinate of the second point defining the line segment.

Returns:

The shortest distance between the point and the line segment.

Return type:

float

core.visualization.is_stutter_permutation(perm, max_arity=False)[source]

Returns whether the permutation is a stutter permutation. Always returns False when the permutation has the maximum arity in the graph. This is used to determine whether to automatically recognize stutters as spurs in a variation on Lehmer’s algorithm.

Parameters:

  • perm (str) – The permutation to check

  • max_arity (bool, optional) – Whether the permutation has the maximum arity in the graph

Returns:

True if the permutation is a stutter permutation, False otherwise.

Return type:

bool

core.visualization.lehmer_path(graph, cli_args, signature)[source]

Implementation Lehmer’s permutations by adjacent interchanges algorithm

Parameters:

  • graph (nx.Graph) – The neighbor-swap graph

  • cli_args (Namespace) – Command line arguments

  • signature (list[int]) – The permutation signature

Returns:

A tuple containing the Lehmer path, spur bases, and spur tips

Return type:

tuple[list, list, list]

References

      1. Lehmer. Permutation by Adjacent Interchanges. Technical Report 2, 1965.

Module contents