Secure your code as it's written. Use Snyk Code to scan source code in minutes - no build needed - and fix issues immediately.
-----
This algorithm appears in [1].
This implementation disallows the possibility of generating
disconnected graphs.
References
----------
.. [1] I. Ispolatov, P. L. Krapivsky, A. Yuryev,
"Duplication-divergence model of protein interaction network",
Phys. Rev. E, 71, 061911, 2005.
"""
if p > 1 or p < 0:
msg = "NetworkXError p={0} is not in [0,1].".format(p)
raise nx.NetworkXError(msg)
if n < 2:
msg = 'n must be greater than or equal to 2'
raise nx.NetworkXError(msg)
G = nx.Graph()
# Initialize the graph with two connected nodes.
G.add_edge(0, 1)
i = 2
while i < n:
# Choose a random node from current graph to duplicate.
random_node = seed.choice(list(G))
# Make the replica.
G.add_node(i)
# flag indicates whether at least one edge is connected on the replica.
flag = False
def decode_attr_elements(self, gexf_keys, obj_xml):
# Use the key information to decode the attr XML
attr = {}
# look for outer "" element
attr_element=obj_xml.find("{%s}attvalues" % self.NS_GEXF)
if attr_element is not None:
# loop over elements
for a in attr_element.findall("{%s}attvalue" % self.NS_GEXF):
key = a.get('for') # for is required
try: # should be in our gexf_keys dictionary
title=gexf_keys[key]['title']
except KeyError:
raise nx.NetworkXError("No attribute defined for=%s"%key)
atype=gexf_keys[key]['type']
value=a.get('value')
if atype=='boolean':
value=self.convert_bool[value]
else:
value=self.python_type[atype](value)
if gexf_keys[key]['mode']=='dynamic':
# for dynamic graphs use list of three-tuples
# [(value1,start1,end1), (value2,start2,end2), etc]
start=a.get('start')
end=a.get('end')
if title in attr:
attr[title].append((value,start,end))
else:
attr[title]=[(value,start,end)]
else:
def _sparse_fruchterman_reingold(A, dim=2, k=None, pos=None, fixed=None,
iterations=50):
# Position nodes in adjacency matrix A using Fruchterman-Reingold
# Entry point for NetworkX graph is fruchterman_reingold_layout()
# Sparse version
import numpy as np
try:
nnodes,_=A.shape
except AttributeError:
raise nx.NetworkXError(
"fruchterman_reingold() takes an adjacency matrix as input")
try:
from scipy.sparse import spdiags,coo_matrix
except ImportError:
raise ImportError("_sparse_fruchterman_reingold() scipy numpy: http://scipy.org/ ")
# make sure we have a LIst of Lists representation
try:
A=A.tolil()
except:
A=(coo_matrix(A)).tolil()
if pos is None:
# random initial positions
pos=np.asarray(np.random.random((nnodes,dim)),dtype=A.dtype)
else:
# make sure positions are of same type as matrix
def ford_fulkerson_impl(G, s, t, capacity):
"""Legacy implementation of the Edmonds-Karp algorithm"""
if G.is_multigraph():
raise nx.NetworkXError(
'MultiGraph and MultiDiGraph not supported (yet).')
if s not in G:
raise nx.NetworkXError('node %s not in graph' % str(s))
if t not in G:
raise nx.NetworkXError('node %s not in graph' % str(t))
if s == t:
raise nx.NetworkXError('source and sink are the same node')
auxiliary = _create_auxiliary_digraph(G, capacity=capacity)
inf_capacity_flows = auxiliary.graph['inf_capacity_flows']
flow_value = 0 # Initial feasible flow.
# As long as there is an (s, t)-path in the auxiliary digraph, find
# the shortest (with respect to the number of arcs) such path and
Notes
-----
The initial graph `G` must be connected, and the resulting graph is
connected. The graph `G` is modified in place.
References
----------
.. [1] C. Gkantsidis and M. Mihail and E. Zegura,
The Markov chain simulation method for generating connected
power law random graphs, 2003.
http://citeseer.ist.psu.edu/gkantsidis03markov.html
"""
if not nx.is_connected(G):
raise nx.NetworkXError("Graph not connected")
if len(G) < 4:
raise nx.NetworkXError("Graph has less than four nodes.")
n = 0
swapcount = 0
deg = G.degree()
# Label key for nodes
dk = list(n for n, d in G.degree())
cdf = nx.utils.cumulative_distribution(list(d for n, d in G.degree()))
discrete_sequence = nx.utils.discrete_sequence
window = 1
while n < nswap:
wcount = 0
swapped = []
# If the window is small, we just check each time whether the graph is
# connected by checking if the nodes that were just separated are still
# connected.
-----
The initial graph ``G`` must be connected, and the resulting graph is
connected. The graph ``G`` is modified in place.
References
----------
.. [1] C. Gkantsidis and M. Mihail and E. Zegura,
The Markov chain simulation method for generating connected
power law random graphs, 2003.
http://citeseer.ist.psu.edu/gkantsidis03markov.html
"""
if not nx.is_connected(G):
raise nx.NetworkXError("Graph not connected")
if len(G) < 4:
raise nx.NetworkXError("Graph has less than four nodes.")
n = 0
swapcount = 0
deg = G.degree()
# Label key for nodes
dk = list(deg.keys())
cdf = nx.utils.cumulative_distribution(list(G.degree().values()))
window = 1
while n < nswap:
wcount = 0
swapped = []
# If the window is small, we just check each time whether the graph is
# connected by checking if the nodes that were just separated are still
# connected.
if window < _window_threshold:
# This Boolean keeps track of whether there was a failure or not.
fail = False
def _triangles(G, e):
""" Return list of all triangles containing edge e"""
u, v = e
if u not in G:
raise nx.NetworkXError("Vertex %s not in graph" % u)
if v not in G[u]:
raise nx.NetworkXError("Edge (%s, %s) not in graph" % (u, v))
triangle_list = []
for x in G[u]:
if x in G[v]:
triangle_list.append((u, v, x))
return triangle_list
def decode_data_elements(self, graphml_keys, obj_xml):
"""Use the key information to decode the data XML if present."""
data = {}
for data_element in obj_xml.findall("{%s}data" % self.NS_GRAPHML):
key = data_element.get("key")
try:
data_name=graphml_keys[key]['name']
data_type=graphml_keys[key]['type']
except KeyError:
raise nx.NetworkXError("Bad GraphML data: no key %s"%key)
text=data_element.text
# assume anything with subelements is a yfiles extension
if text is not None and len(list(data_element))==0:
if data_type==bool:
data[data_name] = self.convert_bool[text]
else:
data[data_name] = data_type(text)
elif len(list(data_element)) > 0:
# Assume yfiles as subelements, try to extract node_label
node_label = None
for node_type in ['ShapeNode', 'SVGNode', 'ImageNode']:
geometry = data_element.find("{%s}%s/{%s}Geometry" %
(self.NS_Y, node_type, self.NS_Y))
if geometry is not None:
data['x'] = geometry.get('x')
data['y'] = geometry.get('y')
--------
global_reaching_centrality
References
----------
.. [1] Mones, Enys, Lilla Vicsek, and Tamás Vicsek.
"Hierarchy Measure for Complex Networks."
*PLoS ONE* 7.3 (2012): e33799.
https://doi.org/10.1371/journal.pone.0033799
"""
if paths is None:
if nx.is_negatively_weighted(G, weight=weight):
raise nx.NetworkXError('edge weights must be positive')
total_weight = G.size(weight=weight)
if total_weight <= 0:
raise nx.NetworkXError('Size of G must be positive')
if weight is not None:
# Interpret weights as lengths.
def as_distance(u, v, d): return total_weight / d.get(weight, 1)
paths = nx.shortest_path(G, source=v, weight=as_distance)
else:
paths = nx.shortest_path(G, source=v)
# If the graph is unweighted, simply return the proportion of nodes
# reachable from the source node ``v``.
if weight is None and G.is_directed():
return (len(paths) - 1) / (len(G) - 1)
if normalized and weight is not None:
norm = G.size(weight=weight) / G.size()
else:
norm = 1
# TODO This can be trivially parallelized.
avgw = (_average_weight(G, path, weight=weight) for path in paths.values())
nodes=v
else: # assume it is a single value
nodes=[v]
order=G.order()
e={}
for v in nodes:
if sp is None:
length=networkx.single_source_shortest_path_length(G,v)
L = len(length)
else:
try:
length=sp[v]
L = len(length)
except TypeError:
raise networkx.NetworkXError('Format of "sp" is invalid.')
if L != order:
msg = "Graph not connected: infinite path length"
raise networkx.NetworkXError(msg)
e[v]=max(length.values())
if len(e)==1:
return list(e.values())[0] # return single value
else:
return e