nbolten / unweaver

A flexible, composable config-based, research-oriented routing engine

Unweaver

Visit https://unweaver.org for the official documentation.

Unweaver is a routing engine focused on flexibility. It can read many data formats (including OpenStreetMap), find shortest-path routes via a web API, and allows completely customizable combinations of cost functions and directions specifications, summarized in "profiles". Unweaver's costing strategy includes dynamics (as opposed to precalculated) edge costs for when profiles need to be heavily parameterized on a per-user basis.

If you want to use unweaver as a command line application or library, see the installation section. If you want to contribute to the development of unweaver itself, see CONTRIBUTING.md.

Installation

unweaver can be used as a command line application or a library that can be used to develop new applications or analyze geospatial networks in a Jupyter notebook.

Regardless of the way you install and use unweaver, it has a set of non-Python dependencies that will need to be installed on your system first.

• Go here to get instructions on installing the non-Python dependencies required by unweaver.

• Go here to get instructions on installing unweaver as a command line application.

• Go here to get instructions on installing unweaver as a library.

Install and configure non-python dependencies

Unweaver depends on the following software packages in order to run:

• SQLite: A file-based SQL database and the format of the routable GeoPackage created by unweaver.
• SpatiaLite: An extension for SQLite that adds geospatial support.
• GDAL: A common geospatial library for reading/writing geodata formats.
• proj4: A common geospatial library for managing map (re)projections.

Platform-specific installation instructions

On a Mac using Homebrew:

brew install sqlite libspatialite gdal proj

