networkit.graph

class networkit.graph.Graph(n=0, weighted=False, directed=False, edgesIndexed=False)

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.

Parameters
  • 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

addEdge(u, v, w=1.0, addMissing=False, checkMultiEdge=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))).

Parameters
  • 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

Returns

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.

Return type

bool

addNode()

Add a new node to the graph and return it.

Returns

The new node.

Return type

int

addNodes(numberOfNewNodes)

Add numberOfNewNodes many new nodes to the graph and return the id of the last node added.

Parameters

numberOfNewNodes (int) – Number of nodes to be added.

Returns

The id of the last node added.

Return type

int

attachNodeAttribute(name, ofType)

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.

Parameters
  • name (str) – Name for this attribute

  • ofType (type) – Type of the attribute (either int, float, or str)

Returns

The resulting node attribute container.

Return type

networkit.graph.NodeAttribute

checkConsistency()

Check for invalid graph states, such as multi-edges.

Returns

True if graph contains invalid graph states.

Return type

bool

compactEdges()

Compact the edge storage, this should be called after executing many edge deletions.

degree(u)

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).

Parameters

u (int) – The input Node.

Returns

The number of neighbors.

Return type

int

degreeIn(u)

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).

Parameters

u (int) – The input Node.

Returns

The number of in-neighbors.

Return type

int

degreeOut(u)

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).

Parameters

u (int) – The Input Node.i

Returns

The number of out-neighbors.

Return type

int

detachNodeAttribute(name)

Detaches a node attribute from the graph.

Notes

Using node attributes is in experimental state. The API may change in future updates.

Parameters

name (str) – The distinguished name for the attribute to detach.

edgeId(u, v)
Parameters
  • u (node) – Node Id from u.

  • v (node) – Node Id from v.

Returns

Id of the edge.

Return type

int

forEdges(callback)

Experimental edge iterator interface

Parameters

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).

forEdgesOf(u, callback)

Experimental incident (outgoing) edge iterator interface

Parameters
  • 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).

forInEdgesOf(u, callback)

Experimental incident edge iterator interface

Parameters
  • 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).

forNodePairs(callback)

Experimental node pair iterator interface

Parameters

callback (object) – Any callable object that takes the parameters tuple(int, int). Parameter list refering to (node id, node id).

forNodes(callback)

Experimental node iterator interface

Parameters

callback (object) – Any callable object that takes the parameter node.

forNodesInRandomOrder(callback)

Experimental node iterator interface

hasEdge(u, v)

Checks if undirected edge {u,`v`} exists in the graph.

Parameters
  • u (int) – Endpoint of edge.

  • v (int) – Endpoint of edge.

Returns

True if the edge exists, False otherwise.

Return type

bool

hasEdgeIds()

Returns true if edges have been indexed

Returns

If edges have been indexed

Return type

bool

hasNode(u)

Checks if the Graph has the node u, i.e. if u hasn’t been deleted and is in the range of valid ids.

Parameters

u (int) – Id of node queried.

Returns

Indicates whether node u is part of the graph.

Return type

bool

increaseWeight(u, v, w)

Increase the weight of an edge. If the edge does not exist, it will be inserted.

Parameters
  • u (int) – Endpoint of edge.

  • v (int) – Endpoint of edge.

  • w (float) – Edge weight.

indexEdges(force=False)

Assign integer ids to edges.

Parameters

force (bool, optional) – Force re-indexing of edges. Default: False

isDirected()

Returns whether a graph is directed.

Returns

True if graph is directed.

Return type

bool

isIsolated(u)

If the node u is isolated.

Parameters

u (int) – The input node.

Returns

Indicates whether the node is isolated.

Return type

bool

isWeighted()

Returns whether a graph is weighted.

Returns

True if this graph supports edge weights other than 1.0.

Return type

bool

iterEdges()

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).

iterEdgesWeights()

Iterates over the edges of the graph and their weights.

iterInNeighbors(u)

Iterates over a range of the in-neighbors of a node.

Parameters

u (int) – The input node.

iterInNeighborsWeights(u)

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.

Parameters

u (int) – The input node.

iterNeighbors(u)

Iterates over a range of the neighbors of a node.

Parameters

u (int) – The input node.

iterNeighborsWeights(u)

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.

Parameters

u (int) – The input node.

iterNodes()

Iterates over the nodes of the graph.

numberOfEdges()

Get the number of edges in the graph.

Returns

The number of edges.

Return type

int

numberOfNodes()

Get the number of nodes in the graph.

Returns

The number of nodes.

Return type

int

numberOfSelfLoops()

Get number of self-loops, i.e. edges {v, v}.

Returns

Number of self-loops.

Return type

int

removeAllEdges()

Removes all the edges in the graph.

removeEdge(u, v)

Removes the undirected edge {u,`v`}.

