Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Functions for generating stochastic graphs from a given weighted directed
2graph.
4"""
6import networkx as nx
7from networkx.classes import DiGraph, MultiDiGraph
8from networkx.utils import not_implemented_for
10__all__ = ["stochastic_graph"]
13@not_implemented_for("undirected")
14@nx._dispatchable(
15 edge_attrs="weight", mutates_input={"not copy": 1}, returns_graph=True
16)
17def stochastic_graph(G, copy=True, weight="weight"):
18 """Returns a right-stochastic representation of directed graph `G`.
20 A right-stochastic graph is a weighted digraph in which for each
21 node, the sum of the weights of all the out-edges of that node is
22 1. If the graph is already weighted (for example, via a 'weight'
23 edge attribute), the reweighting takes that into account.
25 Parameters
26 ----------
27 G : directed graph
28 A :class:`~networkx.DiGraph` or :class:`~networkx.MultiDiGraph`.
30 copy : boolean, optional
31 If this is True, then this function returns a new graph with
32 the stochastic reweighting. Otherwise, the original graph is
33 modified in-place (and also returned, for convenience).
35 weight : edge attribute key (optional, default='weight')
36 Edge attribute key used for reading the existing weight and
37 setting the new weight. If no attribute with this key is found
38 for an edge, then the edge weight is assumed to be 1. If an edge
39 has a weight, it must be a positive number.
41 """
42 if copy:
43 G = MultiDiGraph(G) if G.is_multigraph() else DiGraph(G)
44 # There is a tradeoff here: the dictionary of node degrees may
45 # require a lot of memory, whereas making a call to `G.out_degree`
46 # inside the loop may be costly in computation time.
47 degree = dict(G.out_degree(weight=weight))
48 for u, v, d in G.edges(data=True):
49 if degree[u] == 0:
50 d[weight] = 0
51 else:
52 d[weight] = d.get(weight, 1) / degree[u]
53 nx._clear_cache(G)
54 return G