rs_graph/traits/
refs.rs

1/*
2 * Copyright (c) 2020-2023 Frank Fischer <frank-fischer@shadow-soft.de>
3 *
4 * This program is free software: you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation, either version 3 of the
7 * License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
16 */
17
18//! Reference graph traits.
19use super::{
20    Directed, DirectedEdge, FiniteGraph, GraphIter, GraphIterator, GraphType, IndexDigraph, IndexGraph, Undirected,
21};
22use std::ptr::NonNull;
23
24/// A reference to a basic graph type.
25pub trait GraphTypeRef<'a>: Clone {
26    /// Type of a node.
27    type Node: Copy + Eq;
28
29    /// Type of an edge.
30    type Edge: Copy + Eq;
31}
32
33/// A reference to a basic finite graph.
34///
35/// This trait contains methods with a unrestricted lifetime for `self`.
36pub trait FiniteGraphRef<'a>: GraphTypeRef<'a> {
37    /// Type of an iterator over all nodes.
38    type NodeIt: GraphIterator<Self, Item = Self::Node>;
39
40    /// Type of an iterator over all edges.
41    type EdgeIt: GraphIterator<Self, Item = Self::Edge>;
42
43    /// Return the number of nodes in the graph.
44    fn num_nodes(&self) -> usize;
45
46    /// Return a graph iterator over all nodes.
47    fn nodes_iter(&self) -> Self::NodeIt;
48
49    /// Return an iterator over all nodes.
50    fn nodes(&self) -> GraphIter<Self, Self::NodeIt>
51    where
52        Self: Sized,
53    {
54        GraphIter(FiniteGraphRef::nodes_iter(self), self)
55    }
56
57    /// Return the number of edges in the graph.
58    fn num_edges(&self) -> usize;
59
60    /// Return a graph iterator over all edges.
61    ///
62    /// This iterator traverses only the forward edges.
63    fn edges_iter(&self) -> Self::EdgeIt;
64
65    /// Return an iterator over all edges.
66    ///
67    /// This iterator traverses only the forward edges.
68    fn edges(&self) -> GraphIter<Self, Self::EdgeIt>
69    where
70        Self: Sized,
71    {
72        GraphIter(FiniteGraphRef::edges_iter(self), self)
73    }
74
75    /// Return the nodes connected by an edge.
76    ///
77    /// The order of the nodes is undefined.
78    fn enodes(&self, e: Self::Edge) -> (Self::Node, Self::Node);
79}
80
81/// A reference to a basic graph.
82///
83/// This trait contains methods with a unrestricted lifetime for `self`.
84pub trait FiniteDigraphRef<'a>: FiniteGraphRef<'a> {
85    fn src(&self, e: Self::Edge) -> Self::Node;
86    fn snk(&self, e: Self::Edge) -> Self::Node;
87}
88
89/// A reference to an undirected graph.
90///
91/// This trait contains methods with a unrestricted lifetime for `self`.
92pub trait UndirectedRef<'a>: GraphTypeRef<'a> {
93    /// Type of a graph iterator over all incident edges.
94    type NeighIt: GraphIterator<Self, Item = (Self::Edge, Self::Node)>;
95
96    /// Return a graph iterator over the edges adjacent to some node.
97    fn neigh_iter(&self, u: Self::Node) -> Self::NeighIt;
98
99    /// Return an iterator over the edges adjacent to some node.
100    fn neighs(&self, u: Self::Node) -> super::GraphIter<Self, Self::NeighIt>
101    where
102        Self: Sized,
103    {
104        GraphIter(UndirectedRef::neigh_iter(self, u), self)
105    }
106}
107
108/// A reference to a digraph.
109///
110/// This trait contains methods with a unrestricted lifetime for `self`.
111pub trait DirectedRef<'a>: UndirectedRef<'a> {
112    /// Type of a graph iterator over edges leaving a node.
113    type OutIt: GraphIterator<Self, Item = (Self::Edge, Self::Node)>;
114
115    /// Type of a graph iterator over edges entering a node.
116    type InIt: GraphIterator<Self, Item = (Self::Edge, Self::Node)>;
117
118    /// Type of an iterator over all incident edges.
119    type IncidentIt: GraphIterator<Self, Item = (Self::DirectedEdge, Self::Node)>;
120
121    /// Type of a directed edge.
122    type DirectedEdge: DirectedEdge<Edge = Self::Edge> + Copy + Eq;
123
124    /// Return the source node of an edge.
125
126    /// Return the sink node of an edge.
127    /// Return a graph iterator over the edges leaving a node.
128    fn out_iter(&self, u: Self::Node) -> Self::OutIt;
129
130    /// Return an iterator over the edges leaving a node.
131    fn outedges(&self, u: Self::Node) -> super::GraphIter<Self, Self::OutIt>
132    where
133        Self: Sized,
134    {
135        GraphIter(DirectedRef::out_iter(self, u), self)
136    }
137
138    /// Return a graph iterator over the edges leaving a node.
139    fn in_iter(&self, u: Self::Node) -> Self::InIt;
140
141    /// Return an iterator over the edges leaving a node.
142    fn inedges(&self, u: Self::Node) -> super::GraphIter<Self, Self::InIt>
143    where
144        Self: Sized,
145    {
146        GraphIter(DirectedRef::in_iter(self, u), self)
147    }
148
149    /// Return an iterator over all directed edges incident with a node.
150    fn incident_iter(&self, u: Self::Node) -> Self::IncidentIt;
151
152    /// Return an iterator over all directed edges incident with a node.
153    fn incident_edges(&self, u: Self::Node) -> super::GraphIter<Self, Self::IncidentIt>
154    where
155        Self: Sized,
156    {
157        GraphIter(DirectedRef::incident_iter(self, u), self)
158    }
159}
160
161/// A reference to an indexed graph.
162///
163/// This trait contains methods with a unrestricted lifetime for `self`.
164pub trait IndexGraphRef<'a>: UndirectedRef<'a> {
165    /// Return a unique id associated with a node.
166    fn node_id(&self, u: Self::Node) -> usize;
167
168    /// Return the node associated with the given id.
169    ///
170    /// The method panics if the id is invalid.
171    fn id2node(&self, id: usize) -> Self::Node;
172
173    /// Return a unique id associated with an edge.
174    ///
175    /// The returned id is the same for the edge and its reverse edge.
176    fn edge_id(&self, e: Self::Edge) -> usize;
177
178    /// Return the edge associated with the given id.
179    ///
180    /// The method returns the forward edge.
181    ///
182    /// The method panics if the id is invalid.
183    fn id2edge(&self, id: usize) -> Self::Edge;
184}
185
186/// A reference to an indexed digraph.
187pub trait IndexDigraphRef<'a>: IndexGraphRef<'a> + DirectedRef<'a> {}
188
189#[derive(Clone)]
190pub struct WrapIt<I>(pub I);
191
192impl<'a, G, I> GraphIterator<&'a G> for WrapIt<I>
193where
194    I: GraphIterator<G>,
195{
196    type Item = I::Item;
197
198    fn next(&mut self, g: &&'a G) -> Option<Self::Item> {
199        self.0.next(*g)
200    }
201
202    fn size_hint(&self, g: &&'a G) -> (usize, Option<usize>) {
203        self.0.size_hint(*g)
204    }
205
206    fn count(self, g: &&'a G) -> usize {
207        self.0.count(*g)
208    }
209}
210
211impl<I> From<I> for WrapIt<I> {
212    fn from(it: I) -> WrapIt<I> {
213        WrapIt(it)
214    }
215}
216
217// Implementation for &'a G
218
219impl<'a, G> GraphTypeRef<'a> for &'a G
220where
221    G: GraphType,
222{
223    type Node = G::Node<'a>;
224    type Edge = G::Edge<'a>;
225}
226
227impl<'a, G> FiniteGraphRef<'a> for &'a G
228where
229    G: FiniteGraph,
230{
231    type NodeIt = WrapIt<G::NodeIt<'a>>;
232
233    type EdgeIt = WrapIt<G::EdgeIt<'a>>;
234
235    fn num_nodes(&self) -> usize {
236        (*self).num_nodes()
237    }
238
239    fn nodes_iter(&self) -> Self::NodeIt {
240        (*self).nodes_iter().into()
241    }
242
243    fn num_edges(&self) -> usize {
244        (*self).num_edges()
245    }
246
247    fn edges_iter(&self) -> Self::EdgeIt {
248        (*self).edges_iter().into()
249    }
250
251    fn enodes(&self, e: Self::Edge) -> (Self::Node, Self::Node) {
252        (*self).enodes(e)
253    }
254}
255
256impl<'a, G> UndirectedRef<'a> for &'a G
257where
258    G: Undirected,
259{
260    type NeighIt = WrapIt<G::NeighIt<'a>>;
261
262    fn neigh_iter(&self, u: Self::Node) -> Self::NeighIt {
263        (*self).neigh_iter(u).into()
264    }
265}
266
267impl<'a, G> DirectedRef<'a> for &'a G
268where
269    G: Directed,
270{
271    type OutIt = WrapIt<G::OutIt<'a>>;
272
273    type InIt = WrapIt<G::InIt<'a>>;
274
275    type IncidentIt = WrapIt<G::IncidentIt<'a>>;
276
277    type DirectedEdge = G::DirectedEdge<'a>;
278
279    fn out_iter(&self, u: Self::Node) -> Self::OutIt {
280        (*self).out_iter(u).into()
281    }
282
283    fn in_iter(&self, u: Self::Node) -> Self::InIt {
284        (*self).in_iter(u).into()
285    }
286
287    fn incident_iter(&self, u: Self::Node) -> Self::IncidentIt {
288        (*self).incident_iter(u).into()
289    }
290}
291
292impl<'a, G> IndexGraphRef<'a> for &'a G
293where
294    G: IndexGraph,
295{
296    fn node_id(&self, u: Self::Node) -> usize {
297        (*self).node_id(u)
298    }
299
300    fn edge_id(&self, e: Self::Edge) -> usize {
301        (*self).edge_id(e)
302    }
303
304    fn id2node(&self, id: usize) -> Self::Node {
305        (*self).id2node(id)
306    }
307
308    fn id2edge(&self, id: usize) -> Self::Edge {
309        (*self).id2edge(id)
310    }
311}
312
313impl<'a, G> IndexDigraphRef<'a> for &'a G where G: IndexDigraph {}
314
315// Implementation for NonNull<G>
316
317impl<G, I> GraphIterator<NonNull<G>> for WrapIt<I>
318where
319    I: GraphIterator<G>,
320{
321    type Item = I::Item;
322
323    fn next(&mut self, g: &NonNull<G>) -> Option<Self::Item> {
324        unsafe { self.0.next(g.as_ref()) }
325    }
326
327    fn size_hint(&self, g: &NonNull<G>) -> (usize, Option<usize>) {
328        unsafe { self.0.size_hint(g.as_ref()) }
329    }
330
331    fn count(self, g: &NonNull<G>) -> usize {
332        unsafe { self.0.count(g.as_ref()) }
333    }
334}
335
336impl<'a, G> GraphTypeRef<'a> for NonNull<G>
337where
338    G: GraphType,
339{
340    type Node = G::Node<'a>;
341    type Edge = G::Edge<'a>;
342}
343
344impl<'a, G> FiniteGraphRef<'a> for NonNull<G>
345where
346    G: FiniteGraph + 'a,
347{
348    type NodeIt = WrapIt<G::NodeIt<'a>>;
349
350    type EdgeIt = WrapIt<G::EdgeIt<'a>>;
351
352    fn num_nodes(&self) -> usize {
353        unsafe { self.as_ref().num_nodes() }
354    }
355
356    fn nodes_iter(&self) -> Self::NodeIt {
357        unsafe { self.as_ref().nodes_iter().into() }
358    }
359
360    fn num_edges(&self) -> usize {
361        unsafe { self.as_ref().num_edges() }
362    }
363
364    fn edges_iter(&self) -> Self::EdgeIt {
365        unsafe { self.as_ref().edges_iter().into() }
366    }
367
368    fn enodes(&self, e: Self::Edge) -> (Self::Node, Self::Node) {
369        unsafe { self.as_ref().enodes(e) }
370    }
371}
372
373impl<'a, G> UndirectedRef<'a> for NonNull<G>
374where
375    G: Undirected + 'a,
376{
377    type NeighIt = WrapIt<G::NeighIt<'a>>;
378
379    fn neigh_iter(&self, u: Self::Node) -> Self::NeighIt {
380        unsafe { self.as_ref().neigh_iter(u).into() }
381    }
382}
383
384impl<'a, G> DirectedRef<'a> for NonNull<G>
385where
386    G: Directed + 'a,
387{
388    type OutIt = WrapIt<G::OutIt<'a>>;
389
390    type InIt = WrapIt<G::InIt<'a>>;
391
392    type IncidentIt = WrapIt<G::IncidentIt<'a>>;
393
394    type DirectedEdge = G::DirectedEdge<'a>;
395
396    fn out_iter(&self, u: Self::Node) -> Self::OutIt {
397        unsafe { self.as_ref().out_iter(u).into() }
398    }
399
400    fn in_iter(&self, u: Self::Node) -> Self::InIt {
401        unsafe { self.as_ref().in_iter(u).into() }
402    }
403
404    fn incident_iter(&self, u: Self::Node) -> Self::IncidentIt {
405        unsafe { self.as_ref().incident_iter(u).into() }
406    }
407}
408
409impl<'a, G> IndexGraphRef<'a> for NonNull<G>
410where
411    G: IndexGraph + 'a,
412{
413    fn node_id(&self, u: Self::Node) -> usize {
414        unsafe { self.as_ref().node_id(u) }
415    }
416
417    fn edge_id(&self, e: Self::Edge) -> usize {
418        unsafe { self.as_ref().edge_id(e) }
419    }
420
421    fn id2node(&self, id: usize) -> Self::Node {
422        unsafe { self.as_ref().id2node(id) }
423    }
424
425    fn id2edge(&self, id: usize) -> Self::Edge {
426        unsafe { self.as_ref().id2edge(id) }
427    }
428}
429
430impl<'a, G> IndexDigraphRef<'a> for NonNull<G> where G: IndexDigraph + 'a {}
rs_graph/traits/refs.rs

rs_graph/traits/
refs.rs
