Old Documentation

This page contains the Old Package documentation.

The icdfa Module

cmpy.orderlygen.old.icdfa.B(t, n, k)

Returns the number of complete (t=0) or incomplete (t=1) ICDFAs over n states with k symbols.

cmpy.orderlygen.old.icdfa.N(t, n, k, m, j)
cmpy.orderlygen.old.icdfa.icdfa_to_int(t, n, k, s)

Return the number in the enumeration sequence of n state k symbol DFAs where the string s occurs.

cmpy.orderlygen.old.icdfa.int_to_icdfa(t, n, k, m)

Return the DFA string over n states and k symbols that corresponds to the m-th one generated in the enumeration algorithm.

cmpy.orderlygen.old.icdfa.n_f(t, n, k, f)

Part of the icdfa_to_int() algorithm.

cmpy.orderlygen.old.icdfa.n_r(t, n, k, f, s)

Part of the icdfa_to_int() algorithm.

cmpy.orderlygen.old.icdfa.string_to_flag(t, n, k, s)

Return the flag that corresponds to the DFA string s.

The generator Module

class cmpy.orderlygen.old.generator.CustomDFA(data=None, **attr)

Bases: networkx.classes.digraph.DiGraph

Methods

get_accept_nodes()
get_accept_nodes()
cmpy.orderlygen.old.generator.flag_value(f, s, i)

Given a flag and string representation for an ICDFA, and an index i, return the string element closest to the index in the flag. Part of the DFA generation algorithm.

cmpy.orderlygen.old.generator.generator(f, s)

Given an ICDFA flag and string representation, return the flag and string representation for the next ICDFA. Part of the DFA generation algorithm.

cmpy.orderlygen.old.generator.is_canonical(s, num)

Given a string representation of a DFA, determine if it is 1) strongly connected, 2) the first member of it’s (node) isomorphism class.

cmpy.orderlygen.old.generator.is_full(f, s)

Given a flag and string representation of an ICDFA, return True if no more strings can be generated with the current flag.

cmpy.orderlygen.old.generator.is_minimal(dfa, n, alphabet)
cmpy.orderlygen.old.generator.main()
cmpy.orderlygen.old.generator.next_flags(f, i)

Given a DFA flag f, generate the next flag in the sequence. Part of the DFA generation algorithm.

cmpy.orderlygen.old.generator.next_icdfa(f, s, a, b)

Given a flag and string representation of an ICDFA, generate the next ICDFA in the sequence. Part of the DFA generation algorithm.

cmpy.orderlygen.old.generator.reset(f)

Given a flag f, return the first ICDFA with that flag. Part of the DFA generation algorithm.

cmpy.orderlygen.old.generator.set_last_icdfa()

Compute the last ICDFA that will be generated with n_states and n_symbols.

cmpy.orderlygen.old.generator.string_to_array(s)

Given a string representation of a DFA, convert it to an array representation, like T0,T1,...

cmpy.orderlygen.old.generator.string_to_dfa(s)

Convert a string DFA to a CMPy DFA object.

The enumerate_machines Module

cmpy.orderlygen.old.enumerate_machines.augment(machine_list)
cmpy.orderlygen.old.enumerate_machines.check_permutations(T, codes)
cmpy.orderlygen.old.enumerate_machines.code(T)
cmpy.orderlygen.old.enumerate_machines.is_strongly_connected(T)
cmpy.orderlygen.old.enumerate_machines.main()

The read1 Module

A generator of graphs and digraphs.

The generated graphs have labeled nodes and unlabeled edges. In the
generation, we consider isomorphisms over the node labels and return only one representative from each equivalence class.

Implementation is from:

[1] Read, R.C., “Every one a winner, or how to avoid isomorphism search when
cataloguing combinatorial configurations,” Annals of Discrete Math. 2 (1978) 107-120.

with heuristic checks for non-canonicity from:

[2] Colbourn, Charles J., “Graph Generation,” Research Report CS-77-37,
Department of Computer Science, University of Waterloo (1977). http://www.cs.uwaterloo.ca/research/tr/1977/CS-77-37.pdf
class cmpy.orderlygen.old.read1.DiGraph

Bases: object

Orderly generator for directed graphs without selfloops.

class cmpy.orderlygen.old.read1.DiGraphSelfLoop

Bases: object

Orderly generator for directed graphs with selfloops.

class cmpy.orderlygen.old.read1.EdgeAddition

Bases: cmpy.orderlygen.old.read1.OrderlyGenerator

