portdiff/
graph.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use crate::{port::BoundPort, Site};
4
5use super::port::EdgeEnd;
6
7/// A graph for port diffing.
8///
9/// It must be possible to iterate through all nodes and edges of the graph.
10/// Furthermore, each edge must distinguish a left end and a right end. This
11/// does not have to match the directedness of the edge, but it must be fixed.
12///
13/// Incident edges can furthermore be distinguished using a port label type,
14/// attached to the edge ends.
15pub trait Graph: Default + Clone {
16    type Node: Ord + Copy;
17    type Edge: Ord + Copy;
18    type PortLabel: Ord + Clone;
19
20    /// Iterate over all nodes in the graph.
21    fn nodes_iter(&self) -> impl Iterator<Item = Self::Node> + '_;
22
23    /// Iterate over all edges in the graph.
24    fn edges_iter(&self) -> impl Iterator<Item = Self::Edge> + '_;
25
26    /// Find the site of a bound port.
27    ///
28    /// There is a unique site for every bound port. The reverse is not
29    /// true: site may not have an incident edge, or may have multiple.
30    fn get_port_site(&self, bound_port: BoundPort<Self::Edge>)
31        -> Site<Self::Node, Self::PortLabel>;
32
33    fn get_bound_ports(
34        &self,
35        site: Site<Self::Node, Self::PortLabel>,
36    ) -> impl Iterator<Item = BoundPort<Self::Edge>> + '_;
37
38    fn get_sites(
39        &self,
40        node: Self::Node,
41    ) -> impl Iterator<Item = Site<Self::Node, Self::PortLabel>> + '_;
42
43    /// The node incident to a given edge and port side.
44    ///
45    /// This can be obtained from the bound -> unbound port map.
46    fn incident_node(&self, edge: Self::Edge, end: EdgeEnd) -> Self::Node {
47        let bound_port = BoundPort { edge, end };
48        self.get_port_site(bound_port).node
49    }
50
51    fn link_sites(
52        &mut self,
53        left: Site<Self::Node, Self::PortLabel>,
54        right: Site<Self::Node, Self::PortLabel>,
55    );
56
57    /// Add a subgraph of `graph` to `self`.
58    ///
59    /// Add the subgraph of `graph` that is induced by `nodes`.
60    ///
61    /// Return a map from `nodes` in `graph` to the new nodes in `self`.
62    fn add_subgraph(
63        &mut self,
64        graph: &Self,
65        nodes: &BTreeSet<Self::Node>,
66    ) -> BTreeMap<Self::Node, Self::Node>;
67}
portdiff/graph.rs

portdiff/
graph.rs
