Finding all connected elements between 2 elements

[alexandernst]

I have some elements distributed across a paper. Some of them aren't embedded, some of them are. Some of the elements might be even deep-embedded (embedded inside elements that are embedded inside other elements).

Is there a way I can find all the elements that are connected between 2 elements? (both including and excluding nested embedded elements)

I made a small demo in order to make it easier to understand: https://codesandbox.io/s/jointjs-subgraph-u03xm8

Let's say that I want to get all elements between the 2 violet elements.

Option A (all elements, searching deeply embedded elements) would return the cyan, the blue, and the white elements.
Option B (all elements, excluding deeply embedded elements) would return the cyan and the blue elements, but not the white element.

Note that both options will exclude the red element, because it's not connected (either directly or indirectly) to the second violet element.

If the operation was repeated for the 2 green elements:

Option A (all elements, including deeply embedded elements) would return all elements, except the red one.
Option B (all elements, excluding deeply embedded elements) would return only the orange element.

I thought that maybe getSubgraph would be useful here, but it won't visit any elements that are not directly connected to the elements passed in the array. Then I thought that I might use getNeighbors in a loop with a "visited queue", but I'm not sure if that the most efficient way of doing it.

[kumilingus]

Hi, I would use Dijkstra's shortest path algorithm to receive the Option A (docs, demo). And Option B could be derived from A as discussed here (the descendants of the local hierarchical roots could be filtered out).

const optionBResult = optionAResult.filter((e1, _, elements) => {
    const isEmbeddedInElements = [el, ...elements].find(e2 => e1 !== e2 && e1.isEmbeddedIn(e2));
    return !isEmbeddedInElements;
});

[alexandernst]

I think Dijkstra's shortest path won't work here. The demo I created contains only "1 path", but a real-world-scenario could contain N "different paths" (and I'd need to get them all).

[kumilingus]

Then you might implement the solution suggested at StackOverflow to get Option A. The Option B approach remains.

You're looking for the set of nodes where the start node s can reach the node and that node can reach the destination node t. One way to do this is to do a DFS from s to find all nodes reachable from s and a reverse DFS from t to find all nodes that can reach t, then to take the intersection of those two sets. If you maintain the sets by storing mark bits in the nodes themselves, this runs in linear time.

[alexandernst]

Your suggestion worked like a charm! I want to contribute back to the community, so here goes what I achieved:

  // This works like getNeighbors, except that it doesn't return the "Start" and
  // the "End" elements that are embedded inside this (the group).
  getNeighbors(opt) {
    const ids = [this.getStart().id, this.getEnd().id];
    return this.graph.getNeighbors(this, opt).filter(model => !ids.includes(model.id));
  },

  // Get all the elements in this group, including nested elements, that are
  // connected to the "startingPoint" element.
  // Depending on the "direction" argument, the startingPoit will be the "Start"
  // element (if "direction" = "children") or the "End" element (if "direction"
  // = "parents").
  // If "direction" = "children", the natural direction of the links will be
  // followed. If "direction" = "parents", links will be followed in their
  // inverse direction.
  getConnectedElements(direction = "children") {
    const startingPoint = direction == "children" ? this.getStart() : this.getEnd();
    const opt = direction == "children" ? { outbound: true } : { inbound: true };

    const visited = new Set([startingPoint]);
    const queue = this.graph.getNeighbors(startingPoint, opt);

    while(queue.length > 0) {
      const element = queue.shift();

      if(!element.isEmbeddedIn(this, { deep: false })) continue;
      if(visited.has(element)) continue;

      if(element.isGroup()) {
        element.getConnectedElements(direction).forEach(element => visited.add(element));
        queue.push(...element.getNeighbors(opt));
      } else {
        queue.push(...this.graph.getNeighbors(element, opt));
      }

      visited.add(element);
    }

    return visited;
  },

  // This method will return all the elements that can be found in whatever
  // possible permutation of connections between the Start and the End element.
  getElementsBetweenSE() {
    const top2bottom = this.getConnectedElements("children");
    const bottom2top = this.getConnectedElements("parents");

    const intersection = new Set();
    top2bottom.forEach(element => bottom2top.has(element) && intersection.add(element));

    return intersection;
  }

[kumilingus]

The suggestion was made by someone on StackOverflow 😄 But I am glad you resolved it. With your permission, I would like to use your code for one of Wednesday's demos. Thanks!

[alexandernst]

Sure, absolutely!! You have my permission 😁