Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / bipartite / edgelist.py @ 5cef0f13

History | View | Annotate | Download (11.1 KB)

1
"""
2
**********
3
Bipartite Edge Lists
4
**********
5
Read and write NetworkX graphs as bipartite edge lists.
6

7
Format
8
------
9
You can read or write three formats of edge lists with these functions.
10

11
Node pairs with no data::
12

13
 1 2
14

15
Python dictionary as data::
16

17
 1 2 {'weight':7, 'color':'green'}
18

19
Arbitrary data::
20

21
 1 2 7 green
22

23
For each edge (u, v) the node u is assigned to part 0 and the node v to part 1.
24
"""
25
#    Copyright (C) 2015 by
26
#    Aric Hagberg <hagberg@lanl.gov>
27
#    Dan Schult <dschult@colgate.edu>
28
#    Pieter Swart <swart@lanl.gov>
29
#    All rights reserved.
30
#    BSD license.
31
__all__ = ['generate_edgelist',
32
           'write_edgelist',
33
           'parse_edgelist',
34
           'read_edgelist']
35

    
36
import networkx as nx
37
from networkx.utils import open_file, make_str, not_implemented_for
38

    
39

    
40
@open_file(1, mode='wb')
41
def write_edgelist(G, path, comments="#", delimiter=' ', data=True,
42
                   encoding='utf-8'):
43
    """Write a bipartite graph as a list of edges.
44

45
    Parameters
46
    ----------
47
    G : Graph
48
       A NetworkX bipartite graph
49
    path : file or string
50
       File or filename to write. If a file is provided, it must be
51
       opened in 'wb' mode. Filenames ending in .gz or .bz2 will be compressed.
52
    comments : string, optional
53
       The character used to indicate the start of a comment
54
    delimiter : string, optional
55
       The string used to separate values.  The default is whitespace.
56
    data : bool or list, optional
57
       If False write no edge data.
58
       If True write a string representation of the edge data dictionary..
59
       If a list (or other iterable) is provided, write the  keys specified
60
       in the list.
61
    encoding: string, optional
62
       Specify which encoding to use when writing file.
63

64
    Examples
65
    --------
66
    >>> G=nx.path_graph(4)
67
    >>> G.add_nodes_from([0,2], bipartite=0)
68
    >>> G.add_nodes_from([1,3], bipartite=1)
69
    >>> nx.write_edgelist(G, "test.edgelist")
70
    >>> fh=open("test.edgelist",'wb')
71
    >>> nx.write_edgelist(G, fh)
72
    >>> nx.write_edgelist(G, "test.edgelist.gz")
73
    >>> nx.write_edgelist(G, "test.edgelist.gz", data=False)
74

75
    >>> G=nx.Graph()
76
    >>> G.add_edge(1,2,weight=7,color='red')
77
    >>> nx.write_edgelist(G,'test.edgelist',data=False)
78
    >>> nx.write_edgelist(G,'test.edgelist',data=['color'])
79
    >>> nx.write_edgelist(G,'test.edgelist',data=['color','weight'])
80

81
    See Also
82
    --------
83
    write_edgelist()
84
    generate_edgelist()
85
    """
86
    for line in generate_edgelist(G, delimiter, data):
87
        line += '\n'
88
        path.write(line.encode(encoding))
89

    
90

    
91
@not_implemented_for('directed')
92
def generate_edgelist(G, delimiter=' ', data=True):
93
    """Generate a single line of the bipartite graph G in edge list format.
94

95
    Parameters
96
    ----------
97
    G : NetworkX graph
98
       The graph is assumed to have node attribute `part` set to 0,1 representing
99
       the two graph parts
100

101
    delimiter : string, optional
102
       Separator for node labels
103

104
    data : bool or list of keys
105
       If False generate no edge data.  If True use a dictionary
106
       representation of edge data.  If a list of keys use a list of data
107
       values corresponding to the keys.
108

109
    Returns
110
    -------
111
    lines : string
112
        Lines of data in adjlist format.
113

114
    Examples
115
    --------
116
    >>> from networkx.algorithms import bipartite
117
    >>> G = nx.path_graph(4)
118
    >>> G.add_nodes_from([0,2], bipartite=0)
119
    >>> G.add_nodes_from([1,3], bipartite=1)
120
    >>> G[1][2]['weight'] = 3
121
    >>> G[2][3]['capacity'] = 12
122
    >>> for line in bipartite.generate_edgelist(G, data=False):
123
    ...     print(line)
124
    0 1
125
    2 1
126
    2 3
127

128
    >>> for line in bipartite.generate_edgelist(G):
129
    ...     print(line)
130
    0 1 {}
131
    2 1 {'weight': 3}
132
    2 3 {'capacity': 12}
133

134
    >>> for line in bipartite.generate_edgelist(G,data=['weight']):
135
    ...     print(line)
136
    0 1
137
    2 1 3
138
    2 3
139
    """
