/usr/lib/python3/dist-packages/networkx/generators/line.py is in python3-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 | """
Line graphs.
"""
# Copyright (C) 2010 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
__all__ = ['line_graph']
import networkx as nx
def line_graph(G):
"""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 DiGraphs an edge an edge represents a directed path of length 2.
The original node labels are kept as two-tuple node labels
in the line graph.
Parameters
----------
G : graph
A NetworkX Graph or DiGraph
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
-----
Not implemented for MultiGraph or MultiDiGraph classes.
Graph, node, and edge data are not propagated to the new graph.
"""
if type(G) == nx.MultiGraph or type(G) == nx.MultiDiGraph:
raise Exception("Line graph not implemented for Multi(Di)Graphs")
L=G.__class__()
if G.is_directed():
for u,nlist in G.adjacency_iter(): # same as successors for digraph
# look for directed path of length two
for n in nlist:
nbrs=G[n] # successors
for nbr in nbrs:
if nbr!=u:
L.add_edge((u,n),(n,nbr))
else:
for u,nlist in G.adjacency_iter():
# label nodes as tuple of edge endpoints in original graph
# "node tuple" must be in lexigraphical order
nodes=[tuple(sorted(n)) for n in zip([u]*len(nlist),nlist)]
# add clique of nodes to graph
while nodes:
u=nodes.pop()
L.add_edges_from((u,v) for v in nodes)
return L
|