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 when `graph_type` and `file_format` are invalid choices. IOError it is impossible to read the `input_file`

See also

readGraph

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 a `cnfgen.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 a cnfgen.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` and `d` 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` and `d` is negative or if `r` 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` and `m` 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