lib/python2.7/site-packages/setoolsgui/networkx/algorithms/centrality/current_flow_betweenness_subset.py - platform/prebuilts/python/linux-x86/2.7.5 - Git at Google

 """
 Current-flow betweenness centrality measures for subsets of nodes.
 """
 #    Copyright (C) 2010-2011 by
 #    Aric Hagberg <hagberg@lanl.gov>
 #    Dan Schult <dschult@colgate.edu>
 #    Pieter Swart <swart@lanl.gov>
 #    All rights reserved.
 #    BSD license.
 __author__ = """Aric Hagberg (hagberg@lanl.gov)"""

 __all__ = ['current_flow_betweenness_centrality_subset',
            'edge_current_flow_betweenness_centrality_subset']

 import itertools
 import networkx as nx
 from networkx.algorithms.centrality.flow_matrix import *


 def current_flow_betweenness_centrality_subset(G,sources,targets,
                                                normalized=True,
                                                weight='weight',
                                                dtype=float, solver='lu'):
     r"""Compute current-flow betweenness centrality for subsets of nodes.

     Current-flow betweenness centrality uses an electrical current
     model for information spreading in contrast to betweenness
     centrality which uses shortest paths.

     Current-flow betweenness centrality is also known as
     random-walk betweenness centrality [2]_.

     Parameters
     ----------
     G : graph
       A NetworkX graph

     sources: list of nodes
       Nodes to use as sources for current

     targets: list of nodes
       Nodes to use as sinks for current

     normalized : bool, optional (default=True)
       If True the betweenness values are normalized by b=b/(n-1)(n-2) where
       n is the number of nodes in G.

     weight : string or None, optional (default='weight')
       Key for edge data used as the edge weight.
       If None, then use 1 as each edge weight.

     dtype: data type (float)
       Default data type for internal matrices.
       Set to np.float32 for lower memory consumption.

     solver: string (default='lu')
        Type of linear solver to use for computing the flow matrix.
        Options are "full" (uses most memory), "lu" (recommended), and
        "cg" (uses least memory).

     Returns
     -------
     nodes : dictionary
        Dictionary of nodes with betweenness centrality as the value.

     See Also
     --------
     approximate_current_flow_betweenness_centrality
     betweenness_centrality
     edge_betweenness_centrality
     edge_current_flow_betweenness_centrality

     Notes
     -----
     Current-flow betweenness can be computed in `O(I(n-1)+mn \log n)`
     time [1]_, where `I(n-1)` is the time needed to compute the
     inverse Laplacian.  For a full matrix this is `O(n^3)` but using
     sparse methods you can achieve `O(nm{\sqrt k})` where `k` is the
     Laplacian matrix condition number.

     The space required is `O(nw) where `w` is the width of the sparse
     Laplacian matrix.  Worse case is `w=n` for `O(n^2)`.

     If the edges have a 'weight' attribute they will be used as
     weights in this algorithm.  Unspecified weights are set to 1.

     References
     ----------
     .. [1] Centrality Measures Based on Current Flow.
        Ulrik Brandes and Daniel Fleischer,
        Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
        LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
        http://www.inf.uni-konstanz.de/algo/publications/bf-cmbcf-05.pdf

     .. [2] A measure of betweenness centrality based on random walks,
        M. E. J. Newman, Social Networks 27, 39-54 (2005).
     """
     from networkx.utils import reverse_cuthill_mckee_ordering
     try:
         import numpy as np
     except ImportError:
         raise ImportError('current_flow_betweenness_centrality requires NumPy ',
                           'http://scipy.org/')
     try:
         import scipy
     except ImportError:
         raise ImportError('current_flow_betweenness_centrality requires SciPy ',
                           'http://scipy.org/')
     if G.is_directed():
         raise nx.NetworkXError('current_flow_betweenness_centrality() ',
                                'not defined for digraphs.')
     if not nx.is_connected(G):
         raise nx.NetworkXError("Graph not connected.")
     n = G.number_of_nodes()
     ordering = list(reverse_cuthill_mckee_ordering(G))
     # make a copy with integer labels according to rcm ordering
     # this could be done without a copy if we really wanted to
     mapping=dict(zip(ordering,range(n)))
     H = nx.relabel_nodes(G,mapping)
     betweenness = dict.fromkeys(H,0.0) # b[v]=0 for v in H
     for row,(s,t) in flow_matrix_row(H, weight=weight, dtype=dtype,
                                      solver=solver):
         for ss in sources:
             i=mapping[ss]
             for tt in targets:
                 j=mapping[tt]
                 betweenness[s]+=0.5*np.abs(row[i]-row[j])
                 betweenness[t]+=0.5*np.abs(row[i]-row[j])
     if normalized:
         nb=(n-1.0)*(n-2.0) # normalization factor
     else:
         nb=2.0
     for v in H:
         betweenness[v]=betweenness[v]/nb+1.0/(2-n)
     return dict((ordering[k],v) for k,v in betweenness.items())


 def edge_current_flow_betweenness_centrality_subset(G, sources, targets,
                                                     normalized=True,
                                                     weight='weight',
                                                     dtype=float, solver='lu'):
     """Compute current-flow betweenness centrality for edges using subsets
     of nodes.

     Current-flow betweenness centrality uses an electrical current
     model for information spreading in contrast to betweenness
     centrality which uses shortest paths.

     Current-flow betweenness centrality is also known as
     random-walk betweenness centrality [2]_.

     Parameters
     ----------
     G : graph
       A NetworkX graph

     sources: list of nodes
       Nodes to use as sources for current

     targets: list of nodes
       Nodes to use as sinks for current

     normalized : bool, optional (default=True)
       If True the betweenness values are normalized by b=b/(n-1)(n-2) where
       n is the number of nodes in G.

     weight : string or None, optional (default='weight')
       Key for edge data used as the edge weight.
       If None, then use 1 as each edge weight.

     dtype: data type (float)
       Default data type for internal matrices.
       Set to np.float32 for lower memory consumption.

     solver: string (default='lu')
        Type of linear solver to use for computing the flow matrix.
        Options are "full" (uses most memory), "lu" (recommended), and
        "cg" (uses least memory).

     Returns
     -------
     nodes : dictionary
        Dictionary of edge tuples with betweenness centrality as the value.

     See Also
     --------
     betweenness_centrality
     edge_betweenness_centrality
     current_flow_betweenness_centrality

     Notes
     -----
     Current-flow betweenness can be computed in `O(I(n-1)+mn \log n)`
     time [1]_, where `I(n-1)` is the time needed to compute the
     inverse Laplacian.  For a full matrix this is `O(n^3)` but using
     sparse methods you can achieve `O(nm{\sqrt k})` where `k` is the
     Laplacian matrix condition number.

     The space required is `O(nw) where `w` is the width of the sparse
     Laplacian matrix.  Worse case is `w=n` for `O(n^2)`.

     If the edges have a 'weight' attribute they will be used as
     weights in this algorithm.  Unspecified weights are set to 1.

     References
     ----------
     .. [1] Centrality Measures Based on Current Flow.
        Ulrik Brandes and Daniel Fleischer,
        Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
        LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
        http://www.inf.uni-konstanz.de/algo/publications/bf-cmbcf-05.pdf

     .. [2] A measure of betweenness centrality based on random walks,
        M. E. J. Newman, Social Networks 27, 39-54 (2005).
     """
     from networkx.utils import reverse_cuthill_mckee_ordering
     try:
         import numpy as np
     except ImportError:
         raise ImportError('current_flow_betweenness_centrality requires NumPy ',
                           'http://scipy.org/')
     try:
         import scipy
     except ImportError:
         raise ImportError('current_flow_betweenness_centrality requires SciPy ',
                           'http://scipy.org/')
     if G.is_directed():
         raise nx.NetworkXError('edge_current_flow_betweenness_centrality ',
                                'not defined for digraphs.')
     if not nx.is_connected(G):
         raise nx.NetworkXError("Graph not connected.")
     n = G.number_of_nodes()
     ordering = list(reverse_cuthill_mckee_ordering(G))
     # make a copy with integer labels according to rcm ordering
     # this could be done without a copy if we really wanted to
     mapping=dict(zip(ordering,range(n)))
     H = nx.relabel_nodes(G,mapping)
     betweenness=(dict.fromkeys(H.edges(),0.0))
     if normalized:
         nb=(n-1.0)*(n-2.0) # normalization factor
     else:
         nb=2.0
     for row,(e) in flow_matrix_row(H, weight=weight, dtype=dtype,
                                    solver=solver):
         for ss in sources:
             i=mapping[ss]
             for tt in targets:
                 j=mapping[tt]
                 betweenness[e]+=0.5*np.abs(row[i]-row[j])
         betweenness[e]/=nb
     return dict(((ordering[s],ordering[t]),v)
                 for (s,t),v in betweenness.items())


 # fixture for nose tests
 def setup_module(module):
     from nose import SkipTest
     try:
         import numpy
         import scipy
     except:
         raise SkipTest("NumPy not available")
	"""
	Current-flow betweenness centrality measures for subsets of nodes.
	"""
	# Copyright (C) 2010-2011 by
	# Aric Hagberg <hagberg@lanl.gov>
	# Dan Schult <dschult@colgate.edu>
	# Pieter Swart <swart@lanl.gov>
	# All rights reserved.
	# BSD license.
	__author__ = """Aric Hagberg (hagberg@lanl.gov)"""

	__all__ = ['current_flow_betweenness_centrality_subset',
	'edge_current_flow_betweenness_centrality_subset']

	import itertools
	import networkx as nx
	from networkx.algorithms.centrality.flow_matrix import *


	def current_flow_betweenness_centrality_subset(G,sources,targets,
	normalized=True,
	weight='weight',
	dtype=float, solver='lu'):
	r"""Compute current-flow betweenness centrality for subsets of nodes.

	Current-flow betweenness centrality uses an electrical current
	model for information spreading in contrast to betweenness
	centrality which uses shortest paths.

	Current-flow betweenness centrality is also known as
	random-walk betweenness centrality [2]_.

	Parameters
	----------
	G : graph
	A NetworkX graph

	sources: list of nodes
	Nodes to use as sources for current

	targets: list of nodes
	Nodes to use as sinks for current

	normalized : bool, optional (default=True)
	If True the betweenness values are normalized by b=b/(n-1)(n-2) where
	n is the number of nodes in G.

	weight : string or None, optional (default='weight')
	Key for edge data used as the edge weight.
	If None, then use 1 as each edge weight.

	dtype: data type (float)
	Default data type for internal matrices.
	Set to np.float32 for lower memory consumption.

	solver: string (default='lu')
	Type of linear solver to use for computing the flow matrix.
	Options are "full" (uses most memory), "lu" (recommended), and
	"cg" (uses least memory).

	Returns
	-------
	nodes : dictionary
	Dictionary of nodes with betweenness centrality as the value.

	See Also
	--------
	approximate_current_flow_betweenness_centrality
	betweenness_centrality
	edge_betweenness_centrality
	edge_current_flow_betweenness_centrality

	Notes
	-----
	Current-flow betweenness can be computed in `O(I(n-1)+mn \log n)`
	time [1]_, where `I(n-1)` is the time needed to compute the
	inverse Laplacian. For a full matrix this is `O(n^3)` but using
	sparse methods you can achieve `O(nm{\sqrt k})` where `k` is the
	Laplacian matrix condition number.

	The space required is `O(nw) where `w` is the width of the sparse
	Laplacian matrix. Worse case is `w=n` for `O(n^2)`.

	If the edges have a 'weight' attribute they will be used as
	weights in this algorithm. Unspecified weights are set to 1.

	References
	----------
	.. [1] Centrality Measures Based on Current Flow.
	Ulrik Brandes and Daniel Fleischer,
	Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
	LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
	http://www.inf.uni-konstanz.de/algo/publications/bf-cmbcf-05.pdf

	.. [2] A measure of betweenness centrality based on random walks,
	M. E. J. Newman, Social Networks 27, 39-54 (2005).
	"""
	from networkx.utils import reverse_cuthill_mckee_ordering
	try:
	import numpy as np
	except ImportError:
	raise ImportError('current_flow_betweenness_centrality requires NumPy ',
	'http://scipy.org/')
	try:
	import scipy
	except ImportError:
	raise ImportError('current_flow_betweenness_centrality requires SciPy ',
	'http://scipy.org/')
	if G.is_directed():
	raise nx.NetworkXError('current_flow_betweenness_centrality() ',
	'not defined for digraphs.')
	if not nx.is_connected(G):
	raise nx.NetworkXError("Graph not connected.")
	n = G.number_of_nodes()
	ordering = list(reverse_cuthill_mckee_ordering(G))
	# make a copy with integer labels according to rcm ordering
	# this could be done without a copy if we really wanted to
	mapping=dict(zip(ordering,range(n)))
	H = nx.relabel_nodes(G,mapping)
	betweenness = dict.fromkeys(H,0.0) # b[v]=0 for v in H
	for row,(s,t) in flow_matrix_row(H, weight=weight, dtype=dtype,
	solver=solver):
	for ss in sources:
	i=mapping[ss]
	for tt in targets:
	j=mapping[tt]
	betweenness[s]+=0.5*np.abs(row[i]-row[j])
	betweenness[t]+=0.5*np.abs(row[i]-row[j])
	if normalized:
	nb=(n-1.0)*(n-2.0) # normalization factor
	else:
	nb=2.0
	for v in H:
	betweenness[v]=betweenness[v]/nb+1.0/(2-n)
	return dict((ordering[k],v) for k,v in betweenness.items())


	def edge_current_flow_betweenness_centrality_subset(G, sources, targets,
	normalized=True,
	weight='weight',
	dtype=float, solver='lu'):
	"""Compute current-flow betweenness centrality for edges using subsets
	of nodes.

	Current-flow betweenness centrality uses an electrical current
	model for information spreading in contrast to betweenness
	centrality which uses shortest paths.

	Current-flow betweenness centrality is also known as
	random-walk betweenness centrality [2]_.

	Parameters
	----------
	G : graph
	A NetworkX graph

	sources: list of nodes
	Nodes to use as sources for current

	targets: list of nodes
	Nodes to use as sinks for current

	normalized : bool, optional (default=True)
	If True the betweenness values are normalized by b=b/(n-1)(n-2) where
	n is the number of nodes in G.

	weight : string or None, optional (default='weight')
	Key for edge data used as the edge weight.
	If None, then use 1 as each edge weight.

	dtype: data type (float)
	Default data type for internal matrices.
	Set to np.float32 for lower memory consumption.

	solver: string (default='lu')
	Type of linear solver to use for computing the flow matrix.
	Options are "full" (uses most memory), "lu" (recommended), and
	"cg" (uses least memory).

	Returns
	-------
	nodes : dictionary
	Dictionary of edge tuples with betweenness centrality as the value.

	See Also
	--------
	betweenness_centrality
	edge_betweenness_centrality
	current_flow_betweenness_centrality

	Notes
	-----
	Current-flow betweenness can be computed in `O(I(n-1)+mn \log n)`
	time [1]_, where `I(n-1)` is the time needed to compute the
	inverse Laplacian. For a full matrix this is `O(n^3)` but using
	sparse methods you can achieve `O(nm{\sqrt k})` where `k` is the
	Laplacian matrix condition number.

	The space required is `O(nw) where `w` is the width of the sparse
	Laplacian matrix. Worse case is `w=n` for `O(n^2)`.

	If the edges have a 'weight' attribute they will be used as
	weights in this algorithm. Unspecified weights are set to 1.

	References
	----------
	.. [1] Centrality Measures Based on Current Flow.
	Ulrik Brandes and Daniel Fleischer,
	Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
	LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
	http://www.inf.uni-konstanz.de/algo/publications/bf-cmbcf-05.pdf

	.. [2] A measure of betweenness centrality based on random walks,
	M. E. J. Newman, Social Networks 27, 39-54 (2005).
	"""
	from networkx.utils import reverse_cuthill_mckee_ordering
	try:
	import numpy as np
	except ImportError:
	raise ImportError('current_flow_betweenness_centrality requires NumPy ',
	'http://scipy.org/')
	try:
	import scipy
	except ImportError:
	raise ImportError('current_flow_betweenness_centrality requires SciPy ',
	'http://scipy.org/')
	if G.is_directed():
	raise nx.NetworkXError('edge_current_flow_betweenness_centrality ',
	'not defined for digraphs.')
	if not nx.is_connected(G):
	raise nx.NetworkXError("Graph not connected.")
	n = G.number_of_nodes()
	ordering = list(reverse_cuthill_mckee_ordering(G))
	# make a copy with integer labels according to rcm ordering
	# this could be done without a copy if we really wanted to
	mapping=dict(zip(ordering,range(n)))
	H = nx.relabel_nodes(G,mapping)
	betweenness=(dict.fromkeys(H.edges(),0.0))
	if normalized:
	nb=(n-1.0)*(n-2.0) # normalization factor
	else:
	nb=2.0
	for row,(e) in flow_matrix_row(H, weight=weight, dtype=dtype,
	solver=solver):
	for ss in sources:
	i=mapping[ss]
	for tt in targets:
	j=mapping[tt]
	betweenness[e]+=0.5*np.abs(row[i]-row[j])
	betweenness[e]/=nb
	return dict(((ordering[s],ordering[t]),v)
	for (s,t),v in betweenness.items())


	# fixture for nose tests
	def setup_module(module):
	from nose import SkipTest
	try:
	import numpy
	import scipy
	except:
	raise SkipTest("NumPy not available")