Struct Subgraph 

pub struct Subgraph<G, S = ()>
where
    G: GraphBase,
{ /* private fields */ }

A subgraph of a graph as determined by the vertex and edge predicates.

The vertex or edge presence determination is done lazily. This has a performance impact on some operations that are usually very fast.

Examples

use gryf::{
    adapt::Subgraph,
    core::{facts, marker::Undirected, EdgeSet, VertexSet},
    Graph,
};

let vertices = 0..10;

let mut graph = Graph::<u32, (), Undirected>::with_capacity(
    vertices.len(),
    facts::complete_graph_edge_count::<Undirected>(vertices.len()),
);
graph.extend_with_vertices(vertices);
graph.connect_vertices(|_, _| Some(()));

assert_eq!(graph.vertex_count(), 10);
assert_eq!(graph.edge_count(), 55);

// Subgraph with only "even" vertices.
let subgraph = Subgraph::new(&graph).filter_vertex(|v, g, _| g[v] % 2 == 0);

assert_eq!(subgraph.vertex_count(), 5);
assert_eq!(subgraph.edge_count(), 15);

Implementations

impl<G> Subgraph<G>

where G: GraphBase,

pub fn new(graph: G) -> Self

Creates a new subgraph of the given graph.

Specify the subset of vertices and/or edges by filter_vertex and filter_edge, respectively. If neither is defined, the subgraph represents the full original graph.

If you need some owned additional state for determining the subsets, use the Subgraph::with_state constructor.

impl<G, S> Subgraph<G, S>

where G: GraphBase,

pub fn with_state(graph: G, state: S) -> Self

Creates a new subgraph of the given graph and a state to be used in the predicates.

Specify the subset of vertices and/or edges by filter_vertex and filter_edge, respectively. If neither is defined, the subgraph represents the full original graph.

If you don’t need any state for determining the subsets, use the Subgraph::new constructor.

pub fn into_inner(self) -> G

Returns the original graph.

pub fn filter_vertex<F>(self, predicate: F) -> Self

where F: Fn(&G::VertexId, &G, &S) -> bool + 'static,

Specifies the subset of vertices by a predicate.

The predicate takes the vertex ID, the original graph and the state that was passed in via Subgraph::with_state (if any).

If you run into “something may not live long enough” compiler error due to 'static lifetime bound on the predicate, pass the borrowed value as part of the state via Subgraph::with_state and access it through the last argument of the predicate.

pub fn filter_edge<F>(self, predicate: F) -> Self

where F: Fn(&G::EdgeId, &G, &S) -> bool + 'static,

Specifies the subset of edges by a predicate.

The predicate takes the edge ID, the original graph and the state that was passed in via Subgraph::with_state (if any).

If you run into “something may not live long enough” compiler error due to 'static lifetime bound on the predicate, pass the borrowed value as part of the state via Subgraph::with_state and access it through the last argument of the predicate.

Trait Implementations

impl<G, S> EdgeSet for Subgraph<G, S>

where G: EdgeSet,

type EdgesByIdIter<'a> = SubgraphIter<'a, <G as EdgeSet>::EdgesByIdIter<'a>, <G as GraphBase>::EdgeId> where Self: 'a

Iterator over edge IDs.

type EdgeIdIter<'a> = SubgraphIter<'a, <G as EdgeSet>::EdgeIdIter<'a>, <G as GraphBase>::EdgeId> where Self: 'a

Iterator over edge IDs between two vertices.

fn edges_by_id(&self) -> Self::EdgesByIdIter<'_>

Returns all edges in the graph.

fn edge_id( &self, from: &Self::VertexId, to: &Self::VertexId, ) -> Self::EdgeIdIter<'_>

Returns all edges between two vertices.

fn endpoints( &self, id: &Self::EdgeId, ) -> Option<(Self::VertexId, Self::VertexId)>

Returns the endpoints of the given edge, if it exists.

fn edge_bound(&self) -> usize

where Self::EdgeId: IntegerIdType,

Returns the highest edge ID currently in use.

fn contains_edge(&self, id: &Self::EdgeId) -> bool

Returns true if the graph contains the given edge.

fn edge_count(&self) -> usize

Returns the number of edges in the graph.

fn contains_edge_between( &self, from: &Self::VertexId, to: &Self::VertexId, ) -> bool

Returns true if the graph contains an edge between two vertices.