Abstract base class for orderly generators which add edges.

The following variables are assummed:

nodes : int
The number of nodes in the generated graphs.
length : int
The length of each code.
multi : int
When multi > 1, we are working with multigraphs. This parameter specifies the maximum number of edges that can exist between any two nodes. For directed graphs, this pertains to the maximum number of outgoing edges from one node to another node.

Methods

augment(code) Generates an ordered list of codes having one additional edge.
code2graph(code)
code_generator([edges]) A generator of vector representations of non-isomorphic graphs.
graph2code(code)
graph_generator([edges])
is_canonical(code)
augment(code)

Generates an ordered list of codes having one additional edge.

Parameters:

code : list

A list of integers representing the adjacency matrix.

Returns:

codes : list

An ordered list of candidate codes, which represent graphs which have one more edge than the code used to create the list.

code_generator(edges=None)

A generator of vector representations of non-isomorphic graphs.

Parameters:

edges : list of ints or int

A list of integers which will filter the graphs that are generated. A graph will be yielded only if it has a number of edges matching an integer in the list. If ‘edges’ is an integer, we treat it as a list of length one. The default value is None, meaning no filter will be applied and all graphs will be yielded.

class cmpy.orderlygen.old.read1.EdgeDeletion

Bases: cmpy.orderlygen.old.read1.OrderlyGenerator

Abstract base class for oderly generators which delete edges.

The list order is from low to high.

The following variables are assummed:

nodes : int
The number of nodes in the generated graphs.
length : int
The length of each code.
multi : int
When multi > 1, we are working with multigraphs. This parameter specifies the maximum number of edges that can exist between any two nodes. For directed graphs, this pertains to the maximum number of outgoing edges from one node to another node.

Methods

augment(code) Generates an ordered list of codes having one additional edge.
code2graph(code)
code_generator([edges]) A generator of vector representations of non-isomorphic graphs.
graph2code(code)
graph_generator([edges])
is_canonical(code)
augment(code)

Generates an ordered list of codes having one additional edge.

Parameters:

code : list

A list of integers representing the adjacency matrix.

Returns:

codes : list

An ordered list of candidate codes, which represent graphs which have one more edge than the code used to create the list.

code_generator(edges=None)

A generator of vector representations of non-isomorphic graphs.

Parameters:

edges : list of ints or int

A list of integers which will filter the graphs that are generated. A graph will be yielded only if it has a number of edges matching an integer in the list. If ‘edges’ is an integer, we treat it as a list of length one. The default value is None, meaning no filter will be applied and all graphs will be yielded.

class cmpy.orderlygen.old.read1.Graph(n)

Bases: cmpy.orderlygen.old.read1.EdgeAddition

Orderly generator for undirected graphs without selfloops.

Starting at n=0, the number of graphs on n nodes (no selfloops) is:
1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168
This is Slone sequence A000088:
http://www.research.att.com/~njas/sequences/A000088

Methods

augment(code) Generates an ordered list of codes having one additional edge.
code2graph(code) Returns a NetworkX Graph instance from the code representation.
code_generator([edges]) A generator of vector representations of non-isomorphic graphs.
degrees(code) Returns a list of degrees for each node.
edge(i, j, code) Returns part of code representing an edge between nodes i and j.
graph2code(graph) Returns a code representation of the graph’s adjacency matrix.
graph_generator([edges])
is_canonical(code) Returns True if the code is canonical.
priority(i, j, code) Returns the priority of the code.
code2graph(code)

Returns a NetworkX Graph instance from the code representation.

Parameters:

code : list

The code representing the graph’s adjacency matrix.

Returns:

graph : networkx.Graph

The graph corresponding to the code.

degrees(code)

Returns a list of degrees for each node.

Parameters:

code : list

The code word for a graph.

Returns:

degrees : list

A list of degrees for each node in the graph.

edge(i, j, code)

Returns part of code representing an edge between nodes i and j.

Parameters:

i : int, 0 <= i < self.n

A from node in the graph.

j : int, 0 <= j < self.n

A to node in the graph.

code : list

The code word for a graph.

Returns:

e : int

Part of code corresponding to an edge between nodes i to j. If the edge doesn’t exist, then 0 is returned. If the edge does exist, then 1 is returned.

graph2code(graph)

Returns a code representation of the graph’s adjacency matrix.

Parameters:

graph : networkx.Graph

The graph to be converted into a code.

Returns:

code : list

The code for the graph.

is_canonical(code)

