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 mth 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) 107120.
with heuristic checks for noncanonicity from:
 [2] Colbourn, Charles J., “Graph Generation,” Research Report CS7737,
 Department of Computer Science, University of Waterloo (1977). http://www.cs.uwaterloo.ca/research/tr/1977/CS7737.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 nonisomorphic 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 nonisomorphic 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 nonisomorphic 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 nonisomorphic 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 nonisomorphic 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 nonisomorphic 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 nonisomorphic 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 nonisomorphic 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 outdegree) 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 outdegrees 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 outdegrees 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 nonisomorphic graphs.

cmpy.orderlygen.old.read1.
graph_iter__brute
(num_nodes, alphabet=[0, 1], nodes=None)¶ A brute force generator of nonisomorphic 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 nonisomorphic graphs with num_nodes nodes.

cmpy.orderlygen.old.read1.
num_graphs__brute
(num_nodes)¶ Returns the number of nonisomorphic 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
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 nonisomorphic graphs.

cmpy.orderlygen.old.read1.
vector_iter__brute
(num_nodes)¶ A brute force generator of vector representations for nonisomorphic 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