PgRouting analyzes graphs to find the shortest path between two nodes through edges. In a street network, you can think of nodes as intersections and edges as the streets themselves. I will be using the Chicago street network, which can be found here. I have also uploaded it to the server, named chicagostreets.
1. In order to develop data capable of using PgRouting a source and target geometry must be set up at the start and end of each road. These will serve as the start and end destination points. To perform this follow the “Creating a routable road network” section of this tutorial (blog also has many helpful QGIS tutorials). Another thing to get familiar with in SQL is the WITH Clause. This allows you to reference other SQLs within one query.
2. Once your network is made you can start routing. Follow this tutorial to get multiple options for routing. pgr_dijkstra and pgr_kdijkstraPath are two that work well for visualizing one path or one startpoint to many paths.
3. By joining the geometries in your network to the results of your routing you can import this into QGIS and see your paths.
To reference my SQL query from the tutorial in class, click link.
In order to begin pgrouting you must first set up a a table containing all of your nodes and all of your edges.
My process started with taking all of the roads within a mile buffer of the train stop, finding the nodes at the intersections, then combining the data to create a usable network for routing. A simple tutorial on this can be found under the Create a Routable Road Network section on this blog post.
My interpretation is combined into one step below. Where it says damennetwork is where I name my table. This table will be referenced in the pgRouting SQL later. Anywhere that the SQL says 32 is where I am referencing the gid of the damen train stop. This can be changed to any CTA train stop in Chicago.
CREATE TABLE damennetwork AS
(SELECT transpo.gid, transpo.id, transpo.name, transpo.cost, transpo.geom, source.id as source, target.id as target
FROM
(SELECT
row_number() OVER (ORDER BY transportation.gid)::integer AS gid,
transportation.gid AS id,
transportation.street_nam AS name,
transportation.length AS cost,
transportation.geom,
transportation.geom AS source,
transportation.geom AS target
FROM
(SELECT * FROM cta_railstations
WHERE gid = 32) AS damen
LEFT JOIN transportation
ON st_within(transportation.geom,
st_setsrid(st_buffer(damen.geom, 5280), 3435)))
AS transpo
JOIN
(SELECT row_number() OVER (ORDER BY nodes.gid)::integer AS id,
nodes.gid AS geom
FROM (
SELECT DISTINCT transpo.source AS gid FROM
(SELECT
row_number() OVER (ORDER BY transportation.gid)::integer AS gid,
transportation.gid AS id,
transportation.street_nam AS name,
transportation.length AS cost,
transportation.geom,
transportation.geom AS source,
transportation.geom AS target
FROM
(SELECT * FROM cta_railstations
WHERE gid = 32) AS damen
LEFT JOIN transportation
ON st_within(transportation.geom,
st_setsrid(st_buffer(damen.geom, 5280), 3435))) AS transpo
UNION
SELECT DISTINCT transpo.target AS gid FROM
(SELECT
row_number() OVER (ORDER BY transportation.gid)::integer AS gid,
transportation.gid AS id,
transportation.street_nam AS name,
transportation.length AS cost,
transportation.geom,
transportation.geom AS source,
transportation.geom AS target
FROM
(SELECT * FROM cta_railstations
WHERE gid = 32) AS damen
LEFT JOIN transportation
ON st_within(transportation.geom,
st_setsrid(st_buffer(damen.geom, 5280), 3435))) AS transpo
) AS nodes
GROUP BY nodes.gid)
AS source ON transpo.source = source.geom
JOIN
(SELECT row_number() OVER (ORDER BY nodes.gid)::integer AS id,
nodes.gid AS geom
FROM (
SELECT DISTINCT transpo.source AS gid FROM
(SELECT
row_number() OVER (ORDER BY transportation.gid)::integer AS gid,
transportation.gid AS id,
transportation.street_nam AS name,
transportation.length AS cost,
transportation.geom,
transportation.geom AS source,
transportation.geom AS target
FROM
(SELECT * FROM cta_railstations
WHERE gid = 32) AS damen
LEFT JOIN transportation
ON st_within(transportation.geom,
st_setsrid(st_buffer(damen.geom, 5280), 3435))) AS transpo
UNION
SELECT DISTINCT transpo.target AS gid FROM
(SELECT
row_number() OVER (ORDER BY transportation.gid)::integer AS gid,
transportation.gid AS id,
transportation.street_nam AS name,
transportation.length AS cost,
transportation.geom,
transportation.geom AS source,
transportation.geom AS target
FROM
(SELECT * FROM cta_railstations
WHERE gid = 32) AS damen
LEFT JOIN transportation
ON st_within(transportation.geom,
st_setsrid(st_buffer(damen.geom, 5280), 3435))) AS transpo
) AS nodes
GROUP BY nodes.gid)
AS target ON transpo.target = target.geom);
The launch point of our conversation regarding the prototype which is focused on tracking people and things, hovered around the idea of “dynamic transportation networks”. An interesting and ambitious idea to say the least, but perhaps the idea is more solution than design tool. To open up the proposition and get at some of the fundamentals that might drive the components of such a solution toward design tools, lets abstract back from bus’s + people.
At the very least one would have to know about the following things:
where groups of people were at and where they wanted to go
the state of the network (roads) on which the buses operated
where buses are within the network and what the state of those buses are
To generate dynamic routes for the buses would then involve an algorithm which could find and evaluate paths within the network. This is not unlike systems currently in use by emergency management services to dispatch people and resources for things such as building fires.
To continue the abstraction we could say that the three things we need to be able to do are
identify properties of agents which occupy the network in continuous and discontinuous ways. What or who is at or near a particular node or edge within the network and what properties are exposed to them.
manage the nodes and edges of the network, what are their properties? how do we logically traverse the edges of the network?
formulate singular paths or sub networks from within the network. Consider the way in which a single path through a collection of network nodes, is itself a network, if only a simple one
In this way, the underlying mechanisms that enable us to find say the fastest, or shortest route for a bus might be the same mechanisms that we would use to form ad-hoc networks through nearly any system which can be considered as a network. Perhaps the prototyped design tool might allow it’s user to generate or identify particular sub networks which a person or thing is connected to based on where they are at in space? Of course one of the more interesting conditions of this type of network thinking, still has to do with our “position” or “location” in a network, but perhaps those networks might be logical networks but not physical networks. For instance, where are you located with respect to the social or professional network that is the Architecture community of Chicago, or of the world. Through forming, collecting and analyzing these sub networks over time perhaps we can begin to understand not only where we are or what we are connected to, but how the super networks might be better organized. What kinds of feedback loops can be established here?
Ultimately this question of “Where Is Something”, physically, logically, semantically, is at the heart of what will see in the emerging paradigm of contextual computing.
Technology
Graphs
The graph, a term for network from the area of mathematics referred to as graph theory, describes a collection of nodes and the edges which connect them. Graph theory is one of the most critical and fundamental aspects to computation and data. Much of the underlying data structures for modern software rely on graph representations of system components. Learning how to logically or computationally move or traverse through graphs is essential to searching, sorting, analyzing, and generating: algorithm’s such as Depth-first search, Breadth-first search, Dijkstra’s algorithm, Nearest neighbour algorithm. More specifically algorithm’s such as A* pathfinding algorithms, which underpin much of the artificial intelligence world from video games to data mining, enable goal or objective based navigation of complex networks.
Networks in Databases
To get started operating on data networks it is imperative that we properly store our networked data. While we will likely not be utilizing explicitly graph oriented databases, it is worth mentioning that databases organized around the premise of graph’s exist. In the studio and seminar we will be focusing on the utilization of the postgres/postgis relational database. Fortunately the prevalence of networks in geospatial thinking has lead to the development of some critical tools which aid in our analysis of networks using postgis data structures.
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
Advantages of the database routing approach are:
Data and attributes can be modified by many clients, like Quantum GIS and uDigthrough JDBC, ODBC, or directly using Pl/pgSQL. The clients can either be PCs or mobile devices.
Data changes can be reflected instantaneously through the routing engine. There is no need for precalculation.
The “cost” parameter can be dynamically calculated through SQL and its value can come from multiple fields or tables.
In addition a series of tools for importing data such as street networks have been developed for pgRouting enabling aquisition from sources such as Open Street Map; OSM2PGSQL, and OSM2PGROUTING Tutorials: beginners guide, workshop (extensive)
Startup technologies (first prototype) Without presuming too much about the prototype, it’s safe to say that the system would take some kind of input (perhaps from the physical world i.e. sensor or maybe through an interactive interface), analysis or computation would be performed and some type of network oriented output produced.
Because of the immediacy to topics of transportation and logistics which spear headed the project, I would suggest that you simply begin with the transportation network data which we have access to through the data portal and OSM. A first pass tech prototype would therefore include:
the process of importing this data into pgRouting friendly structures
demonstrable querying and route formation using pgRouting SQL queries
the representation of generated routes within qgis or google earth.
Additional considerations might include the integration of CTA api data into our database. This would involve a simple app which could parse the XML data from the CTA’s system into table structures in our PostGres db for inclusion with base network data.
From this point, we can validate functionality and begin to think more laterally about the criteria used to create and/or interact with the data. We start with shape based networks (road center lines), developing an understanding of how pgRouting is working, then begin to explore other networks and forming networks on the fly rather than as shape file imports.
3. By joining the geometries in your network to the results of your routing you can import this into QGIS and see your paths.
Data Model Prototype 