fuchsia / third_party / github.com / petgraph / petgraph / 5c8ab669a8618059f20989660e8423e97ac905af / . / crates / core / src / graph / directed.rs

use crate::{ | |

edge::{Direction, Edge, EdgeMut}, | |

graph::Graph, | |

node::{Node, NodeId, NodeMut}, | |

storage::DirectedGraphStorage, | |

}; | |

impl<S> Graph<S> | |

where | |

S: DirectedGraphStorage, | |

{ | |

/// Returns an iterator over all edges between the source and target node. | |

/// | |

/// The direction of the edges is always `source → target`. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use std::collections::HashSet; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// let a = *graph.insert_node(0).id(); | |

/// let b = *graph.insert_node(1).id(); | |

/// let c = *graph.insert_node(2).id(); | |

/// | |

/// let ab = *graph.insert_edge(u8::MAX, &a, &b).id(); | |

/// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id(); | |

/// let bc = *graph.insert_edge(u8::MAX - 2, &b, &c).id(); | |

/// | |

/// assert_eq!( | |

/// graph | |

/// .directed_edges_between(&a, &b) | |

/// .map(|edge| (*edge.id(), *edge.weight())) | |

/// .collect::<HashSet<_>>(), | |

/// [(ab, u8::MAX)].into_iter().collect::<HashSet<_>>() | |

/// ); | |

/// | |

/// assert_eq!( | |

/// graph | |

/// .directed_edges_between(&b, &a) | |

/// .map(|edge| (*edge.id(), *edge.weight())) | |

/// .collect::<HashSet<_>>(), | |

/// [(ba, u8::MAX - 1)].into_iter().collect::<HashSet<_>>() | |

/// ); | |

/// ``` | |

pub fn directed_edges_between( | |

&self, | |

source: NodeId, | |

target: NodeId, | |

) -> impl Iterator<Item = Edge<'_, S>> { | |

self.storage.directed_edges_between(source, target) | |

} | |

/// Returns an iterator over all edges, with mutable weights, between the source and target | |

/// node. | |

/// | |

/// The direction of the edges is always `source → target`. | |

/// | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use std::collections::HashSet; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// let a = *graph.insert_node(0).id(); | |

/// let b = *graph.insert_node(1).id(); | |

/// let c = *graph.insert_node(2).id(); | |

/// | |

/// let ab = *graph.insert_edge(u8::MAX, &a, &b).id(); | |

/// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id(); | |

/// let bc = *graph.insert_edge(u8::MAX - 2, &b, &c).id(); | |

/// | |

/// for mut edge in graph.directed_edges_between_mut(&a, &b) { | |

/// *edge.weight_mut() -= 16; | |

/// } | |

/// | |

/// assert_eq!( | |

/// graph | |

/// .edges() | |

/// .map(|node| (*node.id(), *node.weight())) | |

/// .collect::<HashSet<_>>(), | |

/// [(ab, u8::MAX - 16), (ba, u8::MAX - 1), (bc, u8::MAX - 2)] | |

/// .into_iter() | |

/// .collect::<HashSet<_>>() | |

/// ); | |

/// ``` | |

pub fn directed_edges_between_mut( | |

&mut self, | |

source: NodeId, | |

target: NodeId, | |

) -> impl Iterator<Item = EdgeMut<'_, S>> { | |

self.storage.directed_edges_between_mut(source, target) | |

} | |

/// Returns an iterator over all neighbours of the given node in a specific direction. | |

/// | |

/// If the direction is `Outgoing`, the neighbours are all nodes that are reachable from the id | |

/// are returned, if the direction is `Incoming`, all nodes that can reach the id are returned. | |

/// | |

/// If there is a self-loop between the node and itself, it will be returned regardless of the | |

/// direction. | |

/// | |

/// This is an alias for [`Self::neighbours_directed`], due to spelling differences between | |

/// American and British English. | |

#[inline] | |

pub fn neighbors_directed( | |

&self, | |

id: NodeId, | |

direction: Direction, | |

) -> impl Iterator<Item = Node<'_, S>> { | |

