Graph Factories

Creating graphs can be accomplished using factory methods. During runtime the type of the graph can be queried using Graph.type which returns a GraphType instance. This allows algorithms to adjust their behavior depending on the graph they are working on.

Graph

The main factory function which creates graphs is jgrapht.create_graph(). Depending on the given parameters different types of graphs can be represented. All graphs returned by this function are instances of jgrapht.types.Graph. Most users should create graphs using this function:

jgrapht.create_graph(directed=True, allowing_self_loops=False, allowing_multiple_edges=False, weighted=True, dag=False, any_hashable=False, vertex_supplier=None, edge_supplier=None)

Create a graph.

By default this function creates graphs with integer vertices. When parameter any_hashable is true, the returned graph will be able to (a) have any hashable as vertices and edges, and (b) associate attributes/properties with the vertices and edges. Such a any-hashable graph needs to be able to create new objects for vertices and edges. This is accomplished by providing two functions called vertex supplier and edge supplier. If not provided by the user, the default implementation creates instances of object.

Parameters

• directed – if True the graph will be directed, otherwise undirected

• allowing_self_loops – if True the graph will allow the addition of self-loops

• allowing_multiple_edges – if True the graph will allow multiple-edges

• weighted – if True the graph will be weighted, otherwise unweighted

• dag – if True the graph will be a DAG (directed acyclic graph). An error will be raised if either directed is False or allowing_self_loops is True. The returned graph will be an instance of DirectedAcyclicGraph

• any_hashable – if True then the graph will allow the use of any hashable as vertices and edges instead of just integers. This also makes the graph an instance of AttributesGraph

• vertex_supplier – used only in the case that the graph allows any hashable as vertices/edges. Called everytime the graph needs to create a new vertex. If not given, then object instances are used.

• edge_supplier – used only in the case that the graph allows any hashable as vertices/edges. Called everytime the graph needs to create a new edge. If not given, then object instances are used.

Returns

a graph

Return type

Graph

Sparse Graph

The following function creates a special sparse graph representation which has certain benefits and certain drawbacks. The benefits are that (a) it is much smaller w.r.t memory consumption and (b) it is also usually much faster. The drawbacks are that the sparse representation (a) cannot be modified after construction and (b) is forces a user to use vertex and edges that are integers starting from 0 in a continuous range. Since modification is not possible, a user needs to bulk-load the graph by providing both the number of vertices and all edges before hand.

jgrapht.create_sparse_graph(edgelist, num_of_vertices=None, directed=True, weighted=True, any_hashable=False, vertex_supplier=None, edge_supplier=None)

Create a sparse graph.

By default this function creates graphs with integer vertices. When parameter any_hashable is true, the returned graph will be able to (a) have any hashable as vertices and edges, and (b) associate attributes/properties with the vertices and edges. Such a any-hashable graph needs to be able to create new objects for vertices and edges. This is accomplished by providing two functions called vertex supplier and edge supplier. If not provided by the user, the default implementation creates instances of object.

The structure (topology) of a sparse graph is unmodifiable, but weights and properties can be modified.

Parameters

• edgelist – list of tuple (u,v) or (u,v,weight) for weighted graphs. If any_hashable is false, the vertices must be integers.

• num_of_vertices – number of vertices in the graph. Vertices always start from 0 and increase continuously. If not explicitly given and any_hashable is false, the edgelist will be traversed in order to find out the number of vertices

• directed – if True the graph will be directed, otherwise undirected

• weighted – if True the graph will be weighted, otherwise unweighted

• any_hashable – if True then the graph will allow the use of any hashable as vertices and edges instead of just integers. This also makes the graph an instance of AttributesGraph

• vertex_supplier – used only in the case that the graph allows any hashable as vertices/edges. Called everytime the graph needs to create a new vertex. If not given, then object instances are used.

• edge_supplier – used only in the case that the graph allows any hashable as vertices/edges. Called everytime the graph needs to create a new edge. If not given, then object instances are used.

Returns

a graph

Return type

Graph

A helper function jgrapht.copy_to_sparse_graph() can help in order to create a sparse graph from another graph.

jgrapht.copy_to_sparse_graph(graph)

Copy a graph to a sparse graph.

Note

Sparse graphs are unmodifiable w.r.t their structure (topology). Attempting to alter one will result in an error being raised. Attributes and edge weights can be modified.

Parameters

graph – the input graph

Returns

a sparse graph

Return type

jgrapht.types.Graph

Building sparse graphs can be performed by using edge lists. See the section edge list importers.