File: graphical.py

package info (click to toggle)
python-networkx 1.7~rc1-3
  • links: PTS, VCS
  • area: main
  • in suites: wheezy
  • size: 4,128 kB
  • sloc: python: 44,557; makefile: 135
file content (162 lines) | stat: -rw-r--r-- 4,901 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
# -*- coding: utf-8 -*-
"""Generate graphs with a given degree sequence or expected degree sequence.
"""
#    Copyright (C) 2004-2012 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
import networkx as nx
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
                        'Pieter Swart (swart@lanl.gov)',
                        'Dan Schult (dschult@colgate.edu)'
                        'Joel Miller (joel.c.miller.research@gmail.com)'
                        'Ben Edwards'])

__all__ = ['is_valid_degree_sequence',
           'is_valid_degree_sequence_erdos_gallai',
           'is_valid_degree_sequence_havel_hakimi']

def is_valid_degree_sequence(sequence, method='hh'):
    """Returns True if the sequence is a valid degree sequence.

    A degree sequence is valid if some graph can realize it.

    Parameters
    ----------
    sequence : list or iterable container
        A sequence of integer node degrees

    method : "eg" | "hh"
        The method used to validate the degree sequence.
        "eg" corresponds to the Erdős-Gallai algorithm, and
        "hh" to the Havel-Hakimi algorithm.

    Returns
    -------
    valid : bool
        True if the sequence is a valid degree sequence and False if not.

    Examples
    --------
    >>> G = nx.path_graph(4)
    >>> sequence = G.degree().values()
    >>> nx.is_valid_degree_sequence(sequence)
    True

    References
    ----------
    Erdős-Gallai
        [EG1960]_, [choudum1986]_

    Havel-Hakimi
        [havel1955]_, [hakimi1962]_, [CL1996]_
    """
    if method == 'eg':
        valid = is_valid_degree_sequence_erdos_gallai(sequence)
    elif method == 'hh':
        valid = is_valid_degree_sequence_havel_hakimi(sequence)
    else:
        msg = "`method` must be 'eg' or 'hh'"
        raise nx.NetworkXException(msg)
    return valid


def is_valid_degree_sequence_havel_hakimi(sequence):
    r"""Returns True if the sequence is a valid degree sequence.

    A degree sequence is valid if some graph can realize it.
    Validation proceeds via the Havel-Hakimi algorithm.

    Worst-case run time is: `O(n^(log n))`

    Parameters
    ----------
    sequence : list or iterable container
        A sequence of integer node degrees

    Returns
    -------
    valid : bool
        True if the sequence is a valid degree sequence and False if not.

    References
    ----------
    [havel1955]_, [hakimi1962]_, [CL1996]_
    """
    s = list(sequence)  # copy to list
    # some simple tests
    if len(s) == 0:
        return True # empty sequence = empty graph
    if not nx.utils.is_list_of_ints(s):
        return False   # list of ints
    if min(s)<0:
        return False      # each int not negative
    if sum(s)%2:
        return False      # must be even

    # successively reduce degree sequence by removing node of maximum degree
    # as in Havel-Hakimi algorithm
    while s:
        s.sort()    # sort in increasing order
        if s[0]<0:
            return False  # check if removed too many from some node

        d=s.pop()             # pop largest degree
        if d==0: return True  # done! rest must be zero due to ordering

        # degree must be <= number of available nodes
        if d>len(s):   return False

        # remove edges to nodes of next higher degrees
        #s.reverse()  # to make it easy to get at higher degree nodes.
        for i in range(len(s)-1,len(s)-(d+1),-1):
            s[i]-=1

    # should never get here b/c either d==0, d>len(s) or d<0 before s=[]
    return False


def is_valid_degree_sequence_erdos_gallai(sequence):
    r"""Returns True if the sequence is a valid degree sequence.

    A degree sequence is valid if some graph can realize it.
    Validation proceeds via the Erdős-Gallai algorithm.

    Worst-case run time is: `O(n^2)`

    Parameters
    ----------
    sequence : list or iterable container
        A sequence of integer node degrees 

    Returns
    -------
    valid : bool
        True if the sequence is a valid degree sequence and False if not.

    References
    ----------
    [EG1960]_, [choudum1986]_
    """
    deg_seq = sorted(sequence,reverse=True)
    n = len(deg_seq)
    # some simple tests
    if n == 0:
        return True # empty sequence = empty graph
    if not nx.utils.is_list_of_ints(deg_seq):
        return False   # list of ints
    if min(deg_seq)<0:
        return False      # each int not negative
    if sum(deg_seq)%2:
        return False      # must be even

    sigk = [i for i in range(1, len(deg_seq)) if deg_seq[i] < deg_seq[i-1]]
    for k in sigk:
        sum_deg = sum(deg_seq[0:k])
        sum_min = k*(k-1) + sum([min([k,deg_seq[i]])
                                 for i in range(k,n)])
        if sum_deg>sum_min:
            return False
    return True