Struct petgraph::graph::Graph [] [src]

pub struct Graph<N, E, Ty = Directed, Ix = DefaultIx> { /* fields omitted */ }

Graph<N, E, Ty, Ix> is a graph datastructure using an adjacency list representation.

Graph is parameterized over:

  • Associated data N for nodes and E for edges, called weights. The associated data can be of arbitrary type.
  • Edge type Ty that determines whether the graph edges are directed or undirected.
  • Index type Ix, which determines the maximum size of the graph.

The graph uses O(|V| + |E|) space, and allows fast node and edge insert, efficient graph search and graph algorithms. It implements O(e') edge lookup and edge and node removals, where e' is some local measure of edge count. Based on the graph datastructure used in rustc.

Here's an example of building a graph with directed edges, and below an illustration of how it could be rendered with graphviz (see Dot):

use petgraph::Graph;

let mut deps = Graph::<&str, &str>::new();
let pg = deps.add_node("petgraph");
let fb = deps.add_node("fixedbitset");
let qc = deps.add_node("quickcheck");
let rand = deps.add_node("rand");
let libc = deps.add_node("libc");
deps.extend_with_edges(&[
    (pg, fb), (pg, qc),
    (qc, rand), (rand, libc), (qc, libc),
]);

graph-example

Graph Indices

The graph maintains indices for nodes and edges, and node and edge weights may be accessed mutably. Indices range in a compact interval, for example for n nodes indices are 0 to n - 1 inclusive.

NodeIndex and EdgeIndex are types that act as references to nodes and edges, but these are only stable across certain operations. Adding nodes or edges keeps indices stable. Removing nodes or edges may shift other indices. 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 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.

Pros and Cons of Indices

  • The fact that the node and edge indices in the graph each are numbered in compact intervals (from 0 to n - 1 for n nodes) simplifies some graph algorithms.

  • You can select graph index integer type after the size of the graph. A smaller size may have better performance.

  • Using indices allows mutation while traversing the graph, see Dfs, and .neighbors(a).detach().

  • You can create several graphs using the equal node indices but with differing weights or differing edges.

  • The Graph is a regular rust collection and is Send and Sync (as long as associated data N and E are).

  • Some indices shift during node or edge removal, so that is a drawback of removing elements. Indices don't allow as much compile time checking as references.

Methods

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

Create a new Graph with directed edges.

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

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

Create a new Graph with undirected edges.

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

impl<N, E, Ty, Ix> Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

Create a new Graph with estimated capacity.

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

Computes in O(1) time.

Return the number of edges in the graph.

Computes in O(1) time.

Whether the graph has directed edges or not.

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

Access the weight for node a.

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

Access the weight for node a, mutably.

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

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.

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 don't exist.

Access the weight for edge e.

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

Access the weight for edge e, mutably.

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

Access the source and target nodes for e.

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.

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.

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.

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.

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.

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

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: All edges connected to a.

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

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

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

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.

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.

Return an iterator over the node indices of the graph

Return an iterator yielding mutable access to all node weights.

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

Return an iterator over the edge indices of the graph

Create an iterator over all edges, in indexed order.

Iterator element type is EdgeReference<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.

Access the internal node array.

Access the internal edge array.

Convert the graph into a vector of Nodes and a vector of Edges

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

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

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

Reverse the direction of all edges

Remove all nodes and edges

Remove all edges

Return the current node and edge capacity of the graph.

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.

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.

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.

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.

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

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

Shrinks the capacity of the graph as much as possible.

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.

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.

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

use petgraph::Graph;

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

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.

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.

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.

Convert the graph into either undirected or directed. No edge adjustments are done, so you may want to go over the result to remove or add edges.

Computes in O(1) time.

Trait Implementations

impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

Return an iterator of the neighbors of node a.

impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

impl<N, E, Ty, Ix> NodeCount for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

impl<N, E, Ty, Ix> GraphProp for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

The kind edges in the graph.

impl<'a, N: 'a, E: 'a, Ty, Ix> IntoEdgeReferences for &'a Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

impl<N, E, Ty, Ix> NodeIndexable for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

Return an upper bound of the node indices in the graph (suitable for the size of a bitmap). Read more

Convert a to an integer index.

Convert i to a node index

impl<N, E, Ty, Ix> NodeCompactIndexable for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

impl<N, E, Ty, Ix> GraphBase for Graph<N, E, Ty, Ix> where
    Ix: IndexType
[src]

node identifier

edge identifier

impl<N, E, Ty, Ix> Visitable for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

The associated map type

Create a new visitor map

Reset the visitor map (and resize to new size of graph if needed)

impl<N, E, Ty, Ix> Data for Graph<N, E, Ty, Ix> where
    Ix: IndexType
[src]

impl<N, E, Ty, Ix> DataMap for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

impl<N, E, Ty, Ix> DataMapMut for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

impl<N, E, Ty, Ix> Build for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

Add a new edge. If parallel edges (duplicate) are not allowed and the edge already exists, return None. Read more

Add or update the edge from a to b. Return the id of the affected edge. Read more

impl<N, E, Ty, Ix> Create for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

impl<N, E, Ty, Ix> FromElements for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

impl<N, E, Ty, Ix: IndexType> Clone for Graph<N, E, Ty, Ix> where
    N: Clone,
    E: Clone
[src]

The resulting cloned graph has the same graph indices as self.

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

impl<N, E, Ty, Ix> Debug for Graph<N, E, Ty, Ix> where
    N: Debug,
    E: Debug,
    Ty: EdgeType,
    Ix: IndexType
[src]

Formats the value using the given formatter.

impl<'a, N, E, Ty, Ix> IntoEdges for &'a Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

impl<N, E, Ty, Ix> Index<NodeIndex<Ix>> for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

Index the Graph by NodeIndex to access node weights.

Panics if the node doesn't exist.

The returned type after indexing

The method for the indexing (container[index]) operation

impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

Index the Graph by NodeIndex to access node weights.

Panics if the node doesn't exist.

The method for the mutable indexing (container[index]) operation

impl<N, E, Ty, Ix> Index<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

Index the Graph by EdgeIndex to access edge weights.

Panics if the edge doesn't exist.

The returned type after indexing

The method for the indexing (container[index]) operation

impl<N, E, Ty, Ix> IndexMut<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

Index the Graph by EdgeIndex to access edge weights.

Panics if the edge doesn't exist.

The method for the mutable indexing (container[index]) operation

impl<N, E, Ty, Ix> Default for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

Create a new empty Graph.

Returns the "default value" for a type. Read more

impl<'a, N, E, Ty, Ix> IntoNodeReferences for &'a Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

impl<N, E, Ty, Ix> GetAdjacencyMatrix for Graph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType
[src]

The adjacency matrix for Graph is a bitmap that's computed by .adjacency_matrix().

The associated adjacency matrix type

Create the adjacency matrix

Return true if there is an edge from a to b, false otherwise. Read more