Interfaces

Graph

The main interface of the library is the Graph. All graph instances returned by the library follow this interface and almost all library methods revolve around it. The graph interface contains all the necessary methods to query or modify a graph.

class jgrapht.types.Graph[source]

A graph.

abstract add_edge(u, v, weight=None, edge=None)[source]

Add an edge to the graph.

If the user does not provide explicitly an integer edge identifier, a new identifier is automatically created. If the user provides an edge and the edge is already in the graph, then this method does nothing.

Parameters
  • u – the first endpoint (vertex) of the edge

  • v – the second endpoint (vertex) of the edge

  • weight – an optional weight to use for the edge. If the edge is already present, its weight is not adjusted.

  • edge – the integer edge identifier. If None then the graph will automatically create a new edge identifier

Returns

the new edge identifier

Return type

int

add_edges_from(edges)[source]

Add all edges from an iterable.

Parameters

edges – any iterable of edges. Each edge is (u, v, weight, id) where possibly weight and id are missing.

Returns

list of added edge identifiers

abstract add_vertex(vertex=None)[source]

Add a vertex to the graph.

If the user does not provide explicitly an integer vertex identifier, a new identifier is automatically created. If the user provides a vertex and the vertex is already in the graph, then this method does nothing.

Parameters

vertex – an integer identifier for the vertex. If None then the graph will automatically create a new vertex identifier

Returns

the newly created vertex identifier.

Return type

int

add_vertices_from(vertices)[source]

Add a list of vertices to the graph.

Parameters

vertices – a list of vertices

Returns

a list of boolean values indicating whether each vertex is added to the graph

Return type

list of booleans

abstract contains_edge(e)[source]

Check if an edge is contained in the graph.

Parameters

e – the edge identifier to check

Returns

True if the edge belongs to the graph, False otherwise.

Return type

Boolean

abstract contains_edge_between(u, v)[source]

Check if an edge exists between two vertices.

Parameters
  • u – the first vertex

  • v – the second vertex

Returns

True if an edge between u and v exists, False otherwise.

abstract contains_vertex(v)[source]

Check if a vertex is contained in the graph.

Parameters

v – the vertex

Returns

true if the vertex is contained in the graph, False otherwise

Return type

boolean

abstract degree_of(v)[source]

Returns the degree of the specified vertex.

A degree of a vertex in an undirected graph is the number of edges touching that vertex. Edges with same source and target vertices (self-loops) are counted twice. In directed graphs this method returns the sum of the “in degree” and the “out degree”.

Parameters

v – vertex whose degree is to be calculated

Returns

the degree of the specified vertex

Raises

ValueError – if the vertex is not found in the graph

abstract edge_source(e)[source]

Get the source vertex of an edge.

For directed graphs this method always returns the vertex from which the edge originates. For undirected graphs, an arbitrary one of the two vertices, but always the same and always the opposite of what method edge_target() returns.

Parameters

e – the edge

Returns

the source endpoint of the edge

abstract edge_target(e)[source]

Get the target vertex of an edge.

For directed graphs this method always returns the vertex to which this edge points. For undirected graphs, an arbitrary one of the two vertices, but always the same and always the opposite of what method edge_source() returns.

Parameters

e – the edge

Returns

the source endpoint of the edge

edge_tuple(e)[source]

Get an edge as a tuple.

Parameters

e – the edge

Returns

the edge as (u, v, weight). If the graph is unweighted the weight is always 1.0

abstract edges()[source]

Graph edge set.

abstract edges_between(u, v)[source]

Returns all edges between vertices u and v.

Parameters
  • u – the first endpoint

  • v – the second endpoint

Returns

all edges between vertices u and v.

abstract edges_of(v)[source]

Set of all edges touching vertex v.

Parameters

v – the vertex

Returns

the set of all edges touching v.

Raises

ValueError – If the vertex is not in the graph.

abstract get_edge_weight(e)[source]

Get the weight of an edge.

If the graph is unweighted, this method returns 1.0 in order to allow algorithms to also execute on them.

Parameters

e – the edge

Returns

the weight of an edge

Return type

Double

abstract indegree_of(v)[source]

Returns the “in degree” of the specified vertex.

The indegree of a vertex in a directed graph is the number of inward directed edges from that vertex. In the case of undirected graphs this method returns the number of edges touching the vertex. Edges with same source and target vertices (self-loops) are counted twice.

Parameters

v – vertex whose degree is to be calculated

Returns

the degree of the specified vertex

Raises

ValueError – if the vertex is not found in the graph

abstract inedges_of(v)[source]

Set of all edges incoming into vertex v.

In the case of undirected graphs this method returns all edges touching the vertex, thus, some of the returned edges may have their source and target vertices in the opposite order.

Parameters

v – the vertex

Returns

the set of all edges incoming into v.

Raises

ValueError – If the vertex is not in the graph.

number_of_edges()[source]

Get the number of edges in the graph.

number_of_vertices()[source]

