networkit.graph

class networkit.graph.Graph

An undirected graph (with optional weights) and parallel iterator methods.

Graph(n=0, weighted=False, directed=False)

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 : count, optional
Number of nodes.
weighted : bool, optional
If set to True, the graph can have edge weights other than 1.0.
directed : bool, optional
If set to True, the graph will be directed.
BFSEdgesFrom(self, node start, callback)

Experimental BFS search interface that passes edges that are part of the BFS tree to the callback

start: node
The start node from which the BFS shall be started
callback : object
Any callable object that takes the parameter (node, node)
BFSfrom(self, start, callback)

Experimental BFS search interface

start: node or list[node]
One or more start nodes from which the BFS shall be started
callback : object
Any callable object that takes the parameter (node, count) (the second parameter is the depth)
DFSEdgesFrom(self, node start, callback)

Experimental DFS search interface that passes edges that are part of the DFS tree to the callback

start: node
The start node from which the DFS shall be started
callback : object
Any callable object that takes the parameter (node, node)
DFSfrom(self, node start, callback)

Experimental DFS search interface

start: node
The start node from which the DFS shall be started
callback : object
Any callable object that takes the parameter node
addEdge(self, u, v, w=1.0)

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.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
w : edgeweight, optional
Edge weight.
addNode(self)

Add a new node to the graph and return it.

node
The new node.
append(self, Graph G)

Appends another graph to this graph as a new subgraph. Performs node id remapping.

G : Graph

checkConsistency(self)

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

compactEdges(self)

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

copyNodes(self)

Copies all nodes to a new graph

Graph
Graph with the same nodes (without edges)
degree(self, u)

Get the number of neighbors of v.

v : node
Node.
count
The number of neighbors.
degreeIn(self, u)
degreeOut(self, u)
density(self)

Get the density of the graph.

double

edgeId(self, node u, node v)
edgeid
id of the edge
edges(self)

Get list of edges as node pairs.

list
List of edges as node pairs.
forEdges(self, callback)

Experimental edge iterator interface

callback : object
Any callable object that takes the parameter (node, node, edgeweight, edgeid)
forEdgesOf(self, node u, callback)

Experimental incident (outgoing) edge iterator interface

u : node
The node of which incident edges shall be passed to the callback
callback : object
Any callable object that takes the parameter (node, node, edgeweight, edgeid)
forInEdgesOf(self, node u, callback)

Experimental incident incoming edge iterator interface

u : node
The node of which incident edges shall be passed to the callback
callback : object
Any callable object that takes the parameter (node, node, edgeweight, edgeid)
forNodePairs(self, callback)

Experimental node pair iterator interface

callback : object
Any callable object that takes the parameters (node, node)
forNodes(self, callback)

Experimental node iterator interface

callback : object
Any callable object that takes the parameter node
forNodesInRandomOrder(self, callback)

Experimental node iterator interface

callback : object
Any callable object that takes the parameter node
getCoordinate(self, v)
DEPRECATED: Coordinates should be handled outside the Graph class
like general node attributes.

Get the coordinates of node v. Parameters ———- v : node

Node.
pair[float, float]
x and y coordinates of v.
getName(self)

Get the name of the graph.

string
The name of the graph.
hasEdge(self, u, v)

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

u : node
Endpoint of edge.
v : node
Endpoint of edge.
bool
True if the edge exists, False otherwise.
hasEdgeIds(self)

Returns true if edges have been indexed

