__init__.py 8.87 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#! /usr/bin/env python
# graph_tool.py -- a general graph manipulation python module
#
# Copyright (C) 2007 Tiago de Paula Peixoto <tiago@forked.de>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

19
20
21
22
23
"""
``graph_tool.stats`` - Graph Statistics
---------------------------------------
"""

Tiago Peixoto's avatar
Tiago Peixoto committed
24
25
from .. dl_import import dl_import
dl_import("import libgraph_tool_stats")
Tiago Peixoto's avatar
Tiago Peixoto committed
26

27
from .. core import _degree, _prop
Tiago Peixoto's avatar
Tiago Peixoto committed
28
from numpy import *
29
30
import numpy
import sys
Tiago Peixoto's avatar
Tiago Peixoto committed
31

32
__all__ = ["vertex_hist", "edge_hist", "vertex_average", "edge_average",
33
           "label_parallel_edges", "remove_parallel_edges",
34
35
           "label_self_loops", "remove_self_loops", "remove_labeled_edges",
           "distance_histogram", "sampled_distance_histogram"]
Tiago Peixoto's avatar
Tiago Peixoto committed
36

37
def vertex_hist(g, deg, bins=[1], float_count=True):
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
    """
    Return the vertex histogram of the given degree type or property.

    Parameters
    ----------
    g : Graph
        Graph to be used.

    deg : string or PropertyMap
        Degree or property to be used for the histogram. It can be either "in",
        "out" or "total", for in-, out-, or total degree of the vertices. It can
        also be a vertex property map.

    bins : list of bins
        List of bins to be used for the histogram. The values given represent
        the edges of the bins (i,e, lower bounds). If the list contains only one
        value, this will be used to automatically create an appropriate bin
        range, with a constant lenght given by this value.

    float_count : bool (optional, default: True)
        If True, the counts in each histogram bin will be returned as floats. If
        False, they will be returned as integers.

    Returns
    -------
    counts : ndarray
        The bin counts.

    bins : ndarray
        The bin edges.

    See Also
    --------
    edge_hist: Edge histograms.
    vertex_average: Average of vertex properties, degrees.
    edge_average: Average of edge properties.

    Notes
    -----
    The algorithm runs in :math:`O(|V|)` time.

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
    >>> from numpy.random import poisson, seed
    >>> seed(42)
    >>> g = gt.random_graph(1000, lambda: (poisson(5), poisson(5)), seed=42)
    >>> print gt.vertex_hist(g, "out")
    [array([  10.,   35.,   92.,  140.,  162.,  160.,  150.,  109.,   66.,
             37.,   26.,   10.,    2.,    1.]), array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13], dtype=uint64)]

    """

Tiago Peixoto's avatar
Tiago Peixoto committed
92
    ret = libgraph_tool_stats.\
93
          get_vertex_histogram(g._Graph__graph, _degree(g, deg), bins)
94
    return [array(ret[0], dtype="float64") if float_count else ret[0], ret[1]]
Tiago Peixoto's avatar
Tiago Peixoto committed
95

96
def edge_hist(g, eprop, bins=[1], float_count=True):
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
    """
    Return the edge histogram of the given property.

    Parameters
    ----------
    g : Graph
        Graph to be used.

    eprop : PropertyMap
        Edge property to be used for the histogram.

    bins : list of bins
        List of bins to be used for the histogram. The values given represent
        the edges of the bins (i,e, lower bounds). If the list contains only one
        value, this will be used to automatically create an appropriate bin
        range, with a constant lenght given by this value.

    float_count : bool (optional, default: True)
        If True, the counts in each histogram bin will be returned as floats. If
        False, they will be returned as integers.

    Returns
    -------
    counts : ndarray
        The bin counts.

    bins : ndarray
        The bin edges.

    See Also
    --------
    vertex_hist : Vertex histograms.
    vertex_average : Average of vertex properties, degrees.
    edge_average : Average of edge properties.

    Notes
    -----
    The algorithm runs in :math:`O(|E|)` time.

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
    >>> from numpy import arange
    >>> from numpy.random import random
    >>> g = gt.random_graph(1000, lambda: (5, 5), seed=42)
    >>> eprop = g.new_edge_property("double")
    >>> eprop.get_array()[:] = random(g.num_edges())
    >>> print gt.edge_hist(g, eprop, arange(0, 1, 0.1))
    [array([ 500.,  440.,  487.,  494.,  507.,  496.,  524.,  526.,  486.,  540.]), array([ 0. ,  0.1,  0.2,  0.3,  0.4,  0.5,  0.6,  0.7,  0.8,  0.9])]

    """

