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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

use std::{fmt::Debug, vec};

use itertools::Itertools;
use petgraph::{
    graph::DiGraph,
    visit::{
        Data, EdgeFiltered, EdgeRef, GraphBase, IntoEdgeReferences, IntoEdges, IntoEdgesDirected,
        IntoNeighbors, IntoNeighborsDirected, IntoNodeIdentifiers, NodeCount, NodeFiltered,
        Visitable,
    },
    Direction,
};

pub type CFGraph = DiGraph<(), (), usize>;

#[derive(Debug, Clone)]
pub struct CFSubGraph<'a> {
    pub graph: &'a CFGraph,
    pub nodes: Vec<<CFGraph as GraphBase>::NodeId>,
    pub edges: Vec<<CFGraph as GraphBase>::EdgeId>,
}

impl<'a> CFSubGraph<'a> {
    pub fn new(
        graph: &'a CFGraph,
        nodes: impl IntoIterator<Item = <CFGraph as GraphBase>::NodeId>,
        edges: impl IntoIterator<Item = <CFGraph as GraphBase>::EdgeId>,
    ) -> Self {
        Self {
            graph,
            nodes: nodes.into_iter().collect(),
            edges: edges.into_iter().collect(),
        }
    }

    pub fn find_edge(
        &self,
        a: <CFGraph as GraphBase>::NodeId,
        b: <CFGraph as GraphBase>::NodeId,
    ) -> Option<<CFGraph as GraphBase>::EdgeId> {
        self.graph
            .find_edge(a, b)
            .filter(|it| self.edges.contains(it))
    }
}

impl<'a> GraphBase for CFSubGraph<'a> {
    type EdgeId = <CFGraph as GraphBase>::EdgeId;
    type NodeId = <CFGraph as GraphBase>::NodeId;
}

impl<'a> NodeCount for &'a CFSubGraph<'a> {
    fn node_count(&self) -> usize {
        self.nodes.len()
    }
}

impl<'a> IntoNeighbors for &'a CFSubGraph<'a> {
    type Neighbors = vec::IntoIter<Self::NodeId>;

    fn neighbors(self, a: Self::NodeId) -> Self::Neighbors {
        let filtered_nodes = NodeFiltered::from_fn(self.graph, |n| self.nodes.contains(&n));
        let filtered_edges =
            EdgeFiltered::from_fn(&filtered_nodes, |e| self.edges.contains(&e.id()));
        filtered_edges.neighbors(a).collect_vec().into_iter()
    }
}

impl<'a> IntoNeighborsDirected for &'a CFSubGraph<'a> {
    type NeighborsDirected = vec::IntoIter<Self::NodeId>;

    fn neighbors_directed(self, n: Self::NodeId, d: Direction) -> Self::NeighborsDirected {
        let filtered_nodes = NodeFiltered::from_fn(self.graph, |n| self.nodes.contains(&n));
        let filtered_edges =
            EdgeFiltered::from_fn(&filtered_nodes, |e| self.edges.contains(&e.id()));
        filtered_edges
            .neighbors_directed(n, d)
            .collect_vec()
            .into_iter()
    }
}

impl<'a> Data for &'a CFSubGraph<'a> {
    type NodeWeight = <&'a CFGraph as Data>::NodeWeight;
    type EdgeWeight = <&'a CFGraph as Data>::EdgeWeight;
}

impl<'a> IntoEdgeReferences for &'a CFSubGraph<'a> {
    type EdgeRef = <&'a CFGraph as IntoEdgeReferences>::EdgeRef;

    type EdgeReferences = vec::IntoIter<Self::EdgeRef>;

    fn edge_references(self) -> Self::EdgeReferences {
        let filtered_nodes = NodeFiltered::from_fn(self.graph, |n| self.nodes.contains(&n));
        let filtered_edges =
            EdgeFiltered::from_fn(&filtered_nodes, |e| self.edges.contains(&e.id()));
        filtered_edges.edge_references().collect_vec().into_iter()
    }
}

impl<'a> IntoNodeIdentifiers for &'a CFSubGraph<'a> {
    type NodeIdentifiers = vec::IntoIter<Self::NodeId>;

    fn node_identifiers(self) -> Self::NodeIdentifiers {
        let filtered_nodes = NodeFiltered::from_fn(self.graph, |n| self.nodes.contains(&n));
        filtered_nodes.node_identifiers().collect_vec().into_iter()
    }
}

impl<'a> IntoEdges for &'a CFSubGraph<'a> {
    type Edges = vec::IntoIter<Self::EdgeRef>;

    fn edges(self, a: Self::NodeId) -> Self::Edges {
        let filtered_nodes = NodeFiltered::from_fn(self.graph, |n| self.nodes.contains(&n));
        let filtered_edges =
            EdgeFiltered::from_fn(&filtered_nodes, |e| self.edges.contains(&e.id()));
        filtered_edges.edges(a).collect_vec().into_iter()
    }
}

impl<'a> IntoEdgesDirected for &'a CFSubGraph<'a> {
    type EdgesDirected = vec::IntoIter<Self::EdgeRef>;

    fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected {
        let filtered_nodes = NodeFiltered::from_fn(self.graph, |n| self.nodes.contains(&n));
        let filtered_edges =
            EdgeFiltered::from_fn(&filtered_nodes, |e| self.edges.contains(&e.id()));
        filtered_edges
            .edges_directed(a, dir)
            .collect_vec()
            .into_iter()
    }
}

impl<'a> Visitable for &'a CFSubGraph<'a> {
    type Map = <CFGraph as Visitable>::Map;

    fn visit_map(&self) -> Self::Map {
        let filtered_nodes = NodeFiltered::from_fn(self.graph, |n| self.nodes.contains(&n));
        let filtered_edges =
            EdgeFiltered::from_fn(&filtered_nodes, |e| self.edges.contains(&e.id()));
        filtered_edges.visit_map()
    }

    fn reset_map(&self, map: &mut Self::Map) {
        let filtered_nodes = NodeFiltered::from_fn(self.graph, |n| self.nodes.contains(&n));
        let filtered_edges =
            EdgeFiltered::from_fn(&filtered_nodes, |e| self.edges.contains(&e.id()));
        filtered_edges.reset_map(map)
    }
}