Parameters
  • u (int) – Endpoint of edge.

  • v (int) – Endpoint of edge.

removeMultiEdges()

Removes all multi-edges from the graph.

removeNode(u)

Remove a node u and all incident edges from the graph.

Incoming as well as outgoing edges will be removed.

Parameters

u (int) – Id of node to be removed.

removeSelfLoops()

Removes all self-loops from the graph.

restoreNode(u)

Restores a previously deleted node u with its previous id in the graph.

Parameters

u (int) – The input node.

setWeight(u, v, w)

Set the weight of an edge. If the edge does not exist, it will be inserted.

Parameters
  • u (int) – Endpoint of edge.

  • v (int) – Endpoint of edge.

  • w (float) – Edge weight.

sortEdges()

Sorts the adjacency arrays by node id. While the running time is linear this temporarily duplicates the memory.

swapEdge(s1, t1, s2, t2)

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.

Parameters
  • 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.

totalEdgeWeight()

Get the sum of all edge weights.

Returns

The sum of all edge weights.

Return type

float

upperEdgeIdBound()

Get an upper bound for the edge ids in the graph.

Returns

An upper bound for the edge ids in the graph.

Return type

int

upperNodeIdBound()

Get an upper bound for the node ids in the graph.

Returns

An upper bound for the node ids in the graph.

Return type

int

weight(u, v)

Get edge weight of edge {u , v}. Returns 0 if edge does not exist.

Parameters
  • u (int) – Endpoint of edge.

  • v (int) – Endpoint of edge.

Returns

Edge weight of edge {u , v} or 0 if edge does not exist.

Return type

float

weightedDegree(u, countSelfLoopsTwice=False)

Returns the weighted out-degree of u.

For directed graphs this is the sum of weights of all outgoing edges of u.

Parameters
  • u (int) – The input Node.

  • countSelfLoopsTwice (bool, optional) – If set to True, self-loops will be counted twice. Default: False

Returns

The weighted out-degree of u.

Return type

float

weightedDegreeIn(u, countSelfLoopsTwice=False)

Returns the weighted in-degree of u.

For directed graphs this is the sum of weights of all ingoing edges of u.

Parameters
  • u (int) – The input node.

  • countSelfLoopsTwice (bool, optional) – If set to True, self-loops will be counted twice. Default: False

Returns

The weighted in-degree of u.

Return type

float

class networkit.graph.NodeAttribute(typedNodeAttribute, type)

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.

class networkit.graph.RandomMaximumSpanningForest(G, attributes)

Computes a random maximum-weight spanning forest using Kruskal’s algorithm by randomizing the order of edges of the same weight.

Parameters
  • G (networkit.Graph) – The input graph.

  • attribute (list(int) or list(float)) – If given, this edge attribute is used instead of the edge weights.

getAttribute(move=False)

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.

Parameters

move (bool, optional) – If the attribute shall be moved out of the algorithm instance. Default: False

Returns

The list with the bool attribute for each edge.

Return type

list(bool)

getMSF(move)

Gets the calculated maximum-weight spanning forest as graph.

Parameters

move (bool) – If the graph shall be moved out of the algorithm instance.

Returns

The calculated maximum-weight spanning forest.

Return type

networkit.Graph

inMSF(u, v=None)

Checks if the edge (u, v) or the edge with id u is part of the calculated maximum-weight spanning forest.

Parameters
  • 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

Returns

If the edge is part of the calculated maximum-weight spanning forest.

Return type

bool

class networkit.graph.SpanningForest(G, nodes)

Generates a spanning forest for a given graph

Parameters
  • G (networkit.Graph) – The input graph.

  • nodes (list(int)) – A subset of nodes of G which induce the subgraph.

getForest()

Returns the spanning forest.

Returns

The computed spanning forest.

Return type

networkit.Graph

run()

Executes the algorithm.

class networkit.graph.UnionMaximumSpanningForest(G, attribute)

Union maximum-weight spanning forest algorithm, computes the union of all maximum-weight spanning forests using Kruskal’s algorithm.

Parameters
  • G (networkit.Graph) – The input graph.

  • attribute (list(int) or list(float)) – If given, this edge attribute is used instead of the edge weights.

getAttribute(move=False)

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.

Parameters

move (bool, optional) – If the attribute shall be moved out of the algorithm instance. Default: False

Returns

The list with the bool attribute for each edge.

Return type

list(bool)

getUMSF(move=False)

Gets the union of all maximum-weight spanning forests as graph.

Parameters

move (bool, optional) – If the graph shall be moved out of the algorithm instance. Default: False

Returns

The calculated union of all maximum-weight spanning forests.

Return type

networkit.Graph

inUMST(u, v=None)

Checks if the edge (u, v) or the edge with id u is part of any maximum-weight spanning forest.

Parameters
  • 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

Returns

If the edge is part of any maximum-weight spanning forest.

Return type

bool