networkit.graph

class networkit.graph.EdgeAttribute(typedEdgeAttribute, type)

Generic class for edge attributes returned by networkit.graph.attachEdgeAttribute(). Example of attaching an int attribute to a graph g:

att = g.attachEdgeAttribute("name", int)`

Set/get attributes of a single edgeId ‘eid’ with the [] operator:

att[eid] = 0
att_val = att[eid] # 'att_val' is 0

Iterate over all the values of an attribute:

for eid, val in att:
        # The attribute value of edge `eid` is `val`.

Notes

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

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

addEdges(inputData)

Inserts edges from several sources based on the type of inputData.

If the graph is undirected, each pair (i,j) in inputData is inserted twice twice: once as (i,j) and once as (j,i).

Parameter inputData can be one of the following:

  • scipy.sparse.coo_matrix

  • (data, (i,j)) where data, i and j are of type np.ndarray

  • (i,j) where i and j are of type np.ndarray

Note

If only pairs of row and column indices (i,j) are given, each edge is given weight 1.0 (even in case of a weighted graph).

Parameters:
  • inputData (several) – Input data encoded as one of the supported formats.

  • 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

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

attachEdgeAttribute(name, ofType)

Attaches an edge attribute to the graph and returns it.

A = G.attachEdgeAttribute("attributeIdentifier", ofType)

All values are initially undefined for existing edges values can be set/get by

A[edgeId] = value # set
value = A[edgeId] # get

Getting undefined values raises a ValueError removing an edge makes all its attributes undefined

Notes

Using edge 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 edge attribute container.

Return type:

networkit.graph.EdgeAttribute

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

detachEdgeAttribute(name)

Detaches an edge attribute from the graph.

Notes

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

Parameters:

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

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

networkit.graph.GraphFromCoo(inputData, n=0, weighted=False, directed=False, edgesIndexed=False)

graphFromInputData(inputData, n=0, bool_t weighted=False, bool_t directed=False, bool_t edgesIndexed=False):

Creates a graph based on inputData (edge data). Input data is given in triplet format (also known as ijk or coo format). See here for more details: https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.coo_array.html

If the resulting graph is undirected (default case), each pair (i,j) in inputData is inserted twice twice: once as (i,j) and once as (j,i).

Parameter inputData can be one of the following:

  • scipy.sparse.coo_matrix

  • (data, (i,j)) where data, i and j are of type np.ndarray

  • (i,j) where i and j are of type np.ndarray

Note

  • If only pairs of row and column indices (i,j) are given, each edge is given weight 1.0 (even in case of a weighted graph).

  • There is no check if n is the correct size. If the parameter is used, make sure that it is at least the

maximum index from the coordinate data.

Parameters:
  • inputData (several) – Input data encoded as one of the supported formats.

  • n (int, optional) – Number of nodes for the created graph. If n is not given, the nodes are added on the fly during building of the graph. For better performance, it is advised to correctly set the 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

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