Explore alternatives to NetworkX

[s-tikhomirov]

We currently use a Python library called NetworkX for graph modeling. In particular, our route calculation uses NetworkX's all_shortest_paths.

Alternative graph libraries reportedly are much more performant. Examples include: igraph, graph-tool, networkit. Is it worth switching to another graph library?

Note that the current version of the simulator can't be (easily) parallelized. We need to update in-flight HTLCs in channels, which are stored in Python's PriorityQueues inside each ChannelDirection. We use single-threaded functions to get and put elements in / out of the queue. Parallelizing the code would require us to correctly handle the cases where the same queue is updated at the same time from different threads.

We also use (single-threaded) priority queues in Schedule, but the task of creating a schedule doesn't need to be parallelized to begin with.

Further reading:

• Benchmark of popular graph/network packages v2
• What scalability issues are associated with NetworkX?
• Opinions on #igraph vs #netwrokx in #python?
• Working With Large Internal Link Graphs in Python
• What is the maximum number of nodes and edges with attributes that graphs generated by NetworkX package can handle?

[s-tikhomirov]

From a Reddit thread linked above:

Use NetworkX for smaller networks and dynamic networks. NetworkX is pure Python, well documented and handles changes to the network gracefully. iGraph is more performant in terms of speed and ram usage but less flexible for dynamic networks.

Topology-wise, our graph is fixed, but edge attributes (i.e., slot queues) change all the time. Is this considered dynamic?

[szhorvat]

Is this considered dynamic?

igraph developer here. Changing values of attributes is generally fast in igraph. It is only changing the graph topology (i.e. adding or removing edges or vertices) that is expensive.