pushout 0.1.1

A graph rewriting library built on petgraph.
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
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

use petgraph::graph::{Graph, NodeIndex};
use petgraph::Direction;
use std::collections::HashMap;

/// Checks if mapping a pattern node `p` to a graph node `g` is feasible given the current mapping.
/// If `check_edge_labels` is true, then it also checks that the edge weights (or labels) match.
fn is_feasible<N, E>(
    mapping: &HashMap<NodeIndex, NodeIndex>,
    pattern: &Graph<N, E>,
    graph: &Graph<N, E>,
    p: NodeIndex,
    g: NodeIndex,
    check_edge_labels: bool,
) -> bool
where
    N: Eq,
    E: Eq,
{
    // Check node label equality
    if pattern[p] != graph[g] {
        return false;
    }

    // Outgoing edges
    for p_neighbor in pattern.neighbors_directed(p, Direction::Outgoing) {
        if let Some(&g_neighbor) = mapping.get(&p_neighbor) {
            if check_edge_labels {
                let pat_edge_idx = pattern.find_edge(p, p_neighbor).unwrap();
                let pat_weight = pattern.edge_weight(pat_edge_idx).expect("Missing pattern edge weight");
                if let Some(graph_edge_idx) = graph.find_edge(g, g_neighbor) {
                    let graph_weight = graph.edge_weight(graph_edge_idx).expect("Missing graph edge weight");
                    if pat_weight != graph_weight {
                        return false;
                    }
                } else {
                    return false;
                }
            } else if graph.find_edge(g, g_neighbor).is_none() {
                return false;
            }
        }
    }

    // Incoming edges
    for p_neighbor in pattern.neighbors_directed(p, Direction::Incoming) {
        if let Some(&g_neighbor) = mapping.get(&p_neighbor) {
            if check_edge_labels {
                let pat_edge_idx = pattern.find_edge(p_neighbor, p).unwrap();
                let pat_weight = pattern.edge_weight(pat_edge_idx).expect("Missing pattern edge weight");
                if let Some(graph_edge_idx) = graph.find_edge(g_neighbor, g) {
                    let graph_weight = graph.edge_weight(graph_edge_idx).expect("Missing graph edge weight");
                    if pat_weight != graph_weight {
                        return false;
                    }
                } else {
                    return false;
                }
            } else if graph.find_edge(g_neighbor, g).is_none() {
                return false;
            }
        }
    }

    true
}

/// Generates candidate pairs (pattern node, graph node) for mapping.
fn candidate_pairs<N, E>(
    pattern: &Graph<N, E>,
    graph: &Graph<N, E>,
    mapping: &HashMap<NodeIndex, NodeIndex>,
) -> Vec<(NodeIndex, NodeIndex)> {
    let unmapped_p: Vec<_> = pattern
        .node_indices()
        .filter(|p| !mapping.contains_key(p))
        .collect();
    let unmapped_g: Vec<_> = graph
        .node_indices()
        .filter(|g| !mapping.values().any(|&v| v == *g))
        .collect();

    if let Some(&p) = unmapped_p.first() {
        unmapped_g.into_iter().map(|g| (p, g)).collect()
    } else {
        Vec::new()
    }
}

/// Recursively collects all complete mappings (node index maps) from pattern to graph.
fn search_collect<N, E>(
    pattern: &Graph<N, E>,
    graph: &Graph<N, E>,
    mapping: &mut HashMap<NodeIndex, NodeIndex>,
    check_edge_labels: bool,
    results: &mut Vec<HashMap<NodeIndex, NodeIndex>>,
) where
    N: Eq,
    E: Eq + Clone,
{
    if mapping.len() == pattern.node_count() {
        results.push(mapping.clone());
        return;
    }
    for (p, g) in candidate_pairs(pattern, graph, mapping) {
        if is_feasible(mapping, pattern, graph, p, g, check_edge_labels) {
            mapping.insert(p, g);
            search_collect(pattern, graph, mapping, check_edge_labels, results);
            mapping.remove(&p);
        }
    }
}

/// Returns all node mapping solutions of subgraph isomorphisms from `pattern` to `graph`.
pub fn find_mappings<N, E>(
    pattern: &Graph<N, E>,
    graph: &Graph<N, E>,
    check_edge_labels: bool,
) -> Vec<HashMap<NodeIndex, NodeIndex>>
where
    N: Eq,
    E: Eq + Clone,
{
    let mut results = Vec::new();
    let mut mapping = HashMap::new();
    search_collect(pattern, graph, &mut mapping, check_edge_labels, &mut results);
    results
}

/// Returns true if at least one subgraph isomorphism exists.
pub fn vf2_subgraph_isomorphism<N, E>(
    pattern: &Graph<N, E>,
    graph: &Graph<N, E>,
    check_edge_labels: bool,
) -> bool
where
    N: Eq,
    E: Eq + Clone,
{
    !find_mappings(pattern, graph, check_edge_labels).is_empty()
}