Tiago Peixoto's avatar
Tiago Peixoto committed
150
    ret = libgraph_tool_stats.\
151
          get_edge_histogram(g._Graph__graph, _prop("e", g, eprop), bins)
152
    return [array(ret[0], dtype="float64") if float_count else ret[0], ret[1]]
Tiago Peixoto's avatar
Tiago Peixoto committed
153

154
def vertex_average(g, deg):
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
    """
    Return the average of the given degree or vertex property.

    Parameters
    ----------
    g : Graph
        Graph to be used.

    deg : string or PropertyMap
        Degree or property to be used for the histogram. It can be either "in",
        "out" or "total", for in-, out-, or total degree of the vertices. It can
        also be a vertex property map.

    Returns
    -------
    average : float
        The average of the given degree or property.

    std : float
        The standard deviation of the average.

    See Also
    --------
    vertex_hist : Vertex histograms.
    edge_hist : Edge histograms.
    edge_average : Average of edge properties.

    Notes
    -----
    The algorithm runs in :math:`O(|V|)` time.

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
    >>> from numpy.random import poisson, seed
    >>> seed(42)
    >>> g = gt.random_graph(1000, lambda: (poisson(5), poisson(5)), seed=42)
    >>> print gt.vertex_average(g, "in")
    (5.0179999999999998, 0.072661379012512559)
    """

197
198
199
200
201
    ret = libgraph_tool_stats.\
          get_vertex_average(g._Graph__graph, _degree(g, deg))
    return ret

def edge_average(g, eprop):
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
    """
    Return the average of the given degree or vertex property.

    Parameters
    ----------
    g : Graph
        Graph to be used.

    eprop : PropertyMap
        Edge property to be used for the histogram.

    Returns
    -------
    average : float
        The average of the given property.

    std : float
        The standard deviation of the average.

    See Also
    --------
    vertex_hist : Vertex histograms.
    edge_hist : Edge histograms.
    vertex_average : Average of vertex degree, properties.

    Notes
    -----
    The algorithm runs in :math:`O(|E|)` time.

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
    >>> from numpy import arange
    >>> from numpy.random import random
    >>> g = gt.random_graph(1000, lambda: (5, 5), seed=42)
    >>> eprop = g.new_edge_property("double")
    >>> eprop.get_array()[:] = random(g.num_edges())
    >>> print gt.edge_average(g, eprop)
    (0.50951471604395204, 0.0040790901147649975)
    """

244
245
246
247
    ret = libgraph_tool_stats.\
          get_edge_average(g._Graph__graph, _prop("e", g, eprop))
    return ret

248
249
250
251
252
253
254
def remove_labeled_edges(g, label):
    g.stash_filter(all=False, directed=True, reversed=True)
    libgraph_tool_stats.\
          remove_labeled_edges(g._Graph__graph, _prop("e", g, label))
    g.pop_filter(all=False, directed=True, reversed=True)

def label_parallel_edges(g, eprop=None):
255
256
    if eprop == None:
        eprop = g.new_edge_property("int32_t")
Tiago Peixoto's avatar
Tiago Peixoto committed
257
    libgraph_tool_stats.\
258
          label_parallel_edges(g._Graph__graph, _prop("e", g, eprop))
259
    return eprop
Tiago Peixoto's avatar
Tiago Peixoto committed
260

261
262
263
264
265
def remove_parallel_edges(g):
    eprop = label_parallel_edges(g)
    remove_labeled_edges(g, eprop)

def label_self_loops(g, eprop=None):
266
267
    if eprop == None:
        eprop = g.new_edge_property("int32_t")
Tiago Peixoto's avatar
Tiago Peixoto committed
268
    libgraph_tool_stats.\
269
          label_self_loops(g._Graph__graph, _prop("e", g, eprop))
270
    return eprop
271
272
273
274
275

def remove_self_loops(g):
    eprop = label_self_loops(g)
    remove_labeled_edges(g, eprop)

276
277
278
279
280
281
282
283
284
285
286
287
288
def distance_histogram(g, weights=None, bins=[1], float_count=True):
    ret = libgraph_tool_stats.\
            distance_histogram(g._Graph__graph, _prop("e", g, weights), bins)
    return [array(ret[0], dtype="float64") if float_count else ret[0], ret[1]]

def sampled_distance_histogram(g, n_samples, weights=None, bins=[1],
                               float_count=True, seed=0):
    if seed == 0:
        seed = numpy.random.randint(0, sys.maxint)
    ret = libgraph_tool_stats.\
            sampled_distance_histogram(g._Graph__graph, _prop("e", g, weights),
                                       bins, n_samples, seed)
    return [array(ret[0], dtype="float64") if float_count else ret[0], ret[1]]