Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / line.py @ 5cef0f13

History | View | Annotate | Download (17 KB)

1
#    Copyright (C) 2013-2019 by
2
#    Aric Hagberg <hagberg@lanl.gov>
3
#    Dan Schult <dschult@colgate.edu>
4
#    Pieter Swart <swart@lanl.gov>
5
#    All rights reserved.
6
#    BSD license.
7
#
8
# Authors:      James Clough <james.clough91@gmail.com>
9
#               Aric Hagberg <hagberg@lanl.gov>
10
#               Pieter Swart <swart@lanl.gov>
11
#               Dan Schult <dschult@colgate.edu>
12
#               chebee7i <chebee7i@gmail.com>
13
"""Functions for generating line graphs."""
14
from itertools import combinations
15
from collections import defaultdict
16

    
17
import networkx as nx
18
from networkx.utils import arbitrary_element
19
from networkx.utils.decorators import *
20

    
21
__all__ = ['line_graph', 'inverse_line_graph']
22

    
23

    
24
def line_graph(G, create_using=None):
25
    r"""Returns the line graph of the graph or digraph `G`.
26

27
    The line graph of a graph `G` has a node for each edge in `G` and an
28
    edge joining those nodes if the two edges in `G` share a common node. For
29
    directed graphs, nodes are adjacent exactly when the edges they represent
30
    form a directed path of length two.
31

32
    The nodes of the line graph are 2-tuples of nodes in the original graph (or
33
    3-tuples for multigraphs, with the key of the edge as the third element).
34

35
    For information about self-loops and more discussion, see the **Notes**
36
    section below.
37

38
    Parameters
39
    ----------
40
    G : graph
41
        A NetworkX Graph, DiGraph, MultiGraph, or MultiDigraph.
42
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
43
       Graph type to create. If graph instance, then cleared before populated.
44

45
    Returns
46
    -------
47
    L : graph
48
        The line graph of G.
49

50
    Examples
51
    --------
52
    >>> import networkx as nx
53
    >>> G = nx.star_graph(3)
54
    >>> L = nx.line_graph(G)
55
    >>> print(sorted(map(sorted, L.edges())))  # makes a 3-clique, K3
56
    [[(0, 1), (0, 2)], [(0, 1), (0, 3)], [(0, 2), (0, 3)]]
57

58
    Notes
59
    -----
60
    Graph, node, and edge data are not propagated to the new graph. For
61
    undirected graphs, the nodes in G must be sortable, otherwise the
62
    constructed line graph may not be correct.
63

64
    *Self-loops in undirected graphs*
65

66
    For an undirected graph `G` without multiple edges, each edge can be
67
    written as a set `\{u, v\}`.  Its line graph `L` has the edges of `G` as
68
    its nodes. If `x` and `y` are two nodes in `L`, then `\{x, y\}` is an edge
69
    in `L` if and only if the intersection of `x` and `y` is nonempty. Thus,
70
    the set of all edges is determined by the set of all pairwise intersections
71
    of edges in `G`.
72

73
    Trivially, every edge in G would have a nonzero intersection with itself,
74
    and so every node in `L` should have a self-loop. This is not so
75
    interesting, and the original context of line graphs was with simple
76
    graphs, which had no self-loops or multiple edges. The line graph was also
77
    meant to be a simple graph and thus, self-loops in `L` are not part of the
78
    standard definition of a line graph. In a pairwise intersection matrix,
79
    this is analogous to excluding the diagonal entries from the line graph
80
    definition.
81

82
    Self-loops and multiple edges in `G` add nodes to `L` in a natural way, and
83
    do not require any fundamental changes to the definition. It might be
84
    argued that the self-loops we excluded before should now be included.
85
    However, the self-loops are still "trivial" in some sense and thus, are
86
    usually excluded.
87

88
    *Self-loops in directed graphs*
89

90
    For a directed graph `G` without multiple edges, each edge can be written
91
    as a tuple `(u, v)`. Its line graph `L` has the edges of `G` as its
92
    nodes. If `x` and `y` are two nodes in `L`, then `(x, y)` is an edge in `L`
93
    if and only if the tail of `x` matches the head of `y`, for example, if `x
94
    = (a, b)` and `y = (b, c)` for some vertices `a`, `b`, and `c` in `G`.
95

96
    Due to the directed nature of the edges, it is no longer the case that
97
    every edge in `G` should have a self-loop in `L`. Now, the only time
98
    self-loops arise is if a node in `G` itself has a self-loop.  So such
99
    self-loops are no longer "trivial" but instead, represent essential
100
    features of the topology of `G`. For this reason, the historical
101
    development of line digraphs is such that self-loops are included. When the
102
    graph `G` has multiple edges, once again only superficial changes are
103
    required to the definition.
104

105
    References
106
    ----------
107
    * Harary, Frank, and Norman, Robert Z., "Some properties of line digraphs",
108
      Rend. Circ. Mat. Palermo, II. Ser. 9 (1960), 161--168.
109
    * Hemminger, R. L.; Beineke, L. W. (1978), "Line graphs and line digraphs",
110
      in Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory,
111
      Academic Press Inc., pp. 271--305.
112

113
    """