Returns True if the code is canonical.

A code is canonical if it is the largest (lexicographic) code in its isomorphism class.

priority(i, j, code)

Returns the priority of the code.

1 <= j <

Parameters:

i : int, 0 <= i < self.n

A from node in the graph.

j : int, 0 <= j < self.n

A to node in the graph.

code : list

The code word for a graph.

Returns:

p : int

Priority of the code. Used to prune canonicity checks.

class cmpy.orderlygen.old.read1.GraphConnected(n)

Bases: cmpy.orderlygen.old.read1.EdgeDeletion, cmpy.orderlygen.old.read1.Graph

Orderly generator for undirected, connected graphs without selfloops.

The number of connected graphs on n nodes without selfloops from n=1 is:
1, 1, 2, 6, 21, 112, 853, 11117, 261080
This is Slone sequence A001349:
http://www.research.att.com/~njas/sequences/A001349

Methods

augment(code) Generates an ordered list of codes having one additional edge.
code2graph(code) Returns a NetworkX Graph instance from the code representation.
code_generator([edges]) A generator of vector representations of non-isomorphic graphs.
degrees(code) Returns a list of degrees for each node.
edge(i, j, code) Returns part of code representing an edge between nodes i and j.
graph2code(graph) Returns a code representation of the graph’s adjacency matrix.
graph_generator([edges])
is_canonical(code) Returns True if the code is canonical.
priority(i, j, code) Returns the priority of the code.
is_canonical(code)

Returns True if the code is canonical.

A code is canonical if it is the smallest (lexicographic) code in its isomorphism class.

class cmpy.orderlygen.old.read1.GraphConnectedSelfLoop(n)

Bases: cmpy.orderlygen.old.read1.GraphConnected, cmpy.orderlygen.old.read1.GraphSelfLoop

Orderly generator for undirected, connected graphs with selfloops.

From n=1, (parenthesis is from filtering)
2, 3, 10, 49 (89->50), 345 (531->347), 3765 (?)

Methods

augment(code) Generates an ordered list of codes having one additional edge.
code2graph(code) Returns a NetworkX Graph instance from the code representation.
code_generator([edges]) A generator of vector representations of non-isomorphic graphs.
degrees(code) Returns a list of degrees for each node.
edge(i, j, code) Returns part of code representing an edge between nodes i and j.
graph2code(graph) Returns a code representation of the graph’s adjacency matrix.
graph_generator([edges])
is_canonical(code) Returns True if the code is canonical.
priority(i, j, code) Returns the priority of the code.
class cmpy.orderlygen.old.read1.GraphSelfLoop(n)

Bases: cmpy.orderlygen.old.read1.Graph

Orderly generator for undirected graphs with selfloops.

From n=1,
2, 6, 20, 89, 531, 4941

Methods

augment(code) Generates an ordered list of codes having one additional edge.
code2graph(code) Returns a NetworkX Graph instance from the code representation.
code_generator([edges]) A generator of vector representations of non-isomorphic graphs.
degrees(code) Returns a list of degrees for each node.
edge(i, j, code) Returns part of code representing an edge between nodes i and j.
graph2code(graph) Returns a code representation of the graph’s adjacency matrix.
graph_generator([edges])
is_canonical(code) Returns True if the code is canonical.
priority(i, j, code) Returns the priority of the code.
code2graph(code)

Returns a NetworkX Graph instance from the code representation.

Parameters:

code : list

The code representing the graph’s adjacency matrix.

Returns:

graph : cmpy.machines.BaseMachine

The graph corresponding to the code.

degrees(code)

Returns a list of degrees for each node.

Parameters:

code : list

The code word for a graph.

Returns:

degrees : list

A list of degrees for each node in the graph.

edge(i, j, code)

Returns part of code representing an edge between nodes i and j.

Parameters:

i : int, 0 <= i < self.n

A from node in the graph.

j : int, 0 <= j < self.n

A to node in the graph.

code : list

The code word for a graph.

Returns:

e : int

Part of code corresponding to an edge between nodes i to j. If the edge doesn’t exist, then 0 is returned. If the edge does exist, then 1 is returned.

graph2code(graph)

Returns a code representation of the graph’s adjacency matrix.

Parameters:

graph : networkx.Graph

The graph to be converted into a code.

Returns:

code : list

The code for the graph.

class cmpy.orderlygen.old.read1.OrderlyGenerator

Bases: object

Abstract base class for orderly generators of graphs.

All orderly generators should derive from this class, but note that the full implementation will always need to be customized.

