Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / utils / misc.py @ 5cef0f13

History | View | Annotate | Download (12 KB)

1
"""
2
Miscellaneous Helpers for NetworkX.
3

4
These are not imported into the base networkx namespace but
5
can be accessed, for example, as
6

7
>>> import networkx
8
>>> networkx.utils.is_string_like('spam')
9
True
10
"""
11
# Authors:      Aric Hagberg (hagberg@lanl.gov),
12
#               Dan Schult(dschult@colgate.edu),
13
#               Ben Edwards(bedwards@cs.unm.edu)
14

    
15
#    Copyright (C) 2004-2019 by
16
#    Aric Hagberg <hagberg@lanl.gov>
17
#    Dan Schult <dschult@colgate.edu>
18
#    Pieter Swart <swart@lanl.gov>
19
#    All rights reserved.
20
#    BSD license.
21
from collections import defaultdict
22
from collections import deque
23
import warnings
24
import sys
25
import uuid
26
from itertools import tee, chain
27
import networkx as nx
28

    
29
# itertools.accumulate is only available on Python 3.2 or later.
30
#
31
# Once support for Python versions less than 3.2 is dropped, this code should
32
# be removed.
33
try:
34
    from itertools import accumulate
35
except ImportError:
36
    import operator
37

    
38
    # The code for this function is from the Python 3.5 documentation,
39
    # distributed under the PSF license:
40
    # <https://docs.python.org/3.5/library/itertools.html#itertools.accumulate>
41
    def accumulate(iterable, func=operator.add):
42
        it = iter(iterable)
43
        try:
44
            total = next(it)
45
        except StopIteration:
46
            return
47
        yield total
48
        for element in it:
49
            total = func(total, element)
50
            yield total
51

    
52
# 2.x/3.x compatibility
53
try:
54
    basestring
55
except NameError:
56
    basestring = str
57
    unicode = str
58

    
59
# some cookbook stuff
60
# used in deciding whether something is a bunch of nodes, edges, etc.
61
# see G.add_nodes and others in Graph Class in networkx/base.py
62

    
63

    
64
def is_string_like(obj):  # from John Hunter, types-free version
65
    """Check if obj is string."""
66
    return isinstance(obj, basestring)
67

    
68

    
69
def iterable(obj):
70
    """ Return True if obj is iterable with a well-defined len()."""
71
    if hasattr(obj, "__iter__"):
72
        return True
73
    try:
74
        len(obj)
75
    except:
76
        return False
77
    return True
78

    
79

    
80
def flatten(obj, result=None):
81
    """ Return flattened version of (possibly nested) iterable object. """
82
    if not iterable(obj) or is_string_like(obj):
83
        return obj
84
    if result is None:
85
        result = []
86
    for item in obj:
87
        if not iterable(item) or is_string_like(item):
88
            result.append(item)
89
        else:
90
            flatten(item, result)
91
    return obj.__class__(result)
92

    
93

    
94
def is_list_of_ints(intlist):
95
    """ Return True if list is a list of ints. """
96
    if not isinstance(intlist, list):
97
        return False
98
    for i in intlist:
99
        if not isinstance(i, int):
100
            return False
101
    return True
102

    
103

    
104
PY2 = sys.version_info[0] == 2
105
if PY2:
106
    def make_str(x):
107
        """Returns the string representation of t."""
108
        if isinstance(x, unicode):
109
            return x
110
        else:
111
            # Note, this will not work unless x is ascii-encoded.
112
            # That is good, since we should be working with unicode anyway.
113
            # Essentially, unless we are reading a file, we demand that users
114
            # convert any encoded strings to unicode before using the library.
115
            #
116
            # Also, the str() is necessary to convert integers, etc.
117
            # unicode(3) works, but unicode(3, 'unicode-escape') wants a buffer
118
            #
119
            return unicode(str(x), 'unicode-escape')
120
else:
121
    def make_str(x):
122
        """Returns the string representation of t."""
123
        return str(x)
124

    
125

    
126
def generate_unique_node():
127
    """ Generate a unique node label."""
128
    return str(uuid.uuid1())
129

    
130

    
131
def default_opener(filename):
132
    """Opens `filename` using system's default program.
133

134
    Parameters
135
    ----------
136
    filename : str
137
        The path of the file to be opened.
138

139
    """
140
    from subprocess import call
141

    
142
    cmds = {'darwin': ['open'],
143
            'linux': ['xdg-open'],
144
            'linux2': ['xdg-open'],
145
            'win32': ['cmd.exe', '/C', 'start', '']}
146
    cmd = cmds[sys.platform] + [filename]
147
    call(cmd)
