<jupyter_start><jupyter_text>W3 - Graphs & FieldsIn this workshop we will learn about graphs & fields, and explore their application in configuration design.<jupyter_code>!python -m pip install -e ../topogenesis<jupyter_output><empty_output><jupyter_text>0. Initialization<jupyter_code># importing NumPy and NetworkX for working with graphs
import numpy as np
import networkx as nx 

# importing topogenesis for working wiith lattices / regular-grids
import topogenesis as tg

# importing pyvista for visualizations
import pyvista as pv

# importing Pandas and display for clearer representation of table data and matrices
import pandas as pd
from IPython.display import display<jupyter_output><empty_output><jupyter_text>1. Graphs  1.1. Basic Graph<jupyter_code>G_nodes = [0, 1, 2, 3, 4]
G_edges = [ (0, 1),
            (0, 3),
            (1, 2),
            (1, 3),
            (2, 3),
            (2, 4),
            (0, 4)]

G = nx.Graph()
G.add_nodes_from(G_nodes)
G.add_edges_from(G_edges)<jupyter_output><empty_output><jupyter_text>1.2. Graph drawing<jupyter_code># explicitly set positions
pos = { 
    0: (5, 0.03),
    1: (0, 0), 
    2: (-1, 0.3), 
    3: (2, 0.17), 
    4: (4, 0.255)}

options = {
    "font_size": 30,
    "node_size": 1500,
    "node_color": "white",
    "edgecolors": "grey",
    "edge_color": "white",
    "linewidths": 3,
    "width": 3,
}
nx.draw_networkx(G, pos, **options)<jupyter_output><empty_output><jupyter_text>1.3. Vertex - Vertex Matrix<jupyter_code># VV is a matrix with this shape: number of nodes by number of nodes
VV_shape = (len(G_nodes), len(G_nodes))
# Initialize the empty VV
VV = np.zeros(VV_shape, dtype=int)
# iterate over the egdes
for n1, n2 in G_edges:
    # since the graph is undrirected we fill the matrix 
    # on both side of the diagonal line
    VV[n1, n2] = 1 
    VV[n2, n1] = 1

# display as pandas dataframe
display(pd.DataFrame(VV))<jupyter_output><empty_output><jupyter_text>1.4. Edge - Vertex Matrix<jupyter_code># EV is a matrix with this shape: number of edges by number of nodes
EV_shape = (len(G_edges), len(G_nodes))
# Initialize the empty EV
EV = np.zeros(EV_shape, dtype=int)
# iterate over the edges
for e, (n1, n2) in enumerate(G_edges):
    # set each element at row e and column n1, n2 to 1
    EV[e, n1] = 1 
    EV[e, n2] = 1 

# display as pandas dataframe (tag edges in index for readability)
pd.DataFrame(EV, index=G_edges)<jupyter_output><empty_output><jupyter_text>1.5. Edge - Edge Matrix<jupyter_code># EE is a matrix with this shape: number of edges by number of edges
EE_shape = (len(G_edges), len(G_edges))
# Initialize the empty EE
EE = np.zeros(EE_shape, dtype=int)
# iterate over the edges
for e1 ,(n11, n12) in enumerate(G_edges):
    # for each edge, iterate over the edges
    for e2 ,(n21, n22) in enumerate(G_edges):
        # if they shared any node... (Q+): how are we checking that? in what situation this method will not work properly?
        if (n11-n21) * (n11-n22) * (n12-n21) * (n12-n22) == 0:
            # set those edges as adjacent
            EE[e1, e2] = 1

# subtract the identity matrix since each edge does have nodes in common 
# with itself, but is not considered adjacent to itself
EE -= np.identity(len(G_edges), dtype=int)
# display as pandas dataframe (tag edges in index and columns for readability)
pd.DataFrame(EE, index=G_edges, columns=G_edges)<jupyter_output><empty_output><jupyter_text>1.6. Vertex-Vertex Matrixc in networkx<jupyter_code># you can also extract the VV matrix from networkx.
# notice the nodelist property, it specifies the order 
# of nodes in the rows and columns of the matrix
VV_ = nx.linalg.graphmatrix.adjacency_matrix(G, nodelist=G_nodes)
# convert sparse matrix to dense matrix and display it with pandas
pd.DataFrame(VV_.todense())<jupyter_output><empty_output><jupyter_text>1.7. Activity Relationship Chart (ARC)   Image Source   More Info    2. Fields  2.1. Construct a lattice<jupyter_code># import the streetnetwork as a point cloud
street_network_pc = tg.cloud_from_csv("../data/streetnetwork_pointcloud.csv")

# construct the lattice from voxelating the point cloud 
street_network_lattice = street_network_pc.voxelate([3,3,3], closed=True)
street_network_lattice.shape<jupyter_output><empty_output><jupyter_text>2.2. Visualize the lattice<jupyter_code># initiating the plotter
p = pv.PlotterITK() # ITK plotter for interactivity within the python notebook (itkwidgets library is required)

# fast visualization of the point cloud
street_network_pc.fast_notebook_vis(p)