self.neighbours_directed(id, direction) | |

} | |

/// Returns an iterator over all neighbours of the given node in a specific direction. | |

/// | |

/// If the direction is `Outgoing`, the neighbours are all nodes that are reachable from the id | |

/// are returned, if the direction is `Incoming`, all nodes that can reach the id are returned. | |

/// | |

/// If there is a self-loop between the node and itself, it will be returned regardless of the | |

/// direction. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use std::collections::HashSet; | |

/// use petgraph_core::edge::Direction; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// let a = *graph.insert_node(0).id(); | |

/// let b = *graph.insert_node(1).id(); | |

/// let c = *graph.insert_node(2).id(); | |

/// | |

/// let ab = *graph.insert_edge(u8::MAX, &a, &b).id(); | |

/// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id(); | |

/// let bc = *graph.insert_edge(u8::MAX - 2, &b, &c).id(); | |

/// | |

/// assert_eq!( | |

/// graph | |

/// .neighbours_directed(&b, Direction::Outgoing) | |

/// .map(|node| *node.id()) | |

/// .collect::<HashSet<_>>(), | |

/// [a, c].into_iter().collect::<HashSet<_>>() | |

/// ); | |

/// | |

/// assert_eq!( | |

/// graph | |

/// .neighbours_directed(&b, Direction::Incoming) | |

/// .map(|node| *node.id()) | |

/// .collect::<HashSet<_>>(), | |

/// [a].into_iter().collect::<HashSet<_>>() | |

/// ); | |

/// ``` | |

pub fn neighbours_directed( | |

&self, | |

id: NodeId, | |

direction: Direction, | |

) -> impl Iterator<Item = Node<'_, S>> { | |

self.storage.node_directed_neighbours(id, direction) | |

} | |

/// Returns an iterator over all neighbours, with mutable weights, of the given node in a | |

/// specific direction. | |

/// | |

/// If the direction is `Outgoing`, the neighbours are all nodes that are reachable from the id | |

/// are returned, if the direction is `Incoming`, all nodes that can reach the id are returned. | |

/// | |

/// If there is a self-loop between the node and itself, it will be returned regardless of the | |

/// direction. | |

/// | |

/// This is an alias for [`Self::neighbours_directed_mut`], due to spelling differences between | |

/// American and British English. | |

#[inline] | |

pub fn neighbors_directed_mut( | |

&mut self, | |

id: NodeId, | |

direction: Direction, | |

) -> impl Iterator<Item = NodeMut<'_, S>> { | |

self.neighbours_directed_mut(id, direction) | |

} | |

/// Returns an iterator over all neighbours, with mutable weights, of the given node in a | |

/// specific direction. | |

/// | |

/// If the direction is `Outgoing`, the neighbours are all nodes that are reachable from the id | |

/// are returned, if the direction is `Incoming`, all nodes that can reach the id are returned. | |

/// | |

/// If there is a self-loop between the node and itself, it will be returned regardless of the | |

/// direction. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use std::collections::HashSet; | |

/// use petgraph_core::edge::Direction; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// let a = *graph.insert_node(0).id(); | |

/// let b = *graph.insert_node(1).id(); | |

/// let c = *graph.insert_node(2).id(); | |

/// | |

/// let ab = *graph.insert_edge(u8::MAX, &a, &b).id(); | |

/// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id(); | |

/// let bc = *graph.insert_edge(u8::MAX - 2, &b, &c).id(); | |

/// | |

/// for mut node in graph.neighbours_directed_mut(&b, Direction::Outgoing) { | |

/// *node.weight_mut() += 1; | |

/// } | |

/// | |

/// assert_eq!( | |

/// graph | |

/// .nodes() | |

/// .map(|node| (*node.id(), *node.weight())) | |

/// .collect::<HashSet<_>>(), | |

/// [(a, 1), (b, 1), (c, 3)].into_iter().collect::<HashSet<_>>() | |

/// ); | |

/// ``` | |

