This is the second post in a two part series regarding the implementation of graph-tool in an environment where it can interact with a peartree network graph. To learn more about how the installation was performed, please see this blog post for the installation notes.
The purpose of this post is to describe how to take a peartree network and convert it to a graph-tool object. This means transferring over all nodes and edges and all attributes related to each. If you google how to do this (with a query like “convert networkx graph to graph-tool”), the best result will be this terrific blog post from a little over 2 years ago (middle of 2016).
While this post is a great (the author back then also acknowledged what a PIA it was to set up, stating: “It’s a bear to get setup, but once you do things get pretty nice. Moving my network viz over to it now!” - link to Tweet), it’s in Python 2 and some aspects of graph-tool have changed slightly.
Advantage of peartree on graph-tool
graph-tool is much faster than NetworkX at evaluation. NetworkX implements graph-algorithms in pure Python and thus trades perforamnce for ease of use. On more complex networks, performance hits can make iterative development difficult or impossible. graph-tool frees up operations to take advantage of parallelization, as well as the traditional advantages of lower level code to perform computation-intensive operations more quickly and efficiently than pure Python approaches.
Let’s look at an example. A common measure of a graph that I perform is the evaluation of betweenness centrality. Here are the results of performing this operation on an identical graph, once in NetworkX and once in graph-tool:
Stats for network graph being evaluated:
- Nodes: 4,969
- Edges: 5,554
Performance on NetworkX: 2min 34s Performance on graph-tool: 756 ms
Relative performance gain for this graph: 203,703.7% faster.
Clearly, graph-tool is the winner in this comparison. For more details on graph-tool’s performance, be sure to check out the project’s own documentation on this, here.
Acknowledging original authorship
In this post, I seek to update the original post’s method and make comments on those changes. In addition, I will be using a peartree network instead of a simple, arbitrary NetworkX graph. That said, thanks to the author, Benjamin Bengfort for his work, which I am merely regurgitating with slight modification here.
Converting from NetworkX to graph-tool
Again, the logic will largely be similar to what was set out in the source blog post. I will just be making note of some modifications made to get this to play with Python 3.
get_prop_type method has been updated. This method is used to process the outputs of the graph elements that are returned from graph-tool’s Python API. The returned objects, particularly string-like values, are returned encoded as bytes so it is necessary to produce a helper function to handle these types before continuing with process logic. Specifically, the changes are meant to ensure that the
key is not converted to ASCII but instead decoded to a Python 3 string type. The same goes for the
The method now looks like this:
Now that we have a method to handle processing output variable types from interfacing with the items from graph-tool, we can largely preserve the logic developed by Benjamin Bengfort from his previous blog post.
I’ve copied the method, here, for reference. Minor updates (primarily related to updates to the NetworkX node and edge iteration API) were made to make the script Python 3 compatible.
Convert a peartree network graph
Now that we’ve ported the script over to be compatible with both newer versions of NetworkX and Python 3, we can attempt to port a peartree graph output to graph-tool and play with it.
First, let’s parse a GTFS feed with peartree. I’ve probably written this step a million times now, but getting a peak hour network graph from peartree is pretty straightforward. Let’s work with AC Transit’s GTFS:
At this point, it is straightforward to plot the system and take a look at what we have:
The above plot script should return this image:
This is the AC Transit system, covering the East Bay of the San Francisco metro area, represented as a network graph.
At this point, we can take that graph and convert it to a graph-tool graph with our new conversion script.
Terrific. This output should produce a graph plot that looks something like the below:
This layout is somewhat arbitrary. Without any specified positions, the network graph will attempt to determine an optimum layout using an algorithm, Scalable Force Directed Placement (SFDP), which is available as part of the graphviz software (installed in the previous post).
If we’d like to plot the locations based off of the x/y values from the original networks stop positions, we can do so by creating a new
PropertyMap and adding it to the vertices:
In this method, we assign the type for this new property map to be a vector, holding two values (x and y) under the key
Now, we can iterate through those values and add them to the network graph, like so:
The output should look similar to our initial plot, from peartree’s first load of the network from AC Transit’s GTFS:
Similarly, we can plot betweenness centrality (or any of a host of other graph algorithms) through graph-tool’s API. With betweenness, we first import the method to calculate this measures impact on both edges and vertices:
Having acquired these new vertices and edge values, we can recalculate the SFDP layout with these modified edge values in consideration.
With those new positions, we can replete the graph, and also use the vertex and edge calculations to inform line width, to help add some further visual clarity:
This produces quite a nice result, where the core of the AC Transit network (and the hinge around downtown Oakland) are particularly visible.
Hope this post helps with other folks looking to obtain higher performance tooling with graph-tool, particularly those working with peartree. Moving forward, I’d like to explore implementation of accessibility algorithms via graph-tool to enable an “all-in-one” approach to network accessibility measures from just peartree on top of graph-tool.