140
    try:
141
        part0 = [n for n, d in G.nodes.items() if d['bipartite'] == 0]
142
    except:
143
        raise AttributeError("Missing node attribute `bipartite`")
144
    if data is True or data is False:
145
        for n in part0:
146
            for e in G.edges(n, data=data):
147
                yield delimiter.join(map(make_str, e))
148
    else:
149
        for n in part0:
150
            for u, v, d in G.edges(n, data=True):
151
                e = [u, v]
152
                try:
153
                    e.extend(d[k] for k in data)
154
                except KeyError:
155
                    pass  # missing data for this edge, should warn?
156
                yield delimiter.join(map(make_str, e))
157

    
158

    
159
def parse_edgelist(lines, comments='#', delimiter=None,
160
                   create_using=None, nodetype=None, data=True):
161
    """Parse lines of an edge list representation of a bipartite graph.
162

163
    Parameters
164
    ----------
165
    lines : list or iterator of strings
166
        Input data in edgelist format
167
    comments : string, optional
168
       Marker for comment lines
169
    delimiter : string, optional
170
       Separator for node labels
171
    create_using: NetworkX graph container, optional
172
       Use given NetworkX graph for holding nodes or edges.
173
    nodetype : Python type, optional
174
       Convert nodes to this type.
175
    data : bool or list of (label,type) tuples
176
       If False generate no edge data or if True use a dictionary
177
       representation of edge data or a list tuples specifying dictionary
178
       key names and types for edge data.
179

180
    Returns
181
    -------
182
    G: NetworkX Graph
183
        The bipartite graph corresponding to lines
184

185
    Examples
186
    --------
187
    Edgelist with no data:
188

189
    >>> from networkx.algorithms import bipartite
190
    >>> lines = ["1 2",
191
    ...          "2 3",
192
    ...          "3 4"]
193
    >>> G = bipartite.parse_edgelist(lines, nodetype = int)
194
    >>> sorted(G.nodes())
195
    [1, 2, 3, 4]
196
    >>> sorted(G.nodes(data=True))
197
    [(1, {'bipartite': 0}), (2, {'bipartite': 0}), (3, {'bipartite': 0}), (4, {'bipartite': 1})]
198
    >>> sorted(G.edges())
199
    [(1, 2), (2, 3), (3, 4)]
200

201
    Edgelist with data in Python dictionary representation:
202

203
    >>> lines = ["1 2 {'weight':3}",
204
    ...          "2 3 {'weight':27}",
205
    ...          "3 4 {'weight':3.0}"]
206
    >>> G = bipartite.parse_edgelist(lines, nodetype = int)
207
    >>> sorted(G.nodes())
208
    [1, 2, 3, 4]
209
    >>> sorted(G.edges(data = True))
210
    [(1, 2, {'weight': 3}), (2, 3, {'weight': 27}), (3, 4, {'weight': 3.0})]
211

212
    Edgelist with data in a list:
213

214
    >>> lines = ["1 2 3",
215
    ...          "2 3 27",
216
    ...          "3 4 3.0"]
217
    >>> G = bipartite.parse_edgelist(lines, nodetype = int, data=(('weight',float),))
218
    >>> sorted(G.nodes())
219
    [1, 2, 3, 4]
220
    >>> sorted(G.edges(data = True))
221
    [(1, 2, {'weight': 3.0}), (2, 3, {'weight': 27.0}), (3, 4, {'weight': 3.0})]
222

223
    See Also
224
    --------
225
    """
226
    from ast import literal_eval
227
    G = nx.empty_graph(0, create_using)
228
    for line in lines:
229
        p = line.find(comments)
230
        if p >= 0:
231
            line = line[:p]
232
        if not len(line):
233
            continue
234
        # split line, should have 2 or more
235
        s = line.strip().split(delimiter)
236
        if len(s) < 2:
237
            continue
238
        u = s.pop(0)
239
        v = s.pop(0)
240
        d = s
241
        if nodetype is not None:
