{"id":479,"date":"2014-07-23T09:56:25","date_gmt":"2014-07-23T09:56:25","guid":{"rendered":"https:\/\/block.arch.ethz.ch\/blog\/?p=479"},"modified":"2014-07-24T11:08:43","modified_gmt":"2014-07-24T11:08:43","slug":"networks-of-bars-and-nodes","status":"publish","type":"post","link":"https:\/\/block.arch.ethz.ch\/blog\/2014\/07\/networks-of-bars-and-nodes\/","title":{"rendered":"Networks of bars and nodes"},"content":{"rendered":"

Many calculations in structural design involve networks of bars (or branches, edges, …) and nodes (or vertices, …). Essential to these calculations is information about how the elements of the network are connected. This connectivity can be described with a matrix.<\/p>\n

<\/p>\n

Connectivity matrix<\/h2>\n

Each row in a connectivity matrix corresponds to a bar of the network and contains zeros in all columns, except in the columns of the nodes to which it is connected. There the entries are ‘-1’ and ‘+1’ indicating the direction of the edge:<\/p>\n

\\begin{equation}
\n C_{ij} = \\left\\{
\n \\begin{aligned}
\n +1 & \\text{ if vertex } i \\text{ is the head of edge } j\\\\
\n -1 & \\text{ if vertex } i \\text{ is the tail of edge } j\\\\
\n 0 & \\text{ otherwise}
\n \\end{aligned}
\n \\right.
\n\\end{equation}<\/p>\n

The direction of the edges can be chosen arbitrarily. A typical convention is to direct all edges from the vertex with the lower index to the one with the higher index. Constructing a connectivity matrix in Python is easy if you have list of edge vertex pairs.<\/p>\n

\r\nimport numpy as np\r\n\r\nedges = [[0, 4], [1, 4], [2, 4], [3, 4]]\r\nvertices = [[0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0], [0.5, 0.5, 0]]\r\n\r\nm = len(edges)\r\nn = len(vertices)\r\n\r\nC = np.zeros((m, n))\r\nfor i in range(m):\r\n    u, v = edges[i]\r\n    C[i, u] = -1\r\n    C[i, v] = +1\r\n\r\n# print C\r\narray([[-1.,  0.,  0.,  0.,  1.],\r\n      [ 0., -1.,  0.,  0.,  1.],\r\n      [ 0.,  0., -1.,  0.,  1.],\r\n      [ 0.,  0.,  0., -1.,  1.]])\r\n<\/pre>\n
Once you have the connectivity matrix, it is easy to compute some of the properties of the elements of the network.<\/p>\n
\r\nxyz = np.array(vertices)\r\n\r\n# coordinate difference vectors\r\nuvw = C.dot(xyz)\r\n\r\n# edge lengths\r\nl = np.sqrt(np.sum(np.square(uvw), axis=1))\r\n# or, since operations like ** are elementwise\r\nl = np.sum(uvw**2, axis=1)**0.5\r\n\r\n# make l into a column vector\r\nl = l.reshape((-1, 1))\r\n\r\n# normalized coordinate difference vectors\r\nunit = np.divide(uvw, np.tile(l, 3))\r\n# or, since numpy does something called 'broadcasting'\r\nunit = np.divide(uvw, l)\r\n# or, since operations like \/ are elementwise\r\nunit = uvw \/ l\r\n<\/pre>\n
Laplacian matrix, Degree matrix, Adjacency matrix<\/h2>\n
The laplacian matrix of a network can be derived from its connectivity matrix.<\/p>\n
\r\nL = C.T.dot(C)\r\n\r\n# print L\r\narray([[ 1.,  0.,  0.,  0., -1.],\r\n      [ 0.,  1.,  0.,  0., -1.],\r\n      [ 0.,  0.,  1.,  0., -1.],\r\n      [ 0.,  0.,  0.,  1., -1.],\r\n      [-1., -1., -1., -1.,  4.]])\r\n<\/pre>\n
The laplacian matrix contains on its diagonal the degree of each vertex of the network.<\/p>\n
\r\ndegree = L.diagonal()\r\n\r\n# print degree\r\narray([ 1.,  1.,  1.,  1.,  4.])\r\n<\/pre>\n
The laplacian matrix is related to the degree matrix and the adjacency matrix in the following way:<\/p>\n
\\begin{equation}
\n\\mathbf{L} = \\mathbf{D} – \\mathbf{A}
\n\\end{equation}<\/p>\n
Therefore, the adjacency matrix can be derived from the laplacian matrix like this<\/p>\n
\r\nD = np.diagflat(degree)\r\nA = D - L\r\n\r\n# print A\r\narray([[ 0.,  0.,  0.,  0.,  1.],\r\n      [ 0.,  0.,  0.,  0.,  1.],\r\n      [ 0.,  0.,  0.,  0.,  1.],\r\n      [ 0.,  0.,  0.,  0.,  1.],\r\n      [ 1.,  1.,  1.,  1.,  0.]])\r\n<\/pre>\n
Sparse matrices<\/h2>\n
Text will follow later…<\/p>\n
\r\nfrom scipy.sparse import coo_matrix, diags\r\n\r\nm = len(edges)\r\ndata = np.array([-1]*m + [1]*m)\r\nrows = np.array(range(m) + range(m))\r\ncols = np.array([edge[0] for edge in edges] + [edge[1] for edge in edges])\r\nC = coo_matrix((data, (rows, cols))).tocsr()\r\nL = C.transpose().dot(C)\r\nD = diags([L.diagonal()], [0])\r\nA = D - L\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Many calculations in structural design involve networks of bars (or branches, edges, …) and nodes (or vertices, …). Essential to these calculations is information about how the elements of the network are connected. This connectivity can be described with a matrix.<\/p>\n","protected":false},"author":11,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-479","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/block.arch.ethz.ch\/blog\/wp-json\/wp\/v2\/posts\/479","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/block.arch.ethz.ch\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/block.arch.ethz.ch\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/block.arch.ethz.ch\/blog\/wp-json\/wp\/v2\/users\/11"}],"replies":[{"embeddable":true,"href":"https:\/\/block.arch.ethz.ch\/blog\/wp-json\/wp\/v2\/comments?post=479"}],"version-history":[{"count":51,"href":"https:\/\/block.arch.ethz.ch\/blog\/wp-json\/wp\/v2\/posts\/479\/revisions"}],"predecessor-version":[{"id":546,"href":"https:\/\/block.arch.ethz.ch\/blog\/wp-json\/wp\/v2\/posts\/479\/revisions\/546"}],"wp:attachment":[{"href":"https:\/\/block.arch.ethz.ch\/blog\/wp-json\/wp\/v2\/media?parent=479"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/block.arch.ethz.ch\/blog\/wp-json\/wp\/v2\/categories?post=479"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/block.arch.ethz.ch\/blog\/wp-json\/wp\/v2\/tags?post=479"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}