# fast visualization of the lattice
street_network_lattice.fast_notebook_vis(p, show_outline=True, show_centroids=True)

# Set a camera position
p.camera_position = [(0.25, 0.18, 0.5), (0, .1, 0), (0, 1, 0)]

# plotting
p.show()<jupyter_output><empty_output><jupyter_text>2.3. Construct distance field<jupyter_code># creating neighborhood definition
stencil = tg.create_stencil("von_neumann", 1, 1)
# setting the center to zero
stencil.set_index([0,0,0], 0)

print(stencil)
# retrieve the neighbour list of each cell
neighs = street_network_lattice.find_neighbours(stencil)

# initialize the street network distance lattice with all the street cells as 0, and all other cells as maximum distance possible (which equals to sum of the size of the lattice in all dimensions. Can you explain why?)
sn_dist_lattice = 1 - street_network_lattice
sn_dist_lattice[sn_dist_lattice==1] = np.sum(street_network_lattice.shape)

# flatten the distance lattice for easy access
sn_dist_lattice_flat = sn_dist_lattice.flatten()
# set the maximum distance
max_dist = np.sum(street_network_lattice.shape)
# main loop for breath-first traversal
for i in range(1, max_dist):
    # find the neighbours of the previous step
    next_step = neighs[sn_dist_lattice_flat == i - 1]
    # make a copy of the lattice to prevent overwriting in the memory
    sn_nex_dist_lattice_flat = np.copy(sn_dist_lattice_flat)
    # set the next step cells to the current distance
    sn_nex_dist_lattice_flat[next_step.flatten()] = i
    # find the minimum of the current distance and previous distances to avoid overwriting previous steps
    sn_dist_lattice_flat = np.minimum(sn_dist_lattice_flat, sn_nex_dist_lattice_flat)
    
    # check how many of the cells have not been traversed yet
    filled_check = sn_dist_lattice_flat == np.sum(street_network_lattice.shape)
    # if all the cells have been traversed, break the loop
    if filled_check.sum() == 0:
        print(i)
        break

# reshape and construct a lattice from the street network distance list
sn_dist_lattice = sn_dist_lattice_flat.reshape(sn_dist_lattice.shape)
# set the lattice to be visualized
vis_lattice = sn_dist_lattice

# initiating the plotter
p = pv.Plotter(notebook=True)

# Create the spatial reference
grid = pv.UniformGrid()

# Set the grid dimensions: shape because we want to inject our values
grid.dimensions = vis_lattice.shape
# The bottom left corner of the data set
grid.origin = vis_lattice.minbound
# These are the cell sizes along each axis
grid.spacing = vis_lattice.unit

# Add the data values to the cell data
grid.point_arrays["Street Access"] = vis_lattice.flatten(order="F")  # Flatten the Lattice
    
# adding the volume
opacity = np.array([0.0,0.6,0.6,0.6,0.6,0.6,0.6]) * 0.6
p.add_volume(grid, cmap="coolwarm", clim=[0.0, vis_lattice.max()] ,opacity=opacity)

# plotting
p.show()

# the commented code here is the equivalent of the same process but without the assumption that we are working on a regular grid. Producing the distance lattice through this algorithm will take several hours. (Q+) Can you show why these two approaches are equivalent? Can you explain why the second algorithm takes more time? 
"""
# find the number of all voxels
vox_count = street_network_lattice.size 

# initialize the adjacency matrix
adj_mtrx = np.zeros((vox_count,vox_count))

# Finding the index of the available voxels in avail_lattice
avail_index = np.array(np.where(street_network_lattice == 1)).T

# fill the adjacency matrix using the list of all neighbours
for vox_loc in avail_index:
    # find the 1D id
    vox_id = np.ravel_multi_index(vox_loc, street_network_lattice.shape)
    # retrieve the list of neighbours of the voxel based on the stencil
    vox_neighs = street_network_lattice.find_neighbours_masked(stencil, loc = vox_loc)
    # iterating over the neighbours
    for neigh in vox_neighs:
        # setting the entry to one
        adj_mtrx[vox_id, neigh] = 1.0

# construct the graph 
g = nx.from_numpy_array(adj_mtrx)

# compute the distance of all voxels to all voxels using floyd warshal algorithm
dist_mtrx = nx.floyd_warshall_numpy(g)
"""<jupyter_output><empty_output><jupyter_text>Credits<jupyter_code>__author__ = "<NAME>"
__license__ = "MIT"
__version__ = "1.0"
__url__ = "https://github.com/shervinazadi/earthy_workshops"
__summary__ = "Earthy Design Studio"<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09132727476719399, 'fraction_numerical': 0.01952204644900707, 'mean_word_length': 4.509270704573548, 'pattern_counts': {'":': 7, '<': 50, '<?xml version=': 0, '>': 50, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '521329', 'license': 'MIT', 'n_tokens_mistral': 3143, 'n_tokens_neox': 2960, 'n_words': 967, 'path': 'notebooks/w3_graphs_fields.ipynb', 'repo_name': 'shervinazadi/earthy_workshops', 'size': '8920'}