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 nodei
. 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 regardingedg
.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 inedg
at which the outgoing edge relations of node \(i\) begin. The last relation of this node is at positionadj[i+1]-1
. The positions \(n+1 \leq i < 2n+2\) correspond to the indices inedg
that are the incoming edge relations (e.g. atadj[n+1+i]
inedg
is the first incoming edge that points towards node \(i\)). Ifadj[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 atgraph.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