Struct Graph

Source
pub struct Graph<N, E, Ty = Directed, Ix = DefaultIx>(/* private fields */);

Implementations§

Source§

impl<N, E, Ty: EdgeType, Ix: IndexType> Graph<N, E, Ty, Ix>

Source

pub fn with_capacity(nodes: usize, edges: usize) -> Self

Methods from Deref<Target = Graph<N, E, Ty, Ix>>§

Source

pub fn node_count(&self) -> usize

Return the number of nodes (vertices) in the graph.

Computes in O(1) time.

Source

pub fn edge_count(&self) -> usize

Return the number of edges in the graph.

Computes in O(1) time.

Source

pub fn is_directed(&self) -> bool

Whether the graph has directed edges or not.

Source

pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix>

Add a node (also called vertex) with associated data weight to the graph.

Computes in O(1) time.

Return the index of the new node.

Panics if the Graph is at the maximum number of nodes for its index type (N/A if usize).

Source

pub fn node_weight(&self, a: NodeIndex<Ix>) -> Option<&N>

Access the weight for node a.

If node a doesn’t exist in the graph, return None. Also available with indexing syntax: &graph[a].

Source

pub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> Option<&mut N>

Access the weight for node a, mutably.

If node a doesn’t exist in the graph, return None. Also available with indexing syntax: &mut graph[a].

Source

pub fn add_edge( &mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E, ) -> EdgeIndex<Ix>

Add an edge from a to b to the graph, with its associated data weight.

Return the index of the new edge.

Computes in O(1) time.

Panics if any of the nodes don’t exist.
Panics if the Graph is at the maximum number of edges for its index type (N/A if usize).

Note: Graph allows adding parallel (“duplicate”) edges. If you want to avoid this, use .update_edge(a, b, weight) instead.

Source

pub fn update_edge( &mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E, ) -> EdgeIndex<Ix>

Add or update an edge from a to b. If the edge already exists, its weight is updated.

Return the index of the affected edge.

Computes in O(e’) time, where e’ is the number of edges connected to a (and b, if the graph edges are undirected).

Panics if any of the nodes doesn’t exist.

Source

pub fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E>

Access the weight for edge e.

If edge e doesn’t exist in the graph, return None. Also available with indexing syntax: &graph[e].

Source

pub fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut E>

Access the weight for edge e, mutably.

If edge e doesn’t exist in the graph, return None. Also available with indexing syntax: &mut graph[e].

Source

pub fn edge_endpoints( &self, e: EdgeIndex<Ix>, ) -> Option<(NodeIndex<Ix>, NodeIndex<Ix>)>

Access the source and target nodes for e.

If edge e doesn’t exist in the graph, return None.

Source

pub fn remove_node(&mut self, a: NodeIndex<Ix>) -> Option<N>

Remove a from the graph if it exists, and return its weight. If it doesn’t exist in the graph, return None.

Apart from a, this invalidates the last node index in the graph (that node will adopt the removed node index). Edge indices are invalidated as they would be following the removal of each edge with an endpoint in a.

Computes in O(e’) time, where e’ is the number of affected edges, including n calls to .remove_edge() where n is the number of edges with an endpoint in a, and including the edges with an endpoint in the displaced node.

Source

pub fn remove_edge(&mut self, e: EdgeIndex<Ix>) -> Option<E>

Remove an edge and return its edge weight, or None if it didn’t exist.

Apart from e, this invalidates the last edge index in the graph (that edge will adopt the removed edge index).

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.

Source

pub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<'_, E, Ix>

Return an iterator of all nodes with an edge starting from a.

  • Directed: Outgoing edges from a.
  • Undirected: All edges from or to a.

Produces an empty iterator if the node doesn’t exist.
Iterator element type is NodeIndex<Ix>.

Use .neighbors(a).detach() to get a neighbor walker that does not borrow from the graph.

Source

pub fn neighbors_directed( &self, a: NodeIndex<Ix>, dir: Direction, ) -> Neighbors<'_, E, Ix>

Return an iterator of all neighbors that have an edge between them and a, in the specified direction. If the graph’s edges are undirected, this is equivalent to .neighbors(a).

  • Directed, Outgoing: All edges from a.
  • Directed, Incoming: All edges to a.
  • Undirected: All edges from or to a.

Produces an empty iterator if the node doesn’t exist.
Iterator element type is NodeIndex<Ix>.

