Subgraph::new_subgraph() doesn't always respect boundary

[cqc-alec]

For example, this test:

    #[test]
    fn test_boundary() {
        let mut graph = PortGraph::new();
        let n0 = graph.add_node(0, 2);
        let n1 = graph.add_node(2, 2);
        let n2 = graph.add_node(2, 2);
        let n3 = graph.add_node(2, 2);
        let n4 = graph.add_node(2, 2);
        let n5 = graph.add_node(2, 0);
        graph.link_nodes(n0, 0, n1, 0).unwrap();
        graph.link_nodes(n0, 1, n1, 1).unwrap();
        graph.link_nodes(n1, 0, n2, 0).unwrap();
        graph.link_nodes(n1, 1, n2, 1).unwrap();
        graph.link_nodes(n2, 0, n3, 0).unwrap();
        graph.link_nodes(n2, 1, n3, 1).unwrap();
        graph.link_nodes(n3, 0, n4, 0).unwrap();
        graph.link_nodes(n3, 1, n4, 1).unwrap();
        graph.link_nodes(n4, 0, n5, 0).unwrap();
        graph.link_nodes(n4, 1, n5, 1).unwrap();
        let boundary = [
            graph.input(n2, 0).unwrap(),
            graph.input(n2, 1).unwrap(),
            graph.output(n3, 1).unwrap(),
            graph.output(n3, 1).unwrap(),
        ];
        let subg = Subgraph::new_subgraph(&graph, boundary);
        assert_eq!(subg.nodes_iter().collect_vec(), [n2, n3]);
    }

should (I think) generate a subgraph consisting of n2 and n3; instead it generates a subgraph with nodes n2, n3, n4 and n5.

[lmondada]

Did you mean:

        let boundary = [
            graph.input(n2, 0).unwrap(),
            graph.input(n2, 1).unwrap(),
            graph.output(n3, 0).unwrap(),
            graph.output(n3, 1).unwrap(),
        ];

i.e. the third port in the boundary is graph.output(n3, 0)?

[cqc-alec]

Ah, my bad, yes, and the test passes then.

I was actually originally investigating the case where one of the exit ports was missing from the boundary. Is the result what you would expect in that case?

[lmondada]

Yes, I would expect that example to result in the nodes [n2, n3, n4, n5], but would obviously not be convex.

The idea behind this subgraph definition is that any path that starts within the subgraph and never passes through a input or output port is contained within the subgraph. Furthermore, for such a path it is also allowed to traverse edges in the reverse direction (from target to source).

I'm closing this, as the related issue CQCL/hugr#518 will be solved by CQCL/hugr#585.