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

use itertools::Itertools;
use rayon::prelude::*;

use crate::{
    core::utils::are_slices_equal, errors::HypergraphError, HyperedgeIndex, HyperedgeTrait,
    Hypergraph, VertexIndex, VertexTrait,
};

impl<V, HE> Hypergraph<V, HE>
where
    V: VertexTrait,
    HE: HyperedgeTrait,
{
    /// Contracts a set of the vertices of a hyperedge into one single vertex.
    /// Returns the updated vertices.
    /// Based on <https://en.wikipedia.org/wiki/Edge_contraction>
    pub fn contract_hyperedge_vertices(
        &mut self,
        hyperedge_index: HyperedgeIndex,
        vertices: Vec<VertexIndex>,
        target: VertexIndex,
    ) -> Result<Vec<VertexIndex>, HypergraphError<V, HE>> {
        // Get all the vertices of the hyperedge.
        let hyperedge_vertices = self.get_hyperedge_vertices(hyperedge_index)?;

        // Get the deduped vertices.
        // We use `par_sort_unstable` here which means that the order of equal
        // elements is not preserved but this is fine since we dedupe them
        // afterwards.
        let mut deduped_vertices = vertices;

        deduped_vertices.par_sort_unstable();
        deduped_vertices.dedup();

        // Check that the target is included in the deduped vertices.
        if !deduped_vertices
            .par_iter()
            .any(|&current_index| current_index == target)
        {
            return Err(HypergraphError::HyperedgeInvalidContraction {
                index: hyperedge_index,
                target,
                vertices: deduped_vertices,
            });
        }

        // Get the vertices not found in the hyperedge.
        let vertices_not_found = deduped_vertices
            .par_iter()
            .fold_with(vec![], |mut acc: Vec<VertexIndex>, &index| {
                if !hyperedge_vertices
                    .par_iter()
                    .any(|&current_index| current_index == index)
                {
                    acc.push(index.to_owned())
                }

                acc
            })
            .flatten()
            .collect::<Vec<VertexIndex>>();

        // Check that all the vertices - target included - are a subset of
        // the current hyperedge's vertices.
        if !vertices_not_found.is_empty() {
            return Err(HypergraphError::HyperedgeVerticesIndexesNotFound {
                index: hyperedge_index,
                vertices: vertices_not_found,
            });
        }

        // Store all the hyperedges which are going to change.
        let mut all_hyperedges: Vec<HyperedgeIndex> = vec![];

        // Iterate over all the deduped vertices.
        for &vertex in deduped_vertices.iter() {
            // Safely get the hyperedges of the current vertex.
            let mut vertex_hyperedges = self.get_vertex_hyperedges(vertex)?;

            // Concatenate them to the global ones.
            all_hyperedges.append(&mut vertex_hyperedges);
        }

        // Iterate over all the deduped hyperedges.
        for &hyperedge in all_hyperedges.iter().sorted().dedup() {
            let hyperedge_vertices = self.get_hyperedge_vertices(hyperedge)?;

            // Contract the vertices of the hyperedge.
            let contraction = hyperedge_vertices
                .iter()
                // First remap each vertex to itself or to the target.
                .map(|vertex| {
                    if deduped_vertices
                        .par_iter()
                        .any(|&current_index| current_index == *vertex)
                    {
                        target
                    } else {
                        *vertex
                    }
                })
                // Then dedupe the resulting vector.
                .dedup()
                .collect_vec();

            // Only update the hyperedge if necessary.
            if !are_slices_equal(
                &self.get_internal_vertices(&contraction)?,
                &self.get_internal_vertices(hyperedge_vertices)?,
            ) {
                // Safely update the current hyperedge with the contraction.
                self.update_hyperedge_vertices(hyperedge, contraction)?;
            }
        }

        // Return the contraction.
        self.get_hyperedge_vertices(hyperedge_index)
    }
}