portmatching 0.3.3

Fast Graph Matching for Port Graphs
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

use std::collections::BTreeSet;

use portgraph::{algorithms as pg, Direction, NodeIndex, PortGraph, UnmanagedDenseMap};

/// Topological sorting of the graph
///
/// Unlike `portgraph::algorithms::toposort`, this function traverses all
/// descendants of the root node.
pub(crate) fn toposort(g: &PortGraph, root: NodeIndex) -> impl Iterator<Item = NodeIndex> + '_ {
    let desc = pg::postorder(g, [root], Direction::Outgoing).collect::<BTreeSet<_>>();
    let port_filter = move |_, p| {
        if g.port_direction(p).expect("invalid port") == Direction::Outgoing {
            return true;
        }
        let Some(link) = g.port_link(p) else { return true };
        desc.contains(&g.port_node(link).expect("invalid port"))
    };
    pg::toposort_filtered::<UnmanagedDenseMap<_, _>>(
        g,
        [root],
        Direction::Outgoing,
        |_| true,
        port_filter,
    )
}