fn edge_id_any( &self, from: &Self::VertexId, to: &Self::VertexId, ) -> Option<Self::EdgeId>

Returns an edge between two vertices, if any exist.

fn edge_id_map(&self) -> CompactIdMap<Self::EdgeId>

Returns a mapping of edge IDs to virtual IDs representing a contiguous sequence.

impl<G, S> GraphBase for Subgraph<G, S>

where G: GraphBase + GraphBase,

type VertexId = <G as GraphBase>::VertexId

Vertex ID type of the graph.

type EdgeId = <G as GraphBase>::EdgeId

Edge ID type of the graph.

type EdgeType = <G as GraphBase>::EdgeType

Directionality of the graph.

fn vertex_count_hint(&self) -> Option<usize>

Returns the upper bound of the vertex count, if available.

fn edge_count_hint(&self) -> Option<usize>

Returns the upper bound of the edge count, if available.

fn is_directed(&self) -> bool

Returns true if the graph is directed.

impl<V, E, G, S> GraphRef<V, E> for Subgraph<G, S>

where G: GraphRef<V, E>,

type VertexRef<'a> = <G as GraphRef<V, E>>::VertexRef<'a> where Self: 'a, V: 'a

Reference to a vertex.

type VerticesIter<'a> = SubgraphIter<'a, <G as GraphRef<V, E>>::VerticesIter<'a>, <G as GraphRef<V, E>>::VertexRef<'a>> where Self: 'a, V: 'a

Iterator over vertices.

type EdgeRef<'a> = <G as GraphRef<V, E>>::EdgeRef<'a> where Self: 'a, E: 'a

Reference to an edge.

type EdgesIter<'a> = SubgraphIter<'a, <G as GraphRef<V, E>>::EdgesIter<'a>, <G as GraphRef<V, E>>::EdgeRef<'a>> where Self: 'a, E: 'a

Iterator over edges.

fn vertices(&self) -> Self::VerticesIter<'_>

Returns all vertices in the graph with their attributes.

fn edges(&self) -> Self::EdgesIter<'_>

Returns all edges in the graph with their attributes and endpoints.

fn vertex(&self, id: &Self::VertexId) -> Option<&V>

Returns a reference to the vertex attribute, if it exists.

fn edge(&self, id: &Self::EdgeId) -> Option<&E>

Returns a reference to the edge attribute, if it exists.

fn find_vertex(&self, vertex: &V) -> Option<Self::VertexId>

where V: Eq,

Finds a vertex by its attribute.

impl<G, S> Neighbors for Subgraph<G, S>

where G: Neighbors,

type NeighborRef<'a> = <G as Neighbors>::NeighborRef<'a> where Self: 'a

Reference to a neighbor.

type NeighborsIter<'a> = SubgraphIter<'a, <G as Neighbors>::NeighborsIter<'a>, <G as Neighbors>::NeighborRef<'a>> where Self: 'a

Iterator over neighbors of a vertex.

fn neighbors_undirected(&self, from: &G::VertexId) -> Self::NeighborsIter<'_>

Returns all neighbors of the given vertex, regardless of edge direction.

fn neighbors_directed( &self, from: &G::VertexId, dir: Direction, ) -> Self::NeighborsIter<'_>

Returns all neighbors of the given vertex in the given direction.

fn degree_undirected(&self, id: &Self::VertexId) -> usize

Returns the total degree of the given vertex.

fn degree_directed(&self, id: &Self::VertexId, dir: Direction) -> usize

Returns the out or in degree of the given vertex, depending on the edge direction argument.

impl<G, S> VertexSet for Subgraph<G, S>

where G: VertexSet,

type VerticesByIdIter<'a> = SubgraphIter<'a, <G as VertexSet>::VerticesByIdIter<'a>, <G as GraphBase>::VertexId> where Self: 'a

Iterator over vertex IDs.

fn vertices_by_id(&self) -> Self::VerticesByIdIter<'_>

Returns all vertices in the graph.

fn vertex_bound(&self) -> usize

where Self::VertexId: IntegerIdType,

Returns the highest vertex ID currently in use.

fn contains_vertex(&self, id: &Self::VertexId) -> bool

Returns true if the graph contains the given vertex.

fn vertex_count(&self) -> usize

Returns the number of vertices in the graph.

fn vertex_id_map(&self) -> CompactIdMap<Self::VertexId>

Returns a mapping of vertex IDs to virtual IDs representing a contiguous sequence.