Get the number of vertices in the graph.

opposite(e, u)[source]

Get the opposite vertex of an edge.

Parameters
  • e – the edge

  • u – one endpoint of an edge

Returns

the opposite vertex of the edge

abstract outdegree_of(v)[source]

Returns the “out degree” of the specified vertex.

The outdegree of a vertex in a directed graph is the number of outward directed edges from that vertex. In the case of undirected graphs this method returns the number of edges touching the vertex. Edges with same source and target vertices (self-loops) are counted twice.

Parameters

v – vertex whose degree is to be calculated

Returns

the degree of the specified vertex

Raises

ValueError – if the vertex is not found in the graph

abstract outedges_of(v)[source]

Set of all edges outgoing from vertex v.

In the case of undirected graphs this method returns all edges touching the vertex, thus, some of the returned edges may have their source and target vertices in the opposite order.

Parameters

v – the vertex

Returns

the set of all edges outgoing from v.

Raises

ValueError – If the vertex is not in the graph.

abstract remove_edge(e)[source]

Remove an edge from the graph.

Parameters

e – the edge identifier to remove

Returns

True if the edge was removed, False otherwise.

Return type

Boolean

abstract remove_vertex(v)[source]

Remove a vertex from the graph.

Parameters

v – The vertex to remove

abstract set_edge_weight(e, weight)[source]

Set the weight of an edge.

Parameters
  • e – the edge

  • weight – the weight

Raises

UnsupportedOperationError – in case the graph does not support weights

abstract type()[source]

Query the graph type.

Returns

the graph type.

Return type

GraphType

abstract vertices()[source]

Graph vertex set.

AttributesGraph

Some graph implementations are also attribute graphs which means that they can directly associate attributes/properties with the vertices and edges of the graph.

class jgrapht.types.AttributesGraph[source]

A graph which contains vertex/edge/graph attributes.

abstract edge_attrs()[source]

Dictionary with edge attributes.

abstract graph_attrs()[source]

Dictionary with graph attributes.

abstract vertex_attrs()[source]

Dictionary with vertex attributes.

GraphType

The GraphType is used to represent during runtime the properties of the graph.

class jgrapht.types.GraphType(directed=True, allowing_self_loops=False, allowing_multiple_edges=False, allowing_cycles=True, weighted=True, modifiable=True)[source]

Graph Type

property allowing_cycles

Tells if the graph allows cycles.

Returns

True if the graph allows cycles, False otherwise.

property allowing_multiple_edges

Tells if the graph allows multiple edges. Multiple edges are edges which have exactly the same endpoints.

Returns

True if the graph allows multiple-edges, False otherwise.

property allowing_self_loops

Tells if the graph allows self-loops. Self-loops are edges (u,v) where u = v.

Returns

True if the graph allows self-loops, False otherwise.

as_directed()[source]

Return a directed version of this graph type.

Returns

a directed version of this graph type

as_undirected()[source]

Return an undirected version of this graph type.

Returns

an undirected version of this graph type

as_unmodifiable()[source]

Return an unmodifiable version of this graph type.

Returns

an unmodifiable version of this graph type

as_unweighted()[source]

Return an unweighted version of this graph type.

Returns

an unweighted version of this graph type

as_weighted()[source]

Return a weighted version of this graph type.

Returns

a weighted version of this graph type

property directed

Check if the graph is directed.

Returns

True if the graph is directed, False otherwise.

property modifiable

Tells if the graph is modifiable or not.

Returns

True if the graph is modifiable, False otherwise.

property undirected

Tells if the graph is undirected.

Returns

True if the graph is undirected, False otherwise.

property weighted

Tells if the graph is weighted or not.

Returns

True if the graph is weighted, False otherwise.

DirectedAcyclicGraph

A special type is available for directed acyclic graphs (DAGs).

class jgrapht.types.DirectedAcyclicGraph[source]

A directed acyclic graph.

A directed acyclic graph (dag) has all the graph members and the following additional methods.

abstract __iter__()[source]

Get a topological order iterator

__weakref__

list of weak references to the object (if defined)

abstract ancestors(vertex)[source]

Get the ancestors of a vertex

Parameters

vertex – a vertex

Returns

a vertex set

abstract descendants(vertex)[source]

Get the descendants of a vertex

Parameters

vertex – vertex

Returns

a vertex set

ListenableGraph

In case the user wants to listen on structural change events, a special type of listenable graph is also provided.

class jgrapht.types.ListenableGraph[source]

A listenable graph. The listener callbacks accept as the first parameter the vertex or edge of the graph and as second the event type which is GraphEvent.

A listenable graph has all the graph members and the following additional methods which allow users to register and unregister listeners.

abstract add_listener(listener_cb)[source]

Add a listener

Returns

a handle for the listener

abstract remove_listener(listener_handle)[source]

Remove a listener

Parameters

listener_id – the listener handle returned when the listener was added

class jgrapht.types.GraphEvent[source]

An enumeration.