148

    
149

    
150
def dict_to_numpy_array(d, mapping=None):
151
    """Convert a dictionary of dictionaries to a numpy array
152
    with optional mapping."""
153
    try:
154
        return dict_to_numpy_array2(d, mapping)
155
    except (AttributeError, TypeError):
156
        # AttributeError is when no mapping was provided and v.keys() fails.
157
        # TypeError is when a mapping was provided and d[k1][k2] fails.
158
        return dict_to_numpy_array1(d, mapping)
159

    
160

    
161
def dict_to_numpy_array2(d, mapping=None):
162
    """Convert a dictionary of dictionaries to a 2d numpy array
163
    with optional mapping.
164

165
    """
166
    import numpy
167
    if mapping is None:
168
        s = set(d.keys())
169
        for k, v in d.items():
170
            s.update(v.keys())
171
        mapping = dict(zip(s, range(len(s))))
172
    n = len(mapping)
173
    a = numpy.zeros((n, n))
174
    for k1, i in mapping.items():
175
        for k2, j in mapping.items():
176
            try:
177
                a[i, j] = d[k1][k2]
178
            except KeyError:
179
                pass
180
    return a
181

    
182

    
183
def dict_to_numpy_array1(d, mapping=None):
184
    """Convert a dictionary of numbers to a 1d numpy array
185
    with optional mapping.
186

187
    """
188
    import numpy
189
    if mapping is None:
190
        s = set(d.keys())
191
        mapping = dict(zip(s, range(len(s))))
192
    n = len(mapping)
193
    a = numpy.zeros(n)
194
    for k1, i in mapping.items():
195
        i = mapping[k1]
196
        a[i] = d[k1]
197
    return a
198

    
199

    
200
def is_iterator(obj):
201
    """Returns True if and only if the given object is an iterator
202
    object.
203

204
    """
205
    has_next_attr = hasattr(obj, '__next__') or hasattr(obj, 'next')
206
    return iter(obj) is obj and has_next_attr
207

    
208

    
209
def arbitrary_element(iterable):
210
    """Returns an arbitrary element of `iterable` without removing it.
211

212
    This is most useful for "peeking" at an arbitrary element of a set,
213
    but can be used for any list, dictionary, etc., as well::
214

215
        >>> arbitrary_element({3, 2, 1})
216
        1
217
        >>> arbitrary_element('hello')
218
        'h'
219

220
    This function raises a :exc:`ValueError` if `iterable` is an
221
    iterator (because the current implementation of this function would
222
    consume an element from the iterator)::
223

224
        >>> iterator = iter([1, 2, 3])
225
        >>> arbitrary_element(iterator)
226
        Traceback (most recent call last):
227
            ...
228
        ValueError: cannot return an arbitrary item from an iterator
229

230
    """
231
    if is_iterator(iterable):
232
        raise ValueError('cannot return an arbitrary item from an iterator')
233
    # Another possible implementation is ``for x in iterable: return x``.
234
    return next(iter(iterable))
235

    
236

    
237
# Recipe from the itertools documentation.
238
def consume(iterator):
239
    "Consume the iterator entirely."
240
    # Feed the entire iterator into a zero-length deque.
241
    deque(iterator, maxlen=0)
242

    
243

    
244
# Recipe from the itertools documentation.
245
def pairwise(iterable, cyclic=False):
246
    "s -> (s0, s1), (s1, s2), (s2, s3), ..."
247
    a, b = tee(iterable)
248
    first = next(b, None)
249
    if cyclic is True:
250
        return zip(a, chain(b, (first,)))
251
    return zip(a, b)
252

    
253

    
254
def groups(many_to_one):
255
    """Converts a many-to-one mapping into a one-to-many mapping.
256

257
    `many_to_one` must be a dictionary whose keys and values are all
258
    :term:`hashable`.
259

260
    The return value is a dictionary mapping values from `many_to_one`
261
    to sets of keys from `many_to_one` that have that value.
262

263
    For example::
264

265
        >>> from networkx.utils import groups
266
        >>> many_to_one = {'a': 1, 'b': 1, 'c': 2, 'd': 3, 'e': 3}
267
        >>> groups(many_to_one)  # doctest: +SKIP
268
        {1: {'a', 'b'}, 2: {'c'}, 3: {'d', 'e'}}
269

270
    """
271
    one_to_many = defaultdict(set)
272
    for v, k in many_to_one.items():
273
        one_to_many[k].add(v)
274
    return dict(one_to_many)
275

    
276

    
277
def to_tuple(x):
278
    """Converts lists to tuples.
279

280
    For example::
281

282
        >>> from networkx.utils import to_tuple
283
        >>> a_list = [1, 2, [1, 4]]
284
        >>> to_tuple(a_list)
285
        (1, 2, (1, 4))
286

287
    """