242
            try:
243
                u = nodetype(u)
244
                v = nodetype(v)
245
            except:
246
                raise TypeError("Failed to convert nodes %s,%s to type %s."
247
                                % (u, v, nodetype))
248

    
249
        if len(d) == 0 or data is False:
250
            # no data or data type specified
251
            edgedata = {}
252
        elif data is True:
253
            # no edge types specified
254
            try:  # try to evaluate as dictionary
255
                edgedata = dict(literal_eval(' '.join(d)))
256
            except:
257
                raise TypeError(
258
                    "Failed to convert edge data (%s) to dictionary." % (d))
259
        else:
260
            # convert edge data to dictionary with specified keys and type
261
            if len(d) != len(data):
262
                raise IndexError(
263
                    "Edge data %s and data_keys %s are not the same length" %
264
                    (d, data))
265
            edgedata = {}
266
            for (edge_key, edge_type), edge_value in zip(data, d):
267
                try:
268
                    edge_value = edge_type(edge_value)
269
                except:
270
                    raise TypeError(
271
                        "Failed to convert %s data %s to type %s."
272
                        % (edge_key, edge_value, edge_type))
273
                edgedata.update({edge_key: edge_value})
274
        G.add_node(u, bipartite=0)
275
        G.add_node(v, bipartite=1)
276
        G.add_edge(u, v, **edgedata)
277
    return G
278

    
279

    
280
@open_file(0, mode='rb')
281
def read_edgelist(path, comments="#",
282
                  delimiter=None, create_using=None,
283
                  nodetype=None, data=True, edgetype=None,
284
                  encoding='utf-8'):
285
    """Read a bipartite graph from a list of edges.
286

287
    Parameters
288
    ----------
289
    path : file or string
290
       File or filename to read. If a file is provided, it must be
291
       opened in 'rb' mode.
292
       Filenames ending in .gz or .bz2 will be uncompressed.
293
    comments : string, optional
294
       The character used to indicate the start of a comment.
295
    delimiter : string, optional
296
       The string used to separate values.  The default is whitespace.
297
    create_using : Graph container, optional,
298
       Use specified container to build graph.  The default is networkx.Graph,
299
       an undirected graph.
300
    nodetype : int, float, str, Python type, optional
301
       Convert node data from strings to specified type
302
    data : bool or list of (label,type) tuples
303
       Tuples specifying dictionary key names and types for edge data
304
    edgetype : int, float, str, Python type, optional OBSOLETE
305
       Convert edge data from strings to specified type and use as 'weight'
306
    encoding: string, optional
307
       Specify which encoding to use when reading file.
308

309
    Returns
310
    -------
311
    G : graph
312
       A networkx Graph or other type specified with create_using
313

314
    Examples
315
    --------
316
    >>> from networkx.algorithms import bipartite
317
    >>> G = nx.path_graph(4)
318
    >>> G.add_nodes_from([0,2], bipartite=0)
319
    >>> G.add_nodes_from([1,3], bipartite=1)
320
    >>> bipartite.write_edgelist(G, "test.edgelist")
321
    >>> G = bipartite.read_edgelist("test.edgelist")
322

323
    >>> fh = open("test.edgelist", 'rb')
324
    >>> G = bipartite.read_edgelist(fh)
325
    >>> fh.close()
326

327
    >>> G=bipartite.read_edgelist("test.edgelist", nodetype=int)
328

329
    Edgelist with data in a list:
330

331
    >>> textline = '1 2 3'
332
    >>> fh = open('test.edgelist','w')
333
    >>> d = fh.write(textline)
334
    >>> fh.close()
335
    >>> G = bipartite.read_edgelist('test.edgelist', nodetype=int, data=(('weight',float),))
336
    >>> list(G)
337
    [1, 2]
338
    >>> list(G.edges(data=True))
339
    [(1, 2, {'weight': 3.0})]
340

341
    See parse_edgelist() for more examples of formatting.
342

343
    See Also
344
    --------
345
    parse_edgelist
346

347
    Notes
348
    -----
349
    Since nodes must be hashable, the function nodetype must return hashable
350
    types (e.g. int, float, str, frozenset - or tuples of those, etc.)
351
    """
352
    lines = (line.decode(encoding) for line in path)
353
    return parse_edgelist(lines, comments=comments,
354
                          delimiter=delimiter,
355
                          create_using=create_using,
356
                          nodetype=nodetype,
357
                          data=data)