For a Directed graph, neighbors are listed in reverse order of their addition to the graph, so the most recently added edge’s neighbor is listed first. The order in an Undirected graph is arbitrary.

Use .neighbors_directed(a, dir).detach() to get a neighbor walker that does not borrow from the graph.

Source

pub fn neighbors_undirected(&self, a: NodeIndex<Ix>) -> Neighbors<'_, E, Ix>

Return an iterator of all neighbors that have an edge between them and a, in either direction. If the graph’s edges are undirected, this is equivalent to .neighbors(a).

  • Directed and Undirected: All edges from or to a.

Produces an empty iterator if the node doesn’t exist.
Iterator element type is NodeIndex<Ix>.

Use .neighbors_undirected(a).detach() to get a neighbor walker that does not borrow from the graph.

Source

pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<'_, E, Ty, Ix>

Return an iterator of all edges of a.

  • Directed: Outgoing edges from a.
  • Undirected: All edges connected to a.

Produces an empty iterator if the node doesn’t exist.
Iterator element type is EdgeReference<E, Ix>.

Source

pub fn edges_directed( &self, a: NodeIndex<Ix>, dir: Direction, ) -> Edges<'_, E, Ty, Ix>

Return an iterator of all edges of a, in the specified direction.

  • Directed, Outgoing: All edges from a.
  • Directed, Incoming: All edges to a.
  • Undirected, Outgoing: All edges connected to a, with a being the source of each edge.
  • Undirected, Incoming: All edges connected to a, with a being the target of each edge.

Produces an empty iterator if the node a doesn’t exist.
Iterator element type is EdgeReference<E, Ix>.

Source

pub fn edges_connecting( &self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, ) -> EdgesConnecting<'_, E, Ty, Ix>

Return an iterator over all the edges connecting a and b.

  • Directed: Outgoing edges from a.
  • Undirected: All edges connected to a.

Iterator element type is EdgeReference<E, Ix>.

Source

pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool

Lookup if there is an edge from a to b.

Computes in O(e’) time, where e’ is the number of edges connected to a (and b, if the graph edges are undirected).

Source

pub fn find_edge( &self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, ) -> Option<EdgeIndex<Ix>>

Lookup an edge from a to b.

Computes in O(e’) time, where e’ is the number of edges connected to a (and b, if the graph edges are undirected).

Source

pub fn find_edge_undirected( &self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, ) -> Option<(EdgeIndex<Ix>, Direction)>

Lookup an edge between a and b, in either direction.

If the graph is undirected, then this is equivalent to .find_edge().

Return the edge index and its directionality, with Outgoing meaning from a to b and Incoming the reverse, or None if the edge does not exist.

Source

pub fn externals(&self, dir: Direction) -> Externals<'_, N, Ty, Ix>

Return an iterator over either the nodes without edges to them (Incoming) or from them (Outgoing).

An internal node has both incoming and outgoing edges. The nodes in .externals(Incoming) are the source nodes and .externals(Outgoing) are the sinks of the graph.

For a graph with undirected edges, both the sinks and the sources are just the nodes without edges.

The whole iteration computes in O(|V|) time.

Source

pub fn node_indices(&self) -> NodeIndices<Ix>

Return an iterator over the node indices of the graph.

For example, in a rare case where a graph algorithm were not applicable, the following code will iterate through all nodes to find a specific index:

let index = g.node_indices().find(|i| g[*i] == "book").unwrap();
Source

pub fn node_weights_mut(&mut self) -> NodeWeightsMut<'_, N, Ix>

Return an iterator yielding mutable access to all node weights.

The order in which weights are yielded matches the order of their node indices.

Source

pub fn node_weights(&self) -> NodeWeights<'_, N, Ix>

Return an iterator yielding immutable access to all node weights.

The order in which weights are yielded matches the order of their node indices.

Source

pub fn edge_indices(&self) -> EdgeIndices<Ix>

Return an iterator over the edge indices of the graph

Source

pub fn edge_references(&self) -> EdgeReferences<'_, E, Ix>

Create an iterator over all edges, in indexed order.

Iterator element type is EdgeReference<E, Ix>.

Source

pub fn edge_weights(&self) -> EdgeWeights<'_, E, Ix>

Return an iterator yielding immutable access to all edge weights.

The order in which weights are yielded matches the order of their edge indices.

