ioftools / networkxMiCe / networkxmaster / networkx / generators / stochastic.py @ 5cef0f13
History  View  Annotate  Download (2.09 KB)
1 
# Copyright (C) 20102013 by


2 
# Aric Hagberg <hagberg@lanl.gov>

3 
# Dan Schult <dschult@colgate.edu>

4 
# Pieter Swart <swart@lanl.gov>

5 
# All rights reserved.

6 
# BSD license.

7 
"""Functions for generating stochastic graphs from a given weighted directed

8 
graph.

9 

10 
"""

11 
from __future__ import division 
12  
13 
from networkx.classes import DiGraph 
14 
from networkx.classes import MultiDiGraph 
15 
from networkx.utils import not_implemented_for 
16  
17 
__author__ = "Aric Hagberg <aric.hagberg@gmail.com>"

18 
__all__ = ['stochastic_graph']

19  
20  
21 
@not_implemented_for('undirected') 
22 
def stochastic_graph(G, copy=True, weight='weight'): 
23 
"""Returns a rightstochastic representation of directed graph `G`.

24 

25 
A rightstochastic graph is a weighted digraph in which for each

26 
node, the sum of the weights of all the outedges of that node is

27 
1. If the graph is already weighted (for example, via a 'weight'

28 
edge attribute), the reweighting takes that into account.

29 

30 
Parameters

31 


32 
G : directed graph

33 
A :class:`~networkx.DiGraph` or :class:`~networkx.MultiDiGraph`.

34 

35 
copy : boolean, optional

36 
If this is True, then this function returns a new graph with

37 
the stochastic reweighting. Otherwise, the original graph is

38 
modified inplace (and also returned, for convenience).

39 

40 
weight : edge attribute key (optional, default='weight')

41 
Edge attribute key used for reading the existing weight and

42 
setting the new weight. If no attribute with this key is found

43 
for an edge, then the edge weight is assumed to be 1. If an edge

44 
has a weight, it must be a a positive number.

45 

46 
"""

47 
if copy:

48 
G = MultiDiGraph(G) if G.is_multigraph() else DiGraph(G) 
49 
# There is a tradeoff here: the dictionary of node degrees may

50 
# require a lot of memory, whereas making a call to `G.out_degree`

51 
# inside the loop may be costly in computation time.

52 
degree = dict(G.out_degree(weight=weight))

53 
for u, v, d in G.edges(data=True): 
54 
if degree[u] == 0: 
55 
d[weight] = 0

56 
else:

57 
d[weight] = d.get(weight, 1) / degree[u]

58 
return G
