### comparison env/lib/python3.9/site-packages/networkx/algorithms/bipartite/matrix.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """
2 ====================
4 ====================
5 """
6 import itertools
7 from networkx.convert_matrix import _generate_weighted_edges
8 import networkx as nx
9
11
12
14 G, row_order, column_order=None, dtype=None, weight="weight", format="csr"
15 ):
16 r"""Returns the biadjacency matrix of the bipartite graph G.
17
18 Let G = (U, V, E) be a bipartite graph with node sets
19 U = u_{1},...,u_{r} and V = v_{1},...,v_{s}. The biadjacency
20 matrix _ is the r x s matrix B in which b_{i,j} = 1
21 if, and only if, (u_i, v_j) \in E. If the parameter weight is
22 not None and matches the name of an edge attribute, its value is
24
25 Parameters
26 ----------
27 G : graph
28 A NetworkX graph
29
30 row_order : list of nodes
31 The rows of the matrix are ordered according to the list of nodes.
32
33 column_order : list, optional
34 The columns of the matrix are ordered according to the list of nodes.
35 If column_order is None, then the ordering of columns is arbitrary.
36
37 dtype : NumPy data-type, optional
38 A valid NumPy dtype used to initialize the array. If None, then the
39 NumPy default is used.
40
41 weight : string or None, optional (default='weight')
42 The edge data key used to provide each value in the matrix.
43 If None, then each edge has weight 1.
44
45 format : str in {'bsr', 'csr', 'csc', 'coo', 'lil', 'dia', 'dok'}
46 The type of the matrix to be returned (default 'csr'). For
47 some algorithms different implementations of sparse matrices
48 can perform better. See _ for details.
49
50 Returns
51 -------
52 M : SciPy sparse matrix
53 Biadjacency matrix representation of the bipartite graph G.
54
55 Notes
56 -----
57 No attempt is made to check that the input graph is bipartite.
58
59 For directed bipartite graphs only successors are considered as neighbors.
60 To obtain an adjacency matrix with ones (or weight values) for both
61 predecessors and successors you have to generate two biadjacency matrices
62 where the rows of one of them are the columns of the other, and then add
63 one to the transpose of the other.
64
66 --------
69
70 References
71 ----------
73 ..  Scipy Dev. References, "Sparse Matrices",
74 https://docs.scipy.org/doc/scipy/reference/sparse.html
75 """
76 from scipy import sparse
77
78 nlen = len(row_order)
79 if nlen == 0:
80 raise nx.NetworkXError("row_order is empty list")
81 if len(row_order) != len(set(row_order)):
82 msg = "Ambiguous ordering: row_order contained duplicates."
83 raise nx.NetworkXError(msg)
84 if column_order is None:
85 column_order = list(set(G) - set(row_order))
86 mlen = len(column_order)
87 if len(column_order) != len(set(column_order)):
88 msg = "Ambiguous ordering: column_order contained duplicates."
89 raise nx.NetworkXError(msg)
90
91 row_index = dict(zip(row_order, itertools.count()))
92 col_index = dict(zip(column_order, itertools.count()))
93
94 if G.number_of_edges() == 0:
95 row, col, data = [], [], []
96 else:
97 row, col, data = zip(
98 *(
99 (row_index[u], col_index[v], d.get(weight, 1))
100 for u, v, d in G.edges(row_order, data=True)
101 if u in row_index and v in col_index
102 )
103 )
104 M = sparse.coo_matrix((data, (row, col)), shape=(nlen, mlen), dtype=dtype)
105 try:
106 return M.asformat(format)
107 # From Scipy 1.1.0, asformat will throw a ValueError instead of an
108 # AttributeError if the format if not recognized.
109 except (AttributeError, ValueError) as e:
110 raise nx.NetworkXError(f"Unknown sparse matrix format: {format}") from e
111
112
114 r"""Creates a new bipartite graph from a biadjacency matrix given as a
115 SciPy sparse matrix.
116
117 Parameters
118 ----------
119 A: scipy sparse matrix
120 A biadjacency matrix representation of a graph
121
122 create_using: NetworkX graph
123 Use specified graph for result. The default is Graph()
124
125 edge_attribute: string
126 Name of edge attribute to store matrix numeric value. The data will
127 have the same type as the matrix entry (int, float, (real,imag)).
128
129 Notes
130 -----
131 The nodes are labeled with the attribute bipartite set to an integer
132 0 or 1 representing membership in part 0 or part 1 of the bipartite graph.
133
134 If create_using is an instance of :class:networkx.MultiGraph or
135 :class:networkx.MultiDiGraph and the entries of A are of
136 type :class:int, then this function returns a multigraph (of the same
137 type as create_using) with parallel edges. In this case, edge_attribute
138 will be ignored.
139
141 --------
143 from_numpy_array
144
145 References
146 ----------
148 """
149 G = nx.empty_graph(0, create_using)
150 n, m = A.shape
151 # Make sure we get even the isolated nodes of the graph.
153 G.add_nodes_from(range(n, n + m), bipartite=1)
154 # Create an iterable over (u, v, w) triples and for each triple, add an
155 # edge from u to v with weight w.
156 triples = ((u, n + v, d) for (u, v, d) in _generate_weighted_edges(A))
157 # If the entries in the adjacency matrix are integers and the graph is a
158 # multigraph, then create parallel edges, each with weight 1, for each
159 # entry in the adjacency matrix. Otherwise, create one edge for each
160 # positive entry in the adjacency matrix and set the weight of that edge to
161 # be the entry in the matrix.
162 if A.dtype.kind in ("i", "u") and G.is_multigraph():
163 chain = itertools.chain.from_iterable
164 triples = chain(((u, v, 1) for d in range(w)) for (u, v, w) in triples)