An undirected graph (with optional weights) and parallel iterator methods.
Create a graph of n nodes. The graph has assignable edge weights if weighted is set to True. If weighted is set to False each edge has edge weight 1.0 and any other weight assignment will be ignored.
n (int, optional) – Number of nodes. Default: 0
weighted (bool, optional) – If set to True, the graph can have edge weights other than 1.0. Default: False
directed (bool, optional) – If set to True, the graph will be directed. Default: False
edgesIndexed (bool, optional) – If set to True, the graph’s edges will be indexed. Default: False
Insert an undirected edge between the nodes u and v. If the graph is weighted you can optionally set a weight for this edge. The default weight is 1.0. If one or both end-points do not exists and addMissing is set, they are silently added.
Note
By default it is not checked whether this edge already exists, thus it is possible to create multi-edges. Multi-edges are not supported and will NOT be
handled consistently by the graph data structure. To enable set checkMultiEdge to True. Note that this increases the runtime of the function by O(max(deg(u), deg(v))).
u (int) – Endpoint of edge.
v (int) – Endpoint of edge.
w (float, optional) – Edge weight. Default: 1.0
addMissing (bool, optional) – Add missing endpoints if necessary (i.e., increase numberOfNodes). Default: False
checkMultiEdge (bool, optional) – Check if edge is already present in the graph. If detected, do not insert the edge. Default: False
Indicates whether the edge has been added. Is False in case checkMultiEdge is set to True and the new edge would have been a multi-edge.
bool
Add a new node to the graph and return it.
The new node.
int
Add numberOfNewNodes many new nodes to the graph and return the id of the last node added.
numberOfNewNodes (int) – Number of nodes to be added.
The id of the last node added.
int
Attaches a node attribute to the graph and returns it.
A = G.attachNodeAttribute("attributeIdentifier", ofType)
All values are initially undefined for existing nodes values can be set/get by
A[node] = value # set
value = A[node] # get
Getting undefined values raises a ValueError removing a node makes all its attributes undefined
Notes
Using node attributes is in experimental state. The API may change in future updates.
name (str) – Name for this attribute
ofType (type) – Type of the attribute (either int, float, or str)
The resulting node attribute container.
Check for invalid graph states, such as multi-edges.
True if graph contains invalid graph states.
bool
Compact the edge storage, this should be called after executing many edge deletions.
Get the number of neighbors of u.
Note
The existence of the node is not checked. Calling this function with a non-existing node results in a segmentation fault. Node existence can be checked by calling hasNode(u).
u (int) – The input Node.
The number of neighbors.
int
Get the number of in-neighbors of u.
Note
The existence of the node is not checked. Calling this function with a non-existing node results in a segmentation fault. Node existence can be checked by calling hasNode(u).
u (int) – The input Node.
The number of in-neighbors.
int
Get the number of out-neighbors of u.
Note
The existence of the node is not checked. Calling this function with a non-existing node results in a segmentation fault. Node existence can be checked by calling hasNode(u).
u (int) – The Input Node.i
The number of out-neighbors.
int
Detaches a node attribute from the graph.
Notes
Using node attributes is in experimental state. The API may change in future updates.
name (str) – The distinguished name for the attribute to detach.
u (node) – Node Id from u.
v (node) – Node Id from v.
Id of the edge.
int
Experimental edge iterator interface
callback (object) – Any callable object that takes the parameter tuple(int, int, float, int). Parameter list refering to (node id, node id, edge weight, edge id).
Experimental incident (outgoing) edge iterator interface
u (int) – The node of which incident edges shall be passed to the callback
callback (object) – Any callable object that takes the parameter tuple(int, int, float, int). Parameter list refering to (node id, node id, edge weight, edge id).
Experimental incident edge iterator interface
u (int) – The node of which incident edges shall be passed to the callback
callback (object) – Any callable object that takes the parameter tuple(int, int, float, int). Parameter list refering to (node id, node id, edge weight, edge id).
Experimental node pair iterator interface
callback (object) – Any callable object that takes the parameters tuple(int, int). Parameter list refering to (node id, node id).
Experimental node iterator interface
callback (object) – Any callable object that takes the parameter node.
Experimental node iterator interface
Checks if undirected edge {u,`v`} exists in the graph.
u (int) – Endpoint of edge.
v (int) – Endpoint of edge.
True if the edge exists, False otherwise.
bool
Returns true if edges have been indexed
If edges have been indexed
bool
Checks if the Graph has the node u, i.e. if u hasn’t been deleted and is in the range of valid ids.
u (int) – Id of node queried.
Indicates whether node u is part of the graph.
bool
Increase the weight of an edge. If the edge does not exist, it will be inserted.
u (int) – Endpoint of edge.
v (int) – Endpoint of edge.
w (float) – Edge weight.
Assign integer ids to edges.
force (bool, optional) – Force re-indexing of edges. Default: False
Returns whether a graph is directed.
True if graph is directed.
bool
If the node u is isolated.
u (int) – The input node.
Indicates whether the node is isolated.
bool
Returns whether a graph is weighted.
True if this graph supports edge weights other than 1.0.
bool
Iterates over the edges of the graph.
For each node u in the graph in ascending node id order, the iterator yields the out-edges of u in directed graphs and the edges (u,v) in which u < v for undirected graphs.
It does not follow the order of edge ids (if present).
Iterates over the edges of the graph and their weights.
Iterates over a range of the in-neighbors of a node.
u (int) – The input node.
Iterates over a range of the in-neighbors of a node including the edge weights. The iterator is not safe to use with unweighted graphs. To avoid unsafe behavior a runtime error will be thrown.
u (int) – The input node.
Iterates over a range of the neighbors of a node.
u (int) – The input node.
Iterates over a range of the neighbors of a node including the edge weights. The iterator is not safe to use with unweighted graphs. To avoid unsafe behavior a runtime error will be thrown.
u (int) – The input node.
Iterates over the nodes of the graph.
Get the number of edges in the graph.
The number of edges.
int
Get the number of nodes in the graph.
The number of nodes.
int
Get number of self-loops, i.e. edges {v, v}.
Number of self-loops.
int
Removes all the edges in the graph.
Removes the undirected edge {u,`v`}.
u (int) – Endpoint of edge.
v (int) – Endpoint of edge.
Removes all multi-edges from the graph.
Remove a node u and all incident edges from the graph.
Incoming as well as outgoing edges will be removed.
u (int) – Id of node to be removed.
Removes all self-loops from the graph.
Restores a previously deleted node u with its previous id in the graph.
u (int) – The input node.
Set the weight of an edge. If the edge does not exist, it will be inserted.
u (int) – Endpoint of edge.
v (int) – Endpoint of edge.
w (float) – Edge weight.
Sorts the adjacency arrays by node id. While the running time is linear this temporarily duplicates the memory.
Changes the edge (s1, t1) into (s1, t2) and the edge (s2, t2) into (s2, t1).
If there are edge weights or edge ids, they are preserved.
Note
No check is performed if the swap is actually possible, i.e. does not generate duplicate edges.
s1 (int) – Source node of the first edge.
t1 (int) – Target node of the first edge.
s2 (int) – Source node of the second edge.
t2 (int) – Target node of the second edge.
Get the sum of all edge weights.
The sum of all edge weights.
float
Get an upper bound for the edge ids in the graph.
An upper bound for the edge ids in the graph.
int
Get an upper bound for the node ids in the graph.
An upper bound for the node ids in the graph.
int
Get edge weight of edge {u , v}. Returns 0 if edge does not exist.
u (int) – Endpoint of edge.
v (int) – Endpoint of edge.
Edge weight of edge {u , v} or 0 if edge does not exist.
float
Returns the weighted out-degree of u.
For directed graphs this is the sum of weights of all outgoing edges of u.
u (int) – The input Node.
countSelfLoopsTwice (bool, optional) – If set to True, self-loops will be counted twice. Default: False
The weighted out-degree of u.
float
Returns the weighted in-degree of u.
For directed graphs this is the sum of weights of all ingoing edges of u.
u (int) – The input node.
countSelfLoopsTwice (bool, optional) – If set to True, self-loops will be counted twice. Default: False
The weighted in-degree of u.
float
Generic class for node attributes returned by networkit.graph.attachNodeAttribute(). Example of attaching an int attribute to a graph g:
att = g.attachNodeAttribute("name", int)`
Set/get attributes of a single node ‘u’ with the [] operator:
att[u] = 0
att_val = att[u] # 'att_val' is 0
Iterate over all the values of an attribute:
for u, val in att:
# The attribute value of node `u` is `val`.
Notes
Using node attributes is in experimental state. The API may change in future updates.
Computes a random maximum-weight spanning forest using Kruskal’s algorithm by randomizing the order of edges of the same weight.
G (networkit.Graph) – The input graph.
attribute (list(int) or list(float)) – If given, this edge attribute is used instead of the edge weights.
Get a bool attribute that indicates for each edge if it is part of the calculated maximum-weight spanning forest. This attribute is only calculated and can thus only be request if the supplied graph has edge ids.
move (bool, optional) – If the attribute shall be moved out of the algorithm instance. Default: False
The list with the bool attribute for each edge.
list(bool)
Gets the calculated maximum-weight spanning forest as graph.
move (bool) – If the graph shall be moved out of the algorithm instance.
The calculated maximum-weight spanning forest.
Checks if the edge (u, v) or the edge with id u is part of the calculated maximum-weight spanning forest.
u (int) – The first node of the edge to check or the edge id of the edge to check.
v (int, optional) – The second node of the edge to check (only if u is not an edge id). Default: None
If the edge is part of the calculated maximum-weight spanning forest.
bool
Generates a spanning forest for a given graph
G (networkit.Graph) – The input graph.
nodes (list(int)) – A subset of nodes of G which induce the subgraph.
Returns the spanning forest.
The computed spanning forest.
Executes the algorithm.
Union maximum-weight spanning forest algorithm, computes the union of all maximum-weight spanning forests using Kruskal’s algorithm.
G (networkit.Graph) – The input graph.
attribute (list(int) or list(float)) – If given, this edge attribute is used instead of the edge weights.
Get a bool attribute that indicates for each edge if it is part of any maximum-weight spanning forest.
This attribute is only calculated and can thus only be request if the supplied graph has edge ids.
move (bool, optional) – If the attribute shall be moved out of the algorithm instance. Default: False
The list with the bool attribute for each edge.
list(bool)
Gets the union of all maximum-weight spanning forests as graph.
move (bool, optional) – If the graph shall be moved out of the algorithm instance. Default: False
The calculated union of all maximum-weight spanning forests.
Checks if the edge (u, v) or the edge with id u is part of any maximum-weight spanning forest.
u (int) – The first node of the edge to check or the edge id of the edge to check.
v (int, optional) – The second node of the edge to check (only if u is not an edge id). Default: None
If the edge is part of any maximum-weight spanning forest.
bool