114
    if G.is_directed():
115
        L = _lg_directed(G, create_using=create_using)
116
    else:
117
        L = _lg_undirected(G, selfloops=False, create_using=create_using)
118
    return L
119

    
120

    
121
def _node_func(G):
122
    """Returns a function which returns a sorted node for line graphs.
123

124
    When constructing a line graph for undirected graphs, we must normalize
125
    the ordering of nodes as they appear in the edge.
126

127
    """
128
    if G.is_multigraph():
129
        def sorted_node(u, v, key):
130
            return (u, v, key) if u <= v else (v, u, key)
131
    else:
132
        def sorted_node(u, v):
133
            return (u, v) if u <= v else (v, u)
134
    return sorted_node
135

    
136

    
137
def _edge_func(G):
138
    """Returns the edges from G, handling keys for multigraphs as necessary.
139

140
    """
141
    if G.is_multigraph():
142
        def get_edges(nbunch=None):
143
            return G.edges(nbunch, keys=True)
144
    else:
145
        def get_edges(nbunch=None):
146
            return G.edges(nbunch)
147
    return get_edges
148

    
149

    
150
def _sorted_edge(u, v):
151
    """Returns a sorted edge.
152

153
    During the construction of a line graph for undirected graphs, the data
154
    structure can be a multigraph even though the line graph will never have
155
    multiple edges between its nodes.  For this reason, we must make sure not
156
    to add any edge more than once.  This requires that we build up a list of
157
    edges to add and then remove all duplicates.  And so, we must normalize
158
    the representation of the edges.
159

160
    """
161
    return (u, v) if u <= v else (v, u)
162

    
163

    
164
def _lg_directed(G, create_using=None):
165
    """Returns the line graph L of the (multi)digraph G.
166

167
    Edges in G appear as nodes in L, represented as tuples of the form (u,v)
168
    or (u,v,key) if G is a multidigraph. A node in L corresponding to the edge
169
    (u,v) is connected to every node corresponding to an edge (v,w).
170

171
    Parameters
172
    ----------
173
    G : digraph
174
        A directed graph or directed multigraph.
175
    create_using : NetworkX graph constructor, optional
176
       Graph type to create. If graph instance, then cleared before populated.
177
       Default is to use the same graph class as `G`.
178

179
    """
180
    L = nx.empty_graph(0, create_using, default=G.__class__)
181

    
182
    # Create a graph specific edge function.
183
    get_edges = _edge_func(G)
184

    
185
    for from_node in get_edges():
186
        # from_node is: (u,v) or (u,v,key)
187
        L.add_node(from_node)
188
        for to_node in get_edges(from_node[1]):
189
            L.add_edge(from_node, to_node)
190

    
191
    return L
192

    
193

    
194
def _lg_undirected(G, selfloops=False, create_using=None):
195
    """Returns the line graph L of the (multi)graph G.
196

197
    Edges in G appear as nodes in L, represented as sorted tuples of the form
198
    (u,v), or (u,v,key) if G is a multigraph. A node in L corresponding to
199
    the edge {u,v} is connected to every node corresponding to an edge that
200
    involves u or v.
201

202
    Parameters
203
    ----------
204
    G : graph
205
        An undirected graph or multigraph.
206
    selfloops : bool
207
        If `True`, then self-loops are included in the line graph. If `False`,
208
        they are excluded.
209
    create_using : NetworkX graph constructor, optional (default=nx.Graph)
210
       Graph type to create. If graph instance, then cleared before populated.
211

212
    Notes
213
    -----
214
    The standard algorithm for line graphs of undirected graphs does not
215
    produce self-loops.
216

217
    """
218
    L = nx.empty_graph(0, create_using, default=G.__class__)
219

    
220
    # Graph specific functions for edges and sorted nodes.
221
    get_edges = _edge_func(G)
222
    sorted_node = _node_func(G)
223

    
224
    # Determine if we include self-loops or not.
225
    shift = 0 if selfloops else 1
226

    
227
    edges = set([])
228
    for u in G:
229
        # Label nodes as a sorted tuple of nodes in original graph.
230
        nodes = [sorted_node(*x) for x in get_edges(u)]
231

    
232
        if len(nodes) == 1:
233
            # Then the edge will be an isolated node in L.
234
            L.add_node(nodes[0])
235

    
236
        # Add a clique of `nodes` to graph. To prevent double adding edges,
