Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/utils/misc.py: 16%
207 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Miscellaneous Helpers for NetworkX.
4These are not imported into the base networkx namespace but
5can be accessed, for example, as
7>>> import networkx
8>>> networkx.utils.make_list_of_ints({1, 2, 3})
9[1, 2, 3]
10>>> networkx.utils.arbitrary_element({5, 1, 7}) # doctest: +SKIP
111
12"""
14import sys
15import uuid
16import warnings
17from collections import defaultdict, deque
18from collections.abc import Iterable, Iterator, Sized
19from itertools import chain, tee
21import networkx as nx
23__all__ = [
24 "flatten",
25 "make_list_of_ints",
26 "dict_to_numpy_array",
27 "arbitrary_element",
28 "pairwise",
29 "groups",
30 "create_random_state",
31 "create_py_random_state",
32 "PythonRandomInterface",
33 "nodes_equal",
34 "edges_equal",
35 "graphs_equal",
36]
39# some cookbook stuff
40# used in deciding whether something is a bunch of nodes, edges, etc.
41# see G.add_nodes and others in Graph Class in networkx/base.py
44def flatten(obj, result=None):
45 """Return flattened version of (possibly nested) iterable object."""
46 if not isinstance(obj, (Iterable, Sized)) or isinstance(obj, str):
47 return obj
48 if result is None:
49 result = []
50 for item in obj:
51 if not isinstance(item, (Iterable, Sized)) or isinstance(item, str):
52 result.append(item)
53 else:
54 flatten(item, result)
55 return tuple(result)
58def make_list_of_ints(sequence):
59 """Return list of ints from sequence of integral numbers.
61 All elements of the sequence must satisfy int(element) == element
62 or a ValueError is raised. Sequence is iterated through once.
64 If sequence is a list, the non-int values are replaced with ints.
65 So, no new list is created
66 """
67 if not isinstance(sequence, list):
68 result = []
69 for i in sequence:
70 errmsg = f"sequence is not all integers: {i}"
71 try:
72 ii = int(i)
73 except ValueError:
74 raise nx.NetworkXError(errmsg) from None
75 if ii != i:
76 raise nx.NetworkXError(errmsg)
77 result.append(ii)
78 return result
79 # original sequence is a list... in-place conversion to ints
80 for indx, i in enumerate(sequence):
81 errmsg = f"sequence is not all integers: {i}"
82 if isinstance(i, int):
83 continue
84 try:
85 ii = int(i)
86 except ValueError:
87 raise nx.NetworkXError(errmsg) from None
88 if ii != i:
89 raise nx.NetworkXError(errmsg)
90 sequence[indx] = ii
91 return sequence
94def dict_to_numpy_array(d, mapping=None):
95 """Convert a dictionary of dictionaries to a numpy array
96 with optional mapping."""
97 try:
98 return _dict_to_numpy_array2(d, mapping)
99 except (AttributeError, TypeError):
100 # AttributeError is when no mapping was provided and v.keys() fails.
101 # TypeError is when a mapping was provided and d[k1][k2] fails.
102 return _dict_to_numpy_array1(d, mapping)
105def _dict_to_numpy_array2(d, mapping=None):
106 """Convert a dictionary of dictionaries to a 2d numpy array
107 with optional mapping.
109 """
110 import numpy as np
112 if mapping is None:
113 s = set(d.keys())
114 for k, v in d.items():
115 s.update(v.keys())
116 mapping = dict(zip(s, range(len(s))))
117 n = len(mapping)
118 a = np.zeros((n, n))
119 for k1, i in mapping.items():
120 for k2, j in mapping.items():
121 try:
122 a[i, j] = d[k1][k2]
123 except KeyError:
124 pass
125 return a
128def _dict_to_numpy_array1(d, mapping=None):
129 """Convert a dictionary of numbers to a 1d numpy array with optional mapping."""
130 import numpy as np
132 if mapping is None:
133 s = set(d.keys())
134 mapping = dict(zip(s, range(len(s))))
135 n = len(mapping)
136 a = np.zeros(n)
137 for k1, i in mapping.items():
138 i = mapping[k1]
139 a[i] = d[k1]
140 return a
143def arbitrary_element(iterable):
144 """Returns an arbitrary element of `iterable` without removing it.
146 This is most useful for "peeking" at an arbitrary element of a set,
147 but can be used for any list, dictionary, etc., as well.
149 Parameters
150 ----------
151 iterable : `abc.collections.Iterable` instance
152 Any object that implements ``__iter__``, e.g. set, dict, list, tuple,
153 etc.
155 Returns
156 -------
157 The object that results from ``next(iter(iterable))``
159 Raises
160 ------
161 ValueError
162 If `iterable` is an iterator (because the current implementation of
163 this function would consume an element from the iterator).
165 Examples
166 --------
167 Arbitrary elements from common Iterable objects:
169 >>> nx.utils.arbitrary_element([1, 2, 3]) # list
170 1
171 >>> nx.utils.arbitrary_element((1, 2, 3)) # tuple
172 1
173 >>> nx.utils.arbitrary_element({1, 2, 3}) # set
174 1
175 >>> d = {k: v for k, v in zip([1, 2, 3], [3, 2, 1])}
176 >>> nx.utils.arbitrary_element(d) # dict_keys
177 1
178 >>> nx.utils.arbitrary_element(d.values()) # dict values
179 3
181 `str` is also an Iterable:
183 >>> nx.utils.arbitrary_element("hello")
184 'h'
186 :exc:`ValueError` is raised if `iterable` is an iterator:
188 >>> iterator = iter([1, 2, 3]) # Iterator, *not* Iterable
189 >>> nx.utils.arbitrary_element(iterator)
190 Traceback (most recent call last):
191 ...
192 ValueError: cannot return an arbitrary item from an iterator
194 Notes
195 -----
196 This function does not return a *random* element. If `iterable` is
197 ordered, sequential calls will return the same value::
199 >>> l = [1, 2, 3]
200 >>> nx.utils.arbitrary_element(l)
201 1
202 >>> nx.utils.arbitrary_element(l)
203 1
205 """
206 if isinstance(iterable, Iterator):
207 raise ValueError("cannot return an arbitrary item from an iterator")
208 # Another possible implementation is ``for x in iterable: return x``.
209 return next(iter(iterable))
212# Recipe from the itertools documentation.
213def pairwise(iterable, cyclic=False):
214 "s -> (s0, s1), (s1, s2), (s2, s3), ..."
215 a, b = tee(iterable)
216 first = next(b, None)
217 if cyclic is True:
218 return zip(a, chain(b, (first,)))
219 return zip(a, b)
222def groups(many_to_one):
223 """Converts a many-to-one mapping into a one-to-many mapping.
225 `many_to_one` must be a dictionary whose keys and values are all
226 :term:`hashable`.
228 The return value is a dictionary mapping values from `many_to_one`
229 to sets of keys from `many_to_one` that have that value.
231 Examples
232 --------
233 >>> from networkx.utils import groups
234 >>> many_to_one = {"a": 1, "b": 1, "c": 2, "d": 3, "e": 3}
235 >>> groups(many_to_one) # doctest: +SKIP
236 {1: {'a', 'b'}, 2: {'c'}, 3: {'e', 'd'}}
237 """
238 one_to_many = defaultdict(set)
239 for v, k in many_to_one.items():
240 one_to_many[k].add(v)
241 return dict(one_to_many)
244def create_random_state(random_state=None):
245 """Returns a numpy.random.RandomState or numpy.random.Generator instance
246 depending on input.
248 Parameters
249 ----------
250 random_state : int or NumPy RandomState or Generator instance, optional (default=None)
251 If int, return a numpy.random.RandomState instance set with seed=int.
252 if `numpy.random.RandomState` instance, return it.
253 if `numpy.random.Generator` instance, return it.
254 if None or numpy.random, return the global random number generator used
255 by numpy.random.
256 """
257 import numpy as np
259 if random_state is None or random_state is np.random:
260 return np.random.mtrand._rand
261 if isinstance(random_state, np.random.RandomState):
262 return random_state
263 if isinstance(random_state, int):
264 return np.random.RandomState(random_state)
265 if isinstance(random_state, np.random.Generator):
266 return random_state
267 msg = (
268 f"{random_state} cannot be used to create a numpy.random.RandomState or\n"
269 "numpy.random.Generator instance"
270 )
271 raise ValueError(msg)
274class PythonRandomInterface:
275 def __init__(self, rng=None):
276 try:
277 import numpy as np
278 except ImportError:
279 msg = "numpy not found, only random.random available."
280 warnings.warn(msg, ImportWarning)
282 if rng is None:
283 self._rng = np.random.mtrand._rand
284 else:
285 self._rng = rng
287 def random(self):
288 return self._rng.random()
290 def uniform(self, a, b):
291 return a + (b - a) * self._rng.random()
293 def randrange(self, a, b=None):
294 import numpy as np
296 if isinstance(self._rng, np.random.Generator):
297 return self._rng.integers(a, b)
298 return self._rng.randint(a, b)
300 # NOTE: the numpy implementations of `choice` don't support strings, so
301 # this cannot be replaced with self._rng.choice
302 def choice(self, seq):
303 import numpy as np
305 if isinstance(self._rng, np.random.Generator):
306 idx = self._rng.integers(0, len(seq))
307 else:
308 idx = self._rng.randint(0, len(seq))
309 return seq[idx]
311 def gauss(self, mu, sigma):
312 return self._rng.normal(mu, sigma)
314 def shuffle(self, seq):
315 return self._rng.shuffle(seq)
317 # Some methods don't match API for numpy RandomState.
318 # Commented out versions are not used by NetworkX
320 def sample(self, seq, k):
321 return self._rng.choice(list(seq), size=(k,), replace=False)
323 def randint(self, a, b):
324 import numpy as np
326 if isinstance(self._rng, np.random.Generator):
327 return self._rng.integers(a, b + 1)
328 return self._rng.randint(a, b + 1)
330 # exponential as expovariate with 1/argument,
331 def expovariate(self, scale):
332 return self._rng.exponential(1 / scale)
334 # pareto as paretovariate with 1/argument,
335 def paretovariate(self, shape):
336 return self._rng.pareto(shape)
339# weibull as weibullvariate multiplied by beta,
340# def weibullvariate(self, alpha, beta):
341# return self._rng.weibull(alpha) * beta
342#
343# def triangular(self, low, high, mode):
344# return self._rng.triangular(low, mode, high)
345#
346# def choices(self, seq, weights=None, cum_weights=None, k=1):
347# return self._rng.choice(seq
350def create_py_random_state(random_state=None):
351 """Returns a random.Random instance depending on input.
353 Parameters
354 ----------
355 random_state : int or random number generator or None (default=None)
356 If int, return a random.Random instance set with seed=int.
357 if random.Random instance, return it.
358 if None or the `random` package, return the global random number
359 generator used by `random`.
360 if np.random package, return the global numpy random number
361 generator wrapped in a PythonRandomInterface class.
362 if np.random.RandomState or np.random.Generator instance, return it
363 wrapped in PythonRandomInterface
364 if a PythonRandomInterface instance, return it
365 """
366 import random
368 try:
369 import numpy as np
371 if random_state is np.random:
372 return PythonRandomInterface(np.random.mtrand._rand)
373 if isinstance(random_state, (np.random.RandomState, np.random.Generator)):
374 return PythonRandomInterface(random_state)
375 if isinstance(random_state, PythonRandomInterface):
376 return random_state
377 except ImportError:
378 pass
380 if random_state is None or random_state is random:
381 return random._inst
382 if isinstance(random_state, random.Random):
383 return random_state
384 if isinstance(random_state, int):
385 return random.Random(random_state)
386 msg = f"{random_state} cannot be used to generate a random.Random instance"
387 raise ValueError(msg)
390def nodes_equal(nodes1, nodes2):
391 """Check if nodes are equal.
393 Equality here means equal as Python objects.
394 Node data must match if included.
395 The order of nodes is not relevant.
397 Parameters
398 ----------
399 nodes1, nodes2 : iterables of nodes, or (node, datadict) tuples
401 Returns
402 -------
403 bool
404 True if nodes are equal, False otherwise.
405 """
406 nlist1 = list(nodes1)
407 nlist2 = list(nodes2)
408 try:
409 d1 = dict(nlist1)
410 d2 = dict(nlist2)
411 except (ValueError, TypeError):
412 d1 = dict.fromkeys(nlist1)
413 d2 = dict.fromkeys(nlist2)
414 return d1 == d2
417def edges_equal(edges1, edges2):
418 """Check if edges are equal.
420 Equality here means equal as Python objects.
421 Edge data must match if included.
422 The order of the edges is not relevant.
424 Parameters
425 ----------
426 edges1, edges2 : iterables of with u, v nodes as
427 edge tuples (u, v), or
428 edge tuples with data dicts (u, v, d), or
429 edge tuples with keys and data dicts (u, v, k, d)
431 Returns
432 -------
433 bool
434 True if edges are equal, False otherwise.
435 """
436 from collections import defaultdict
438 d1 = defaultdict(dict)
439 d2 = defaultdict(dict)
440 c1 = 0
441 for c1, e in enumerate(edges1):
442 u, v = e[0], e[1]
443 data = [e[2:]]
444 if v in d1[u]:
445 data = d1[u][v] + data
446 d1[u][v] = data
447 d1[v][u] = data
448 c2 = 0
449 for c2, e in enumerate(edges2):
450 u, v = e[0], e[1]
451 data = [e[2:]]
452 if v in d2[u]:
453 data = d2[u][v] + data
454 d2[u][v] = data
455 d2[v][u] = data
456 if c1 != c2:
457 return False
458 # can check one direction because lengths are the same.
459 for n, nbrdict in d1.items():
460 for nbr, datalist in nbrdict.items():
461 if n not in d2:
462 return False
463 if nbr not in d2[n]:
464 return False
465 d2datalist = d2[n][nbr]
466 for data in datalist:
467 if datalist.count(data) != d2datalist.count(data):
468 return False
469 return True
472def graphs_equal(graph1, graph2):
473 """Check if graphs are equal.
475 Equality here means equal as Python objects (not isomorphism).
476 Node, edge and graph data must match.
478 Parameters
479 ----------
480 graph1, graph2 : graph
482 Returns
483 -------
484 bool
485 True if graphs are equal, False otherwise.
486 """
487 return (
488 graph1.adj == graph2.adj
489 and graph1.nodes == graph2.nodes
490 and graph1.graph == graph2.graph
491 )