rustworkx_core/graph_ext/
multigraph.rs

1// Licensed under the Apache License, Version 2.0 (the "License"); you may
2// not use this file except in compliance with the License. You may obtain
3// a copy of the License at
4//
5//     http://www.apache.org/licenses/LICENSE-2.0
6//
7// Unless required by applicable law or agreed to in writing, software
8// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10// License for the specific language governing permissions and limitations
11// under the License.
12
13//! This module defines graph traits for multi-graphs.
14
15use hashbrown::HashSet;
16use petgraph::visit::{EdgeCount, EdgeRef, GraphBase, GraphProp, IntoEdgeReferences, Visitable};
17use petgraph::{Directed, Undirected};
18use std::hash::Hash;
19
20pub trait HasParallelEdgesUndirected: GraphBase {
21    fn has_parallel_edges(&self) -> bool;
22}
23
24impl<G> HasParallelEdgesUndirected for G
25where
26    G: GraphProp<EdgeType = Undirected> + Visitable + EdgeCount,
27    G::NodeId: Eq + Hash,
28    for<'b> &'b G: GraphBase<NodeId = G::NodeId> + IntoEdgeReferences,
29{
30    fn has_parallel_edges(&self) -> bool {
31        let mut edges: HashSet<[Self::NodeId; 2]> = HashSet::with_capacity(2 * self.edge_count());
32        for edge in self.edge_references() {
33            let endpoints = [edge.source(), edge.target()];
34            let endpoints_rev = [edge.target(), edge.source()];
35            if edges.contains(&endpoints) || edges.contains(&endpoints_rev) {
36                return true;
37            }
38            edges.insert(endpoints);
39            edges.insert(endpoints_rev);
40        }
41        false
42    }
43}
44
45pub trait HasParallelEdgesDirected: GraphBase {
46    fn has_parallel_edges(&self) -> bool;
47}
48
49impl<G> HasParallelEdgesDirected for G
50where
51    G: GraphProp<EdgeType = Directed> + Visitable + EdgeCount,
52    G::NodeId: Eq + Hash,
53    for<'b> &'b G: GraphBase<NodeId = G::NodeId> + IntoEdgeReferences,
54{
55    fn has_parallel_edges(&self) -> bool {
56        let mut edges: HashSet<[Self::NodeId; 2]> = HashSet::with_capacity(self.edge_count());
57        for edge in self.edge_references() {
58            let endpoints = [edge.source(), edge.target()];
59            if edges.contains(&endpoints) {
60                return true;
61            }
62            edges.insert(endpoints);
63        }
64        false
65    }
66}
rustworkx_core/graph_ext/multigraph.rs

rustworkx_core/graph_ext/
multigraph.rs