(See this troubleshooting on Mac section if you still can't load SQLite extensions with unweaver)

On a debian-based distribution:

apt install libsqlite3 libspatialite libgdal libproj

Enable SQLite extension support in Python

Python may be distributed with or without SQLite and extensions support. For example, if you are using pyenv to manage your Python installation, you will need to ensure it is built with flags enable SQLite support.

Install unweaver as a command line application

Unweaver is build with the poetry toolkit. When Unweaver is properly released on PyPI, installing the module will be as simple as running poetry add unweaver. For now, it must be installed from this repository. This can be done using either with poetry (ideal) or pip (for backwards compatibility).

With pip:

This can be done with a one-liner:

pip install git+https://github.com/nbolten/unweaver.git@f9f4bed#egg=unweaver

Where the @ entry is the commit. This can also be set to a branch name.

Install unweaver as a library

With poetry:

Edit your pyproject.toml to include a line like this under [tool.poetry.dependencies]:

unweaver = {git = "https://github.com/nbolten/unweaver.git", rev = "f9f4bed"}

You can choose rev to be whatever git commit hash you want to use.

With pip:

This can be done with a one-liner:

pip install git+https://github.com/nbolten/unweaver.git@f9f4bed#egg=unweaver

Where the @ entry is the commit. This can also be set to a branch name.

Data format flexibility

Unweaver can ingest any linear (LineString) format processable by GDAL, including GeoJSON and Shapefiles. The primary graph data structure created from these data is a portable, routable GeoPackage.

This GeoPackage stores network information in an edge list format using two feature tables: nodes and edges.

nodes has a primary key (fid), a unique node id (_n), and a Point geometry column (geom by default). The nodes table can be extended to include any number of other columns, but unweaver does not automatically do so during the build step at this time.

edges has a primary key (fid) a unique pair of node ids that describe the edge (_u and _v), and a LineString geometry column. The edges table is automatically extended during the build process, transforming input linear data properties into column names and values. For example, a "length" numeric property in the input data will result in the creation of a numeric "length" column populated with the associated values. The use of _u and _v to uniquely identify an edge means that unweaver describes a digraph and not a multidigraph. Multidigraph support is planned for the near future, as real-world networks frequently have multiple paths starting and ending at the same location.

Running the example

Get the data

The example expects there to be a GeoJSON file representing a sidewalk network in the example/layers directory. You may need to create the layers directory. Unfortunately, we don't have a consistent place to put this example data yet, so to get it please request it from someone at the Taskar Center or from the repo author.

Build the graph

Run unweaver build ./example in the main repo. If you are running Unweaver as a developer using poetry, run poetry run python -m unweaver build ./example.

This will create example/graph.gpkg, a GeoPackage that Unweaver can use for network queries, including routing.

Weight the graph

Run unweaver weight ./example in the main repo. If you are running Unweaver as a developer using poetry, run poetry run python -m unweaver weight ./example.

This will update example/graph.gpkg with a precalculated weight value for a (necessarily non-representative) stereotyped manual wheelchair user.

Run the web server

Run unweaver serve ./example in the main repo. If you are running Unweaver as a developer using poetry, run poetry run python -m unweaver server ./example.

This will run a Flask web server to which requests to the /shortest_path/<profile>.json, /shortest_path_tree/<profile>.json, and /reachable_tree/<profile>.json endpoints may be sent.

Troubleshooting

Can't load extensions on a Mac

Unweaver needs to load the SpatiaLite extension for SQLite3, but the version of SQLite3 that comes with Macs cannot load extensions by default. You will need to:

1. Install sqlite3 from a third party, such as homebrew: brew install sqlite3
2. After installing (or after running brew link sqlite3), follow the instructions to set up your PATH and library flag locations to be the homebrew ones. This will involve editing your shell's config, usually .bashrc or .zshrc.
3. Ensure that your environment is set up correctly by opening a new terminal and running which sqlite3. If the path is /usr/bin/sqlite3 and not a path with the word Cellar in it, your environment is not correct and you need to (1) run source .bashrc (or .zshrc) to enable it in your current environment, then test again, and (2) troubleshoot your environment until it automatically loads your shell config automatically (sometimes a restart is required).
4. Install Python such that it links to this sqlite3 or builds its own with extension support. pyenv can be configured to do so with some flags. Example here.
5. Use this version of Python to set up your poetry environment below using poetry env <path/to/your/pyenv/bin/python or <path/to/your/pyenv/bin/python> -m venv venv to create a non-poetry custom virtual environment.

unweaver's Issues

`invert` is not used by the reachable function web API

Documentation for running the Web API

1. The README.md says that you have to run poetry run python -m unweaver server ./example to run the server; however, the correct command should be poetry run python -m unweaver serve ./example (i.e. change server to serve).
2. There isn't any documentation on how to format the web requests to send to the server.

Load different spatialite extension on Macs

Macs expect the load_module function to point to "mod_spatialite", not "mod_spatialite.so".

Handle transactions effectively for different use cases

Unweaver currently sets the SQLite isolation level to None, which disables implicit transactions. This has decreased the chance of the database being left in a non-connectable state, but also means that transactions are effectively unused throughout the application. Recently, this led to the discovery that the initial bulk import of graph edges was thousands of times slower than necessary (and a hacky fix was applied).

We should be more deliberate and strategic when it comes to the use of transactions. This issue is a starting point for that discussion / strategizing.

Some initial ideas:

1. Restore global isolation levels and fix the previous bugs in a different way.
2. Use implicit transaction isolation levels for some connections and not others.
3. Make explicit use of transactions at certain points in the code (conn.execute("BEGIN"); conn.execute(...); conn.execute("COMMIT")).

Return node information from Web API

Currently when requesting a walkshed from the Web API, the GeoJSON contains information about the edges (footways, sidewalks, etc), but there is no information about the nodes (raised, lowered curb, etc), only the cost at each node. I think it will be very useful to have access to that node information in the returned GeoJSON as well.

Create a project generator command

Create a project initialization command so that a working set of default files can be easily generated.

Disallow profile IDs incompatible with SQLite column names

Add a check for profile IDs vs. SQLite column naming requirements so that users (and we) don't accidentally use them and get opaque errors.

README improvements

• Add specific instructions on how to install python dependencies for windows or linux
• Step 4 of Mac specific instructions applies to linux installation
• Clarify what to do with the pyproject.toml for different uses of unweaver

Add code test coverage report (possibly a requirement)

Some recent bugs are due to not testing certain scopes of the Unweaver code base. All code in Unweaver should be run at least once during testing to avoid these kinds of issues.

Transition to multi-directed graphs

We currently only support a directed graph representation (a networkx DiGraph wrapper). Real-world transportation networks are multigraphs, so we should be supporting a networkx MultiDiGraph wrapper.

Create test case for 'origin' or 'both' in candidates check

As of commit 789fe90, line 209 would always fail with a ValueError, saying too many values to unpack (expected 2). The new commit b150746 should fix this, but this also means our test suite didn't catch the error!

We should create a test that fails when using G[u] but succeeds with G.successors[u], per that line 209.

Implement input points as destinations, not just origins

Currently the input points can only be used as origin points of a walkshed, so adding the option to use those points as destinations. This would require identifying the start node differently but also reversing the cost function.