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
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
197
198
199
200
201
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
|
# -*- coding: ascii -*-
"""
Line graph algorithms.
Undirected Graphs
-----------------
For an undirected graph G without multiple edges, each edge can be written as
a set {u,v}. Its line graph L has the edges of G as its nodes. If x and y
are two nodes in L, then {x,y} is an edge in L if and only if the intersection
of x and y is nonempty. Thus, the set of all edges is determined by the
set of all pair-wise intersections of edges in G.
Trivially, every edge x={u,v} in G would have a nonzero intersection with
itself, and so every node in L should have a self-loop. This is not so
interesting, and the original context of line graphs was with simple graphs,
which had no self-loops or multiple edges. The line graph was also meant
to be simple graph and thus, self-loops in L are not part of the standard
definition of a line graph. In a pair-wise intersection matrix, this is
analogous to not including the diagonal as part of the line graph definition.
Self-loops and multiple edges in G add nodes to L in a natural way, and do not
require any fundamental changes to the definition. It might be argued that
the self-loops we excluded before should now be included. However, the
self-loops are still "trivial" in some sense and thus, are usually excluded.
Directed Graphs
---------------
For a directed graph G without multiple edges, each edge can be written as a
tuple (u,v). Its line graph L has the edges of G as its nodes. If x=(a,b) and
y=(c,d) are two nodes in L, then (x,y) is an edge in L if and only if the
tail of x matches the head of y---e.g., b=c.
Due to the directed nature of the edges, it is no longer the case that
every edge x=(u,v) should be connected to itself with a self-loop in L. Now,
the only time self-loops arise is if G itself has a self-loop. So such
self-loops are no longer "trivial" but instead, represent essential features
of the topology of G. For this reason, the historical development of line
digraphs is such that self-loops are included. When the graph G has multiple
edges, once again only superficial changes are required to the definition.
References
----------
Harary, Frank, and Norman, Robert Z., "Some properties of line digraphs",
Rend. Circ. Mat. Palermo, II. Ser. 9 (1960), 161--168.
Hemminger, R. L.; Beineke, L. W. (1978), "Line graphs and line digraphs",
in Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, Academic
Press Inc., pp. 271--305.
"""
# Copyright (C) 2013 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__author__ = "\n".join(["Aric Hagberg (hagberg@lanl.gov)",
"Pieter Swart (swart@lanl.gov)",
"Dan Schult (dschult@colgate.edu)",
"chebee7i (chebee7i@gmail.com)"])
__all__ = ['line_graph']
import networkx as nx
def line_graph(G, create_using=None):
"""Return the line graph of the graph or digraph G.
The line graph of a graph G has a node for each edge in G and an edge
between those nodes if the two edges in G share a common node. For directed
graphs, nodes are connected only if they form a directed path of length 2.
The nodes of the line graph are 2-tuples of nodes in the original graph
(or 3-tuples for multigraphs, with the key of the edge as the 3rd element).
For more discussion, see the docstring in :mod:`networkx.generators.line`.
Parameters
----------
G : graph
A NetworkX Graph, DiGraph, MultiGraph, or MultiDigraph.
Returns
-------
L : graph
The line graph of G.
Examples
--------
>>> G = nx.star_graph(3)
>>> L = nx.line_graph(G)
>>> print(sorted(L.edges())) # makes a clique, K3
[((0, 1), (0, 2)), ((0, 1), (0, 3)), ((0, 3), (0, 2))]
Notes
-----
Graph, node, and edge data are not propagated to the new graph. For
undirected graphs, the nodes in G must be sortable---otherwise, the
constructed line graph may not be correct.
"""
if G.is_directed():
L = _lg_directed(G, create_using=create_using)
else:
L = _lg_undirected(G, selfloops=False, create_using=create_using)
return L
def _node_func(G):
"""Returns a function which returns a sorted node for line graphs.
When constructing a line graph for undirected graphs, we must normalize
the ordering of nodes as they appear in the edge.
"""
if G.is_multigraph():
def sorted_node(u, v, key):
return (u, v, key) if u <= v else (v, u, key)
else:
def sorted_node(u, v):
return (u, v) if u <= v else (v, u)
return sorted_node
def _edge_func(G):
"""Returns the edges from G, handling keys for multigraphs as necessary.
"""
if G.is_multigraph():
def get_edges(nbunch=None):
return G.edges_iter(nbunch, keys=True)
else:
def get_edges(nbunch=None):
return G.edges_iter(nbunch)
return get_edges
def _sorted_edge(u, v):
"""Returns a sorted edge.
During the construction of a line graph for undirected graphs, the data
structure can be a multigraph even though the line graph will never have
multiple edges between its nodes. For this reason, we must make sure not
to add any edge more than once. This requires that we build up a list of
edges to add and then remove all duplicates. And so, we must normalize
the representation of the edges.
"""
return (u, v) if u <= v else (v, u)
def _lg_directed(G, create_using=None):
"""Return the line graph L of the (multi)digraph G.
Edges in G appear as nodes in L, represented as tuples of the form (u,v)
or (u,v,key) if G is a multidigraph. A node in L corresponding to the edge
(u,v) is connected to every node corresponding to an edge (v,w).
Parameters
----------
G : digraph
A directed graph or directed multigraph.
create_using : None
A digraph instance used to populate the line graph.
"""
if create_using is None:
L = G.__class__()
else:
L = create_using
# Create a graph specific edge function.
get_edges = _edge_func(G)
for from_node in get_edges():
# from_node is: (u,v) or (u,v,key)
L.add_node(from_node)
for to_node in get_edges(from_node[1]):
L.add_edge(from_node, to_node)
return L
def _lg_undirected(G, selfloops=False, create_using=None):
"""Return the line graph L of the (multi)graph G.
Edges in G appear as nodes in L, represented as sorted tuples of the form
(u,v), or (u,v,key) if G is a multigraph. A node in L corresponding to
the edge {u,v} is connected to every node corresponding to an edge that
involves u or v.
Parameters
----------
G : graph
An undirected graph or multigraph.
selfloops : bool
If `True`, then self-loops are included in the line graph. If `False`,
they are excluded.
create_using : None
A graph instance used to populate the line graph.
Notes
-----
The standard algorithm for line graphs of undirected graphs does not
produce self-loops.
"""
if create_using is None:
L = G.__class__()
else:
L = create_using
# Graph specific functions for edges and sorted nodes.
get_edges = _edge_func(G)
sorted_node = _node_func(G)
# Determine if we include self-loops or not.
shift = 0 if selfloops else 1
edges = set([])
for u in G:
# Label nodes as a sorted tuple of nodes in original graph.
nodes = [ sorted_node(*x) for x in get_edges(u) ]
if len(nodes) == 1:
# Then the edge will be an isolated node in L.
L.add_node(nodes[0])
# Add a clique of `nodes` to graph. To prevent double adding edges,
# especially important for multigraphs, we store the edges in
# canonical form in a set.
for i, a in enumerate(nodes):
edges.update([ _sorted_edge(a,b) for b in nodes[i+shift:] ])
L.add_edges_from(edges)
return L
|