Source

pub fn edge_weights_mut(&mut self) -> EdgeWeightsMut<'_, E, Ix>

Return an iterator yielding mutable access to all edge weights.

The order in which weights are yielded matches the order of their edge indices.

Source

pub fn raw_nodes(&self) -> &[Node<N, Ix>]

Access the internal node array.

Source

pub fn raw_edges(&self) -> &[Edge<E, Ix>]

Access the internal edge array.

Source

pub fn first_edge( &self, a: NodeIndex<Ix>, dir: Direction, ) -> Option<EdgeIndex<Ix>>

Accessor for data structure internals: the first edge in the given direction.

Source

pub fn next_edge( &self, e: EdgeIndex<Ix>, dir: Direction, ) -> Option<EdgeIndex<Ix>>

Accessor for data structure internals: the next edge for the given direction.

Source

pub fn index_twice_mut<T, U>( &mut self, i: T, j: U, ) -> (&mut <Graph<N, E, Ty, Ix> as Index<T>>::Output, &mut <Graph<N, E, Ty, Ix> as Index<U>>::Output)
where Graph<N, E, Ty, Ix>: IndexMut<T> + IndexMut<U>, T: GraphIndex, U: GraphIndex,

Index the Graph by two indices, any combination of node or edge indices is fine.

Panics if the indices are equal or if they are out of bounds.

use petgraph::{Graph, Incoming};
use petgraph::visit::Dfs;

let mut gr = Graph::new();
let a = gr.add_node(0.);
let b = gr.add_node(0.);
let c = gr.add_node(0.);
gr.add_edge(a, b, 3.);
gr.add_edge(b, c, 2.);
gr.add_edge(c, b, 1.);

// walk the graph and sum incoming edges into the node weight
let mut dfs = Dfs::new(&gr, a);
while let Some(node) = dfs.next(&gr) {
    // use a walker -- a detached neighbors iterator
    let mut edges = gr.neighbors_directed(node, Incoming).detach();
    while let Some(edge) = edges.next_edge(&gr) {
        let (nw, ew) = gr.index_twice_mut(node, edge);
        *nw += *ew;
    }
}

// check the result
assert_eq!(gr[a], 0.);
assert_eq!(gr[b], 4.);
assert_eq!(gr[c], 2.);
Source

pub fn reverse(&mut self)

Reverse the direction of all edges

Source

pub fn clear(&mut self)

Remove all nodes and edges

Source

pub fn clear_edges(&mut self)

Remove all edges

Source

pub fn capacity(&self) -> (usize, usize)

Return the current node and edge capacity of the graph.

Source

pub fn reserve_nodes(&mut self, additional: usize)

Reserves capacity for at least additional more nodes to be inserted in the graph. Graph may reserve more space to avoid frequent reallocations.

Panics if the new capacity overflows usize.

Source

pub fn reserve_edges(&mut self, additional: usize)

Reserves capacity for at least additional more edges to be inserted in the graph. Graph may reserve more space to avoid frequent reallocations.

Panics if the new capacity overflows usize.

Source

pub fn reserve_exact_nodes(&mut self, additional: usize)

Reserves the minimum capacity for exactly additional more nodes to be inserted in the graph. Does nothing if the capacity is already sufficient.

Prefer reserve_nodes if future insertions are expected.

Panics if the new capacity overflows usize.

Source

pub fn reserve_exact_edges(&mut self, additional: usize)

Reserves the minimum capacity for exactly additional more edges to be inserted in the graph. Does nothing if the capacity is already sufficient.

Prefer reserve_edges if future insertions are expected.

Panics if the new capacity overflows usize.

Source

pub fn shrink_to_fit_nodes(&mut self)

Shrinks the capacity of the underlying nodes collection as much as possible.

Source

pub fn shrink_to_fit_edges(&mut self)

Shrinks the capacity of the underlying edges collection as much as possible.

Source

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the graph as much as possible.

Source

