Routing with graphs

A critical aspect of architectural design is understanding the way people move through and experience a space. Because such experiences tend to be subjective, they have traditionally been difficult to simulate in the computer. However, by treating the problem more narrowly, we can come up with ways of measuring specific aspects of this experience such as how far people travel between different programs in a space (adjacency), and potential bottlenecks where such movement is concentrated (congestion). These occupant-level metrics give a deeper understanding of the space from the point of view of its occupants, and often relate more to the needs of the client than the global form or structural system of the building. To compute these kinds of metrics we can rely on a branch of mathematics called graph theory, which is based on a data structure called a graph.

A graph is defined by a list of nodes (sometimes called vertices) which store some properties and a list of edges which connect sets of two nodes and represent a relationship between them. In a directed graph, edges represent one-way relationships, while in a bi-directional graph (or bi-graph for short) the connections go both ways.

Graph structures are very flexible and can represent many types of relationships. In spatial applications, the nodes typically represent locations in space, and the edges represent relationships or connections between the locations. For example, edges might represent walkable connections between two locations, a section of road, or a public transit line.

If we represent our spatial information as a graph, we can take advantage of many existing algorithms developed for answering specific questions about such structures. For example, if we want to know the length of the shortest path between two points in a space, we can represent all possible paths as a graph of nodes and edges and use Dijkstra’s Algorithm to efficiently compute the shortest path. In this tutorial, we will use an existing Python library to convert geometry from Grasshopper to a graph structure, and then use an implementation of Dijkstra’s Algorithm to find the shortest path between any two nodes in the graph. We will then use this method to generate metrics for the generative design process that measure goals such as decreasing the distance between programs in a floor plan (adjacency) or decreasing the concentrations of traversals within the space (congestion).

Downloading the ‘gd_tools’ library

For this tutorial we will not write all the code from scratch, but will rely on existing code which we will reference into our Python script as a library.

To get started, go to the gd_tools repository on GitHub, download the zip file by clicking the green button in the upper right corner, and uncompress the folder to a local directory on your computer. This repository contains a single python file called ‘gd_tools.py’ which contains a set of functions and class definitions which are useful for generative design applications, including code for generating and analyzing graph structures.

The Python Script node

Now open a blank Rhino and Grasshopper file, and create a single Python Script component with the following inputs:

• lib_path — this is the path to the ‘gd_tools.py’ file downloaded earlier
• lines (type: Line)— a set of connected line segments which represent the edges of the graph
• origins (type: Point3d) — a set of points which specify the starting points for routes in the graph
• destinations (type: Point3d)— a set of points specifying the ending points for routes in the graph

Make sure that you set the lines, sources, and destinations inputs to ‘List Access’ by right-clicking on each input and choosing ‘List Access’ from the context menu. Also, make sure to indicate the type of data that is being input into Python (where specified in the parentheses after the input name above) by right clicking on each input, selecting ‘Type hint’, and selecting the proper type.

Next, set the following outputs for the component:

• edges — will output all edges in the graph as Line objects
• edge_traversals — will output the number of paths going through each edge
• nodes — will output all nodes in the graph as Point3d objects
• node_traversals — will output the number of paths going through each node
• paths — will output all paths as Polyline objects

Inputs and outputs of Python Script node

Defining inputs

To set the location of the gd_tools library, create a File Path component and set a file path by right clicking on the component, selecting ‘Set One File Path’, and searching for the ‘gd_tools.py’ file downloaded earlier. Connect the output of the File Path component to the ‘lib_path’ input of the Python Script node.

Next, we will create some geometry in Grasshopper to input into the Python script. The code we will be using will create a graph from a set of line segments and then route paths between each pair of origin and destination points. For this to work the lines should connect at their end points, and the origin and destination lists should have the same number of points.

To generate the lines, we will first create a set of random points and then connect each one to a set of its closest neighbors. Then we will sample random origin and destination points by shuffling the list of points and slicing it according to the number of routes we want.

This definition requires the standard Grasshopper components Populate 2d, Closest Points, Line, Jitter, and Split List. In addition, we will use the Remove Duplicate Lines component from the Karamba library to make sure that we only pass valid, non-duplicated lines into the Python script. Try to build the definition represented in the image below. If you get stuck, you can download the completed file for this tutorial here.

