1

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?

JoseOrtiz3
  • 1,785
  • 17
  • 28

1 Answers1

2

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.

sbromberger
  • 1,026
  • 6
  • 12
  • Actually `SimpleGraphs` has the behavior I'm looking for. It preserves node indices for subgraphs (`SimpleGraphs.induce()`). It appears that `LightGraphs` itself consolidates indices to {1, 2,... |V|} during subgraphing. Correct me if I'm wrong. Then I will just use `SimpleGraphs`. – JoseOrtiz3 Dec 08 '19 at 21:47
  • `SimpleGraphs` returns a map for `induced_subgraph()` that tells you where your original vertices were. If that's sufficient, then yes - you're good. Note that accessing a graph using indices (`g[[1,3,5,7]]`) is the same as `induced_subgraph()` but without this vertex mapping. – sbromberger Dec 09 '19 at 02:19
  • I'm a bit confused by "`SimpleGraphs` returns a map for `induced_subgraph`". `LightGraphs.induced_subgraph` returns a (graph, vmap) tuple with the new graph having consolidated node indices, which requires a lot of extra code to calculate vmap1[vmap2[vmap3[....vertex_idx]]] down in the recursion layers to handle subgraphs of subgraphs. `SimpleGraphs.induce` returns only a new graph with node identifiers unchanged, no vmap to worry about, which is the behavior required. – JoseOrtiz3 Dec 09 '19 at 02:59
  • Oh, are you talking about `SimpleGraphs.jl`, the unrelated package? I'm not that familiar with it, but if it does what you need, then that's great. We have some naming overload going on here (there's a history behind that, but it's best left in the past). In any case, glad to hear you found a package that meets your needs. – sbromberger Dec 09 '19 at 05:21
  • 1
    Oh, what a fortuitous accident. Haha. Thanks for the help. – JoseOrtiz3 Dec 09 '19 at 06:58