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_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.
-
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
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.
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.
-
property
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.
-
__weakref__
¶ list of weak references to the object (if defined)
-
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.