vf2 1.0.1

VF2 subgraph isomorphism algorithm in Rust.
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
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

use crate::state::State;
use crate::{Graph, Isomorphism};
use std::fmt::Debug;

/// An isomorphism iterator.
///
/// This traverses the state space representation and yields
/// isomorphisms as they are found.
#[derive(Clone, Debug)]
pub struct IsomorphismIter<'a, Query, Data, NodeEq, EdgeEq> {
    state: State<'a, Query, Data, NodeEq, EdgeEq>,
}

impl<'a, Query, Data, NodeEq, EdgeEq> IsomorphismIter<'a, Query, Data, NodeEq, EdgeEq>
where
    Query: Graph,
    Data: Graph,
    NodeEq: Fn(&Query::NodeLabel, &Data::NodeLabel) -> bool,
    EdgeEq: Fn(&Query::EdgeLabel, &Data::EdgeLabel) -> bool,
{
    pub(crate) fn new(
        query: &'a Query,
        data: &'a Data,
        node_eq: Option<NodeEq>,
        edge_eq: Option<EdgeEq>,
        induced: bool,
    ) -> Self {
        Self {
            state: State::new(query, data, node_eq, edge_eq, induced),
        }
    }

    /// Advances the search and returns the next isomorphism.
    ///
    /// Unlike [`next`], this does not allocate.
    /// Returns [`None`] if the search is complete.
    ///
    /// [`next`]: Self::next
    pub fn into_next(mut self) -> Option<Isomorphism> {
        match self.next_ref() {
            None => None,
            Some(_) => Some(self.state.into_query_map()),
        }
    }

    /// Advances the search and returns a reference
    /// to the next isomorphism.
    ///
    /// Unlike [`next`], this returns a reference so as not to allocate.
    /// Returns [`None`] when the search is complete.
    ///
    /// [`next`]: Self::next
    pub fn next_ref(&mut self) -> Option<&Isomorphism> {
        while !self.state.step() {}
        self.state.all_covered().then_some(self.state.query_map())
    }
}

impl<'a, Query, Data, NodeEq, EdgeEq> Iterator for IsomorphismIter<'a, Query, Data, NodeEq, EdgeEq>
where
    Query: Graph,
    Data: Graph,
    NodeEq: Fn(&Query::NodeLabel, &Data::NodeLabel) -> bool,
    EdgeEq: Fn(&Query::EdgeLabel, &Data::EdgeLabel) -> bool,
{
    type Item = Isomorphism;

    fn next(&mut self) -> Option<Self::Item> {
        self.next_ref().cloned()
    }
}