networkit.graphtools

class networkit.graphtools.GraphTools

Bases: object

static append(G, G1)

Appends graph G1 to graph G as a new subgraph. Performs node id remapping.

Parameters

• G (networkit.Graph) – Graph where G1 will be appended to.

• G1 (networkit.Graph) – Graph that will be appended to G.

static augmentGraph(G)

Augments the input graph in-place as required by ForestCentrality. With respect to the input graph G, the augmented graph has a new root node connected to all the other nodes in the graph.

Parameters

G (networkit.Graph) – The input graph (undirected).

Returns

Returns the node id of the new root node.

Return type

int

static copyNodes(graph)

Copies all nodes of the input graph to a new graph (edges are not copied).

Parameters

graph (networkit.Graph) – The input graph.

Returns

graph – Graph with the same nodes as the input graph (and without any edge).

Return type

networkit.Graph

static createAugmentedGraph(G)

Constructs an augmented graph as required by ForestCentrality. With respect to the input graph G, the augmented graph has a new root node connected to all the other nodes in the graph.

Parameters

G (networkit.Graph) – The input graph (undirected).

Returns

Returns a tuple (G, root) where G is the augmented graph and root is the id of the root node.

Return type

tuple(networkit.Graph, int)

static density(graph)

Get the density of the input graph.

Parameters

graph (networkit.Graph) – The input graph.

Returns

The density of the input graph.

Return type

float

static getCompactedGraph(graph, nodeIdMap)

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

Parameters

• graph (networkit.Graph) – The graph to be compacted.

• nodeIdMap (list(int)) – The map providing the information about the node ids.

Returns

The compacted graph

Return type

networkit.Graph

static getContinuousNodeIds(graph)

Computes a map of node ids to continuous node ids.

Parameters

graph (networkit.Graph) – The graph of which the node id map is wanted.

Returns

Returns the node id map

Return type

list(int)

static getRandomContinuousNodeIds()

getRandomContinuousNodeIds(graph):

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

Parameters

graph (networkit.Graph) – The graph of which the node id map is wanted.

Returns

Returns the node id map

Return type

list(int)

static inVolume(graph, nodes)

Get the inVolume (for all incoming edges) of a subgraph, defined by the input graph and a corresponding subset of nodes.

Parameters

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

• nodes (list(int)) – A vector of nodes from the graph.

Returns

The inVolume of the input graph.

Return type

float

static maxDegree(G)

Returns the maximum out-degree of the graph.

Parameters

G (networkit.Graph) – The input graph.

Returns

The maximum out-degree of the graph.

Return type

int

static maxInDegree(G)

Returns the maximum in-degree of the graph.

Parameters

G (networkit.Graph) – The input graph.

Returns

The maximum in-degree of the graph.

Return type

int

static maxWeightedDegree(G)

Returns the maximum weighted out-degree of the graph.

Parameters

G (networkit.Graph) – The input graph.

Returns

The maximum weighted out-degree of the graph.

Return type

float

static maxWeightedInDegree(G)

Returns the maximum weighted in-degree of the graph.

Parameters

G (networkit.Graph) – The input graph.

Returns

The maximum weighted in-degree of the graph.

Return type

float

static merge(G, G1)

Modifies graph G to be the union of it and graph G1. Nodes with the same ids are identified with each other.

Parameters

• G (networkit.Graph) – Result of the merge.

• G1 (networkit.Graph) – Graph that will be merged with G.

static randomEdge(G, uniformDistribution=False)

Get a random edge of the graph.

Notes

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

Parameters

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

• uniformDistribution (bool, optional) – If the distribution of the edge shall be uniform. Default: False

Returns

Random edge.

Return type

tuple(int, int)

static randomEdges(G, numEdges)

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

Parameters

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

• numEdges (int) – The number of edges to choose.

Returns

List of with numEdges random edges.

Return type

list(tuple(int, int))

static randomNeighbor(G, u)

Returns a random neighbor of node u.

Parameters

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

• u (int) – A node in G.

Returns

A random neighbor of u.

Return type

int

static randomNode(G)

Returns a random node of the input graph.

Parameters

G (networkit.Graph) – The input graph.

Returns

A random node.

Return type

int

static randomNodes(G, n)