Sample input geometry (above) and Grasshopper component setup (below)

Writing the script

Now let’s write the Python code for generating the graph and calculating routes. Double-click on the Python Script component to open the script editor and enter the following lines of code in order starting from the top.

The first line of code will import the Rhino.Geometry library so we can work with Rhino geometry in our Python code.

import Rhino.Geometry as rh

From now on we can access any classes and functions of the Rhino geometry library by using the keyword ‘rh’. Next, we need to also import the ‘gd_tools.py’ file download earlier as a library so we can use its classes and functions within our script.

import sys
sys.path.append('\\'.join(lib_path.split('\\')[:-1]))
import gd_tools as gd

To do this we first import the sys library which stores paths where Python searches for libraries. Then we add the local folder specified in the ‘lib_path’ input variable to the list of paths. Finally, we import the gd_tools library and set its keyword to ‘gd’ so we can access its functions more conveniently.

Next, we need to translate the line geometry passed into the ‘lines’ input to a form which can be understood by the ‘gd_tools’ library. The library expects the line information to come in as a 3-dimensional Python list where each line is represented by a list of two points, and each point is represented by a list of three numbers representing the x, y, and z coordinate of the point. For example, a small data set of two lines would look like:

[
    [ [x, y, z], [x, y, z] ],
    [ [x, y, z], [x, y, z] ]
]

To generate this data from the input line geometry we first make an empty list to store the data, and then iterate over the ‘lines’ input, using some Rhino.Geometry functions to get the necessary data from each line and its end points:

line_data = []
for line in lines:
    p_1 = line.ToNurbsCurve().PointAtStart
    p_2 = line.ToNurbsCurve().PointAtEnd
    line_data.append([[p_1.X, p_1.Y, p_1.Z], [p_2.X, p_2.Y, p_2.Z]])

The .ToNurbsCurve() function first converts the line to a Nurbs curve, which allows us to use its .PointAtStart and .PointAtEnd properties to get the start and end points as Point3d objects. We can then use the points’ .X , .Y , and .Z properties to get the coordinates of the points and store them in the proper list structure.

Next, we will use the .lines2graph() function of the ‘gd_tools.py’ library to build a graph structure from the lines data:

graph = gd.lines2graph(line_data)

To make sure the graph was generated correctly, you can print the graph structure by adding the line:

print graph

This will list all of the node objects with their coordinates, as well as the edge objects with the nodes they connect.

Next, we need to process the origin and destination point information in a similar way as the line information. The ‘gd_tools.py’ library expects the point data as a 2-dimensional list, with each point represented as a list of three numbers representing its x, y, and z coordinates. In this case, instead of using a full ‘for’ loop we can process the data more efficiently with list comprehensions:

origins = [[p.X, p.Y, p.Z] for p in origins]
destinations = [[p.X, p.Y, p.Z] for p in destinations]

These list comprehensions efficiently convert a list of Point3d objects to a list of lists of the points’ coordinates.

Next, we will create an empty list to store the Polyline geometry of the paths we generate:

paths = []

Now we are ready to loop over the origin and destination points to generate the paths. Copy the following block of code into your script, being careful to follow the proper indent structure:

for i in range(len(origins)):
    origin_node = graph.search_node(origins[i])
    dest_node = graph.search_node(destinations[i])
    
    path_nodes = graph.get_route(origin_node, dest_node)
    if path_nodes:
        print "[", str(i), "] route found -->", [n.get_id() for n in path_nodes]
    else:
        print "[", i, "] no route found"
        continue
    all_points = [rh.Point3d(*n.get_coords()) for n in path_nodes]
    paths.append( rh.PolylineCurve(all_points) )

The first line iterates according to the length of the ‘origins’ list (which should match the length of the ‘destinations’ list). The next two lines pull out a single point from both the origins and destinations lists and process them through the graph’s .search_node() method. This method will search the graph for a node that matches the location of the input point. If it finds one it will return a reference to that node. If not, it will create a new node, create an edge between it and the closest node in the graph, and return a reference to the new node. Thus the code will work whether or not the origin and destination points exist in the original graph. We will store the references to these two nodes in the origin_node and dest_node variables.

