Struct petgraph::matrix_graph::MatrixGraph[][src]

pub struct MatrixGraph<N, E, Ty = Directed, Null: Nullable<Wrapped = E> = Option<E>, Ix = u16> { /* fields omitted */ }

MatrixGraph<N, E, Ty, Null> is a graph datastructure using an adjacency matrix representation.

MatrixGraph is parameterized over:

The graph uses O(|V^2|) space, with fast edge insertion & amortized node insertion, as well as efficient graph search and graph algorithms on dense graphs.

This graph is backed by a flattened 2D array. For undirected graphs, only the lower triangular matrix is stored. Since the backing array stores edge weights, it is recommended to box large edge weights.

Implementations

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> MatrixGraph<N, E, Ty, Null, Ix>[src]

pub fn with_capacity(node_capacity: usize) -> Self[src]

Create a new MatrixGraph with estimated capacity for nodes.

pub fn clear(&mut self)[src]

Remove all nodes and edges.

pub fn node_count(&self) -> usize[src]

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

Computes in O(1) time.

pub fn edge_count(&self) -> usize[src]

Return the number of edges in the graph.

Computes in O(1) time.

pub fn is_directed(&self) -> bool[src]

Return whether the graph has directed edges or not.

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

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 MatrixGraph is at the maximum number of nodes for its index type.

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

Remove a from the graph.

Computes in O(V) time, due to the removal of edges with other nodes.

Panics if the node a does not exist.

pub fn update_edge(
    &mut self,
    a: NodeIndex<Ix>,
    b: NodeIndex<Ix>,
    weight: E
) -> Option<E>
[src]

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

Return the previous data, if any.

Computes in O(1) time, best case. Computes in O(|V|^2) time, worst case (matrix needs to be re-allocated).

Panics if any of the nodes don’t exist.

pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E)[src]

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, best case. Computes in O(|V|^2) time, worst case (matrix needs to be re-allocated).

Panics if any of the nodes don’t exist. Panics if an edge already exists from a to b.

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

pub fn remove_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> E[src]

Remove the edge from a to b to the graph.

Panics if any of the nodes don’t exist. Panics if no edge exists between a and b.

pub fn has_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool[src]

Return true if there is an edge between a and b.

Panics if any of the nodes don’t exist.

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

Access the weight for node a.

Also available with indexing syntax: &graph[a].

Panics if the node doesn’t exist.

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

Access the weight for node a, mutably.

Also available with indexing syntax: &mut graph[a].

Panics if the node doesn’t exist.

pub fn edge_weight(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &E[src]

Access the weight for edge e.

Also available with indexing syntax: &graph[e].

Panics if no edge exists between a and b.

pub fn edge_weight_mut(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &mut E[src]

Access the weight for edge e, mutably.

Also available with indexing syntax: &mut graph[e].

Panics if no edge exists between a and b.

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

Notable traits for Neighbors<'a, Ty, Null, Ix>

impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for Neighbors<'a, Ty, Null, Ix> type Item = NodeIndex<Ix>;
[src]

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>.

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

Notable traits for Edges<'a, Ty, Null, Ix>

impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for Edges<'a, Ty, Null, Ix> type Item = (NodeIndex<Ix>, NodeIndex<Ix>, &'a Null::Wrapped);
[src]

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 Edges<E, Ix>.

pub fn from_edges<I>(iterable: I) -> Self where
    I: IntoIterator,
    I::Item: IntoWeightedEdge<E>,
    <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
    N: Default
[src]

Create a new MatrixGraph 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.

use petgraph::matrix_graph::MatrixGraph;

let gr = MatrixGraph::<(), i32>::from_edges(&[
    (0, 1), (0, 2), (0, 3),
    (1, 2), (1, 3),
    (2, 3),
]);

pub fn extend_with_edges<I>(&mut self, iterable: I) where
    I: IntoIterator,
    I::Item: IntoWeightedEdge<E>,
    <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
    N: Default
[src]

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.

impl<N, E, Null: Nullable<Wrapped = E>, Ix: IndexType> MatrixGraph<N, E, Directed, Null, Ix>[src]

pub fn neighbors_directed(
    &self,
    a: NodeIndex<Ix>,
    d: Direction
) -> Neighbors<'_, Directed, Null, Ix>

Notable traits for Neighbors<'a, Ty, Null, Ix>

impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for Neighbors<'a, Ty, Null, Ix> type Item = NodeIndex<Ix>;
[src]

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).

  • Outgoing: All edges from a.
  • Incoming: All edges to a.

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

pub fn edges_directed(
    &self,
    a: NodeIndex<Ix>,
    d: Direction
) -> Edges<'_, Directed, Null, Ix>

Notable traits for Edges<'a, Ty, Null, Ix>

impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for Edges<'a, Ty, Null, Ix> type Item = (NodeIndex<Ix>, NodeIndex<Ix>, &'a Null::Wrapped);
[src]

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

  • Outgoing: All edges from a.
  • Incoming: All edges to a.

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

impl<N, E> MatrixGraph<N, E, Directed>[src]