288
    if not isinstance(x, (tuple, list)):
289
        return x
290
    return tuple(map(to_tuple, x))
291

    
292

    
293
def create_random_state(random_state=None):
294
    """Returns a numpy.random.RandomState instance depending on input.
295

296
    Parameters
297
    ----------
298
    random_state : int or RandomState instance or None  optional (default=None)
299
        If int, return a numpy.random.RandomState instance set with seed=int.
300
        if numpy.random.RandomState instance, return it.
301
        if None or numpy.random, return the global random number generator used
302
        by numpy.random.
303
    """
304
    import numpy as np
305

    
306
    if random_state is None or random_state is np.random:
307
        return np.random.mtrand._rand
308
    if isinstance(random_state, np.random.RandomState):
309
        return random_state
310
    if isinstance(random_state, int):
311
        return np.random.RandomState(random_state)
312
    msg = '%r cannot be used to generate a numpy.random.RandomState instance'
313
    raise ValueError(msg % random_state)
314

    
315

    
316
class PythonRandomInterface(object):
317
    try:
318
        def __init__(self, rng=None):
319
            import numpy
320
            if rng is None:
321
                self._rng = numpy.random.mtrand._rand
322
            self._rng = rng
323
    except ImportError:
324
        msg = 'numpy not found, only random.random available.'
325
        warnings.warn(msg, ImportWarning)
326

    
327
    def random(self):
328
        return self._rng.random_sample()
329

    
330
    def uniform(self, a, b):
331
        return a + (b - a) * self._rng.random_sample()
332

    
333
    def randrange(self, a, b=None):
334
        return self._rng.randint(a, b)
335

    
336
    def choice(self, seq):
337
        return seq[self._rng.randint(0, len(seq))]
338

    
339
    def gauss(self, mu, sigma):
340
        return self._rng.normal(mu, sigma)
341

    
342
    def shuffle(self, seq):
343
        return self._rng.shuffle(seq)
344

    
345
#    Some methods don't match API for numpy RandomState.
346
#    Commented out versions are not used by NetworkX
347

    
348
    def sample(self, seq, k):
349
        return self._rng.choice(list(seq), size=(k,), replace=False)
350

    
351
    def randint(self, a, b):
352
        return self._rng.randint(a, b + 1)
353

    
354
#    exponential as expovariate with 1/argument,
355
    def expovariate(self, scale):
356
        return self._rng.exponential(1/scale)
357

    
358
#    pareto as paretovariate with 1/argument,
359
    def paretovariate(self, shape):
360
        return self._rng.pareto(shape)
361

    
362
#    weibull as weibullvariate multiplied by beta,
363
#    def weibullvariate(self, alpha, beta):
364
#        return self._rng.weibull(alpha) * beta
365
#
366
#    def triangular(self, low, high, mode):
367
#        return self._rng.triangular(low, mode, high)
368
#
369
#    def choices(self, seq, weights=None, cum_weights=None, k=1):
370
#        return self._rng.choice(seq
371

    
372

    
373
def create_py_random_state(random_state=None):
374
    """Returns a random.Random instance depending on input.
375

376
    Parameters
377
    ----------
378
    random_state : int or random number generator or None (default=None)
379
        If int, return a random.Random instance set with seed=int.
380
        if random.Random instance, return it.
381
        if None or the `random` package, return the global random number
382
        generator used by `random`.
383
        if np.random package, return the global numpy random number
384
        generator wrapped in a PythonRandomInterface class.
385
        if np.random.RandomState instance, return it wrapped in
386
        PythonRandomInterface
387
        if a PythonRandomInterface instance, return it
388
    """
389
    import random
390
    try:
391
        import numpy as np
392
        if random_state is np.random:
393
            return PythonRandomInterface(np.random.mtrand._rand)
394
        if isinstance(random_state, np.random.RandomState):
395
            return PythonRandomInterface(random_state)
396
        if isinstance(random_state, PythonRandomInterface):
397
            return random_state
398
        has_numpy = True
399
    except ImportError:
400
        has_numpy = False
401

    
402
    if random_state is None or random_state is random:
403
        return random._inst
404
    if isinstance(random_state, random.Random):
405
        return random_state
406
    if isinstance(random_state, int):
407
        return random.Random(random_state)
408
    msg = '%r cannot be used to generate a random.Random instance'
409
    raise ValueError(msg % random_state)
410

    
411

    
412
# fixture for nose tests
413
def setup_module(module):
414
    from nose import SkipTest
415
    try:
416
        import numpy
417
    except:
418
        raise SkipTest("NumPy not available")