2
Adjacency matrix and incidence matrix of graphs.
4
# Copyright (C) 2004-2011 by
5
# Aric Hagberg <hagberg@lanl.gov>
6
# Dan Schult <dschult@colgate.edu>
7
# Pieter Swart <swart@lanl.gov>
11
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
12
'Pieter Swart (swart@lanl.gov)',
13
'Dan Schult(dschult@colgate.edu)'])
15
__all__ = ['incidence_matrix',
16
'adj_matrix', 'adjacency_matrix',
20
def incidence_matrix(G, nodelist=None, edgelist=None,
21
oriented=False, weight=None):
22
"""Return incidence matrix of G.
24
The incidence matrix assigns each row to a node and each column to an edge.
25
For a standard incidence matrix a 1 appears wherever a row's node is
26
incident on the column's edge. For an oriented incidence matrix each
27
edge is assigned an orientation (arbitrarily for undirected and aligning to
28
direction for directed). A -1 appears for the tail of an edge and 1
29
for the head of the edge. The elements are zero otherwise.
36
nodelist : list, optional (default= all nodes in G)
37
The rows are ordered according to the nodes in nodelist.
38
If nodelist is None, then the ordering is produced by G.nodes().
40
edgelist : list, optional (default= all edges in G)
41
The columns are ordered according to the edges in edgelist.
42
If edgelist is None, then the ordering is produced by G.edges().
44
oriented: bool, optional (default=False)
45
If True, matrix elements are +1 or -1 for the head or tail node
46
respectively of each edge. If False, +1 occurs at both nodes.
48
weight : string or None, optional (default=None)
49
The edge data key used to provide each value in the matrix.
50
If None, then each edge has weight 1. Edge weights, if used,
51
should be positive so that the orientation can provide the sign.
56
The incidence matrix of G.
60
For MultiGraph/MultiDiGraph, the edges in edgelist should be
63
"Networks are the best discrete model for so many problems in
64
applied mathematics" [1]_.
68
.. [1] Gil Strang, Network applications: A = incidence matrix,
69
http://academicearth.org/lectures/network-applications-incidence-matrix
75
"incidence_matrix() requires numpy: http://scipy.org/ ")
80
edgelist = G.edges(keys=True)
83
A = np.zeros((len(nodelist),len(edgelist)))
84
node_index = dict( (node,i) for i,node in enumerate(nodelist) )
85
for ei,e in enumerate(edgelist):
87
if u == v: continue # self loops give zero column
92
raise NetworkXError('node %s or %s in edgelist '
93
'but not in nodelist"%(u,v)')
99
wt = G[u][v][ekey].get(weight,1)
101
wt = G[u][v].get(weight,1)
108
return np.asmatrix(A)
110
def adjacency_matrix(G, nodelist=None, weight='weight'):
111
"""Return adjacency matrix of G.
118
nodelist : list, optional
119
The rows and columns are ordered according to the nodes in nodelist.
120
If nodelist is None, then the ordering is produced by G.nodes().
122
weight : string or None, optional (default='weight')
123
The edge data key used to provide each value in the matrix.
124
If None, then each edge has weight 1.
129
Adjacency matrix representation of G.
133
If you want a pure Python adjacency matrix representation try
134
networkx.convert.to_dict_of_dicts which will return a
135
dictionary-of-dictionaries format that can be addressed as a
138
For MultiGraph/MultiDiGraph, the edges weights are summed.
139
See to_numpy_matrix for other options.
146
return nx.to_numpy_matrix(G,nodelist=nodelist,weight=weight)
148
adj_matrix=adjacency_matrix
150
# fixture for nose tests
151
def setup_module(module):
152
from nose import SkipTest
156
raise SkipTest("NumPy not available")