ModuleIndex and NodeIndex API problems

[taeruh]

The (public) APIs for ModuleIndex and NodeIndex (in the modular_decomposition crate) are a little bit inconsistent and inconvenient to use:

• md_tree::ModuleIndex is not public, however, the type is used in other public API (MDTree::{root, children, module_kind})
• md_tree::ModuleKind uses md_tree::NodeIndex for the Node variant, but ModuleIndex uses petgraph::graph::NodeIndex
• md_tree::NodeIndex::index returns a usize, but the inner type is actually a u32

These three problems make it a little bit inconvenient to convert, for example, the root node into a petgraph::graph::NodeIndex, which can then be used in the standard petgraph methods. It is possible, but it looks like the following (and it can also not completely put into a helper function since ModuleIndex is not public):

let root = if let ModuleKind::Node(node) = md_tree.module_kind(md_root).unwrap() {
    NodeIndex::from(u32::try_from(node.index()).unwrap())
} else {
    unreachable!()
};

---

Are there specific reasons for the current API? If not, then I would address the issues as follows:

• use petgraph::graph::NodeIndex in ModuleKind::Node (and maybe remove md_tree::NodeIndex?)
• make ModuleIndex public
• expose a method ModuleIndex method that returns the underlining NodeIndex
• maybe make it possible to construct ModuleIndex from petgraph::graph:NodeIndex (From trait?)

But note, that these changes would extend the public API and with that restrict a little bit how things can be changed later on without a breaking change.

What do you think? I could make a PR or PR draft for that if you want (thought I first address the problem in an issue)?

[jonasspinner]

Thank you for bringing that that up. I just want to give a quick reply and look at it a bit more at the weekend.

The initial design goals for the public API was to not rely on any petgraph types. The index types are inspired by petgraph::graph:NodeIndex and mimic the u32 on the inside and usize on the outside for efficiency and convenience. The more user-friendly option might be to fully use the petgraph types in the API.

At a first glance your suggested chances seem like a good idea. You can put them in a PR or I can also take care of that in a few days. Whatever you prefer.

Just a quick question. I'm curious, how did you find the project and how do you use it?

[taeruh]

Thanks, that sounds good; I'll make a PR next week.

I'm using the modular decomposition to find twins, claws and simplicial cliques (cf. growing without cloning) in graphs. These things tend to be easier with the decomposition tree. I haven't used this crate much yet, only just started.
I simply found the project by searching for a Rust implemenation of the algorithm. Luckily enough I found this here; I was not very keen on implementing it from scratch, but also wanted to have a Rust implementation since I might tweak it later on for my specific use case (and Rust is my preferred language for this type of problem).

[jonasspinner]

It's nice to hear that.

I had the time to look into the issue.

• md_tree::ModuleIndex is not public, however, the type is used in other public API (MDTree::{root, children, module_kind})
• make ModuleIndex public

Yes!

• md_tree::NodeIndex::index returns a usize, but the inner type is actually a u32

Similar to the petgraph index types, the index method is used for making indexing into Vec's easier.

• md_tree::ModuleKind uses md_tree::NodeIndex for the Node variant, but ModuleIndex uses petgraph::graph::NodeIndex

There are two kinds of indices for the modular decomposition. The first kind is used to identify the vertices/nodes of the input graph. They are used in ModuleKind::Node. The second kind is used to refer to the modules/nodes of the modular decomposition tree. ModuleIndex is used for that.

Your sample code tries to convert the root from a ModuleIndex to a petgraph::graph::NodeIndex via the ModuleKind of the root. This does not work. The modules with ModuleKind::Node are the leave nodes and the nodes refer to the original graph, not the modular decomposition tree.

I have created a pull request #2. This change removes md_tree::NodeIndex from the public API, makes ModuleKind generic over the node type and adds a method to convert ModuleIndex into a usize.

[taeruh]

Thank you. I looked at the PR and fetched it; it works really well now. Using G::NodeId seems like a good idea to me.

Sorry about the mistake in my example; I was testing on a graph with a single node ..., just trying to make it compile.

Happy to close this here with #2.

[jonasspinner]

Okay, perfect. I'll merge the PR and release a new version.