Find an alternative to the graph_tool dependency
Issue
The library uses graph to order operators and find independent execution paths. For now we use graph_tool to handle all the graph logic and associated algorithms. This module is not pip installable and has a very long to build time with important memory requirements. We do not need such a high performance graph library for our use case with O(100) nodes (operators). Moreover this module is currently a blocking point for the portable hysop library (see issue #41 (closed)). We could easily scale to thousand of operators with a simple python only module.
Requirements
- Support for directed graphs
- Identification of nodes with integer ids
- Custom edge and vertex properties: int, string and generic python objects
- Algorithms: is_DAG, remove parallel edges, topological sort, transitive reduction, all simple paths from A to B
- Serialization for MPI support (may be required to get the same graph on each node).
- Optional: GUI support for display
Graphtool alternatives
Here we list maintained alternatives to graph_tool and their features:
| Module | Python 2 | Python 3 | Build time | Size | Latest release | Licence | Dependencies |
|---|---|---|---|---|---|---|---|
| NetworkX | pip (2.2) | pip (2.4) | Python only | 7.4MB | 2.4 (2019) | 3-clause BSD | python modules |
| igraph | pip (0.8.0) | pip (0.8.0) | C library, 36s | 10MB | 0.8.1 (2020) | GNU GPLv2 | libxml2, zlib, gmp |
| Features | directed | node identifier | edge/vertex properties | algorithms | serialization | GUI |
|---|---|---|---|---|---|---|
| NetworkX | yes | any hashable object | object/object | all required | builtin with pickle | basic rendering, possibility of interaction with pyvis |
| igraph | yes | int | object/object | all required | manual with pickle | basic rendering |
Those two alternatives are worth a try, with a slight advantage for NetworkX (python only, builtin pickling). Performance-wise igraph may be a better choice due to its C core library. The pyvis module can be used to provide interactive graphs with any graph backend. Thus we will first try to introduce NetworkX along with optional pyvis for interactive visualization of graphs.
TODO list
- Patch hysop/core/graph/*.py to work with the new graph module
- Check that everything works like before for serial problems
- Upgrade docker image for CI
- Check regressions for MPI support
- Implement GUI support with pyvis
Notes
Topological sort has been replaced with lexicographical topological sort based on graph node id (which is based on insertion order in the graph). All related MPI problems should be resolved now.
The GUI has been completely reworked to show more information on graph:
Miscellaneous
This change may also solve a problem linked to setting MKL_THREADING_LAYER to something other than OMP because graph_tools was compiled against GNU OpenMP.