Julia module for subgraphing a graph (nodes / vertices and edges) without changing or relabeling node indices?

Question

Terminology note: "vertices"="nodes", "vertex/node labels" = "indices"

LightGraphs in Julia changes node indices when producing induced subgraphs.

For instance, if a graph has nodes [1, 2, 3, 4], its LightGraphs.induced_subgraph induced by nodes [3,4] will be a new graph with nodes [3,4] getting relabeled as [1,2].

In state-of-the-art graph algorithms, recursive subgraphing is used, with sets of nodes being modified and passed up and down the recursion layers. For these algorithms to properly keep track of node identities (labels), subgraphing must not change the indices.

Subgraphing in networkx in Python, for instance, preserves node labels.

One can use MetaGraphs by adding a node attribute :id, which is preserved by subgraphing, but then you have to write a lot of extra code to convert between node indices and node :id's.

Is there not a Julia package that "just works" when it comes to subgraphing and preserving node identities?

Answer 1

I'd first like to take the opportunity to clarify some terminology here: LightGraphs itself doesn't dictate a graph type. It's a collection of algorithms and an interface specification. The limitations you're seeing are for SimpleGraphs, which is a graph type that ships with the LightGraphs package and is the default type for Graph and DiGraph.

The reason this is significant is that it is (or at least should be) very easy to create a graph type that does exactly what you want and that can take advantage of the existing LightGraphs infrastructure. All you (theoretically) need to do is to implement the interface functions described in src/interface.jl. If you implement them correctly, all the LightGraphs algorithms should Just Work (tm) (though they might not be performant; that's up to the data structures you've chosen and interface decisions you've made).

So - my advice is to write the graph structure you want, and implement the dozen or so interface functions, and see what works and what doesn't. If there's an existing algorithm that breaks with your interface implementation, file a bug report and we'll see where the problem is.