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(graph)¶

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.

• 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, nodeIdMap=None, checkMapping=False)¶

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. Node ids must either be continuous or you must provide a continuous node id mapping.

Parameters:

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

• nodeIdMap (dict(int, int), optional) – Optional continuous node id mapping.

• checkMapping (bool, optional) – Flag to determine if the node id mapping should be checked that it is continuous. This check takes O(|V|) time and space.

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