//! **Graph\<N, E, Ty, Ix\>** is a graph datastructure using an adjacency list representation.
use std::fmt;
use std::slice;
use std::iter;
use std::ops::{Index, IndexMut};
use super::{
EdgeDirection, Outgoing, Incoming,
Undirected,
Directed,
EdgeType,
};
/// The default integer type for node and edge indices in **Graph**.
/// **u32** is the default to reduce the size of the graph's data and improve
/// performance in the common case.
pub type DefIndex = u32;
/// Trait for the unsigned integer type used for node and edge indices.
pub trait IndexType : Copy + Clone + Ord + fmt::Debug + 'static
{
fn new(x: usize) -> Self;
fn index(&self) -> usize;
fn max() -> Self;
}
impl IndexType for usize {
#[inline(always)]
fn new(x: usize) -> Self { x }
#[inline(always)]
fn index(&self) -> Self { *self }
#[inline(always)]
fn max() -> Self { ::std::usize::MAX }
}
impl IndexType for u32 {
#[inline(always)]
fn new(x: usize) -> Self { x as u32 }
#[inline(always)]
fn index(&self) -> usize { *self as usize }
#[inline(always)]
fn max() -> Self { ::std::u32::MAX }
}
// FIXME: These aren't stable, so a public wrapper of node/edge indices
// should be lifetimed just like pointers.
/// Node identifier.
#[derive(Copy, Clone, Debug, PartialEq, PartialOrd, Eq, Ord, Hash)]
pub struct NodeIndex<Ix=DefIndex>(Ix);
impl<Ix: IndexType = DefIndex> NodeIndex<Ix>
{
#[inline]
pub fn new(x: usize) -> Self {
NodeIndex(IndexType::new(x))
}
#[inline]
pub fn index(self) -> usize
{
self.0.index()
}
#[inline]
pub fn end() -> Self
{
NodeIndex(IndexType::max())
}
}
/// Edge identifier.
#[derive(Copy, Clone, PartialEq, PartialOrd, Eq, Ord, Hash)]
pub struct EdgeIndex<Ix=DefIndex>(Ix);
impl<Ix: IndexType = DefIndex> EdgeIndex<Ix>
{
#[inline]
pub fn new(x: usize) -> Self {
EdgeIndex(IndexType::new(x))
}
#[inline]
pub fn index(self) -> usize
{
self.0.index()
}
/// An invalid **EdgeIndex** used to denote absence of an edge, for example
/// to end an adjacency list.
#[inline]
pub fn end() -> Self {
EdgeIndex(IndexType::max())
}
}
impl<Ix: IndexType> fmt::Debug for EdgeIndex<Ix>
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
try!(write!(f, "EdgeIndex("));
if *self == EdgeIndex::end() {
try!(write!(f, "End"));
} else {
try!(write!(f, "{}", self.index()));
}
write!(f, ")")
}
}
const DIRECTIONS: [EdgeDirection; 2] = [EdgeDirection::Outgoing, EdgeDirection::Incoming];
/// The graph's node type.
#[derive(Debug, Clone)]
pub struct Node<N, Ix: IndexType = DefIndex> {
/// Associated node data.
pub weight: N,
/// Next edge in outgoing and incoming edge lists.
next: [EdgeIndex<Ix>; 2],
}
impl<N, Ix: IndexType = DefIndex> Node<N, Ix>
{
/// Accessor for data structure internals: the first edge in the given direction.
pub fn next_edge(&self, dir: EdgeDirection) -> EdgeIndex<Ix>
{
self.next[dir as usize]
}
}
/// The graph's edge type.
#[derive(Debug, Clone)]
pub struct Edge<E, Ix: IndexType = DefIndex> {
/// Associated edge data.
pub weight: E,
/// Next edge in outgoing and incoming edge lists.
next: [EdgeIndex<Ix>; 2],
/// Start and End node index
node: [NodeIndex<Ix>; 2],
}
impl<E, Ix: IndexType = DefIndex> Edge<E, Ix>
{
/// Accessor for data structure internals: the next edge for the given direction.
pub fn next_edge(&self, dir: EdgeDirection) -> EdgeIndex<Ix>
{
self.next[dir as usize]
}
/// Return the source node index.
pub fn source(&self) -> NodeIndex<Ix>
{
self.node[0]
}
/// Return the target node index.
pub fn target(&self) -> NodeIndex<Ix>
{
self.node[1]
}
}
/// **Graph\<N, E, Ty, Ix\>** is a graph datastructure using an adjacency list representation.
///
/// **Graph** is parameterized over the node weight **N**, edge weight **E**,
/// edge type **Ty** that determines whether the graph has directed edges or not,
/// and **Ix** which is the index type used.
///
/// Based on the graph implementation in rustc.
///
/// The graph maintains unique indices for nodes and edges, and node and edge
/// weights may be accessed mutably.
///
/// **NodeIndex** and **EdgeIndex** are types that act as references to nodes and edges,
/// but these are only stable across certain operations. **Removing nodes or edges may shift
/// other indices**. Adding to the graph keeps
/// all indices stable, but removing a node will force the last node to shift its index to
/// take its place. Similarly, removing an edge shifts the index of the last edge.
///
/// The fact that the node and edge indices in the graph are numbered in a compact interval from
/// 0 to *n* - 1 simplifies some graph algorithms.
///
/// The **Ix** parameter is **u32** by default. The goal is that you can ignore this parameter
/// completely unless you need a very big graph -- then you can use **usize**.
#[derive(Clone)]
pub struct Graph<N, E, Ty = Directed, Ix: IndexType = DefIndex> {
nodes: Vec<Node<N, Ix>>,
edges: Vec<Edge<E, Ix>>,
}
impl<N, E, Ty, Ix> fmt::Debug for Graph<N, E, Ty, Ix> where
N: fmt::Debug, E: fmt::Debug, Ty: EdgeType, Ix: IndexType
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
for (index, n) in self.nodes.iter().enumerate() {
try!(writeln!(f, "{}: {:?}", index, n));
}
for (index, n) in self.edges.iter().enumerate() {
try!(writeln!(f, "{}: {:?}", index, n));
}
Ok(())
}
}
enum Pair<T> {
Both(T, T),
One(T),
None,
}
fn index_twice<T>(slc: &mut [T], a: usize, b: usize) -> Pair<&mut T>
{
if a == b {
slc.get_mut(a).map_or(Pair::None, Pair::One)
} else {
if a >= slc.len() || b >= slc.len() {
Pair::None
} else {
// safe because a, b are in bounds and distinct
unsafe {
let ar = &mut *(slc.get_unchecked_mut(a) as *mut _);
let br = &mut *(slc.get_unchecked_mut(b) as *mut _);
Pair::Both(ar, br)
}
}
}
}
impl<N, E> Graph<N, E, Directed>
{
/// Create a new **Graph** with directed edges.
pub fn new() -> Self
{
Graph{nodes: Vec::new(), edges: Vec::new()}
}
}
impl<N, E> Graph<N, E, Undirected>
{
/// Create a new **Graph** with undirected edges.
pub fn new_undirected() -> Self
{
Graph{nodes: Vec::new(), edges: Vec::new()}
}
}
impl<N, E, Ty=Directed, Ix=DefIndex> Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
{
/// Create a new **Graph** with estimated capacity.
pub fn with_capacity(nodes: usize, edges: usize) -> Self
{
Graph{nodes: Vec::with_capacity(nodes), edges: Vec::with_capacity(edges)}
}
/// Return the number of nodes (vertices) in the graph.
pub fn node_count(&self) -> usize
{
self.nodes.len()
}
/// Return the number of edges in the graph.
///
/// Computes in **O(1)** time.
pub fn edge_count(&self) -> usize
{
self.edges.len()
}
/// Remove all nodes and edges
pub fn clear(&mut self)
{
self.nodes.clear();
self.edges.clear();
}
/// Return whether the graph has directed edges or not.
#[inline]
pub fn is_directed(&self) -> bool
{
<Ty as EdgeType>::is_directed()
}
/// Cast the graph as either undirected or directed. No edge adjustments
/// are done.
///
/// Computes in **O(1)** time.
pub fn into_edge_type<NewTy>(self) -> Graph<N, E, NewTy, Ix> where
NewTy: EdgeType
{
Graph{nodes: self.nodes, edges: self.edges}
}
/// Add a node (also called vertex) with weight **w** to the graph.
///
/// Computes in **O(1)** time.
///
/// Return the index of the new node.
pub fn add_node(&mut self, w: N) -> NodeIndex<Ix>
{
let node = Node{weight: w, next: [EdgeIndex::end(), EdgeIndex::end()]};
let node_idx = NodeIndex::new(self.nodes.len());
assert!(NodeIndex::end() != node_idx);
self.nodes.push(node);
node_idx
}
/// Access node weight for node **a**.
pub fn node_weight(&self, a: NodeIndex<Ix>) -> Option<&N>
{
self.nodes.get(a.index()).map(|n| &n.weight)
}
/// Access node weight for node **a**.
pub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> Option<&mut N>
{
self.nodes.get_mut(a.index()).map(|n| &mut n.weight)
}
/// Return an iterator of all nodes with an edge starting from **a**.
///
/// Produces an empty iterator if the node doesn't exist.
///
/// Iterator element type is **NodeIndex<Ix>**.
pub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<E, Ix>
{
if self.is_directed() {
self.neighbors_directed(a, Outgoing)
} else {
self.neighbors_undirected(a)
}
}
/// Return an iterator of all neighbors that have an edge between them and **a**,
/// in the specified direction.
/// If the graph is undirected, this is equivalent to *.neighbors(a)*.
///
/// Produces an empty iterator if the node doesn't exist.
///
/// Iterator element type is **NodeIndex<Ix>**.
pub fn neighbors_directed(&self, a: NodeIndex<Ix>, dir: EdgeDirection) -> Neighbors<E, Ix>
{
let mut iter = self.neighbors_undirected(a);
if self.is_directed() {
// remove the other edges not wanted.
let k = dir as usize;
iter.next[1 - k] = EdgeIndex::end();
}
iter
}
/// Return an iterator of all neighbors that have an edge between them and **a**,
/// in either direction.
/// If the graph is undirected, this is equivalent to *.neighbors(a)*.
///
/// Produces an empty iterator if the node doesn't exist.
///
/// Iterator element type is **NodeIndex<Ix>**.
pub fn neighbors_undirected(&self, a: NodeIndex<Ix>) -> Neighbors<E, Ix>
{
Neighbors {
edges: &self.edges,
next: match self.nodes.get(a.index()) {
None => [EdgeIndex::end(), EdgeIndex::end()],
Some(n) => n.next,
}
}
}
/// Return an iterator over the neighbors of node **a**, paired with their respective edge
/// weights.
///
/// Produces an empty iterator if the node doesn't exist.
///
/// Iterator element type is **(NodeIndex<Ix>, &'a E)**.
pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<E, Ix>
{
let mut iter = self.edges_both(a);
if self.is_directed() {
iter.next[Incoming as usize] = EdgeIndex::end();
}
iter
}
/// Return an iterator over the edgs from **a** to its neighbors, then *to* **a** from its
/// neighbors.
///
/// Produces an empty iterator if the node doesn't exist.
///
/// Iterator element type is **(NodeIndex<Ix>, &'a E)**.
pub fn edges_both(&self, a: NodeIndex<Ix>) -> Edges<E, Ix>
{
Edges{
edges: &self.edges,
next: match self.nodes.get(a.index()) {
None => [EdgeIndex::end(), EdgeIndex::end()],
Some(n) => n.next,
}
}
}
/// Add an edge from **a** to **b** to the graph, with its edge weight.
///
/// **Note:** **Graph** allows adding parallel (“duplicate”) edges. If you want
/// to avoid this, use [*.update_edge(a, b, weight)*](#method.update_edge) instead.
///
/// Computes in **O(1)** time.
///
/// Return the index of the new edge.
///
/// **Panics** if any of the nodes don't exist.
pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix>
{
let edge_idx = EdgeIndex::new(self.edges.len());
assert!(edge_idx != EdgeIndex::end());
match index_twice(self.nodes.as_mut_slice(), a.index(), b.index()) {
Pair::None => panic!("NodeIndices out of bounds"),
Pair::One(an) => {
let edge = Edge {
weight: weight,
node: [a, b],
next: an.next,
};
an.next[0] = edge_idx;
an.next[1] = edge_idx;
self.edges.push(edge);
}
Pair::Both(an, bn) => {
// a and b are different indices
let edge = Edge {
weight: weight,
node: [a, b],
next: [an.next[0], bn.next[1]],
};
an.next[0] = edge_idx;
bn.next[1] = edge_idx;
self.edges.push(edge);
}
}
edge_idx
}
/// Add or update an edge from **a** to **b**.
///
/// If the edge already exists, its weight is updated.
///
/// Computes in **O(e')** time, where **e'** is the number of edges
/// connected to the vertices **a** (and **b**).
///
/// Return the index of the affected edge.
///
/// **Panics** if any of the nodes don't exist.
pub fn update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix>
{
if let Some(ix) = self.find_edge(a, b) {
match self.edge_weight_mut(ix) {
Some(ed) => {
*ed = weight;
return ix;
}
None => {}
}
}
self.add_edge(a, b, weight)
}
/// Access the edge weight for **e**.
pub fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E>
{
self.edges.get(e.index()).map(|ed| &ed.weight)
}
/// Access the edge weight for **e** mutably.
pub fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut E>
{
self.edges.get_mut(e.index()).map(|ed| &mut ed.weight)
}
/// Remove **a** from the graph if it exists, and return its weight.
/// If it doesn't exist in the graph, return **None**.
pub fn remove_node(&mut self, a: NodeIndex<Ix>) -> Option<N>
{
match self.nodes.get(a.index()) {
None => return None,
_ => {}
}
for d in DIRECTIONS.iter() {
let k = *d as usize;
/*
println!("Starting edge removal for k={}, node={}", k, a);
for (i, n) in self.nodes.iter().enumerate() {
println!("Node {}: Edges={}", i, n.next);
}
for (i, ed) in self.edges.iter().enumerate() {
println!("Edge {}: {}", i, ed);
}
*/
// Remove all edges from and to this node.
loop {
let next = self.nodes[a.index()].next[k];
if next == EdgeIndex::end() {
break
}
let ret = self.remove_edge(next);
debug_assert!(ret.is_some());
let _ = ret;
}
}
// Use swap_remove -- only the swapped-in node is going to change
// NodeIndex<Ix>, so we only have to walk its edges and update them.
let node = self.nodes.swap_remove(a.index());
// Find the edge lists of the node that had to relocate.
// It may be that no node had to relocate, then we are done already.
let swap_edges = match self.nodes.get(a.index()) {
None => return Some(node.weight),
Some(ed) => ed.next,
};
// The swapped element's old index
let old_index = NodeIndex::new(self.nodes.len());
let new_index = a;
// Adjust the starts of the out edges, and ends of the in edges.
for &d in DIRECTIONS.iter() {
let k = d as usize;
for (_, curedge) in EdgesMut::new(self.edges.as_mut_slice(), swap_edges[k], d) {
debug_assert!(curedge.node[k] == old_index);
curedge.node[k] = new_index;
}
}
Some(node.weight)
}
/// For edge **e** with endpoints **edge_node**, replace links to it,
/// with links to **edge_next**.
fn change_edge_links(&mut self, edge_node: [NodeIndex<Ix>; 2], e: EdgeIndex<Ix>,
edge_next: [EdgeIndex<Ix>; 2])
{
for &d in DIRECTIONS.iter() {
let k = d as usize;
let node = match self.nodes.get_mut(edge_node[k].index()) {
Some(r) => r,
None => {
debug_assert!(false, "Edge's endpoint dir={:?} index={:?} not found",
d, edge_node[k]);
return
}
};
let fst = node.next[k];
if fst == e {
//println!("Updating first edge 0 for node {}, set to {}", edge_node[0], edge_next[0]);
node.next[k] = edge_next[k];
} else {
for (_i, curedge) in EdgesMut::new(self.edges.as_mut_slice(), fst, d) {
if curedge.next[k] == e {
curedge.next[k] = edge_next[k];
break; // the edge can only be present once in the list.
}
}
}
}
}
/// Remove an edge and return its edge weight, or **None** if it didn't exist.
///
/// Computes in **O(e')** time, where **e'** is the size of four particular edge lists, for
/// the vertices of **e** and the vertices of another affected edge.
pub fn remove_edge(&mut self, e: EdgeIndex<Ix>) -> Option<E>
{
// every edge is part of two lists,
// outgoing and incoming edges.
// Remove it from both
let (edge_node, edge_next) = match self.edges.get(e.index()) {
None => return None,
Some(x) => (x.node, x.next),
};
// Remove the edge from its in and out lists by replacing it with
// a link to the next in the list.
self.change_edge_links(edge_node, e, edge_next);
self.remove_edge_adjust_indices(e)
}
fn remove_edge_adjust_indices(&mut self, e: EdgeIndex<Ix>) -> Option<E>
{
// swap_remove the edge -- only the removed edge
// and the edge swapped into place are affected and need updating
// indices.
let edge = self.edges.swap_remove(e.index());
let swap = match self.edges.get(e.index()) {
// no elment needed to be swapped.
None => return Some(edge.weight),
Some(ed) => ed.node,
};
let swapped_e = EdgeIndex::new(self.edges.len());
// Update the edge lists by replacing links to the old index by references to the new
// edge index.
self.change_edge_links(swap, swapped_e, [e, e]);
Some(edge.weight)
}
/// Lookup an edge from **a** to **b**.
///
/// Computes in **O(e')** time, where **e'** is the number of edges
/// connected to the vertices **a** (and **b**).
pub fn find_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<EdgeIndex<Ix>>
{
if !self.is_directed() {
self.find_edge_undirected(a, b).map(|(ix, _)| ix)
} else {
match self.nodes.get(a.index()) {
None => None,
Some(node) => {
let mut edix = node.next[0];
while let Some(edge) = self.edges.get(edix.index()) {
if edge.node[1] == b {
return Some(edix)
}
edix = edge.next[0];
}
None
}
}
}
}
/// Lookup an edge between **a** and **b**, in either direction.
///
/// If the graph is undirected, then this is equivalent to *.find_edge()*.
pub fn find_edge_undirected(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<(EdgeIndex<Ix>, EdgeDirection)>
{
match self.nodes.get(a.index()) {
None => None,
Some(node) => {
for &d in DIRECTIONS.iter() {
let k = d as usize;
let mut edix = node.next[k];
while let Some(edge) = self.edges.get(edix.index()) {
if edge.node[1 - k] == b {
return Some((edix, d))
}
edix = edge.next[k];
}
}
None
}
}
}
/// Reverse the direction of all edges
pub fn reverse(&mut self)
{
for edge in self.edges.iter_mut() {
edge.node.swap(0, 1)
}
}
/* Removed: Easy to implement externally with iterate in reverse
*
/// Retain only nodes that return **true** from the predicate.
pub fn retain_nodes<F>(&mut self, mut visit: F) where
F: FnMut(&Self, NodeIndex<Ix>, &Node<N>) -> bool
{
for index in (0..self.node_count()).rev() {
let nix = NodeIndex<Ix>(index);
if !visit(&self, nix, &self.nodes[nix.index()]) {
let ret = self.remove_node(nix);
debug_assert!(ret.is_some());
let _ = ret;
}
}
}
/// Retain only edges that return **true** from the predicate.
pub fn retain_edges<F>(&mut self, mut visit: F) where
F: FnMut(&Self, EdgeIndex, &Edge<E>) -> bool
{
for index in (0..self.edge_count()).rev() {
let eix = EdgeIndex::new(index);
if !visit(&self, eix, &self.edges[eix.index()]) {
let ret = self.remove_edge(EdgeIndex::new(index));
debug_assert!(ret.is_some());
let _ = ret;
}
}
}
*/
/// Access the internal node array
pub fn raw_nodes(&self) -> &[Node<N, Ix>]
{
&self.nodes
}
/// Access the internal edge array
pub fn raw_edges(&self) -> &[Edge<E, Ix>]
{
&self.edges
}
/// Accessor for data structure internals: the first edge in the given direction.
pub fn first_edge(&self, a: NodeIndex<Ix>, dir: EdgeDirection) -> Option<EdgeIndex<Ix>>
{
match self.nodes.get(a.index()) {
None => None,
Some(node) => {
let edix = node.next[dir as usize];
if edix == EdgeIndex::end() {
None
} else { Some(edix) }
}
}
}
/// Accessor for data structure internals: the next edge for the given direction.
pub fn next_edge(&self, e: EdgeIndex<Ix>, dir: EdgeDirection) -> Option<EdgeIndex<Ix>>
{
match self.edges.get(e.index()) {
None => None,
Some(node) => {
let edix = node.next[dir as usize];
if edix == EdgeIndex::end() {
None
} else { Some(edix) }
}
}
}
/// Return an iterator over either the nodes without edges to them or from them.
///
/// The nodes in *.without_edges(Incoming)* are the initial nodes and
/// *.without_edges(Outgoing)* are the terminals.
///
/// For an undirected graph, the initials/terminals are just the vertices without edges.
///
/// The whole iteration computes in **O(|V|)** time.
pub fn without_edges(&self, dir: EdgeDirection) -> WithoutEdges<N, Ty, Ix>
{
WithoutEdges{iter: self.nodes.iter().enumerate(), dir: dir}
}
}
/// An iterator over either the nodes without edges to them or from them.
pub struct WithoutEdges<'a, N: 'a, Ty, Ix: IndexType = DefIndex> {
iter: iter::Enumerate<slice::Iter<'a, Node<N, Ix>>>,
dir: EdgeDirection,
}
impl<'a, N: 'a, Ty, Ix> Iterator for WithoutEdges<'a, N, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
{
type Item = NodeIndex<Ix>;
fn next(&mut self) -> Option<NodeIndex<Ix>>
{
let k = self.dir as usize;
loop {
match self.iter.next() {
None => return None,
Some((index, node)) => {
if node.next[k] == EdgeIndex::end() &&
(<Ty as EdgeType>::is_directed() ||
node.next[1-k] == EdgeIndex::end()) {
return Some(NodeIndex::new(index))
} else {
continue
}
},
}
}
}
}
/*
/// Iterator over the neighbors of a node.
///
/// Iterator element type is **NodeIndex**.
pub struct DiNeighbors<'a, E: 'a> {
edges: &'a [Edge<E>],
next: EdgeIndex,
dir: EdgeDirection,
}
impl<'a, E> Iterator for DiNeighbors<'a, E>
{
type Item = NodeIndex;
fn next(&mut self) -> Option<NodeIndex>
{
let k = self.dir as usize;
match self.edges.get(self.next.index()) {
None => None,
Some(edge) => {
self.next = edge.next[k];
Some(edge.node[1-k])
}
}
}
}
*/
/// Iterator over the neighbors of a node.
///
/// Iterator element type is **NodeIndex**.
pub struct Neighbors<'a, E: 'a, Ix: 'a = DefIndex> where
Ix: IndexType,
{
edges: &'a [Edge<E, Ix>],
next: [EdgeIndex<Ix>; 2],
}
impl<'a, E, Ix> Iterator for Neighbors<'a, E, Ix> where
Ix: IndexType,
{
type Item = NodeIndex<Ix>;
fn next(&mut self) -> Option<NodeIndex<Ix>>
{
match self.edges.get(self.next[0].index()) {
None => {}
Some(edge) => {
self.next[0] = edge.next[0];
return Some(edge.node[1])
}
}
match self.edges.get(self.next[1].index()) {
None => None,
Some(edge) => {
self.next[1] = edge.next[1];
Some(edge.node[0])
}
}
}
}
struct EdgesMut<'a, E: 'a, Ix: IndexType = DefIndex> {
edges: &'a mut [Edge<E, Ix>],
next: EdgeIndex<Ix>,
dir: EdgeDirection,
}
impl<'a, E, Ix> EdgesMut<'a, E, Ix> where
Ix: IndexType,
{
fn new(edges: &'a mut [Edge<E, Ix>], next: EdgeIndex<Ix>, dir: EdgeDirection) -> Self
{
EdgesMut{
edges: edges,
next: next,
dir: dir
}
}
}
impl<'a, E, Ix> Iterator for EdgesMut<'a, E, Ix> where
Ix: IndexType,
{
type Item = (EdgeIndex<Ix>, &'a mut Edge<E, Ix>);
fn next(&mut self) -> Option<(EdgeIndex<Ix>, &'a mut Edge<E, Ix>)>
{
let this_index = self.next;
let k = self.dir as usize;
match self.edges.get_mut(self.next.index()) {
None => None,
Some(edge) => {
self.next = edge.next[k];
// We cannot in safe rust, derive a &'a mut from &mut self,
// when the life of &mut self is shorter than 'a.
//
// We guarantee that this will not allow two pointers to the same
// edge, and use unsafe to extend the life.
//
// See http://stackoverflow.com/a/25748645/3616050
let long_life_edge = unsafe {
&mut *(edge as *mut _)
};
Some((this_index, long_life_edge))
}
}
}
}
/// Iterator over the edges of a node.
pub struct Edges<'a, E: 'a, Ix: IndexType = DefIndex> {
edges: &'a [Edge<E, Ix>],
next: [EdgeIndex<Ix>; 2],
}
impl<'a, E, Ix> Iterator for Edges<'a, E, Ix> where
Ix: IndexType,
{
type Item = (NodeIndex<Ix>, &'a E);
fn next(&mut self) -> Option<(NodeIndex<Ix>, &'a E)>
{
// First any outgoing edges
match self.edges.get(self.next[0].index()) {
None => {}
Some(edge) => {
self.next[0] = edge.next[0];
return Some((edge.node[1], &edge.weight))
}
}
// Then incoming edges
match self.edges.get(self.next[1].index()) {
None => None,
Some(edge) => {
self.next[1] = edge.next[1];
Some((edge.node[0], &edge.weight))
}
}
}
}
impl<N, E, Ty, Ix> Index<NodeIndex<Ix>> for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
{
type Output = N;
/// Index the **Graph** by **NodeIndex** to access node weights.
///
/// **Panics** if the node doesn't exist.
fn index(&self, index: &NodeIndex<Ix>) -> &N {
&self.nodes[index.index()].weight
}
}
impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
{
type Output = N;
/// Index the **Graph** by **NodeIndex** to access node weights.
///
/// **Panics** if the node doesn't exist.
fn index_mut(&mut self, index: &NodeIndex<Ix>) -> &mut N {
&mut self.nodes[index.index()].weight
}
}
impl<N, E, Ty, Ix> Index<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
{
type Output = E;
/// Index the **Graph** by **EdgeIndex** to access edge weights.
///
/// **Panics** if the edge doesn't exist.
fn index(&self, index: &EdgeIndex<Ix>) -> &E {
&self.edges[index.index()].weight
}
}
impl<N, E, Ty, Ix> IndexMut<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
{
type Output = E;
/// Index the **Graph** by **EdgeIndex** to access edge weights.
///
/// **Panics** if the edge doesn't exist.
fn index_mut(&mut self, index: &EdgeIndex<Ix>) -> &mut E {
&mut self.edges[index.index()].weight
}
}