Methods

augment(code)
code2graph(code)
code_generator()
graph2code(code)
graph_generator([edges])
is_canonical(code)
augment(code)
code2graph(code)
code_generator()
graph2code(code)
graph_generator(edges=None)
is_canonical(code)
cmpy.orderlygen.old.read1.augment(vector, **keywords)

Generates an ordered list of vectors with an additional edge.

Parameters:

vector : list

The vector should be a list of integers.

max_multi : int

When max_multi > 1, we are working with multigraphs. This parameter specifies the maximum number of edges that can exist between any two nodes. For directed graphs, this pertains to the maximum number of outgoing edges from one node to another node. Note that this is not an explicit restriction on the degree (or out-degree) of each node. The default value is 1.

Returns:

vectors : list

An ordered list of candidate vectors, which represent graphs which have one more edge than the vector used to create the list.

cmpy.orderlygen.old.read1.degrees(vector, **keywords)

Returns a list of degrees, for each node in the graph.

For directed graphs, a list of out-degrees is returned.

Parameters:

vector : list

The vector should be a list of integers.

directed : bool, optional

Specifies if the graph is directed. Default value is False.

selfloops : bool, optional

Specifies if selfloops are allowed. Default value is False.

Returns:

degrees : list

For undirected graphs, this is a list of degrees for each node. For directed graphs, this is a list of out-degrees for each node.

Notes

The order of the list is derived from the order of the vector.

cmpy.orderlygen.old.read1.edge(i, j, num_nodes, vector)

Returns component of vector representing an edge from node i to node j.

Parameters:

i : int, 0 <= i < num_nodes

A from node in the graph.

j : int, 0 <= j < num_nodes

A to node in the graph.

num_nodes : int

The total number of nodes in the graph.

vector : list

A list of integers representing a graph.

directed : bool, optional

Specifies if the graph is directed. Default value is False.

selfloops : bool, optional

Specifies if selfloops are allowed. Default value is False.

Returns:

v : int

Component of vector corresponding to an edge from i to j. If the edge doesn’t exist, then the component of the vector should be zero. If the edge does exist, then the component of the vector will be some positive integer.

cmpy.orderlygen.old.read1.graph_iter(num_nodes, nodes=None)

A generator of non-isomorphic graphs.

cmpy.orderlygen.old.read1.graph_iter__brute(num_nodes, alphabet=[0, 1], nodes=None)

A brute force generator of non-isomorphic graphs.

cmpy.orderlygen.old.read1.is_canonical(vector, **keywords)

Returns True if the vector is canonical.

A vector is canonical if it is the largest (lexicographic) vector in its isomorphism class.

Parameters:

directed : bool, optional

Specifies if the graph is directed. Default value is False.

selfloops : bool, optional

Specifies if selfloops are allowed. Default value is False.

cmpy.orderlygen.old.read1.num_graphs(num_nodes)

Returns the number of non-isomorphic graphs with num_nodes nodes.

cmpy.orderlygen.old.read1.num_graphs__brute(num_nodes)

Returns the number of non-isomorphic graphs with num_nodes nodes.

cmpy.orderlygen.old.read1.num_nodes(vector_length, **keywords)

Returns the number of nodes from the length of the vector.

Parameters:

vector_length : int

The length of the vector.

directed : bool, optional

Specifies if the graph is directed. Default value is False.

selfloops : bool, optional

Specifies if selfloops are allowed. Default value is False.

Returns:

num_nodes : int

The number of nodes in the graph.

See also

vector_length

Notes

An Exception is raised if num_nodes is not an integer.

cmpy.orderlygen.old.read1.permute(l)
cmpy.orderlygen.old.read1.priority(i, j, n, vector)

Returns the priority of node at index i with respect to node at index j.

cmpy.orderlygen.old.read1.vector_iter(num_nodes, num_edges=None)

A generator of vector representations of non-isomorphic graphs.

cmpy.orderlygen.old.read1.vector_iter__brute(num_nodes)

A brute force generator of vector representations for non-isomorphic graphs.

cmpy.orderlygen.old.read1.vector_length(num_nodes, **keywords)

Returns the vector length given the number of nodes.

Parameters:

num_nodes : int

The number of nodes in the graph.

directed : bool, optional

Specifies if the graph is directed. Default value is False.

selfloops : bool, optional

Specifies if selfloops are allowed. Default value is False.

Returns:

length : int

The length of the vector, given the number of nodes.

See also

num_nodes