cpd 0.3.2

Collaboration Pattern Detection: A tool to search for context-aware and relaxed frequent subgraphs (patterns) in a graph database
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

use std::collections::{HashMap, HashSet};

use crate::data::edge::Edge;

use super::{graph::EdgeVectorKey, graph::Graph, graph::VertexVectorKey, vertex::Vertex};

/// Check if the vertices of a graph are connected through edges
pub fn vertices_are_connected(vertices: &Vec<&Vertex>) -> bool {
    let v_ids: HashSet<usize> = vertices.iter().map(|v| v.id).collect();
    let mut edges: Vec<&Edge> = vertices
        .iter()
        .flat_map(|v| &v.edges)
        .filter(|e| v_ids.contains(&e.from) && v_ids.contains(&e.to))
        .collect();
    let mut visited_v = HashSet::with_capacity(v_ids.len());
    visited_v.insert(vertices.first().unwrap().id);
    let mut to_remove = HashSet::new();
    while v_ids.len() != visited_v.len() {
        for edge in edges.iter() {
            if visited_v.contains(&edge.from) || visited_v.contains(&edge.to) {
                visited_v.insert(edge.from);
                visited_v.insert(edge.to);
                to_remove.insert(edge.id);
            }
        }
        if to_remove.is_empty() {
            break;
        } else {
            edges.retain(|e| !to_remove.contains(&e.id));
            to_remove.clear();
        }
    }
    v_ids.len() == visited_v.len()
}

/// Build the vertex vector of a graph -> Number of unique (label, vertex_type) tuples
pub fn build_vertex_vector(graph: &Graph) -> HashMap<VertexVectorKey, usize> {
    let mut result = HashMap::new();
    graph.vertices.iter().for_each(|v| {
        *result.entry((v.label, v.vertex_type)).or_insert(0) += 1;
    });
    result
}

/// Build the edge vector of a graph -> Number of unique (From vetrex label, from vertex type, edge
/// label, to vertex label, to vertex types) tuples
pub fn build_edge_vector(graph: &Graph) -> HashMap<EdgeVectorKey, usize> {
    let mut result = HashMap::new();
    graph.vertices.iter().for_each(|v| {
        v.edges.iter().for_each(|e| {
            let to = graph.vertices.get(e.to).unwrap();
            let to_label = to.label;
            let to_type = to.vertex_type;
            *result
                .entry((v.label, v.vertex_type, e.e_label, to_label, to_type))
                .or_insert(0) += 1;
        });
    });
    result
}

#[cfg(test)]
mod tests {
    use crate::data::graph::Graph;

    use super::*;

    #[test]
    fn test_vertices_are_connected() {
        let mut graph = Graph::new(1);
        graph.create_vertex_with_data(1, 2);
        graph.create_vertex_with_data(2, 2);
        graph.create_vertex_with_data(3, 4);
        graph.create_vertex_with_data(4, 2);
        graph.vertices.get_mut(0).unwrap().push(1, 0);
        graph.vertices.get_mut(0).unwrap().push(2, 0);
        graph.vertices.get_mut(1).unwrap().push(2, 0);
        graph.vertices.get_mut(1).unwrap().push(3, 0);
        graph.vertices.get_mut(3).unwrap().push(2, 0);
        let result = vertices_are_connected(&graph.vertices.iter().collect());
        assert!(result);
        let result = vertices_are_connected(&vec![
            graph.vertices.first().unwrap(),
            graph.vertices.get(1).unwrap(),
            graph.vertices.get(3).unwrap(),
        ]);
        assert!(result);
        let result = vertices_are_connected(&vec![
            graph.vertices.first().unwrap(),
            graph.vertices.get(3).unwrap(),
        ]);
        assert!(!result);
    }

    #[test]
    fn test_vertex_vector() {
        let mut graph = Graph::new(1);
        graph.create_vertex_with_data(1, 2);
        graph.create_vertex_with_data(2, 2);
        graph.create_vertex_with_data(3, 4);
        graph.create_vertex_with_data(2, 2);
        graph.vertices.get_mut(0).unwrap().push(1, 0);
        graph.vertices.get_mut(0).unwrap().push(2, 0);
        graph.vertices.get_mut(1).unwrap().push(2, 0);
        graph.vertices.get_mut(1).unwrap().push(3, 0);
        graph.vertices.get_mut(3).unwrap().push(2, 0);
        let vertex_vector = build_vertex_vector(&graph);
        assert_eq!(vertex_vector.len(), 3);
        assert_eq!(vertex_vector[&(1, 2)], 1);
        assert_eq!(vertex_vector[&(2, 2)], 2);
        assert_eq!(vertex_vector[&(3, 4)], 1);
    }

    #[test]
    fn test_edge_vector() {
        let mut graph = Graph::new(1);
        graph.create_vertex_with_data(1, 2); // 0
        graph.create_vertex_with_data(2, 2); // 1
        graph.create_vertex_with_data(3, 4); // 2
        graph.create_vertex_with_data(2, 2); // 3
        graph.vertices.get_mut(0).unwrap().push(1, 1);
        graph.vertices.get_mut(0).unwrap().push(2, 2);
        graph.vertices.get_mut(1).unwrap().push(2, 3);
        graph.vertices.get_mut(1).unwrap().push(3, 4);
        graph.vertices.get_mut(3).unwrap().push(3, 4);
        let edge_vector = build_edge_vector(&graph);
        assert_eq!(edge_vector.len(), 4);
        assert_eq!(edge_vector[&(1, 2, 1, 2, 2)], 1);
        assert_eq!(edge_vector[&(1, 2, 2, 3, 4)], 1);
        assert_eq!(edge_vector[&(2, 2, 3, 3, 4)], 1);
        assert_eq!(edge_vector[&(2, 2, 4, 2, 2)], 2);
    }
}