# Introduction¶

The JGraphT library is a highly efficient graph library containing state-of-the-art graph data-structures as well as a multitude of sophisticated graph algorithms. It has been in development for many years already and is currently used in production both in research and industry.

The Python bindings of JGraphT is a pure python/native package having no dependency on the JVM. During the build
process the backend JGraphT library is compiled as a shared library and bundled inside the python
package. It provides a *graph* data-structure capable of representing various different
kind of graphs/networks such as:

directed: in directed graphs an edge \((u,v)\) is an ordered pair of vertices,

undirected: in undirected graphs an edge \(\{u,v\}\) is an unordered pair of vertices,with

self-loops: self-loops are edges of the form \((v,v)\) where both endpoints are the same,graphs with

multiple-edges: multiple-edges are edges \(e = (u,v)\) and \(e' = (u,v)\) which have the exact same endpoints,

weightedgraphs: graphs where each edge is associated with a double value called its weight,

unweightedgraphs: graphs where the weight of each edge is 1.0 (uniform weight function)

A graph \(G(V,E)\) contains vertices and edges. Each edge \(e = (u,v)\) is associated with

its two endpoints \(u\) and \(v\), and

a double value called its weight.

Additionally, both vertices and edges are usually associated with information called attributes or properties. All access to information about the graph happens using the graph object. Thus, given an edge, finding its source, target and weight can be performed using graph methods. Similarly, information about the vertices, such as its incident edges, can also be performed using corresponding graph methods.

The Python bindings of JGraphT contains two main graph implementations which we describe next. Creating graphs of
either category can be done using the `jgrapht.create_graph()`

factory method.

## integer graphs¶

The *integer graph* is oriented torwards simplicity and performance. Its main characteristic is that
vertices and edges are always integers. When manipulating graphs, beside its structure (topology),
users usually associate additional information with the vertices and edges. Such vertex and edge
attributes/properties, are fully supported when exporting and importing graphs, by using callback
functions. Storing such attributes/properties, however, is not performed inside the graph. The
user is responsible to maintain external dictionaries with the vertex and edge identifier as the key.
While this might seem like a restriction at first, it allows for several optimizations at the graph
level. Combined with the simplicity and power of dictionaries in Python, it should pose no real
restriction to the user, except possibly some aesthetic effect.

A special version of the integer graph which is also supported is the *sparse* graph. The sparse graph
is a static variant which can only be bulk-loaded from a list of edges. Its benefits is that it is
condiderably faster and less memory hungry, at the expense of not being modifiable. It is best suited
for less dynamic workloads where the user creates a graph once and executes complex algorithms on it.

## any-hashable graphs¶

The *any-hashable graph* is a graph implementation which allows the use of any Python hashable as vertices
or edges. Additionally, it provides support for maintaining the attributes/properties dictionaries
inside the graph. During creation the user can provide a vertex and edge factory function (called vertex
supplier and edge supplier) which the graph can use whenever it needs to create new vertices or edges.
If not explicitly provided, the implementation uses object instances for all automatically created vertices
and edges. Importers and exporters automatically support graphs, by importing/exporting their associated
attributes.

Note

Any-hashable graphs are implemented by wrapping the integer graph which means that they incur a performance penalty compared to the integer graph.