5.2. kwant.graph – Low-level, efficient directed graphs

Graphs, as handled by this module, consist of nodes (numbered by integers, usually \(\geq 0\)). Pairs of nodes can be connected by edges (numbered by integers \(\geq 0\)). An edge is described by a pair (tail, head) of node numbers and is always directed.

The basic workflow is to

1. create an object of type Graph,

2. add edges to it using the methods add_edge and add_edges,

3. create a compressed copy of the graph using the method compressed,

4. and use the thus created object for efficient queries.

Example:

>>> import kwant
>>> g = kwant.graph.Graph()
>>> g.add_edge(0, 1)
0
>>> g.add_edge(0, 2)
1
>>> g = g.compressed()
>>> list(g.out_neighbors(0))
[1, 2]

Node numbers can be assigned freely, but if they are not consecutive integers starting with zero, storage space is wasted in the compressed graph. Negative node numbers are special and can be allowed optionally (see further).

Whenever a method returns multiple edges or nodes (via an iterator), they appear in the order in which the edges associated with them were added to the graph during construction.

Edge IDs are non-negative integers which identify edges unambiguously. They are assigned automatically when the graph is compressed. The edge IDs of edges with the same tail will occupy a dense interval of integers. The IDs of edges sharing the same tail will be assigned from lowest to highest in the order in which these edges had been added.

The method Graph.compressed takes a parameter which determines whether the graph will be one-way (the default) or two-way. One-way graphs can be queried for the existence of an edge and provide the nodes to which a node points (=outgoing neighbors). In addition, two-way graphs can be queried for the nodes which point to a node (=incoming neighbors).

Another parameter of Graph.compressed, edge_nr_translation, determines whether it will be possible to use the method edge_id of the compressed graph. This method returns the edge ID of an edge given the edge number that was returned when an edge was added.

Negative node numbers can be allowed for a Graph (parameter allow_negative_nodes of the constructor). Edges with negative nodes are considered to be dangling: negative nodes can be neighbors of other nodes, but cannot be queried directly for neighbors. Consequently, “doubly-dangling” edges which connect two negative nodes do not make sense and are never allowed. The range of values used for the negative node numbers does not influence the required storage space in any way.

Compressed graphs have the read-only attributes num_nodes and num_edges.

Graph types

Graph	An uncompressed graph.
CGraph	A compressed graph which can be efficiently queried for the existence of edges and outgoing neighbors.

Other

gint_dtype

Data type used for graph nodes and edges