5.2. kwant.graph
– Lowlevel, 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
create an object of type
Graph
,create a compressed copy of the graph using the method
compressed
,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 nonnegative 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 oneway (the default) or twoway. Oneway graphs can be queried
for the existence of an edge and provide the nodes to which a node points
(=outgoing neighbors). In addition, twoway 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, “doublydangling”
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 readonly attributes num_nodes and num_edges.
Graph types#
An uncompressed graph. 

A compressed graph which can be efficiently queried for the existence of edges and outgoing neighbors. 
Other#

Data type used for graph nodes and edges 