pysaucy

Module contents

class pysaucy.Graph(adjacency_list, directed=False)

Bases: object

The adjacency_list must have length n (number of nodes) and adjacency_list[i] contains an iterable of node ids to which an edge exists.

If directed is False, the adjacency list will be transformed so that for each node id i holds i <= min(adjacency_list[i]). I.e. only the right upper triangular matrix is saved.

If directed is True, each edge in the adjacency list will be interpreted as directed edge.

Hint

Saucy natively supports loops in graphs. So having loops simply means that i in adjacency_list[i] is True. You can check if the graph has loops using the corresponding property.

Parameters:

• adjacency_list – An iterable of n entries, each an iterable of adjacent node ids
• directed – (Optional) Does the adjacency list describe a directed graph?

adjacency_list

Return the (possibly transformed, see pysaucy.graph.Graph.__init__()) adjacency list.

Returns:List of length \(n\) of lists of adjacent node ids.

directed

Is this graph directed?

Returns:True | False

has_loops

Has the graph loops?

Returns:True | False

m

Number of edges \(m\)

Returns:\(m\)

n

Number of nodes \(n\)

Returns:\(n\)

pysaucy.run_saucy(g, colors=None, on_automorphism=None)

Make the saucy call.

Warning

Using the on_automorphism callback is quite expensive and will slow down the algorithm significantly if many generators are found.

The automorphism group size is defined by group size base \(b\) and group size exponent \(e\) as \(b\cdot10^e\).

The returned orbits are a list of orbit ids where orbits[i] is some (integer) orbit id and all nodes on the same orbit have the same id.

Parameters:

• g – The graph
• colors – (Optional) A partition of node colors of length \(n\)
• on_automorphism – An optional callback function with signature (graph, permutation, support)

Returns:

(group size base, group size exponent, levels, nodes, bads, number of generators, support, orbits)