remove recursive try_match impl
diff --git a/src/isomorphism.rs b/src/isomorphism.rs
index 0d307b9..ba8e3f7 100644
--- a/src/isomorphism.rs
+++ b/src/isomorphism.rs
@@ -17,7 +17,7 @@
struct Vf2State<Ty, Ix> {
/// The current mapping M(s) of nodes from G0 → G1 and G1 → G0,
/// NodeIndex::end() for no mapping.
- pub mapping: Vec<NodeIndex<Ix>>,
+ mapping: Vec<NodeIndex<Ix>>,
/// out[i] is non-zero if i is in either M_0(s) or Tout_0(s)
/// These are all the next vertices that are not mapped yet, but
/// have an outgoing edge from the mapping.
@@ -173,12 +173,7 @@
}
let mut st = [Vf2State::new(g0), Vf2State::new(g1)];
- //let y = try_match(&mut st, g0, g1, &mut NoSemanticMatch, &mut NoSemanticMatch).unwrap_or(false);
- //st = [Vf2State::new(g0), Vf2State::new(g1)];
- let x = try_match_iter(&mut st, g0, g1, &mut NoSemanticMatch, &mut NoSemanticMatch).unwrap_or(false);
- //println!("{:?}", (&x, &y));
- //debug_assert!(x == y);
- return x;
+ return try_match(&mut st, g0, g1, &mut NoSemanticMatch, &mut NoSemanticMatch).unwrap_or(false);
}
/// [Graph] Return `true` if the graphs `g0` and `g1` are isomorphic.
@@ -226,7 +221,7 @@
}
/// Return Some(bool) if isomorphism is decided, else None.
-fn try_match_iter<N, E, Ty, Ix, F, G>(mut st: &mut [Vf2State<Ty, Ix>; 2],
+fn try_match<N, E, Ty, Ix, F, G>(mut st: &mut [Vf2State<Ty, Ix>; 2],
g0: &Graph<N, E, Ty, Ix>,
g1: &Graph<N, E, Ty, Ix>,
node_match: &mut F,
@@ -444,10 +439,8 @@
true
};
let mut stack = vec![Frame::Outer];
- println!("readysetgo! {:?}", &stack);
while let Some(frame) = stack.pop() {
- println!("\t{:?}", &frame);
match frame {
Frame::Unwind{nodes, open_list: ol} => {
pop_state(&mut st, nodes);
@@ -497,242 +490,3 @@
}
None
}
-
-/// Return Some(bool) if isomorphism is decided, else None.
-fn try_match<N, E, Ty, Ix, F, G>(st: &mut [Vf2State<Ty, Ix>; 2],
- g0: &Graph<N, E, Ty, Ix>,
- g1: &Graph<N, E, Ty, Ix>,
- node_match: &mut F,
- edge_match: &mut G)
- -> Option<bool>
- where Ty: EdgeType,
- Ix: IndexType,
- F: SemanticMatcher<N>,
- G: SemanticMatcher<E>,
-{
- let g = [g0, g1];
- let graph_indices = 0..2;
- let end = NodeIndex::end();
-
- // if all are mapped -- we are done and have an iso
- if st[0].is_complete() {
- return Some(true)
- }
-
- // A "depth first" search of a valid mapping from graph 1 to graph 2
-
- // F(s, n, m) -- evaluate state s and add mapping n <-> m
-
- // Find least T1out node (in st.out[1] but not in M[1])
- #[derive(Copy, Clone, PartialEq, Debug)]
- enum OpenList {
- Out,
- In,
- Other,
- }
- let mut open_list = OpenList::Out;
-
- let mut to_index;
- let mut from_index = None;
- // Try the out list
- to_index = st[1].next_out_index(0);
-
- if to_index.is_some() {
- from_index = st[0].next_out_index(0);
- open_list = OpenList::Out;
- }
-
- // Try the in list
- if to_index.is_none() || from_index.is_none() {
- to_index = st[1].next_in_index(0);
-
- if to_index.is_some() {
- from_index = st[0].next_in_index(0);
- open_list = OpenList::In;
- }
- }
-
- // Try the other list -- disconnected graph
- if to_index.is_none() || from_index.is_none() {
- to_index = st[1].next_rest_index(0);
- if to_index.is_some() {
- from_index = st[0].next_rest_index(0);
- open_list = OpenList::Other;
- }
- }
-
- let (cand0, cand1) = match (from_index, to_index) {
- (Some(n), Some(m)) => (n, m),
- // No more candidates
- _ => return None,
- };
-
- let mut nx = NodeIndex::new(cand0);
- let mx = NodeIndex::new(cand1);
- println!("{:?}\n{:?}\n{:?}\n", (cand0, cand1), &st[0].mapping, &st[1].mapping);
-
- let mut first = true;
-
- 'candidates: loop {
- if !first {
- // Find the next node index to try on the `from` side of the mapping
- let start = nx.index() + 1;
- let cand0 = match open_list {
- OpenList::Out => st[0].next_out_index(start),
- OpenList::In => st[0].next_in_index(start),
- OpenList::Other => st[0].next_rest_index(start),
- }.map(|c| c + start); // compensate for start offset.
- println!(" {:?}", (cand0, cand1));
- nx = match cand0 {
- None => break, // no more candidates
- Some(ix) => NodeIndex::new(ix),
- };
- debug_assert!(nx.index() >= start);
- }
- first = false;
-
- let nodes = [nx, mx];
-
- // Check syntactic feasibility of mapping by ensuring adjacencies
- // of nx map to adjacencies of mx.
- //
- // nx == map to => mx
- //
- // R_succ
- //
- // Check that every neighbor of nx is mapped to a neighbor of mx,
- // then check the reverse, from mx to nx. Check that they have the same
- // count of edges.
- //
- // Note: We want to check the lookahead measures here if we can,
- // R_out: Equal for G0, G1: Card(Succ(G, n) ^ Tout); for both Succ and Pred
- // R_in: Same with Tin
- // R_new: Equal for G0, G1: Ñ n Pred(G, n); both Succ and Pred,
- // Ñ is G0 - M - Tin - Tout
- // last attempt to add these did not speed up any of the testcases
- let mut succ_count = [0, 0];
- for j in graph_indices.clone() {
- for n_neigh in g[j].neighbors(nodes[j]) {
- succ_count[j] += 1;
- // handle the self loop case; it's not in the mapping (yet)
- let m_neigh = if nodes[j] != n_neigh {
- st[j].mapping[n_neigh.index()]
- } else {
- nodes[1 - j]
- };
- if m_neigh == end {
- continue;
- }
- let has_edge = g[1-j].is_adjacent(&st[1-j].adjacency_matrix, nodes[1-j], m_neigh);
- if !has_edge {
- continue 'candidates;
- }
- }
- }
- if succ_count[0] != succ_count[1] {
- continue 'candidates;
- }
-
- // R_pred
- if g[0].is_directed() {
- let mut pred_count = [0, 0];
- for j in graph_indices.clone() {
- for n_neigh in g[j].neighbors_directed(nodes[j], Incoming) {
- pred_count[j] += 1;
- // the self loop case is handled in outgoing
- let m_neigh = st[j].mapping[n_neigh.index()];
- if m_neigh == end {
- continue;
- }
- let has_edge = g[1-j].is_adjacent(&st[1-j].adjacency_matrix, m_neigh, nodes[1-j]);
- if !has_edge {
- continue 'candidates;
- }
- }
- }
- if pred_count[0] != pred_count[1] {
- continue 'candidates;
- }
- }
-
- // semantic feasibility: compare associated data for nodes
- if F::enabled() && !node_match.eq(&g[0][nodes[0]], &g[1][nodes[1]]) {
- continue 'candidates;
- }
-
- // semantic feasibility: compare associated data for edges
- if G::enabled() {
- // outgoing edges
- for j in graph_indices.clone() {
- let mut edges = g[j].neighbors(nodes[j]).detach();
- while let Some((n_edge, n_neigh)) = edges.next(g[j]) {
- // handle the self loop case; it's not in the mapping (yet)
- let m_neigh = if nodes[j] != n_neigh {
- st[j].mapping[n_neigh.index()]
- } else {
- nodes[1 - j]
- };
- if m_neigh == end {
- continue;
- }
- match g[1-j].find_edge(nodes[1 - j], m_neigh) {
- Some(m_edge) => {
- if !edge_match.eq(&g[j][n_edge], &g[1-j][m_edge]) {
- continue 'candidates;
- }
- }
- None => unreachable!() // covered by syntactic check
- }
- }
- }
-
- // incoming edges
- if g[0].is_directed() {
- for j in graph_indices.clone() {
- let mut edges = g[j].neighbors_directed(nodes[j], Incoming).detach();
- while let Some((n_edge, n_neigh)) = edges.next(g[j]) {
- // the self loop case is handled in outgoing
- let m_neigh = st[j].mapping[n_neigh.index()];
- if m_neigh == end {
- continue;
- }
- match g[1-j].find_edge(m_neigh, nodes[1-j]) {
- Some(m_edge) => {
- if !edge_match.eq(&g[j][n_edge], &g[1-j][m_edge]) {
- continue 'candidates;
- }
- }
- None => unreachable!() // covered by syntactic check
- }
- }
- }
- }
- }
- println!("\tfeasible");
-
- // Add mapping nx <-> mx to the state
- for j in graph_indices.clone() {
- st[j].push_mapping(nodes[j], nodes[1-j], g[j]);
- }
-
- // Check cardinalities of Tin, Tout sets
- if st[0].out_size == st[1].out_size &&
- st[0].ins_size == st[1].ins_size
- {
- println!("\trecurse");
- // Recurse
- match try_match(st, g0, g1, node_match, edge_match) {
- None => {}
- result => return result,
- }
- }
- println!("\tpop");
-
- // Restore state.
- for j in graph_indices.clone() {
- st[j].pop_mapping(nodes[j], g[j]);
- }
- }
- None
-}
-
