Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / operators / all.py @ 5cef0f13

History | View | Annotate | Download (4.54 KB)

1
"""Operations on many graphs.
2
"""
3
#    Copyright (C) 2013 by
4
#    Aric Hagberg <hagberg@lanl.gov>
5
#    Dan Schult <dschult@colgate.edu>
6
#    Pieter Swart <swart@lanl.gov>
7
#    All rights reserved.
8
#    BSD license.
9
try:
10
    from itertools import izip_longest as zip_longest
11
except ImportError:  # Python3 has zip_longest
12
    from itertools import zip_longest
13
import networkx as nx
14

    
15
__author__ = """\n""".join(['Robert King <kingrobertking@gmail.com>',
16
                            'Aric Hagberg <aric.hagberg@gmail.com>'])
17

    
18
__all__ = ['union_all', 'compose_all', 'disjoint_union_all',
19
           'intersection_all']
20

    
21

    
22
def union_all(graphs, rename=(None,)):
23
    """Returns the union of all graphs.
24

25
    The graphs must be disjoint, otherwise an exception is raised.
26

27
    Parameters
28
    ----------
29
    graphs : list of graphs
30
       List of NetworkX graphs
31

32
    rename : bool , default=(None, None)
33
       Node names of G and H can be changed by specifying the tuple
34
       rename=('G-','H-') (for example).  Node "u" in G is then renamed
35
       "G-u" and "v" in H is renamed "H-v".
36

37
    Returns
38
    -------
39
    U : a graph with the same type as the first graph in list
40

41
    Raises
42
    ------
43
    ValueError
44
       If `graphs` is an empty list.
45

46
    Notes
47
    -----
48
    To force a disjoint union with node relabeling, use
49
    disjoint_union_all(G,H) or convert_node_labels_to integers().
50

51
    Graph, edge, and node attributes are propagated to the union graph.
52
    If a graph attribute is present in multiple graphs, then the value
53
    from the last graph in the list with that attribute is used.
54

55
    See Also
56
    --------
57
    union
58
    disjoint_union_all
59
    """
60
    if not graphs:
61
        raise ValueError('cannot apply union_all to an empty list')
62
    graphs_names = zip_longest(graphs, rename)
63
    U, gname = next(graphs_names)
64
    for H, hname in graphs_names:
65
        U = nx.union(U, H, (gname, hname))
66
        gname = None
67
    return U
68

    
69

    
70
def disjoint_union_all(graphs):
71
    """Returns the disjoint union of all graphs.
72

73
    This operation forces distinct integer node labels starting with 0
74
    for the first graph in the list and numbering consecutively.
75

76
    Parameters
77
    ----------
78
    graphs : list
79
       List of NetworkX graphs
80

81
    Returns
82
    -------
83
    U : A graph with the same type as the first graph in list
84

85
    Raises
86
    ------
87
    ValueError
88
       If `graphs` is an empty list.
89

90
    Notes
91
    -----
92
    It is recommended that the graphs be either all directed or all undirected.
93

94
    Graph, edge, and node attributes are propagated to the union graph.
95
    If a graph attribute is present in multiple graphs, then the value
96
    from the last graph in the list with that attribute is used.
97
    """
98
    if not graphs:
99
        raise ValueError('cannot apply disjoint_union_all to an empty list')
100
    graphs = iter(graphs)
101
    U = next(graphs)
102
    for H in graphs:
103
        U = nx.disjoint_union(U, H)
104
    return U
105

    
106

    
107
def compose_all(graphs):
108
    """Returns the composition of all graphs.
109

110
    Composition is the simple union of the node sets and edge sets.
111
    The node sets of the supplied graphs need not be disjoint.
112

113
    Parameters
114
    ----------
115
    graphs : list
116
       List of NetworkX graphs
117

118
    Returns
119
    -------
120
    C : A graph with the same type as the first graph in list
121

122
    Raises
123
    ------
124
    ValueError
125
       If `graphs` is an empty list.
126

127
    Notes
128
    -----
129
    It is recommended that the supplied graphs be either all directed or all
130
    undirected.
131

132
    Graph, edge, and node attributes are propagated to the union graph.
133
    If a graph attribute is present in multiple graphs, then the value
134
    from the last graph in the list with that attribute is used.
135
    """
136
    if not graphs:
137
        raise ValueError('cannot apply compose_all to an empty list')
138
    graphs = iter(graphs)
139
    C = next(graphs)
140
    for H in graphs:
141
        C = nx.compose(C, H)
142
    return C
143

    
144

    
145
def intersection_all(graphs):
146
    """Returns a new graph that contains only the edges that exist in
147
    all graphs.
148

149
    All supplied graphs must have the same node set.
150

151
    Parameters
152
    ----------
153
    graphs : list
154
       List of NetworkX graphs
155

156
    Returns
157
    -------
158
    R : A new graph with the same type as the first graph in list
159

160
    Raises
161
    ------
162
    ValueError
163
       If `graphs` is an empty list.
164

165
    Notes
166
    -----
167
    Attributes from the graph, nodes, and edges are not copied to the new
168
    graph.
169
    """
170
    if not graphs:
171
        raise ValueError('cannot apply intersection_all to an empty list')
172
    graphs = iter(graphs)
173
    R = next(graphs)
174
    for H in graphs:
175
        R = nx.intersection(R, H)
176
    return R