pub fn neighbours_directed_mut( | |

&mut self, | |

id: NodeId, | |

direction: Direction, | |

) -> impl Iterator<Item = NodeMut<'_, S>> { | |

self.storage.node_directed_neighbours_mut(id, direction) | |

} | |

/// Returns an iterator over all edges, where one of the endpoints is the given node. | |

/// | |

/// If the direction is `Outgoing`, the edges are all edges where the node is the source, if the | |

/// direction is `Incoming`, all edges where the node is the target are returned. | |

/// | |

/// If there is a self-loop between the node and itself, it will be returned regardless of the | |

/// direction. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use std::collections::HashSet; | |

/// use petgraph_core::edge::Direction; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// let a = *graph.insert_node(0).id(); | |

/// let b = *graph.insert_node(1).id(); | |

/// let c = *graph.insert_node(2).id(); | |

/// | |

/// let ab = *graph.insert_edge(u8::MAX, &a, &b).id(); | |

/// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id(); | |

/// let bc = *graph.insert_edge(u8::MAX - 2, &b, &c).id(); | |

/// | |

/// assert_eq!( | |

/// graph | |

/// .connections_directed(&b, Direction::Outgoing) | |

/// .map(|edge| (*edge.id(), *edge.weight())) | |

/// .collect::<HashSet<_>>(), | |

/// [(ba, u8::MAX - 1), (bc, u8::MAX - 2)] | |

/// .into_iter() | |

/// .collect::<HashSet<_>>() | |

/// ); | |

/// ``` | |

pub fn connections_directed( | |

&self, | |

id: NodeId, | |

direction: Direction, | |

) -> impl Iterator<Item = Edge<'_, S>> { | |

self.storage.node_directed_connections(id, direction) | |

} | |

/// Returns an iterator over all edges, with mutable weights, where one of the endpoints is the | |

/// given node. | |

/// | |

/// If the direction is `Outgoing`, the edges are all edges where the node is the source, if the | |

/// direction is `Incoming`, all edges where the node is the target are returned. | |

/// | |

/// If there is a self-loop between the node and itself, it will be returned regardless of the | |

/// direction. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use std::collections::HashSet; | |

/// use petgraph_core::edge::Direction; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// let a = *graph.insert_node(0).id(); | |

/// let b = *graph.insert_node(1).id(); | |

/// let c = *graph.insert_node(2).id(); | |

/// | |

/// let ab = *graph.insert_edge(u8::MAX, &a, &b).id(); | |

/// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id(); | |

/// let bc = *graph.insert_edge(u8::MAX - 2, &b, &c).id(); | |

/// | |

/// for mut edge in graph.connections_directed_mut(&b, Direction::Outgoing) { | |

/// *edge.weight_mut() -= 16; | |

/// } | |

/// | |

/// assert_eq!( | |

/// graph | |

/// .edges() | |

/// .map(|edge| (*edge.id(), *edge.weight())) | |

/// .collect::<HashSet<_>>(), | |

/// [(ab, u8::MAX), (ba, u8::MAX - 17), (bc, u8::MAX - 18)] | |

/// .into_iter() | |

/// .collect::<HashSet<_>>() | |

/// ); | |

/// ``` | |

pub fn connections_directed_mut( | |

&mut self, | |

id: NodeId, | |

direction: Direction, | |

) -> impl Iterator<Item = EdgeMut<'_, S>> { | |

self.storage.node_directed_connections_mut(id, direction) | |

} | |

// TODO: move into operators and then extension trait via `GraphOperators` | |

// pub fn reverse(self) -> Result<Self, S::Error> { | |

// let (nodes, edges) = self.storage.into_parts(); | |

// | |

// let edges = edges.map(|mut edge| { | |

// let source = edge.u; | |

// let target = edge.v; | |

// | |

// edge.u = target; | |

// edge.v = source; | |

// | |

// edge | |

// }); | |

// | |

// Self::from_parts(nodes, edges) | |

// } | |

// These should go into extensions: | |

// into_undirected, into_directed, from_edges, extend_with_edges | |

} |