pub fn new() -> Self[src]

Create a new MatrixGraph with directed edges.

This is a convenience method. Use MatrixGraph::with_capacity or MatrixGraph::default for a constructor that is generic in all the type parameters of MatrixGraph.

impl<N, E> MatrixGraph<N, E, Undirected>[src]

pub fn new_undirected() -> Self[src]

Create a new MatrixGraph with undirected edges.

This is a convenience method. Use MatrixGraph::with_capacity or MatrixGraph::default for a constructor that is generic in all the type parameters of MatrixGraph.

Trait Implementations

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Build for MatrixGraph<N, E, Ty, Null, Ix>[src]

impl<N: Clone, E: Clone, Ty: Clone, Null: Clone + Nullable<Wrapped = E>, Ix: Clone> Clone for MatrixGraph<N, E, Ty, Null, Ix>[src]

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Data for MatrixGraph<N, E, Ty, Null, Ix>[src]

type NodeWeight = N

type EdgeWeight = E

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Default for MatrixGraph<N, E, Ty, Null, Ix>[src]

Create a new empty MatrixGraph.

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GetAdjacencyMatrix for MatrixGraph<N, E, Ty, Null, Ix>[src]

type AdjMatrix = ()

The associated adjacency matrix type

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GraphBase for MatrixGraph<N, E, Ty, Null, Ix>[src]

type NodeId = NodeIndex<Ix>

node identifier

type EdgeId = (NodeIndex<Ix>, NodeIndex<Ix>)

edge identifier

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GraphProp for MatrixGraph<N, E, Ty, Null, Ix>[src]

type EdgeType = Ty

The kind edges in the graph.

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Index<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix>[src]

Index the MatrixGraph by NodeIndex pair to access edge weights.

Also available with indexing syntax: &graph[e].

Panics if no edge exists between a and b.

type Output = E

The returned type after indexing.

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Index<NodeIndex<Ix>> for MatrixGraph<N, E, Ty, Null, Ix>[src]

Index the MatrixGraph by NodeIndex to access node weights.

Panics if the node doesn’t exist.

type Output = N

The returned type after indexing.

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IndexMut<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix>[src]

Index the MatrixGraph by NodeIndex pair to access edge weights.

Also available with indexing syntax: &mut graph[e].

Panics if no edge exists between a and b.

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IndexMut<NodeIndex<Ix>> for MatrixGraph<N, E, Ty, Null, Ix>[src]

Index the MatrixGraph by NodeIndex to access node weights.

Panics if the node doesn’t exist.

impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdgeReferences for &'a MatrixGraph<N, E, Ty, Null, Ix>[src]

type EdgeRef = (NodeIndex<Ix>, NodeIndex<Ix>, &'a E)

type EdgeReferences = EdgeReferences<'a, Ty, Null, Ix>

impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdges for &'a MatrixGraph<N, E, Ty, Null, Ix>[src]

type Edges = Edges<'a, Ty, Null, Ix>

impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNeighbors for &'a MatrixGraph<N, E, Ty, Null, Ix>[src]

type Neighbors = Neighbors<'a, Ty, Null, Ix>

impl<'a, N, E: 'a, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNeighborsDirected for &'a MatrixGraph<N, E, Directed, Null, Ix>[src]

type NeighborsDirected = Neighbors<'a, Directed, Null, Ix>

impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNodeIdentifiers for &'a MatrixGraph<N, E, Ty, Null, Ix>[src]

impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNodeReferences for &'a MatrixGraph<N, E, Ty, Null, Ix>[src]

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeCount for MatrixGraph<N, E, Ty, Null, Ix>[src]

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeIndexable for MatrixGraph<N, E, Ty, Null, Ix>[src]

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Visitable for MatrixGraph<N, E, Ty, Null, Ix>[src]

type Map = FixedBitSet

The associated map type

impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeCompactIndexable for MatrixGraph<N, E, Ty, Null, Ix>[src]

Auto Trait Implementations

impl<N, E, Ty, Null, Ix> RefUnwindSafe for MatrixGraph<N, E, Ty, Null, Ix> where
    Ix: RefUnwindSafe,
    N: RefUnwindSafe,
    Null: RefUnwindSafe,
    Ty: RefUnwindSafe

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

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

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

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

Blanket Implementations

impl<T> Any for T where
    T: 'static + ?Sized
[src]

impl<T> Borrow<T> for T where
    T: ?Sized
[src]

impl<T> BorrowMut<T> for T where
    T: ?Sized
[src]

impl<T> From<T> for T[src]

impl<T, U> Into<U> for T where
    U: From<T>, 
[src]

impl<T> Pointable for T[src]

type Init = T

The type for initializers.

impl<T> ToOwned for T where
    T: Clone
[src]

type Owned = T

The resulting type after obtaining ownership.

impl<T, U> TryFrom<U> for T where
    U: Into<T>, 
[src]

type Error = Infallible

The type returned in the event of a conversion error.

impl<T, U> TryInto<U> for T where
    U: TryFrom<T>, 
[src]

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

The type returned in the event of a conversion error.