/usr/lib/python3/dist-packages/networkx/linalg/graphmatrix.py is in python3-networkx 1.11-2.
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 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 | """
Adjacency matrix and incidence matrix of graphs.
"""
# Copyright (C) 2004-2015 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
import networkx as nx
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
'Pieter Swart (swart@lanl.gov)',
'Dan Schult(dschult@colgate.edu)'])
__all__ = ['incidence_matrix',
'adj_matrix', 'adjacency_matrix',
]
def incidence_matrix(G, nodelist=None, edgelist=None,
oriented=False, weight=None):
"""Return incidence matrix of G.
The incidence matrix assigns each row to a node and each column to an edge.
For a standard incidence matrix a 1 appears wherever a row's node is
incident on the column's edge. For an oriented incidence matrix each
edge is assigned an orientation (arbitrarily for undirected and aligning to
direction for directed). A -1 appears for the tail of an edge and 1
for the head of the edge. The elements are zero otherwise.
Parameters
----------
G : graph
A NetworkX graph
nodelist : list, optional (default= all nodes in G)
The rows are ordered according to the nodes in nodelist.
If nodelist is None, then the ordering is produced by G.nodes().
edgelist : list, optional (default= all edges in G)
The columns are ordered according to the edges in edgelist.
If edgelist is None, then the ordering is produced by G.edges().
oriented: bool, optional (default=False)
If True, matrix elements are +1 or -1 for the head or tail node
respectively of each edge. If False, +1 occurs at both nodes.
weight : string or None, optional (default=None)
The edge data key used to provide each value in the matrix.
If None, then each edge has weight 1. Edge weights, if used,
should be positive so that the orientation can provide the sign.
Returns
-------
A : SciPy sparse matrix
The incidence matrix of G.
Notes
-----
For MultiGraph/MultiDiGraph, the edges in edgelist should be
(u,v,key) 3-tuples.
"Networks are the best discrete model for so many problems in
applied mathematics" [1]_.
References
----------
.. [1] Gil Strang, Network applications: A = incidence matrix,
http://academicearth.org/lectures/network-applications-incidence-matrix
"""
import scipy.sparse
if nodelist is None:
nodelist = G.nodes()
if edgelist is None:
if G.is_multigraph():
edgelist = G.edges(keys=True)
else:
edgelist = G.edges()
A = scipy.sparse.lil_matrix((len(nodelist),len(edgelist)))
node_index = dict( (node,i) for i,node in enumerate(nodelist) )
for ei,e in enumerate(edgelist):
(u,v) = e[:2]
if u == v: continue # self loops give zero column
try:
ui = node_index[u]
vi = node_index[v]
except KeyError:
raise NetworkXError('node %s or %s in edgelist '
'but not in nodelist"%(u,v)')
if weight is None:
wt = 1
else:
if G.is_multigraph():
ekey = e[2]
wt = G[u][v][ekey].get(weight,1)
else:
wt = G[u][v].get(weight,1)
if oriented:
A[ui,ei] = -wt
A[vi,ei] = wt
else:
A[ui,ei] = wt
A[vi,ei] = wt
return A.asformat('csc')
def adjacency_matrix(G, nodelist=None, weight='weight'):
"""Return adjacency matrix of G.
Parameters
----------
G : graph
A NetworkX graph
nodelist : list, optional
The rows and columns are ordered according to the nodes in nodelist.
If nodelist is None, then the ordering is produced by G.nodes().
weight : string or None, optional (default='weight')
The edge data key used to provide each value in the matrix.
If None, then each edge has weight 1.
Returns
-------
A : SciPy sparse matrix
Adjacency matrix representation of G.
Notes
-----
For directed graphs, entry i,j corresponds to an edge from i to j.
If you want a pure Python adjacency matrix representation try
networkx.convert.to_dict_of_dicts which will return a
dictionary-of-dictionaries format that can be addressed as a
sparse matrix.
For MultiGraph/MultiDiGraph with parallel edges the weights are summed.
See to_numpy_matrix for other options.
The convention used for self-loop edges in graphs is to assign the
diagonal matrix entry value to the edge weight attribute
(or the number 1 if the edge has no weight attribute). If the
alternate convention of doubling the edge weight is desired the
resulting Scipy sparse matrix can be modified as follows:
>>> import scipy as sp
>>> G = nx.Graph([(1,1)])
>>> A = nx.adjacency_matrix(G)
>>> print(A.todense())
[[1]]
>>> A.setdiag(A.diagonal()*2)
>>> print(A.todense())
[[2]]
See Also
--------
to_numpy_matrix
to_scipy_sparse_matrix
to_dict_of_dicts
"""
return nx.to_scipy_sparse_matrix(G,nodelist=nodelist,weight=weight)
adj_matrix=adjacency_matrix
# fixture for nose tests
def setup_module(module):
from nose import SkipTest
try:
import scipy
except:
raise SkipTest("SciPy not available")
|