cnfformula.graphs module

Utilities to manage graph formats and graph files in order to build formulas that are graph based.

supported_formats()

The graph file formats supported by the library.

readGraph(input_file, graph_type, file_format='autodetect', multi_edges=False)

Read a Graph from file

The graph are managed using the NetworkX library, and most of the input and output formats are the ones supported by it. Plus we added support for some more hackish formats that are useful in applications.

for the “simple” and “bipartite” types, the graph is actually a (Multi)Graph object, while it is a (Multi)DiGraph in case of “dag” or “digraph”.

In the case of “dag” type, the graph is guaranteed to be acyclic and to pass the is_dag test. In the case of “bipartite” type, the graph is guaranteed to have the two parts labeled and to pass the has_bipartition test.

Parameters:

input_file: str, unicode 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.

graph_type: string in {“simple”,”digraph”,”dag”,”bipartite”}

see also cnfformula.graph.supported_formats()

file_format: string, optional

The file format that the parser should expect to receive. See also cnfformula.graph.supported_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 among networkx.DiGraph, networkx.MultiDiGraph, networkx.Graph, networkx.MultiGraph object.

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

writeGraph, is_dag, has_bipartition

writeGraph(G, output_file, graph_type, file_format='autodetect')

Write a graph to a file

Parameters:

G : networkx.Graph (or similar)

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.

graph_type: string in {“simple”,”digraph”,”dag”,”bipartite”}

see also cnfformula.graph.supported_formats()

file_format: string, optional

The file format that the parser should expect to receive. See also cnfformula.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 when graph_type and file_format are invalid choices.

IOError

it is impossible to write on the output_file

See also

readGraph

is_dag(digraph)

Test is a directed graph is acyclic

if the input graph has a member `topologically_sorted’ then assumed that there is a member `ordered_vertices’ and that it is a topological order.

Arguments: - digraph: input graph

has_bipartition(G)

Check that the graph is labelled with a bipartition

NetworkX follows the convention that bipartite graphs have their vertices labeled with the bipartition. In particular each vertex has the ‘bipartite’ attribute with is either 0 or 1.

Parameters:

G: networkx.Graph

bipartite_sets(G)

enumerate_vertices(graph)

Return the ordered list of vertices of graph

Parameters:

graph : input graph

enumerate_edges(graph)

Return the ordered list of edges of graph

Parameters:

graph : input graph

neighbors(graph, v)

Return the ordered list of neighbors ov a vertex

Parameters:

graph : input graph

v : vertex

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:

networkx.Graph

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.

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 of vertices at the left side

seed : hashable object

seed of random generator

Returns:

networkx.Graph

Raises:

ValueError

if one among l, r and d is negative or if r does not divides l*d

References

[1] http://…

dag_complete_binary_tree(height)

Generates the complete binary tree DAG

Parameters:

height : int

the height of the tree

Returns:

networkx.DiGraph

dag_pyramid(height)

Generates the pyramid DAG

Parameters:

height : int

the height of the tree

Returns:

networkx.DiGraph