rustworkx_core/graph_ext/
mod.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 traits that extend PetGraph's graph
14//! data structures.
15//!
16//! The `-Directed` and `-Undirected` trait variants are implemented as
17//! applicable for directed and undirected graph types. For example, only
18//! directed graph types are concerned with cycle checking and corresponding
19//! error handling, so these traits provide applicable parameters and return
20//! types to account for this.
21//!
22//! ### Node Contraction
23//!
24//! There are four traits related to node contraction available for different
25//! graphs / configurations, including:
26//!
27//! - [`ContractNodesDirected`]
28//! - [`ContractNodesSimpleDirected`]
29//! - [`ContractNodesUndirected`]
30//! - [`ContractNodesSimpleUndirected`]
31//!
32//! Of these, the `ContractNodesSimple-` traits provide a
33//! `contract_nodes_simple` method for applicable graph types, which performs
34//! node contraction without introducing parallel edges between nodes (edges
35//! between any two given nodes are merged via the method's merge function).
36//! These traits can be used for node contraction within simple graphs to
37//! preserve this property, or on multi-graphs to ensure that the contraction
38//! does not introduce additional parallel edges.
39//!
40//! The other `ContractNodes-` traits provide a `contract_nodes` method, which
41//! happily introduces parallel edges when multiple nodes in the contraction
42//! have an incoming edge from the same source node or when multiple nodes in
43//! the contraction have an outgoing edge to the same target node.
44//!
45//! ### Multi-graph Extensions
46//!
47//! These traits provide additional helper methods for use with multi-graphs,
48//! e.g. [`HasParallelEdgesDirected`].
49//!
50//! ### Graph Extension Trait Implementations
51//!
52//! The following table lists the traits that are currently implemented for
53//! each graph type:
54//!
55//! |                               | Graph | StableGraph | GraphMap | MatrixGraph | Csr   | List  |
56//! | ----------------------------- | :---: | :---------: | :------: | :---------: | :---: | :---: |
57//! | ContractNodesDirected         |       |  x          |    x     |             |       |       |
58//! | ContractNodesSimpleDirected   |       |  x          |    x     |             |       |       |
59//! | ContractNodesUndirected       |       |  x          |    x     |             |       |       |
60//! | ContractNodesSimpleUndirected |       |  x          |    x     |             |       |       |
61//! | HasParallelEdgesDirected      | x     |  x          |    x     | x           | x     | x     |
62//! | HasParallelEdgesUndirected    | x     |  x          |    x     | x           | x     | x     |
63//! | NodeRemovable                 | x     |  x          |    x     | x           |       |       |
64//! | EdgeRemovable                 | x     |  x          |          |             |       |       |
65//! | EdgeFindable                  | x     |  x          |          |             |       |       |
66
67use petgraph::graph::IndexType;
68use petgraph::graphmap::{GraphMap, NodeTrait};
69use petgraph::matrix_graph::{MatrixGraph, Nullable};
70use petgraph::stable_graph::StableGraph;
71use petgraph::visit::{Data, IntoNodeIdentifiers};
72use petgraph::{EdgeType, Graph};
73
74pub mod contraction;
75pub mod multigraph;
76
77pub use contraction::{
78    ContractNodesDirected, ContractNodesSimpleDirected, ContractNodesSimpleUndirected,
79    ContractNodesUndirected,
80};
81pub use multigraph::{HasParallelEdgesDirected, HasParallelEdgesUndirected};
82
83/// A graph whose nodes may be removed.
84pub trait NodeRemovable: Data {
85    type Output;
86    fn remove_node(&mut self, node: Self::NodeId) -> Self::Output;
87}
88
89impl<N, E, Ty, Ix> NodeRemovable for StableGraph<N, E, Ty, Ix>
90where
91    Ty: EdgeType,
92    Ix: IndexType,
93{
94    type Output = Option<Self::NodeWeight>;
95    fn remove_node(&mut self, node: Self::NodeId) -> Option<Self::NodeWeight> {
96        self.remove_node(node)
97    }
98}
99
100impl<N, E, Ty, Ix> NodeRemovable for Graph<N, E, Ty, Ix>
101where
102    Ty: EdgeType,
103    Ix: IndexType,
104{
105    type Output = Option<Self::NodeWeight>;
106    fn remove_node(&mut self, node: Self::NodeId) -> Option<Self::NodeWeight> {
107        self.remove_node(node)
108    }
109}
110
111impl<N, E, Ty> NodeRemovable for GraphMap<N, E, Ty>
112where
113    N: NodeTrait,
114    Ty: EdgeType,
115{
116    type Output = bool;
117    fn remove_node(&mut self, node: Self::NodeId) -> Self::Output {
118        self.remove_node(node)
119    }
120}
121
122impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeRemovable
123    for MatrixGraph<N, E, Ty, Null, Ix>
124{
125    type Output = Option<Self::NodeWeight>;
126    fn remove_node(&mut self, node: Self::NodeId) -> Self::Output {
127        for n in self.node_identifiers() {
128            if node == n {
129                return Some(self.remove_node(node));
130            }
131        }
132        None
133    }
134}
135
136/// A graph whose edge may be removed by an edge id.
137pub trait EdgeRemovable: Data {
138    type Output;
139    fn remove_edge(&mut self, edge: Self::EdgeId) -> Self::Output;
140}
141
142impl<N, E, Ty, Ix> EdgeRemovable for StableGraph<N, E, Ty, Ix>
143where
144    Ty: EdgeType,
145    Ix: IndexType,
146{
147    type Output = Option<Self::EdgeWeight>;
148    fn remove_edge(&mut self, edge: Self::EdgeId) -> Option<Self::EdgeWeight> {
149        self.remove_edge(edge)
150    }
151}
152
153impl<N, E, Ty, Ix> EdgeRemovable for Graph<N, E, Ty, Ix>
154where
155    Ty: EdgeType,
156    Ix: IndexType,
157{
158    type Output = Option<Self::EdgeWeight>;
159    fn remove_edge(&mut self, edge: Self::EdgeId) -> Option<Self::EdgeWeight> {
160        self.remove_edge(edge)
161    }
162}
163
164/// A graph that can find edges by a pair of node ids.
165pub trait EdgeFindable: Data {
166    fn edge_find(&self, a: Self::NodeId, b: Self::NodeId) -> Option<Self::EdgeId>;
167}
168
169impl<N, E, Ty, Ix> EdgeFindable for &StableGraph<N, E, Ty, Ix>
170where
171    Ty: EdgeType,
172    Ix: IndexType,
173{
174    fn edge_find(&self, a: Self::NodeId, b: Self::NodeId) -> Option<Self::EdgeId> {
175        self.find_edge(a, b)
176    }
177}
178
179impl<N, E, Ty, Ix> EdgeFindable for &Graph<N, E, Ty, Ix>
180where
181    Ty: EdgeType,
182    Ix: IndexType,
183{
184    fn edge_find(&self, a: Self::NodeId, b: Self::NodeId) -> Option<Self::EdgeId> {
185        self.find_edge(a, b)
186    }
187}
rustworkx_core/graph_ext/mod.rs

rustworkx_core/graph_ext/
mod.rs
