Definition of SiblingSubgraph

[lmondada]

@acl-cqc has pointed out that my definition of a subgraph was a bit hard to follow. I have suggested the following rewording of the well-formedness conditions.

See below for details, or #336 (comment) for the original discussion.

What do people think?

[lmondada]

To make this self-contained:

I suggest defining sibling subgraphs as follows.

Let $G = (V, E)$ be a graph and $B$ the set of boundary edges. Edges in $B$ can be an incoming boundary edge, an outgoing boundary edge, or both. Then the subgraph defined by $B$ is the graph given by the connected components of $G' = (V, E \setminus B)$ that contain a node that is either the target of an incoming boundary edge, or the source of an outgoing boundary edge.

A subgraph is well-formed if every edge in $B$ into the subgraph is an incoming boundary edge and every edge in $B$ pointing out of the subgraph is an outgoing boundary edge.

As an edge case, the subgraph $B = \varnothing$ is defined as the entire graph $G$.

This would easily allow the definition of subgraphs such as the following:

graph TD
  0-->|incoming|1
  subgraph "subgraph"
  2-->1
  end
  1-->|outgoing|3

Loading

More generally, any subgraph can be defined in this way, except for the empty subgraph. I think it is good to be able to define non-convex subgraphs, as that makes the convexity check more useful. Restricting the type of subgraphs that are representable would mean one of two things

• we push (part of) the convexity check to the client by implicitly assuming that the subgraph is convex (e.g. only allowing induced subgraphs given by sets of nodes)
• we perform a convexity check at construction time, but in this case we still need the above specification. At that point I don't see the advantage of forbidding non-convex subgraph definitions.

[lmondada]

NB this definition also allows for slightly mind-bending stuff such as

graph TD
0 --> 1
1 -.->|incoming/outgoing| 0

Loading

where nodes 0, 1 would be in the subgraph but the dotted edge would not be. This is meant to be a feature not a bug, but feel free to disagree.

[acl-cqc]

So are we concerned with general graphs here or can we restrict to "let G=(V,E) be a directed acyclic graph"....? I think we have a DAG, so this particular nasty case doesn't happen; not sure if there are any others equally "weird".

In general I feel there's a requirement that an incoming edge has source NOT IN the subgraph and target IN the subgraph, and an outgoing edge has source IN the subgraph and target NOT IN, but I'm not sure how/where that goes.

[lmondada]

Yes what you are saying is correct. I have gone with only allowing induced subgraphs, which can be defined by a set of nodes. Implicitly any edge between such nodes will be part of the subgraph and boundary edges will always have one of their ports out of the subgraph.

[cqc-alec]

Sorry, I got confused at the first sentence of the definition; I think it needs to be clarified.

$G = (V, E)$

looks like the traditional mathematical definition of a graph as a set of vertices and a set of (ordered) pairs of vertices. But this has no notion of "boundary edges". I guess that by

Let $G = (V, E)$ be a graph and $B$ the set of boundary edges

you mean something like

Let $G = (V, E)$ be a graph and $B$ be a subset of $E$

But then which are "incoming" and which are "outgoing"?

Not meaning to be pedantic, just trying to understand the definition.

[lmondada]

Yes, you are right we can do better.

How about:

Given a HUGR and a node of the HUGR, let E be the set of edges of its sibling graph. A sibling subgraph is described by a set of boundary edges B ⊂ E that can be marked as incoming boundary edge, outgoing boundary edge or both.

[cqc-alec]

OK, thanks. Would this work?