237
        # especially important for multigraphs, we store the edges in
238
        # canonical form in a set.
239
        for i, a in enumerate(nodes):
240
            edges.update([_sorted_edge(a, b) for b in nodes[i + shift:]])
241

    
242
    L.add_edges_from(edges)
243
    return L
244

    
245

    
246
@not_implemented_for('directed')
247
@not_implemented_for('multigraph')
248
def inverse_line_graph(G):
249
    """ Returns the inverse line graph of graph G.
250

251
    If H is a graph, and G is the line graph of H, such that H = L(G).
252
    Then H is the inverse line graph of G.
253

254
    Not all graphs are line graphs and these do not have an inverse line graph.
255
    In these cases this generator returns a NetworkXError.
256

257
    Parameters
258
    ----------
259
    G : graph
260
        A NetworkX Graph
261

262
    Returns
263
    -------
264
    H : graph
265
        The inverse line graph of G.
266

267
    Raises
268
    ------
269
    NetworkXNotImplemented
270
        If G is directed or a multigraph
271

272
    NetworkXError
273
        If G is not a line graph
274

275
    Notes
276
    -----
277
    This is an implementation of the Roussopoulos algorithm.
278

279
    References
280
    ----------
281
    * Roussopolous, N, "A max {m, n} algorithm for determining the graph H from
282
      its line graph G", Information Processing Letters 2, (1973), 108--112.
283

284
    """
285
    if G.number_of_edges() == 0 or G.number_of_nodes() == 0:
286
        msg = "G is not a line graph (has zero vertices or edges)"
287
        raise nx.NetworkXError(msg)
288

    
289
    starting_cell = _select_starting_cell(G)
290
    P = _find_partition(G, starting_cell)
291
    # count how many times each vertex appears in the partition set
292
    P_count = {u: 0 for u in G.nodes()}
293
    for p in P:
294
        for u in p:
295
            P_count[u] += 1
296

    
297
    if max(P_count.values()) > 2:
298
        msg = "G is not a line graph (vertex found in more " \
299
              "than two partition cells)"
300
        raise nx.NetworkXError(msg)
301
    W = tuple([(u,) for u in P_count if P_count[u] == 1])
302
    H = nx.Graph()
303
    H.add_nodes_from(P)
304
    H.add_nodes_from(W)
305
    for a, b in combinations(H.nodes(), 2):
306
        if len(set(a).intersection(set(b))) > 0:
307
            H.add_edge(a, b)
308
    return H
309

    
310

    
311
def _triangles(G, e):
312
    """ Return list of all triangles containing edge e"""
313
    u, v = e
314
    if u not in G:
315
        raise nx.NetworkXError("Vertex %s not in graph" % u)
316
    if v not in G.neighbors(u):
317
        raise nx.NetworkXError("Edge (%s, %s) not in graph" % (u, v))
318
    triangle_list = []
319
    for x in G.neighbors(u):
320
        if x in G.neighbors(v):
321
            triangle_list.append((u, v, x))
322
    return triangle_list
323

    
324

    
325
def _odd_triangle(G, T):
326
    """ Test whether T is an odd triangle in G
327

328
    Parameters
329
    ----------
330
    G : NetworkX Graph
331
    T : 3-tuple of vertices forming triangle in G
332

333
    Returns
334
    -------
335
    True is T is an odd triangle
336
    False otherwise
337

338
    Raises
339
    ------
340
    NetworkXError
341
        T is not a triangle in G
342

343
    Notes
344
    -----
345
    An odd triangle is one in which there exists another vertex in G which is
346
    adjacent to either exactly one or exactly all three of the vertices in the
347
    triangle.
348

349
    """
350
    for u in T:
351
        if u not in G.nodes():
352
            raise nx.NetworkXError("Vertex %s not in graph" % u)
353
    for e in list(combinations(T, 2)):
354
        if e[0] not in G.neighbors(e[1]):
355
            raise nx.NetworkXError("Edge (%s, %s) not in graph" % (e[0], e[1]))
356

    
357
    T_neighbors = defaultdict(int)
358
    for t in T:
359
        for v in G.neighbors(t):
360
            if v not in T:
361
                T_neighbors[v] += 1
362
    for v in T_neighbors:
363
        if T_neighbors[v] in [1, 3]:
364
            return True
365
    return False
366

    
367

    
368
def _find_partition(G, starting_cell):
369
    """ Find a partition of the vertices of G into cells of complete graphs
370

371
    Parameters
372
    ----------
373
    G : NetworkX Graph
374
    starting_cell : tuple of vertices in G which form a cell
375

376
    Returns
377
    -------
378
    List of tuples of vertices of G
379

380
    Raises
381
    ------
382
    NetworkXError
383
        If a cell is not a complete subgraph then G is not a line graph
384
    """