Returns n distinct random nodes of the input graph.

Parameters

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

• n (int) – The number of desired nodes.

Returns

A list of distinct random nodes.

Return type

list(int)

static randomizeWeights(G)

Randomizes the weights of the given graph. The weights are uniformly distributed in the range [0, 1] by default, unless a different distribution is provided. However it is only strictly in-place for already weighted graphs. For unweighted graphs a copy is created before randomizing weights.

Parameters

G (networkit.Graph) – The input graph.

static removeEdgesFromIsolatedSet(graph, nodes)

Efficiently removes all the edges adjacent to a set of nodes that is not connected to the rest of the graph. This is meant to optimize the Kadabra algorithm.

Parameters

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

• nodes (list(int)) – Isolates set of nodes from where the edges will be removed.

static size(graph)

Return the size of the graph.

Returns

a pair (n, m) where n is the number of nodes and m is the number of edges.

Return type

tuple(int, int)

static sortEdgesByWeight(G, decreasing=False)

Sorts the adjacency arrays by edge weight.

Parameters

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

• decreasing (bool, optional) – If True adjacency arrays are sorted by non-increasing edge weights, if False adjacency arrays are sorted by non-decreasing edge weights. Ties are broken by using node ids. Default: False

static subgraphAndNeighborsFromNodes(graph, nodes, includeOutNeighbors=False, includeInNeighbors=False)

Returns an induced subgraph of this graph (including potential edge weights/directions)

There a two relevant sets of nodes:

• Nodes are such passed as arguments.

• Neighbors are empty by default.

The subgraph contains all nodes in Nodes + Neighbors and all edges which have one end point in Nodes and the other in Nodes or Neighbors.

Parameters

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

• nodes (list(int)) – Nodes in the induced subgraph.

• includeOutNeighbors (bool, optional) – If set to True, out-neighbors will also be included. Default: False

• includeInNeighbors (bool, optional) – If set to True, in-neighbors will also be included. Default: False

Returns

graph – Induced subgraph.

Return type

networkit.Graph

static subgraphFromNodes(graph, list(int) nodes, includeOutNeighbors=False, includeInNeighbors=False, compact = False)

Parameters

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

• nodes (list(int)) – Nodes in the induced subgraph.

• includeOutNeighbors (bool, optional) – DEPRECATED. Use subgraphAndNeighborsFromNodes instead. If set to true, out-neighbors will also be included. Default: False

• includeInNeighbors (bool, optional) – DEPRECATED. Use subgraphAndNeighborsFromNodes instead. If set to true, in-neighbors will also be included. Default: False

• compact (bool, optional) – Indicates whether the resulting graph shall have compact, continuous node ids. If False node ids of the input graph are kept. Default: False

Returns

graph – Induced subgraph of the input graph (including potential edge/weight directions).

Return type

networkit.Graph

static toUndirected(graph)

Returns an undirected copy of the input graph.

Parameters

graph (networkit.Graph) – The input graph.

Returns

graph – Undirected copy of the input graph.

Return type

networkit.Graph

static toUnweighted(graph)

Returns an unweighted copy of the input graph.

Parameters

graph (networkit.Graph) – The input graph.

Returns

graph – Unweighted copy of the input graph.

Return type

networkit.Graph

static toWeighted(graph)

Returns a weighted copy of the input graph.

Parameters

graph (networkit.Graph) – The input graph.

Returns

graph – Weighted copy of the input graph.

Return type

networkit.Graph

static topologicalSort(G)

Given a directed graph G, the topology sort algorithm creates one valid topology order of nodes. Undirected graphs are not accepted as input, since a topology sort is a linear ordering of vertices such that for every edge u -> v, node u comes before v in the ordering.

Parameters

G (networkit.Graph) – The directed input graph.

static transpose(graph)

Returns the transpose of the input graph. The graph must be directed.

Parameters

graph (networkit.Graph) – The input graph.

Returns

graph – Transpose of the input graph.

Return type

networkit.Graph

static volume(graph, nodes=None)

Get the volume (for all outgoing edges) of a graph. If a list of nodes of the graph is given, the volume for the corresponding subgraph is computed.

Parameters

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

• nodes (list(int), optional) – List of nodes from the graph.

Returns

The volume of the subgraph.

Return type

float