hypergraph/core/hyperedges/
contract_hyperedge_vertices.rs

1use itertools::Itertools;
2use rayon::prelude::*;
3
4use crate::{
5    HyperedgeIndex,
6    HyperedgeTrait,
7    Hypergraph,
8    VertexIndex,
9    VertexTrait,
10    core::utils::are_slices_equal,
11    errors::HypergraphError,
12};
13
14impl<V, HE> Hypergraph<V, HE>
15where
16    V: VertexTrait,
17    HE: HyperedgeTrait,
18{
19    /// Contracts a set of the vertices of a hyperedge into one single vertex.
20    /// Returns the updated vertices.
21    /// Based on <https://en.wikipedia.org/wiki/Edge_contraction>
22    pub fn contract_hyperedge_vertices(
23        &mut self,
24        hyperedge_index: HyperedgeIndex,
25        vertices: Vec<VertexIndex>,
26        target: VertexIndex,
27    ) -> Result<Vec<VertexIndex>, HypergraphError<V, HE>> {
28        // Get all the vertices of the hyperedge.
29        let hyperedge_vertices = self.get_hyperedge_vertices(hyperedge_index)?;
30
31        // Get the deduped vertices.
32        // We use `par_sort_unstable` here which means that the order of equal
33        // elements is not preserved but this is fine since we dedupe them
34        // afterwards.
35        let mut deduped_vertices = vertices;
36
37        deduped_vertices.par_sort_unstable();
38        deduped_vertices.dedup();
39
40        // Check that the target is included in the deduped vertices.
41        if !deduped_vertices
42            .par_iter()
43            .any(|&current_index| current_index == target)
44        {
45            return Err(HypergraphError::HyperedgeInvalidContraction {
46                index: hyperedge_index,
47                target,
48                vertices: deduped_vertices,
49            });
50        }
51
52        // Get the vertices not found in the hyperedge.
53        let vertices_not_found = deduped_vertices
54            .par_iter()
55            .fold_with(vec![], |mut acc: Vec<VertexIndex>, &index| {
56                if !hyperedge_vertices
57                    .par_iter()
58                    .any(|&current_index| current_index == index)
59                {
60                    acc.push(index);
61                }
62
63                acc
64            })
65            .flatten()
66            .collect::<Vec<VertexIndex>>();
67
68        // Check that all the vertices - target included - are a subset of
69        // the current hyperedge's vertices.
70        if !vertices_not_found.is_empty() {
71            return Err(HypergraphError::HyperedgeVerticesIndexesNotFound {
72                index: hyperedge_index,
73                vertices: vertices_not_found,
74            });
75        }
76
77        // Store all the hyperedges which are going to change.
78        let mut all_hyperedges: Vec<HyperedgeIndex> = vec![];
79
80        // Iterate over all the deduped vertices.
81        for &vertex in &deduped_vertices {
82            // Safely get the hyperedges of the current vertex.
83            let mut vertex_hyperedges = self.get_vertex_hyperedges(vertex)?;
84
85            // Concatenate them to the global ones.
86            all_hyperedges.append(&mut vertex_hyperedges);
87        }
88
89        // Iterate over all the deduped hyperedges.
90        for &hyperedge in all_hyperedges.iter().sorted().dedup() {
91            let hyperedge_vertices = self.get_hyperedge_vertices(hyperedge)?;
92
93            // Contract the vertices of the hyperedge.
94            let contraction = hyperedge_vertices
95                .iter()
96                // First remap each vertex to itself or to the target.
97                .map(|vertex| {
98                    if deduped_vertices
99                        .par_iter()
100                        .any(|&current_index| current_index == *vertex)
101                    {
102                        target
103                    } else {
104                        *vertex
105                    }
106                })
107                // Then dedupe the resulting vector.
108                .dedup()
109                .collect_vec();
110
111            // Only update the hyperedge if necessary.
112            if !are_slices_equal(
113                &self.get_internal_vertices(&contraction)?,
114                &self.get_internal_vertices(hyperedge_vertices)?,
115            ) {
116                // Safely update the current hyperedge with the contraction.
117                self.update_hyperedge_vertices(hyperedge, contraction)?;
118            }
119        }
120
121        // Return the contraction.
122        self.get_hyperedge_vertices(hyperedge_index)
123    }
124}
hypergraph/core/hyperedges/contract_hyperedge_vertices.rs

hypergraph/core/hyperedges/
contract_hyperedge_vertices.rs