bool
if edges have been indexed
hasNode(self, 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.

u : node
Node
bool
If the Graph has the node u
increaseWeight(self, u, v, w)

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

u : node
Endpoint of edge.
v : node
Endpoint of edge.
w : edgeweight
Edge weight.
indexEdges(self, bool force=False)

Assign integer ids to edges.

force : bool
Force re-indexing of edges.
initCoordinates(self)
DEPRECATED: Coordinates should be handled outside the Graph class
like general node attributes.
isDirected(self)
isIsolated(self, u)

If the node u is isolated

u : node
Node.
bool
If the node is isolated
isWeighted(self)
bool
True if this graph supports edge weights other than 1.0.
merge(self, Graph G)
Modifies this graph to be the union of it and another graph.
Nodes with the same ids are identified with each other.

G : Graph

neighbors(self, u)

Get list of neighbors of u.

u : node
Node.
list
List of neighbors of `u.
nodes(self)

Get list of all nodes.

list
List of all nodes.
numberOfEdges(self)

Get the number of edges in the graph.

count
The number of edges.
numberOfNodes(self)

Get the number of nodes in the graph.

count
The number of nodes.
numberOfSelfLoops(self)

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

number of self-loops.
randomEdge(self, bool uniformDistribution=False)

Get a random edge of the graph.

uniformDistribution : bool
If the distribution of the edge shall be uniform
pair
Random random edge.

Fast, but not uniformly random if uniformDistribution is not set, slow and uniformly random otherwise.

randomEdges(self, count numEdges)

Returns a list with numEdges random edges. The edges are chosen uniformly at random.

numEdges : count
The number of edges to choose.
list of pairs
The selected edges.
randomNeighbor(self, u)

Get a random neighbor of v and none if degree is zero.

v : node
Node.
node
A random neighbor of `v.
randomNode(self)

Get a random node of the graph.

node
A random node.
removeEdge(self, u, v)

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

u : node
Endpoint of edge.
v : node
Endpoint of edge.
removeNode(self, u)

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

Incoming as well as outgoing edges will be removed.

u : node
Node.
removeSelfLoops(self)

Removes all self-loops from the graph.

restoreNode(self, u)

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

u : node
Node.
setCoordinate(self, v, value)
DEPRECATED: Coordinates should be handled outside the Graph class
like general node attributes.

Set the coordinates of node v. Parameters ———- v : node

Node.
value : pair[float, float]
x and y coordinates of v.
setName(self, name)

Set name of graph to name.

name : string
The name.
setWeight(self, u, v, w)

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

u : node
Endpoint of edge.
v : node
Endpoint of edge.
w : edgeweight
Edge weight.
size(self)

Get the size of the graph.

tuple
a pair (n, m) where n is the number of nodes and m is the number of edges
sortEdges(self)

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

subgraphFromNodes(self, nodes)

Create a subgraph induced by the set nodes.

nodes : list
A subset of nodes of G which induce the subgraph.
Graph
The subgraph induced by nodes.

The returned graph G’ is isomorphic (structurally identical) to the subgraph in G, but node indices are not preserved.

swapEdge(self, node s1, node t1, node s2, node 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 that no check is performed if the swap is actually possible, i.e. does not generate duplicate edges.

s1 : node
Source node of the first edge
t1 : node
Target node of the first edge
s2 : node
Source node of the second edge
t2 : node
Target node of the second edge
toString(self)

Get a string representation of the graph.

string
A string representation of the graph.
toUndirected(self)

Return an undirected version of this graph.

undirected graph.
toUnweighted(self)

Return an unweighted version of this graph.

graph.
totalEdgeWeight(self)

Get the sum of all edge weights.

edgeweight
The sum of all edge weights.
transpose(self)

Return the transpose of this (directed) graph.

directed graph.
upperEdgeIdBound(self)

Get an upper bound for the edge ids in the graph

count
An upper bound for the edge ids in the graph
upperNodeIdBound(self)

Get an upper bound for the node ids in the graph

count
An upper bound for the node ids in the graph
weight(self, u, v)

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

u : node
Endpoint of edge.
v : node
Endpoint of edge.
edgeweight
Edge weight of edge {u , v} or 0 if edge does not exist.
weightedDegree(self, v)

Returns the weighted degree of v.

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

v : node
Node.
double
The weighted degree of v.
class networkit.graph.GraphTools
static getCompactedGraph(Graph graph, nodeIdMap)

Computes a graph with the same structure but with continuous node ids.

static getContinuousNodeIds(Graph graph)

Computes a map of node ids to continuous node ids.

static getRandomContinuousNodeIds(Graph graph)

Computes a map of node ids to continuous, randomly permutated node ids.

class networkit.graph.RandomMaximumSpanningForest

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

G : Graph
The input graph.
attribute : list
If given, this edge attribute is used instead of the edge weights.
getAttribute(self, bool move=False)

Get a boolean 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 : boolean
If the attribute shall be moved out of the algorithm instance.
list
The list with the boolean attribute for each edge.
getMSF(self, bool move=False)

Gets the calculated maximum-weight spanning forest as graph.

move : boolean
If the graph shall be moved out of the algorithm instance.
Graph
The calculated maximum-weight spanning forest.
inMSF(self, node u, node v=_none)

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

u : node or edgeid
The first node of the edge to check or the edge id of the edge to check
v : node
The second node of the edge to check (only if u is not an edge id)
boolean
If the edge is part of the calculated maximum-weight spanning forest.
class networkit.graph.SpanningForest

Generates a spanning forest for a given graph

G : Graph
The graph.
nodes : list
A subset of nodes of G which induce the subgraph.
generate(self)
class networkit.graph.UnionMaximumSpanningForest

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

G : Graph
The input graph.
attribute : list
If given, this edge attribute is used instead of the edge weights.
getAttribute(self, bool move=False)

Get a boolean 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 : boolean
If the attribute shall be moved out of the algorithm instance.
list
The list with the boolean attribute for each edge.
getUMSF(self, bool move=False)

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

move : boolean
If the graph shall be moved out of the algorithm instance.
Graph
The calculated union of all maximum-weight spanning forests.
inUMST(self, node u, node v=_none)

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

u : node or edgeid
The first node of the edge to check or the edge id of the edge to check
v : node
The second node of the edge to check (only if u is not an edge id)
boolean
If the edge is part of any maximum-weight spanning forest.