Let $G = (V, E)$ be a directed graph and $B_\mathrm{I}, B_\mathrm{O} \subseteq E$. The subgraph of $G$ defined by $(B_\mathrm{I}, B_\mathrm{O})$ is the graph $(V^{'}, E^{'})$ where $V^{'}$ is the set of nodes in $V$ that either in the "future" (w.r.t. $G$) of targets of edges in $B_\mathrm{I}$ or in the "past" (w.r.t. $G$) of sources of edges in $B_\mathrm{O}$, and $E^{'}$ is the set of edges in $E$ whose source and target is in $V^{'}$ and which are not in $B_\mathrm{I}$ or $B_\mathrm{O}$.

(Here "future" means reachable by following edges, and "past" means reachable by following reverse edges.)

(Note I haven't said "HUGR" because I'm not sure the definition needs any more structure than "graph", does it?)

And "well-formedness" would be something like: for every edge $e \in B_\mathrm{O}$, the target of $e$ is not in $V^{'}$, and for every edge $e \in B_\mathrm{I}$, the source of $e$ is not in $V^{'}$?

[lmondada]

It is correct that

• we do not need more structure than "graph",
• we can split $B$ into $B_I, B_O \subseteq E$ as you have done it,
• the set $V'$ might be a strict subset of $V$, unlike my proposed definition.

However, using "future" and "past" would miss some edge cases. In the following example, "4" is neither in the past of $B_O$ nor in the future of $B_I$.

graph TD
  0-->|incoming|1
  subgraph "subgraph"
  2-->1
  2-->4
  end
  1-->|outgoing|3

Loading

That being said, your proposal works if we replace "past" and "future" with "there is a path in the underlying undirected graph obtained from $E \setminus (B_O \cup B_I)$".

Finally, using nodes instead of edges for the definition as you have done means that we lose the ability to define non-induced graphs such as the example above. For induced graphs, your well-formedness condition is correct, but it is more restrictive than my proposal.

In view of these things, which formulation do you prefer? For me both are perfectly workable, and I'm keen to hear which one you find more understandable.

[cqc-alec]

I see. So, we are concerned with DAGs here right, rather than general directed graphs?

I suspect that this would be an easier concept to nail down -- and we would even get convexity for free -- if our graph were a bounded DAG, that is, a DAG with an initial node 0 a terminal node 1 such that every node is in the future of 0 and in the past of 1.

We can convert any DAG to a bounded DAG by adding initial and terminal nodes 0 and 1, with edges from 0 to all nodes having no inputs and edges from all nodes having no outputs to 1.

If we have a bounded DAG, then given sets of nodes $A$ and $B$ we can simply define our subgraph as the set of nodes in the future of $A$ and the past of $B$.

Conversely, given any convex subset $S$ of nodes in a bounded DAG, we can take $A$ to be the set of nodes in $S$ having no incoming edges from nodes in $S$, and similarly for $B$; and then $A$ and $B$ will induce the set $S$ by the above definition.

So, for your example above, there would be edges from 0 to (2) and from (4) to 1, and we would just take $A = \{1,2\}$ and $B = \{4\}$.

Would this be general enough for your purposes?

[lmondada]

I need this datastructure for convexity checking, i.e. given a matching subgraph, check whether it's convex.

If we bake in convexity in the representation, aren't we pushing the convexity check to the client? I suppose we can perform a convexity check at construction time, but in this case we still need a way to specify non-convex subgraphs to be passed as arguments to the constructor.

At that point I don't see the advantage of forbidding non-convex subgraph definitions.

Am I missing your point?

[cqc-alec]

I thought we were looking for a way to specify convex subgraphs, and if the specification guarantees convexity then all the better. But I must have misunderstood the application.

given a matching subgraph, check whether it's convex.

What exactly is the thing you are given? Just a set of nodes?

[lmondada]

graph G
in -> G -> CPY -> out0
CPY -> G' -> out1
end

Loading

[lmondada]

After our discussion yesterday, I have gone with the simplest solution of all: we can only represent convex subgraphs (convexity is checked at construction time). Subgraphs will simply be defined by the set of nodes inducing the subgraph.

Convex graphs are always induced subgraphs, so they can be defined by a set of nodes. Furthermore, given that the entire subgraph must be traversed to check for convexity and find minimal and maximal node sets, we might as well store all the nodes that we traverse. Runtime overhead will be tiny, and space overhead should not be an issue for our purposes, as we are mostly interested in rewriting small regions.