cnfgen.graphs module¶
Utilities to manage graph formats and graph files in order to build formulas that are graph based.
-
readGraph
(input_file, graph_type, file_format='autodetect', multi_edges=False)¶ Read a Graph from file
In the case of “bipartite” type, the graph obtained is of
cnfgen.graphs.BipartiteGraph
.In the case of “simple” type, the graph is obtained of
cnfgen.graphs.Graph
.In the case of “dag” or “directed” type, the graph obtained is of
cnfgen.graphs.DirectedGraph
.The supported file formats are enumerated by the respective class method
supported_file_formats
In the case of “dag” type, the graph read in input must have increasing edges, in the sense that all edges must be such that the source has lower identifier than the sink. (I.e. the numeric identifiers of the vertices are a topological order for the graph)
Parameters: - input_file: str or file-like object
the input file from which the graph is read. If it is a string then the graph is read from a file with that string as filename. Otherwise if the input_file is a file object (or a text stream), the graph is read from there.
Input files are assumed to be UTF-8 by default.
- graph_type: string in {“simple”,”digraph”,”dag”,”bipartite”}
- file_format: string, optional
The file format that the parser should expect to receive. See also the method py:method::
supported_file_formats
. By default it tries to autodetect it from the file name extension (when applicable).- multi_edges: bool,optional
are multiple edge allowed in the graph? By default this is not allowed.
Returns: - a graph object
one type among Graph, DirectedGraph, BipartiteGraph
Raises: - ValueError
raised when either
input_file
is neither a file object nor a string, or whengraph_type
andfile_format
are invalid choices.- IOError
it is impossible to read the
input_file
See also
writeGraph
,is_dag
,has_bipartition
-
writeGraph
(G, output_file, graph_type, file_format='autodetect')¶ Write a graph to a file
Parameters: - G : BaseGraph
- output_file: file object
the output file to which the graph is written. If it is a string then the graph is written to a file with that string as filename. Otherwise if
output_file
is a file object (or a text stream), the graph is written there.The file is written in UTF-8 by default.
- graph_type: string in {“simple”,”digraph”,”dag”,”bipartite”}
see also
cnfgen.graph.supported_formats()
- file_format: string, optional
The file format that the parser should expect to receive. See also
cnfgen.graph.supported_formats()
. By default it tries to autodetect it from the file name extension (when applicable).
Returns: - None
Raises: - ValueError
raised when either
output_file
is neither a file object nor a string, or whengraph_type
andfile_format
are invalid choices.- IOError
it is impossible to write on the
output_file
See also
-
class
Graph
(n, name=None)¶ Bases:
cnfgen.graphs.BaseGraph
Methods
edges
()Outputs all edges in the graph from_file
(fileorname[, fileformat])Load the graph from a file from_networkx
(G)Create a graph object from a networkx graph graph_type_name
()Simple graphs are laleled as ‘simple’ is_bipartite
()Test whether the graph is a bipartite object is_dag
()Test whether the graph is directed acyclic is_directed
()Test whether the graph is directed is_multigraph
()Test whether the graph can have multi-edges neighbors
(u)Outputs the neighbors of vertex u normalize
(G[, varname])Guarantees a cnfgen.graphs.Graph object supported_file_formats
()File formats supported for simple graph I/O to_networkx
()Convert the graph TO a networkx object. add_edge add_edges_from complete_graph degree empty_graph has_edge null_graph number_of_edges number_of_vertices order star_graph vertices -
add_edge
(u, v)¶
-
classmethod
complete_graph
(n)¶
-
degree
(u)¶
-
edges
()¶ Outputs all edges in the graph
-
classmethod
empty_graph
(n)¶
-
classmethod
from_networkx
(G)¶ Create a graph object from a networkx graph
-
classmethod
graph_type_name
()¶ Simple graphs are laleled as ‘simple’
-
has_edge
(u, v)¶
-
is_dag
()¶ Test whether the graph is directed acyclic
This is not a full test. It only checks that all directed edges (u,v) have that u < v.
-
is_directed
()¶ Test whether the graph is directed
-
neighbors
(u)¶ Outputs the neighbors of vertex u
The sequence of neighbors is guaranteed to be sorted.
-
classmethod
normalize
(G, varname='')¶ Guarantees a cnfgen.graphs.Graph object
If the given graph G is a networkx.Graph object, this method produces a CNFgen simple graph object, relabeling vertices so that vertices are labeled as numbers from 1 to n, where n is the number of vertices in G. If the vertices in the original graph have some kind of order, the order is preserved.
If G is already a cnfgen.graphs.Graph object, nothing is done.
Parameters: - cls: a class
- G : networkx.Graph or cnfgen.Graph
the graph to normalize/check
- varname: str
the variable name, for error messages (default: ‘G’)
-
classmethod
null_graph
()¶
-
number_of_edges
()¶
-
number_of_vertices
()¶
-
classmethod
star_graph
(n)¶
-
classmethod
supported_file_formats
()¶ File formats supported for simple graph I/O
-
to_networkx
()¶ Convert the graph TO a networkx object.
-
vertices
()¶
-
-
class
DirectedGraph
(n, name='a simple directed graph')¶ Bases:
cnfgen.graphs.BaseGraph
Methods
from_file
(fileorname[, fileformat])Load the graph from a file from_networkx
(G)Create a graph object from a networkx graph graph_type_name
()Directed graphs are laleled as ‘digraph’ has_edge
(src, dest)True if graph contains directed edge (src,dest) is_bipartite
()Test whether the graph is a bipartite object is_dag
()Is the graph acyclic? is_directed
()Test whether the graph is directed is_multigraph
()Test whether the graph can have multi-edges normalize
(G[, varname])Guarantees a cnfgen.graphs.DirerctedGraph object predecessors
(u)Outputs the predecessors of vertex u successors
(u)Outputs the successors of vertex u supported_file_formats
()File formats supported for directed graph I/O to_networkx
()Convert the graph TO a networkx object. add_edge add_edges_from edges edges_ordered_by_successors in_degree number_of_edges number_of_vertices order out_degree vertices -
add_edge
(src, dest)¶
-
edges
()¶
-
edges_ordered_by_successors
()¶
-
classmethod
from_networkx
(G)¶ Create a graph object from a networkx graph
-
classmethod
graph_type_name
()¶ Directed graphs are laleled as ‘digraph’
-
has_edge
(src, dest)¶ True if graph contains directed edge (src,dest)
-
in_degree
(u)¶
-
is_dag
()¶ Is the graph acyclic?
The vertices in the graph are assumed to be topologically sorted, therefore this function just determines whether there are edges going backward with respect to this order, which can be done in O(1) because edges can be added and not removed.
-
is_directed
()¶ Test whether the graph is directed
-
classmethod
normalize
(G, varname='G')¶ Guarantees a cnfgen.graphs.DirerctedGraph object
If the given graph G is a networkx.DiGraph object, this method produces a CNFgen directed graph object, relabeling vertices so that vertices are labeled as numbers from 1 to n, where n is the number of vertices in G. If the vertices in the original graph have some kind of order, the order is preserved.
If all edges go from lower vertices to higher vertices, with respect to the labeling, then t he graph is considered a directed acyclic graph DAG.
If G is already a cnfgen.graphs.DirectedGraph object, nothing is done.
Parameters: - cls: a class
- G : networkx.DiGraph or cnfgen.DirectedGraph
the graph to normalize/check
- varname: str
the variable name, for error messages (default: ‘G’)
-
number_of_edges
()¶
-
number_of_vertices
()¶
-
out_degree
(v)¶
-
predecessors
(u)¶ Outputs the predecessors of vertex u
The sequence of predecessors is guaranteed to be sorted.
-
successors
(u)¶ Outputs the successors of vertex u
The sequence of successors is guaranteed to be sorted.
-
classmethod
supported_file_formats
()¶ File formats supported for directed graph I/O
-
to_networkx
()¶ Convert the graph TO a networkx object.
-
vertices
()¶
-
-
class
BipartiteGraph
(L, R, name=None)¶ Bases:
cnfgen.graphs.BaseBipartiteGraph
Methods
add_edge
(u, v)Add an edge to the graph. from_file
(fileorname[, fileformat])Load the graph from a file from_networkx
(G)Convert a networkx.Graph
into acnfgen.graphs.BipartiteGraph
graph_type_name
()Bipartite graphs are laleled as ‘bipartite’ is_bipartite
()Test whether the graph is a bipartite object is_dag
()Test whether the graph is directed acyclic is_directed
()Test whether the graph is directed is_multigraph
()Test whether the graph can have multi-edges left_neighbors
(v)Outputs the neighbors of right vertex u normalize
(G[, varname])Guarantees a cnfgen.graphs.BipartiteGraph object right_neighbors
(u)Outputs the neighbors of a left vertex u supported_file_formats
()File formats supported for bipartite graph I/O to_networkx
()Convert the graph TO a networkx object. add_edges_from edges has_edge left_degree left_order number_of_edges number_of_vertices order parts right_degree right_order vertices -
add_edge
(u, v)¶ Add an edge to the graph.
- multi-edges are not allowed
- neighbors of a vertex are kept in numberic order
Examples
>>> G = BipartiteGraph(3,5) >>> G.add_edge(2,3) >>> G.add_edge(2,2) >>> G.add_edge(2,3) >>> G.right_neighbors(2) [2, 3]
-
classmethod
from_networkx
(G)¶ Convert a
networkx.Graph
into acnfgen.graphs.BipartiteGraph
In order to convert a
networkx.Graph
object G, it is necessary that all nodes in G have the property bipartite set to either 0 or 1.If this is not the case, or if there are edges between the two parts,
ValueError
is raised.
-
classmethod
graph_type_name
()¶ Bipartite graphs are laleled as ‘bipartite’
-
has_edge
(u, v)¶
-
left_neighbors
(v)¶ Outputs the neighbors of right vertex u
The sequence of neighbors is guaranteed to be sorted.
-
classmethod
normalize
(G, varname='G')¶ Guarantees a cnfgen.graphs.BipartiteGraph object
If the given graph G is a networkx.Graph object with a bipartition, this method produces a CNFgen bipartite graph object, relabeling vertices so that vertices og each side are labeled as numbers from 1 to n and 1 to m respectively, where n and m are the numbers of vertices in G on the left and right side, respectively. If the vertices in the original graph have some kind of order, the order is preserved.
If G is already a cnfgen.graphs.BipartiteGraph object, nothing is done.
-
number_of_edges
()¶
-
right_neighbors
(u)¶ Outputs the neighbors of a left vertex u
The sequence of neighbors is guaranteed to be sorted.
-
classmethod
supported_file_formats
()¶ File formats supported for bipartite graph I/O
-
-
supported_graph_formats
()¶ File formats supported for graph I/O
Given as a dictionary that maps graph types to the respective supported formats.
E.g. ‘dag’ -> [‘dimacs’, ‘kthlist’]
-
bipartite_random_left_regular
(l, r, d, seed=None)¶ Returns a random bipartite graph with constant left degree.
Each vertex on the left side has d neighbors on the right side, picked uniformly at random without repetition.
Each vertex in the graph has an attribute bipartite which is 0 for the vertices on the left side and 1 for the vertices on the right side.
Parameters: - l : int
vertices on the left side
- r : int
vertices on the right side
- d : int
degree on the left side.
- seed : hashable object
seed the random generator
Returns: - BipartiteGraph
Raises: - ValueError
unless
l
,r
andd
are non negative.
-
bipartite_random_regular
(l, r, d, seed=None)¶ Returns a random bipartite graph with constant degree on both sides.
The graph is d-regular on the left side and regular on the right size, so it must be that d*l / r is an integer number.
Parameters: - l : int
vertices on the left side
- r : int
vertices on the right side
- d : int
degree of vertices at the left side
- seed : hashable object
seed of random generator
Returns: - BipartiteGraph
Raises: - ValueError
if one among
l
,r
andd
is negative or ifr
does not divides l*d
References
[1] http://…
-
bipartite_random_m_edges
(L, R, m, seed=None)¶ Returns a random bipartite graph with M edges
Build a random bipartite graph with \(L\) left vertices, \(R\) right vertices and \(m\) edges sampled at random without repetition.
Parameters: - L : int
vertices on the left side
- R : int
vertices on the right side
- m : int
number of edges.
- seed : hashable object
seed the random generator
Returns: - BipartiteGraph
Raises: - ValueError
unless
L
,R
andm
are non negative.
-
bipartite_random
(L, R, p, seed=None)¶ Returns a random bipartite graph with independent edges
Build a random bipartite graph with \(L\) left vertices, \(R\) right vertices, where each edge is sampled independently with probability \(p\).
Parameters: - L : int
vertices on the left side
- R : int
vertices on the right side
- p : float
probability to pick an edge
- seed : hashable object
seed the random generator
Returns: - BipartiteGraph
Raises: - ValueError
unless
L
,R
are non negative and 0<=``p``<=1.
-
dag_complete_binary_tree
(height)¶ Generates the complete binary tree DAG
Vertices are indexed from the bottom layer, starting from index 1
Parameters: - height : int
the height of the tree
Returns: - cnfgen.graphs.DirectedGraph
Raises: - ValueError
-
dag_pyramid
(height)¶ Generates the pyramid DAG
Vertices are indexed from the bottom layer, starting from index 1
Parameters: - height : int
the height of the pyramid graph (>=0)
Returns: - cnfgen.graphs.DirectedGraph
Raises: - ValueError
-
dag_path
(length)¶ Generates a directed path DAG
Vertices are indexed from 1..length+1
Parameters: - length : int
the length of the path
Returns: - cnfgen.graphs.DirectedGraph
Raises: - ValueError