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

// Licensed under the Apache License, Version 2.0 (the "License"); you may
// not use this file except in compliance with the License. You may obtain
// a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations
// under the License.

//! This module defines graph traits for multi-graphs.

use hashbrown::HashSet;
use petgraph::visit::{EdgeCount, EdgeRef, GraphBase, GraphProp, IntoEdgeReferences, Visitable};
use petgraph::{Directed, Undirected};
use std::hash::Hash;

pub trait HasParallelEdgesUndirected: GraphBase {
    fn has_parallel_edges(&self) -> bool;
}

impl<G> HasParallelEdgesUndirected for G
where
    G: GraphProp<EdgeType = Undirected> + Visitable + EdgeCount,
    G::NodeId: Eq + Hash,
    for<'b> &'b G: GraphBase<NodeId = G::NodeId> + IntoEdgeReferences,
{
    fn has_parallel_edges(&self) -> bool {
        let mut edges: HashSet<[Self::NodeId; 2]> = HashSet::with_capacity(2 * self.edge_count());
        for edge in self.edge_references() {
            let endpoints = [edge.source(), edge.target()];
            let endpoints_rev = [edge.target(), edge.source()];
            if edges.contains(&endpoints) || edges.contains(&endpoints_rev) {
                return true;
            }
            edges.insert(endpoints);
            edges.insert(endpoints_rev);
        }
        false
    }
}

pub trait HasParallelEdgesDirected: GraphBase {
    fn has_parallel_edges(&self) -> bool;
}

impl<G> HasParallelEdgesDirected for G
where
    G: GraphProp<EdgeType = Directed> + Visitable + EdgeCount,
    G::NodeId: Eq + Hash,
    for<'b> &'b G: GraphBase<NodeId = G::NodeId> + IntoEdgeReferences,
{
    fn has_parallel_edges(&self) -> bool {
        let mut edges: HashSet<[Self::NodeId; 2]> = HashSet::with_capacity(self.edge_count());
        for edge in self.edge_references() {
            let endpoints = [edge.source(), edge.target()];
            if edges.contains(&endpoints) {
                return true;
            }
            edges.insert(endpoints);
        }
        false
    }
}