pub fn retain_nodes<F>(&mut self, visit: F)
where F: FnMut(Frozen<'_, Graph<N, E, Ty, Ix>>, NodeIndex<Ix>) -> bool,

Keep all nodes that return true from the visit closure, remove the others.

visit is provided a proxy reference to the graph, so that the graph can be walked and associated data modified.

The order nodes are visited is not specified.

Source

pub fn retain_edges<F>(&mut self, visit: F)
where F: FnMut(Frozen<'_, Graph<N, E, Ty, Ix>>, EdgeIndex<Ix>) -> bool,

Keep all edges that return true from the visit closure, remove the others.

visit is provided a proxy reference to the graph, so that the graph can be walked and associated data modified.

The order edges are visited is not specified.

Source

pub fn extend_with_edges<I>(&mut self, iterable: I)

Extend the graph from an iterable of edges.

Node weights N are set to default values. Edge weights E may either be specified in the list, or they are filled with default values.

Nodes are inserted automatically to match the edges.

Source

pub fn map<'a, F, G, N2, E2>( &'a self, node_map: F, edge_map: G, ) -> Graph<N2, E2, Ty, Ix>
where F: FnMut(NodeIndex<Ix>, &'a N) -> N2, G: FnMut(EdgeIndex<Ix>, &'a E) -> E2,

Create a new Graph by mapping node and edge weights to new values.

The resulting graph has the same structure and the same graph indices as self.

Source

pub fn filter_map<'a, F, G, N2, E2>( &'a self, node_map: F, edge_map: G, ) -> Graph<N2, E2, Ty, Ix>
where F: FnMut(NodeIndex<Ix>, &'a N) -> Option<N2>, G: FnMut(EdgeIndex<Ix>, &'a E) -> Option<E2>,

Create a new Graph by mapping nodes and edges. A node or edge may be mapped to None to exclude it from the resulting graph.

Nodes are mapped first with the node_map closure, then edge_map is called for the edges that have not had any endpoint removed.

The resulting graph has the structure of a subgraph of the original graph. If no nodes are removed, the resulting graph has compatible node indices; if neither nodes nor edges are removed, the result has the same graph indices as self.

Trait Implementations§

Source§

impl<N, E, Ty, Ix> Clone for Graph<N, E, Ty, Ix>
where Graph<N, E, Ty, Ix>: Clone,

Source§

fn clone(&self) -> Self

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, E, Ty, Ix> Debug for Graph<N, E, Ty, Ix>
where Graph<N, E, Ty, Ix>: Debug,

Source§

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

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

impl<N, E, Ty, Ix> Deref for Graph<N, E, Ty, Ix>

Source§

type Target = Graph<N, E, Ty, Ix>

The resulting type after dereferencing.
Source§

fn deref(&self) -> &Self::Target

Dereferences the value.
Source§

impl<N, E, Ty, Ix> DerefMut for Graph<N, E, Ty, Ix>

Source§

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.
Source§

impl<N, E, Ty, Ix> From<Graph<N, E, Ty, Ix>> for Graph<N, E, Ty, Ix>

Source§

fn from(inner: Graph<N, E, Ty, Ix>) -> Self

Converts to this type from the input type.

Auto Trait Implementations§

§

impl<N, E, Ty, Ix> Freeze for Graph<N, E, Ty, Ix>

§

impl<N, E, Ty, Ix> RefUnwindSafe for Graph<N, E, Ty, Ix>

§

impl<N, E, Ty, Ix> Send for Graph<N, E, Ty, Ix>
where Ty: Send, N: Send, E: Send, Ix: Send,

§

impl<N, E, Ty, Ix> Sync for Graph<N, E, Ty, Ix>
where Ty: Sync, N: Sync, E: Sync, Ix: Sync,

§

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

§

impl<N, E, Ty, Ix> UnwindSafe for Graph<N, E, Ty, Ix>
where Ty: UnwindSafe, N: UnwindSafe, E: UnwindSafe, Ix: UnwindSafe,

Blanket Implementations§

Source§

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

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

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

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

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

Source§

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

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where 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> IntoEither for T

Source§

fn into_either(self, into_left: bool) -> Either<Self, Self>

Converts self into a Left variant of Either<Self, Self> if into_left is true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
Source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
where F: FnOnce(&Self) -> bool,

Converts self into a Left variant of Either<Self, Self> if into_left(&self) returns true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
Source§

impl<P, T> Receiver for P
where P: Deref<Target = T> + ?Sized, T: ?Sized,

Source§

type Target = T

🔬This is a nightly-only experimental API. (arbitrary_self_types)
The target type on which the method may be called.
Source§

impl<T> ToOwned for T
where T: Clone,

Source§

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 T
where U: Into<T>,

Source§

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 T
where U: TryFrom<T>,

Source§

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.