Add subgraph insertion

[milroy]

As a first step toward elastic scheduling with k8s, flux-sched needs to handle insertion of subgraphs at a target vertex. This will consist of adding capability to resource-query and/or match.

[dongahn]

Sounds good to me!

[milroy]

My first pass effort at this issue uses boost copy_graph. While the time complexity is indicated as O(|V| + |E|), the documentation doesn't specify which graph (parent, subgraph to be inserted, or union) the complexity applies to.

The copy_graph code indicates the vertices and edges of the subgraph to be inserted are added into the parent graph (g_out), which must be a model of MutableGraph.

[dongahn]

Sounds reasonable to me.

As far as adding new vertices and edges does not result in resizing of the underlying std::vector, this would be as good as you get. At first I felt a bit nervous to rely on the reading of the source code -- because the implementation can change while the interface stays the same. But at the same time, we don't want to write code when the code is already implemented inside BGL.

As I understood, once a copy is made, you wanted to splice the original and copied graphs for all the connecting vertices?

[milroy]

That's correct, but raises a question: are there cases where the original graph and subgraph will need to have multiple connecting edges? Are you thinking of the case where multiple original graphs need to be connected to multiple subgraphs (e.g. original containment is connected to subgraph containment, and original network is connected to subgraph network)?

I'll consider alternatives to boost::copy_graph as well.

[dongahn]

@milroy and I discussed this after our meeting yesterday. Two things:

We agreed it would be better to use attach amd detach instead of our initial grow and shrink because the latter set is already used by the execution system in RFC. We thought about join but it has a different meaning in graph theory.

We also discussed ways to attach a sub graph into the existing graph. It seems whether we do this inside or outside the method, we will have to deserialize the sub graph and walk nodes and edges in each subsystem to attach it comprehensively.

@milroy asked what are the major cases where this sub graph is constructed and we agreed that th is will be

• subgraph coming from the parent Flux instance (even if a sibling is giving up on a resource set, will go to the parent and come down)
• external like K2s will capture the currently available resources and serialized then into JGF and pass it to our scheduler
• users can construct a subgraph and this would be mostly for testing.

[dongahn]

@milroy and I chatted about this yesterday. This is also highly related to our work on resiliency (which is my next task to complete). Issue #470.

[dongahn]

@milroy: I'm going to group together issues that support elasticity with a new label.