The next line uses the graph’s .get_route() method to trace the shortest route between the two nodes. If it is able to find a route, the method will return a list of node objects through which the path travels. If it can’t find a route (for example if the graph is disconnected), it returns ‘None’.

The next section of code uses a conditional to check whether a route was found and either prints the ID’s of the traversed nodes, or prints that no route was found and continues to the next set of points (the ‘continue’ statement exits out of the current loop iteration and goes directly to the next one). This conditional works because when tested as a boolean, a ‘None’ returns ‘False’, while any valid data type returns ‘True’.

The last two lines of code generate the Polyline geometry of the found route and store it in the ‘paths’ list variable. The first line uses a list comprehension to get the coordinates of each node object in the ‘path_nodes’ list and convert them to a list of Rhino Point3d objects. The * symbol right before n.get_coords() converts the list of coordinates output by the node’s .get_coords() method to a set of arguments as expected by the .Point3d() function. The second line passes the list of Point3d objects to the .PolylineCurve() function which builds a Polyline object going through those points. This Polyline is then appended to the ‘paths’ list variable which stores the geometry of all the paths.

Once all the routes have been computed, we want to export the node and edge geometry as well as the number of routes going through them. We will use this data later for visualization and metric computation.

edges = [rh.Line(rh.Point3d(*e.get_nodes()[0].get_coords()), rh.Point3d(*e.get_nodes()[1].get_coords())) for e in graph.get_edges()]
edge_traversals = [e.get_traversal() for e in graph.get_edges()]
nodes = [rh.Point3d(*n.get_coords()) for n in graph.get_nodes()]
node_traversals = [n.get_traversal() for n in graph.get_nodes()]

The first line of code converts the edges of the graph to a list of Line objects using a single list comprehension. If you unpack the code you will see that it is iterating over the edges of the graph which is returned by the graph’s .get_edges() method. For each of the edges, both of its end nodes (retrieved by the edge’s .get_nodes() method) are first converted to Point3d objects, and then passed into the .Line() function to create the Line geometry.

The next line uses a list comprehension to iterate over each edge in the graph and store it’s traversals (the number of routes going through it) in a list. The following two lines use very similar list comprehensions to get the nodes and store them as a list of Point3d objects and to get the traversals going through the nodes. These geometries and traversal counts will be output from the Python script back to Grasshopper where we can use them for visualization and computing metrics. When you are done with the code press the ‘Ok’ button to exit out of the script editor window.

Visualizing outputs

Next, we will use Grasshopper to visualize the computed routes and the traversals in the graph. For the line visualizations we will rely on the Custom Preview Lineweights component from the Human library for Grasshopper. This is a very useful library for creating custom visualizations in Grasshopper beyond what you can do with the standard components.

First, let’s visualize the chosen origin and destination points, as well as the traced routes, using the Dot Display component to visualize the points and the Custom Preview Lineweights component from the Human library to visualize the lines. To make the points and lines more visible we can use a black color generated by the Colour Swatch component and a heavier lineweight.

Next we will visualize the edges of the whole graph according to the number of routes which go through them. This traversal data can be used to predict the ‘congestion’ within the graph, or the edges which have the most routes running through them. To visualize the edges we will use the Custom Preview Lineweights component to give custom color and lineweight to the Line geometry coming from the Python component’s ‘edges’ output. To generate a range of colors corresponding to the number of traversals in each edge, we use a Gradient node which receives the list of traversal values remapped to the range [0,1] and maps them to a set of colors. To generate a range of line widths we do a similar remapping, this time using a range of [1,10] (corresponding to 1px for the lightest line and 10px for the heaviest).

Finally, let’s use a similar strategy to visualize the nodes according to their traversals. This definition is almost exactly the same as the one for visualizing edges except using the Dot Display component and a smaller range of [0.10, 0.50] for the dot sizes.

This completes the basic graph routing tutorial. If you got lost along the way, you can download the final definition here.

Computing metrics

Besides visualization, we can also use the graph data to compute a variety of metrics relevant to the experience of a space. For example, we can measure the lengths of the Polyline paths to compute more accurate travel distances between different programs in a space. We can also use the node and edge traversal data as a proxy for the congestion in the space, or the areas where many paths are likely to overlap. In the following section we will look at two sample Generative Design models which use graph routing to optimize a space plan based on desired adjacency and distribution of congestion.