Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / stochastic.py @ 5cef0f13

History | View | Annotate | Download (2.09 KB)

1
#    Copyright (C) 2010-2013 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 right-stochastic representation of directed graph `G`.
24

25
    A right-stochastic graph is a weighted digraph in which for each
26
    node, the sum of the weights of all the out-edges 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 in-place (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