pysaucy2.graph

Module contents

class pysaucy2.graph.Graph(edge_lists, colors=None, directed=False)

Bases: object

Create a new graph. The edge_lists parameter is a list of lists, where edge_lists[i] is a list of adjacent nodes of node i. Loops are allowed. If directed is False, \(i \leq \min(\texttt{edge_lists[i]})\) must hold (i.e. edges are provided as i to j for \(i<j\) which means there is an undirected edge between those nodes). If directed is True, edge_lists[i] contains all target nodes \(j\), i.e. directed edges that point from \(i\) to \(j\).

Parameters:
  • edge_lists (list) – An adjacency list of length \(n\)
  • colors (list) – (Optional) A list of colors, one color for each node
  • directed (boolean) – (Optional) Determine that the graph is directed
adj

Get the adjacency relations. These can only be interpreted in combination with edg. The values of the list are index pointers regarding edg.

If the graph is undirected, the length is \(n+1\), else \(2n+2\). In the directed case, adj[i] (\(0 \leq i < n\)) corresponds to the index in edg at which the outgoing edge relations of node \(i\) begin. The last relation of this node is at position adj[i+1]-1. The positions \(n+1 \leq i < 2n+2\) correspond to the indices in edg that are the incoming edge relations (e.g. at adj[n+1+i] in edg is the first incoming edge that points towards node \(i\)). If adj[i] == adj[i+1] node \(i\) has no incoming/outgoing edges.

In the undirected case, incoming and outgoing edges are ‘the same’. Therefore, adj[i] is the index of the first edge incident to node \(i\).

Returns:A list of adjacency relations in the format that saucy needs
Return type:list
colors

Get or set the node colors.

getter

Returns:A list of colors, \(0 \leq c < n\) for each node.
Return type:list

setter

Parameters:colors (list) – A list of colors, \(0 \leq c < n\) for each node.
directed

Is the graph directed?

Returns:Directedness of the graph
Return type:boolean
edg

Get the edge relations. These can only be interpreted in combination with adj. See the detailed description at graph.Graph.adj().

Returns:A list of edge relations in the format that saucy needs
Return type:list
m
Returns:Number of edges of the graph
Return type:int
n
Returns:Number of nodes of the graph
Return type:int
orbits

Get the orbit partition as list of orbit ids.

You can access this property during a run of saucy to get the incompletely explored orbits. Nodes not yet explored have the orbit id \(-1\). Note, however, that the orbit ids are subject to change until completion!

Returns:A list of orbit ids, \(0 \leq o < n\) for each node.
Return type:list
run_saucy(self, on_automorphism=None)

Make the saucy call.

Warning

Using the on_automorphism callback is very 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\).

Parameters: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)
to_edge_lists(self)

Convert this graph back to a list of adjacency lists.

Returns:Adjacency edge lists
Return type:list