1use crate::data::{Build, DataMap, DataMapMut};
3use crate::iter_format::NoPretty;
4use crate::visit::{
5 self, EdgeCount, EdgeRef, GetAdjacencyMatrix, IntoEdgeReferences, IntoNeighbors, NodeCount,
6};
7use fixedbitset::FixedBitSet;
8use std::fmt;
9use std::ops::Range;
10
11#[doc(no_inline)]
12pub use crate::graph::{DefaultIx, IndexType};
13
14pub type NodeIndex<Ix = DefaultIx> = Ix;
16
17#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
19pub struct EdgeIndex<Ix = DefaultIx>
20where
21 Ix: IndexType,
22{
23 from: NodeIndex<Ix>,
25 successor_index: usize,
27}
28
29iterator_wrap! {
30impl (Iterator) for
31#[derive(Debug, Clone)]
35struct OutgoingEdgeIndices <Ix> where { Ix: IndexType }
36item: EdgeIndex<Ix>,
37iter: std::iter::Map<std::iter::Zip<Range<usize>, std::iter::Repeat<NodeIndex<Ix>>>, fn((usize, NodeIndex<Ix>)) -> EdgeIndex<Ix>>,
38}
39
40#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
42struct WSuc<E, Ix: IndexType> {
43 suc: Ix,
45 weight: E,
47}
48
49type Row<E, Ix> = Vec<WSuc<E, Ix>>;
51type RowIter<'a, E, Ix> = std::slice::Iter<'a, WSuc<E, Ix>>;
52
53iterator_wrap! {
54impl (Iterator DoubleEndedIterator ExactSizeIterator) for
55#[derive(Debug, Clone)]
57struct Neighbors<'a, E, Ix> where { Ix: IndexType }
58item: NodeIndex<Ix>,
59iter: std::iter::Map<RowIter<'a, E, Ix>, fn(&WSuc<E, Ix>) -> NodeIndex<Ix>>,
60}
61
62#[derive(Debug, Eq, PartialEq, Ord, PartialOrd)]
64pub struct EdgeReference<'a, E, Ix: IndexType> {
65 id: EdgeIndex<Ix>,
67 edge: &'a WSuc<E, Ix>,
69}
70
71impl<'a, E, Ix: IndexType> Copy for EdgeReference<'a, E, Ix> {}
72impl<'a, E, Ix: IndexType> Clone for EdgeReference<'a, E, Ix> {
73 fn clone(&self) -> Self {
74 EdgeReference {
75 id: self.id,
76 edge: self.edge,
77 }
78 }
79}
80
81impl<'a, E, Ix: IndexType> visit::EdgeRef for EdgeReference<'a, E, Ix> {
82 type NodeId = NodeIndex<Ix>;
83 type EdgeId = EdgeIndex<Ix>;
84 type Weight = E;
85 fn source(&self) -> Self::NodeId {
86 self.id.from
87 }
88 fn target(&self) -> Self::NodeId {
89 self.edge.suc
90 }
91 fn id(&self) -> Self::EdgeId {
92 self.id
93 }
94 fn weight(&self) -> &Self::Weight {
95 &self.edge.weight
96 }
97}
98
99#[derive(Debug, Clone)]
100pub struct EdgeIndices<'a, E, Ix: IndexType> {
101 rows: std::iter::Enumerate<std::slice::Iter<'a, Row<E, Ix>>>,
102 row_index: usize,
103 row_len: usize,
104 cur: usize,
105}
106
107impl<'a, E, Ix: IndexType> Iterator for EdgeIndices<'a, E, Ix> {
108 type Item = EdgeIndex<Ix>;
109 fn next(&mut self) -> Option<EdgeIndex<Ix>> {
110 loop {
111 if self.cur < self.row_len {
112 let res = self.cur;
113 self.cur += 1;
114 return Some(EdgeIndex {
115 from: Ix::new(self.row_index),
116 successor_index: res,
117 });
118 } else {
119 match self.rows.next() {
120 Some((index, row)) => {
121 self.row_index = index;
122 self.cur = 0;
123 self.row_len = row.len();
124 }
125 None => return None,
126 }
127 }
128 }
129 }
130}
131
132iterator_wrap! {
133 impl (Iterator DoubleEndedIterator ExactSizeIterator) for
134 #[derive(Debug, Clone)]
136 struct NodeIndices <Ix> where {}
137 item: Ix,
138 iter: std::iter::Map<Range<usize>, fn(usize) -> Ix>,
139}
140
141#[derive(Clone, Default)]
158pub struct List<E, Ix = DefaultIx>
159where
160 Ix: IndexType,
161{
162 suc: Vec<Row<E, Ix>>,
163}
164
165impl<E, Ix: IndexType> List<E, Ix> {
166 pub fn new() -> List<E, Ix> {
168 List { suc: Vec::new() }
169 }
170
171 pub fn with_capacity(nodes: usize) -> List<E, Ix> {
173 List {
174 suc: Vec::with_capacity(nodes),
175 }
176 }
177
178 pub fn clear(&mut self) {
180 self.suc.clear()
181 }
182
183 pub fn edge_count(&self) -> usize {
187 self.suc.iter().map(|x| x.len()).sum()
188 }
189
190 pub fn add_node(&mut self) -> NodeIndex<Ix> {
193 let i = self.suc.len();
194 self.suc.push(Vec::new());
195 Ix::new(i)
196 }
197
198 pub fn add_node_with_capacity(&mut self, successors: usize) -> NodeIndex<Ix> {
201 let i = self.suc.len();
202 self.suc.push(Vec::with_capacity(successors));
203 Ix::new(i)
204 }
205
206 pub fn add_node_from_edges<I: Iterator<Item = (NodeIndex<Ix>, E)>>(
209 &mut self,
210 edges: I,
211 ) -> NodeIndex<Ix> {
212 let i = self.suc.len();
213 self.suc
214 .push(edges.map(|(suc, weight)| WSuc { suc, weight }).collect());
215 Ix::new(i)
216 }
217
218 pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix> {
230 if b.index() >= self.suc.len() {
231 panic!(
232 "{} is not a valid node index for a {} nodes adjacency list",
233 b.index(),
234 self.suc.len()
235 );
236 }
237 let row = &mut self.suc[a.index()];
238 let rank = row.len();
239 row.push(WSuc { suc: b, weight });
240 EdgeIndex {
241 from: a,
242 successor_index: rank,
243 }
244 }
245
246 fn get_edge(&self, e: EdgeIndex<Ix>) -> Option<&WSuc<E, Ix>> {
247 self.suc
248 .get(e.from.index())
249 .and_then(|row| row.get(e.successor_index))
250 }
251
252 fn get_edge_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut WSuc<E, Ix>> {
253 self.suc
254 .get_mut(e.from.index())
255 .and_then(|row| row.get_mut(e.successor_index))
256 }
257
258 pub fn edge_endpoints(&self, e: EdgeIndex<Ix>) -> Option<(NodeIndex<Ix>, NodeIndex<Ix>)> {
262 self.get_edge(e).map(|x| (e.from, x.suc))
263 }
264
265 pub fn edge_indices_from(&self, a: NodeIndex<Ix>) -> OutgoingEdgeIndices<Ix> {
266 let proj: fn((usize, NodeIndex<Ix>)) -> EdgeIndex<Ix> =
267 |(successor_index, from)| EdgeIndex {
268 from,
269 successor_index,
270 };
271 let iter = (0..(self.suc[a.index()].len()))
272 .zip(std::iter::repeat(a))
273 .map(proj);
274 OutgoingEdgeIndices { iter }
275 }
276
277 pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
281 match self.suc.get(a.index()) {
282 None => false,
283 Some(row) => row.iter().any(|x| x.suc == b),
284 }
285 }
286
287 pub fn find_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<EdgeIndex<Ix>> {
291 self.suc.get(a.index()).and_then(|row| {
292 row.iter()
293 .enumerate()
294 .find(|(_, x)| x.suc == b)
295 .map(|(i, _)| EdgeIndex {
296 from: a,
297 successor_index: i,
298 })
299 })
300 }
301
302 pub fn node_indices(&self) -> NodeIndices<Ix> {
306 NodeIndices {
307 iter: (0..self.suc.len()).map(Ix::new),
308 }
309 }
310
311 pub fn edge_indices(&self) -> EdgeIndices<E, Ix> {
315 EdgeIndices {
316 rows: self.suc.iter().enumerate(),
317 row_index: 0,
318 row_len: 0,
319 cur: 0,
320 }
321 }
322}
323
324pub type UnweightedList<Ix> = List<(), Ix>;
326
327impl<E, Ix: IndexType> Build for List<E, Ix> {
328 fn add_node(&mut self, _weight: ()) -> NodeIndex<Ix> {
331 self.add_node()
332 }
333
334 fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> Option<EdgeIndex<Ix>> {
346 Some(self.add_edge(a, b, weight))
347 }
348
349 fn update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix> {
358 let row = &mut self.suc[a.index()];
359 for (i, info) in row.iter_mut().enumerate() {
360 if info.suc == b {
361 info.weight = weight;
362 return EdgeIndex {
363 from: a,
364 successor_index: i,
365 };
366 }
367 }
368 let rank = row.len();
369 row.push(WSuc { suc: b, weight });
370 EdgeIndex {
371 from: a,
372 successor_index: rank,
373 }
374 }
375}
376
377impl<'a, E, Ix> fmt::Debug for EdgeReferences<'a, E, Ix>
378where
379 E: fmt::Debug,
380 Ix: IndexType,
381{
382 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
383 let mut edge_list = f.debug_list();
384 let iter: Self = self.clone();
385 for e in iter {
386 if std::mem::size_of::<E>() != 0 {
387 edge_list.entry(&(
388 NoPretty((e.source().index(), e.target().index())),
389 e.weight(),
390 ));
391 } else {
392 edge_list.entry(&NoPretty((e.source().index(), e.target().index())));
393 }
394 }
395 edge_list.finish()
396 }
397}
398
399impl<E, Ix> fmt::Debug for List<E, Ix>
400where
401 E: fmt::Debug,
402 Ix: IndexType,
403{
404 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
405 let mut fmt_struct = f.debug_struct("adj::List");
406 fmt_struct.field("node_count", &self.node_count());
407 fmt_struct.field("edge_count", &self.edge_count());
408 if self.edge_count() > 0 {
409 fmt_struct.field("edges", &self.edge_references());
410 }
411 fmt_struct.finish()
412 }
413}
414
415impl<E, Ix> visit::GraphBase for List<E, Ix>
416where
417 Ix: IndexType,
418{
419 type NodeId = NodeIndex<Ix>;
420 type EdgeId = EdgeIndex<Ix>;
421}
422
423impl<E, Ix> visit::Visitable for List<E, Ix>
424where
425 Ix: IndexType,
426{
427 type Map = FixedBitSet;
428 fn visit_map(&self) -> FixedBitSet {
429 FixedBitSet::with_capacity(self.node_count())
430 }
431 fn reset_map(&self, map: &mut Self::Map) {
432 map.clear();
433 map.grow(self.node_count());
434 }
435}
436
437impl<'a, E, Ix: IndexType> visit::IntoNodeIdentifiers for &'a List<E, Ix> {
438 type NodeIdentifiers = NodeIndices<Ix>;
439 fn node_identifiers(self) -> NodeIndices<Ix> {
440 self.node_indices()
441 }
442}
443
444impl<Ix: IndexType> visit::NodeRef for NodeIndex<Ix> {
445 type NodeId = NodeIndex<Ix>;
446 type Weight = ();
447 fn id(&self) -> Self::NodeId {
448 *self
449 }
450 fn weight(&self) -> &Self::Weight {
451 &()
452 }
453}
454
455impl<'a, Ix: IndexType, E> visit::IntoNodeReferences for &'a List<E, Ix> {
456 type NodeRef = NodeIndex<Ix>;
457 type NodeReferences = NodeIndices<Ix>;
458 fn node_references(self) -> Self::NodeReferences {
459 self.node_indices()
460 }
461}
462
463impl<E, Ix: IndexType> visit::Data for List<E, Ix> {
464 type NodeWeight = ();
465 type EdgeWeight = E;
466}
467
468impl<'a, E, Ix: IndexType> IntoNeighbors for &'a List<E, Ix> {
469 type Neighbors = Neighbors<'a, E, Ix>;
470 fn neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors {
475 let proj: fn(&WSuc<E, Ix>) -> NodeIndex<Ix> = |x| x.suc;
476 let iter = self.suc[a.index()].iter().map(proj);
477 Neighbors { iter }
478 }
479}
480
481type SomeIter<'a, E, Ix> = std::iter::Map<
482 std::iter::Zip<std::iter::Enumerate<RowIter<'a, E, Ix>>, std::iter::Repeat<Ix>>,
483 fn(((usize, &'a WSuc<E, Ix>), Ix)) -> EdgeReference<'a, E, Ix>,
484>;
485
486iterator_wrap! {
487impl (Iterator) for
488struct EdgeReferences<'a, E, Ix> where { Ix: IndexType }
490item: EdgeReference<'a, E, Ix>,
491iter: std::iter::FlatMap<
492 std::iter::Enumerate<
493 std::slice::Iter<'a, Row<E, Ix>>
494 >,
495 SomeIter<'a, E, Ix>,
496 fn(
497 (usize, &'a Vec<WSuc<E, Ix>>)
498 ) -> SomeIter<'a, E, Ix>,
499>,
500}
501
502impl<'a, E, Ix: IndexType> Clone for EdgeReferences<'a, E, Ix> {
503 fn clone(&self) -> Self {
504 EdgeReferences {
505 iter: self.iter.clone(),
506 }
507 }
508}
509
510fn proj1<E, Ix: IndexType>(
511 ((successor_index, edge), from): ((usize, &WSuc<E, Ix>), Ix),
512) -> EdgeReference<E, Ix> {
513 let id = EdgeIndex {
514 from,
515 successor_index,
516 };
517 EdgeReference { id, edge }
518}
519fn proj2<E, Ix: IndexType>((row_index, row): (usize, &Vec<WSuc<E, Ix>>)) -> SomeIter<E, Ix> {
520 row.iter()
521 .enumerate()
522 .zip(std::iter::repeat(Ix::new(row_index)))
523 .map(proj1 as _)
524}
525
526impl<'a, Ix: IndexType, E> visit::IntoEdgeReferences for &'a List<E, Ix> {
527 type EdgeRef = EdgeReference<'a, E, Ix>;
528 type EdgeReferences = EdgeReferences<'a, E, Ix>;
529 fn edge_references(self) -> Self::EdgeReferences {
530 let iter = self.suc.iter().enumerate().flat_map(proj2 as _);
531 EdgeReferences { iter }
532 }
533}
534
535iterator_wrap! {
536impl (Iterator) for
537#[derive(Debug, Clone)]
539struct OutgoingEdgeReferences<'a, E, Ix> where { Ix: IndexType }
540item: EdgeReference<'a, E, Ix>,
541iter: SomeIter<'a, E, Ix>,
542}
543
544impl<'a, Ix: IndexType, E> visit::IntoEdges for &'a List<E, Ix> {
545 type Edges = OutgoingEdgeReferences<'a, E, Ix>;
546 fn edges(self, a: Self::NodeId) -> Self::Edges {
547 let iter = self.suc[a.index()]
548 .iter()
549 .enumerate()
550 .zip(std::iter::repeat(a))
551 .map(proj1 as _);
552 OutgoingEdgeReferences { iter }
553 }
554}
555
556impl<E, Ix: IndexType> visit::GraphProp for List<E, Ix> {
557 type EdgeType = crate::Directed;
558 fn is_directed(&self) -> bool {
559 true
560 }
561}
562
563impl<E, Ix: IndexType> NodeCount for List<E, Ix> {
564 fn node_count(&self) -> usize {
568 self.suc.len()
569 }
570}
571
572impl<E, Ix: IndexType> EdgeCount for List<E, Ix> {
573 fn edge_count(&self) -> usize {
577 List::edge_count(self)
578 }
579}
580
581impl<E, Ix: IndexType> visit::NodeIndexable for List<E, Ix> {
582 fn node_bound(&self) -> usize {
583 self.node_count()
584 }
585 #[inline]
586 fn to_index(&self, a: Self::NodeId) -> usize {
587 a.index()
588 }
589 #[inline]
590 fn from_index(&self, i: usize) -> Self::NodeId {
591 Ix::new(i)
592 }
593}
594
595impl<E, Ix: IndexType> visit::NodeCompactIndexable for List<E, Ix> {}
596
597impl<E, Ix: IndexType> DataMap for List<E, Ix> {
598 fn node_weight(&self, n: Self::NodeId) -> Option<&()> {
599 if n.index() < self.suc.len() {
600 Some(&())
601 } else {
602 None
603 }
604 }
605
606 fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E> {
610 self.get_edge(e).map(|x| &x.weight)
611 }
612}
613
614impl<E, Ix: IndexType> DataMapMut for List<E, Ix> {
615 fn node_weight_mut(&mut self, n: Self::NodeId) -> Option<&mut ()> {
616 if n.index() < self.suc.len() {
617 let b = Box::new(());
620 Some(Box::leak(b))
621 } else {
622 None
623 }
624 }
625 fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut E> {
629 self.get_edge_mut(e).map(|x| &mut x.weight)
630 }
631}
632
633impl<E, Ix> GetAdjacencyMatrix for List<E, Ix>
636where
637 Ix: IndexType,
638{
639 type AdjMatrix = FixedBitSet;
640
641 fn adjacency_matrix(&self) -> FixedBitSet {
642 let n = self.node_count();
643 let mut matrix = FixedBitSet::with_capacity(n * n);
644 for edge in self.edge_references() {
645 let i = edge.source().index() * n + edge.target().index();
646 matrix.put(i);
647
648 let j = edge.source().index() + n * edge.target().index();
649 matrix.put(j);
650 }
651 matrix
652 }
653
654 fn is_adjacent(&self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
655 let n = self.edge_count();
656 let index = n * a.index() + b.index();
657 matrix.contains(index)
658 }
659}