Struct cargo::util::graph::Graph

source ·
pub struct Graph<N: Clone, E: Clone> {
    nodes: OrdMap<N, OrdMap<N, E>>,
}

Fields§

§nodes: OrdMap<N, OrdMap<N, E>>

Implementations§

source§

impl Graph<PackageId, HashSet<Dependency>>

source

pub fn parents_of( &self, p: PackageId ) -> impl Iterator<Item = (PackageId, bool)> + '_

source§

impl<N: Eq + Ord + Clone, E: Default + Clone> Graph<N, E>

source

pub fn new() -> Graph<N, E>

source

pub fn add(&mut self, node: N)

source

pub fn contains<Q>(&self, k: &Q) -> boolwhere N: Borrow<Q>, Q: Ord + Eq + ?Sized,

source

pub fn edge(&self, from: &N, to: &N) -> Option<&E>

source

pub fn edges(&self, from: &N) -> impl Iterator<Item = (&N, &E)>

source

pub fn sort(&self) -> Vec<N>

A topological sort of the Graph

source

fn sort_inner_visit(&self, node: &N, dst: &mut Vec<N>, marks: &mut BTreeSet<N>)

source

pub fn iter(&self) -> impl Iterator<Item = &N>

source

pub fn is_path_from_to<'a>(&'a self, from: &'a N, to: &'a N) -> bool

Checks if there is a path from from to to.

source

pub fn path_to_bottom<'a>(&'a self, pkg: &'a N) -> Vec<(&'a N, Option<&'a E>)>

Resolves one of the paths from the given dependent package down to a leaf.

The path return will be the shortest path, or more accurately one of the paths with the shortest length.

Each element contains a node along with an edge except the first one. The representation would look like:

(Node0,) -> (Node1, Edge01) -> (Node2, Edge12)…

source

pub fn path_to_top<'a>(&'a self, pkg: &'a N) -> Vec<(&'a N, Option<&'a E>)>

Resolves one of the paths from the given dependent package up to the root.

The path return will be the shortest path, or more accurately one of the paths with the shortest length.

Each element contains a node along with an edge except the first one. The representation would look like:

(Node0,) -> (Node1, Edge01) -> (Node2, Edge12)…

source§

impl<'s, N: Eq + Ord + Clone + 's, E: Default + Clone + 's> Graph<N, E>

source

fn path_to<'a, F, I>( &'s self, pkg: &'a N, fn_edge: F ) -> Vec<(&'a N, Option<&'a E>)>where I: Iterator<Item = (&'a N, &'a E)>, F: Fn(&'s Self, &'a N) -> I, 'a: 's,

source§

impl<N: Eq + Ord + Clone, E: Clone> Graph<N, E>

source

fn print_for_test(&self)

Prints the graph for constructing unit tests.

For purposes of graph traversal algorithms the edge values do not matter, and the only value of the node we care about is the order it gets compared in. This constructs a graph with the same topology but with integer keys and unit edges.

Trait Implementations§

source§

impl<N: Eq + Ord + Clone, E: Clone> Clone for Graph<N, E>

source§

fn clone(&self) -> Graph<N, E>

Returns a copy of the value. Read more
1.0.0 · source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
source§

impl<N: Display + Eq + Ord + Clone, E: Clone> Debug for Graph<N, E>

source§

fn fmt(&self, fmt: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
source§

impl<N: Eq + Ord + Clone, E: Default + Clone> Default for Graph<N, E>

source§

fn default() -> Graph<N, E>

Returns the “default value” for a type. Read more
source§

impl<N: Eq + Ord + Clone, E: Eq + Clone> PartialEq<Graph<N, E>> for Graph<N, E>

source§

fn eq(&self, other: &Graph<N, E>) -> bool

This method tests for self and other values to be equal, and is used by ==.
1.0.0 · source§

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
source§

impl<N: Eq + Ord + Clone, E: Eq + Clone> Eq for Graph<N, E>

Auto Trait Implementations§

§

impl<N, E> RefUnwindSafe for Graph<N, E>where E: RefUnwindSafe, N: RefUnwindSafe,

§

impl<N, E> !Send for Graph<N, E>

§

impl<N, E> !Sync for Graph<N, E>

§

impl<N, E> Unpin for Graph<N, E>where E: Unpin, N: Unpin,

§

impl<N, E> UnwindSafe for Graph<N, E>where E: UnwindSafe + RefUnwindSafe, N: UnwindSafe + RefUnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
§

impl<Q, K> Equivalent<K> for Qwhere Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

§

fn equivalent(&self, key: &K) -> bool

Checks if this value is equivalent to the given key. Read more
§

impl<Q, K> Equivalent<K> for Qwhere Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

§

fn equivalent(&self, key: &K) -> bool

Compare self to key and return true if they are equal.
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T> Instrument for T

source§

fn instrument(self, span: Span) -> Instrumented<Self>

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more
source§

fn in_current_span(self) -> Instrumented<Self>

Instruments this type with the current Span, returning an Instrumented wrapper. Read more
source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> Same<T> for T

§

type Output = T

Should always be Self
source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for Twhere V: MultiLane<T>,

§

fn vzip(self) -> V

source§

impl<T> WithSubscriber for T

source§

fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>where S: Into<Dispatch>,

Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

fn with_current_subscriber(self) -> WithDispatch<Self>

Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more

Layout§

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 16 bytes