Question about gomory_hu_tree for multi-component graphs

Usage
,
1

Can the Graph().gomory_hu_tree() method be directly applied to an undirected graph with multiple components or do we have to run Graph().decompose() first to get a list of every connected component, then run Graph().gomory_hu_tree() on each component?

My intuition is that running the algorithm on the whole graph should return a gomory hu tree where the shortest path between two nodes not connected in the original graph should have an edge with weight 0. This seems to be the case for a few sample graphs I tried (up to 600 components), but is this guaranteed?

2

Yes, this should work.

3

Thanks! Also I’m wondering, does this algorithm (and other flow algorithms in iGraph) work with non-integer / non-whole number capacities (unlike Ford Fulkerson)?

4

Yes.

All limitations should be mentioned in the documentation of the C library, igraph Reference Manual