385
    G_partition = G.copy()
386
    P = [starting_cell]  # partition set
387
    G_partition.remove_edges_from(list(combinations(starting_cell, 2)))
388
    # keep list of partitioned nodes which might have an edge in G_partition
389
    partitioned_vertices = list(starting_cell)
390
    while G_partition.number_of_edges() > 0:
391
        # there are still edges left and so more cells to be made
392
        u = partitioned_vertices[-1]
393
        deg_u = len(G_partition[u])
394
        if deg_u == 0:
395
            # if u has no edges left in G_partition then we have found
396
            # all of its cells so we do not need to keep looking
397
            partitioned_vertices.pop()
398
        else:
399
            # if u still has edges then we need to find its other cell
400
            # this other cell must be a complete subgraph or else G is
401
            # not a line graph
402
            new_cell = [u] + list(G_partition.neighbors(u))
403
            for u in new_cell:
404
                for v in new_cell:
405
                    if (u != v) and (v not in G.neighbors(u)):
406
                        msg = "G is not a line graph" \
407
                              "(partition cell not a complete subgraph)"
408
                        raise nx.NetworkXError(msg)
409
            P.append(tuple(new_cell))
410
            G_partition.remove_edges_from(list(combinations(new_cell, 2)))
411
            partitioned_vertices += new_cell
412
    return P
413

    
414

    
415
def _select_starting_cell(G, starting_edge=None):
416
    """ Select a cell to initiate _find_partition
417

418
    Parameters
419
    ----------
420
    G : NetworkX Graph
421
    starting_edge: an edge to build the starting cell from
422

423
    Returns
424
    -------
425
    Tuple of vertices in G
426

427
    Raises
428
    ------
429
    NetworkXError
430
        If it is determined that G is not a line graph
431

432
    Notes
433
    -----
434
    If starting edge not specified then pick an arbitrary edge - doesn't
435
    matter which. However, this function may call itself requiring a
436
    specific starting edge. Note that the r, s notation for counting
437
    triangles is the same as in the Roussopoulos paper cited above.
438
    """
439
    if starting_edge is None:
440
        e = arbitrary_element(list(G.edges()))
441
    else:
442
        e = starting_edge
443
        if e[0] not in G[e[1]]:
444
            msg = 'starting_edge (%s, %s) is not in the Graph'
445
            raise nx.NetworkXError(msg % e)
446
    e_triangles = _triangles(G, e)
447
    r = len(e_triangles)
448
    if r == 0:
449
        # there are no triangles containing e, so the starting cell is just e
450
        starting_cell = e
451
    elif r == 1:
452
        # there is exactly one triangle, T, containing e. If other 2 edges
453
        # of T belong only to this triangle then T is starting cell
454
        T = e_triangles[0]
455
        a, b, c = T
456
        # ab was original edge so check the other 2 edges
457
        ac_edges = [x for x in _triangles(G, (a, c))]
458
        bc_edges = [x for x in _triangles(G, (b, c))]
459
        if len(ac_edges) == 1:
460
            if len(bc_edges) == 1:
461
                starting_cell = T
462
            else:
463
                return _select_starting_cell(G, starting_edge=(b, c))
464
        else:
465
            return _select_starting_cell(G, starting_edge=(a, c))
466
    else:
467
        # r >= 2 so we need to count the number of odd triangles, s
468
        s = 0
469
        odd_triangles = []
470
        for T in e_triangles:
471
            if _odd_triangle(G, T):
472
                s += 1
473
                odd_triangles.append(T)
474
        if r == 2 and s == 0:
475
            # in this case either triangle works, so just use T
476
            starting_cell = T
477
        elif r - 1 <= s <= r:
478
            # check if odd triangles containing e form complete subgraph
479
            # there must be exactly s+2 of them
480
            # and they must all be connected
481
            triangle_nodes = set([])
482
            for T in odd_triangles:
483
                for x in T:
484
                    triangle_nodes.add(x)
485
            if len(triangle_nodes) == s + 2:
486
                for u in triangle_nodes:
487
                    for v in triangle_nodes:
488
                        if u != v and (v not in G.neighbors(u)):
489
                            msg = "G is not a line graph (odd triangles " \
490
                                  "do not form complete subgraph)"
491
                            raise nx.NetworkXError(msg)
492
                # otherwise then we can use this as the starting cell
493
                starting_cell = tuple(triangle_nodes)
494
            else:
495
                msg = "G is not a line graph (odd triangles " \
496
                      "do not form complete subgraph)"
497
                raise nx.NetworkXError(msg)
498
        else:
499
            msg = "G is not a line graph (incorrect number of " \
500
                  "odd triangles around starting edge)"
501
            raise nx.NetworkXError(msg)
502
    return starting_cell