Struct Topology 

pub struct Topology<R = Direct> { /* private fields */ }

Topology.

This data type represents the topology of a graph, which allows to find the outgoing and incoming edges for each node in linear time by using efficient adjacency lists. Our implementation does not support edge weights, as they would add unnecessary complexity and overhead.

Topologies can be Direct and Transitive, the latter of which allows to determine whether one node is reachable from another. The Direct topology is the default, and can be converted on-demand.

Implementations

impl Topology<Direct>

pub fn new(nodes: usize, edges: &[Edge]) -> Self

Creates a topology of the given graph.

This method constructs a topology from a graph’s nodes and edges, and is the key component of an executable Graph. It’s usually not needed to create a topology manually, as it’s automatically created when the graph is built using the Builder::build method.

Examples

use zrx_graph::{Graph, Topology};

// Create graph builder and add nodes
let mut builder = Graph::builder();
let a = builder.add_node("a");
let b = builder.add_node("b");
let c = builder.add_node("c");

// Create edges between nodes
builder.add_edge(a, b)?;
builder.add_edge(b, c)?;

// Create topology
let topology = Topology::new(builder.len(), builder.edges());

pub fn into_transitive(self) -> Topology<Transitive>

Converts this topology into one with transitive reachability.

Examples

use zrx_graph::{Graph, Topology};

// Create graph builder and add nodes
let mut builder = Graph::builder();
let a = builder.add_node("a");
let b = builder.add_node("b");
let c = builder.add_node("c");

// Create edges between nodes
builder.add_edge(a, b)?;
builder.add_edge(b, c)?;

// Create transitive topology
let topology = Topology::new(builder.len(), builder.edges())
    .into_transitive();

impl Topology<Transitive>

pub fn has_path(&self, source: usize, target: usize) -> bool

Returns whether there is a path from the source to the target.

impl<R> Topology<R>

pub fn outgoing(&self) -> &Adjacency

Returns a reference to the outgoing edges.

pub fn incoming(&self) -> &Adjacency

Returns a reference to the incoming edges.

Trait Implementations

impl<R> Clone for Topology<R>

fn clone(&self) -> Self

Clones the topology.

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

Performs copy-assignment from source.

impl<R: Debug> Debug for Topology<R>

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

Formats the value using the given formatter.

impl<R> Eq for Topology<R>

impl<R> PartialEq for Topology<R>

fn eq(&self, other: &Self) -> bool

Compares two topologies for equality.

Examples

use zrx_graph::{Graph, Topology};

// Create graph builder and add nodes
let mut builder = Graph::builder();
let a = builder.add_node("a");
let b = builder.add_node("b");
let c = builder.add_node("c");

// Create edges between nodes
builder.add_edge(a, b)?;
builder.add_edge(b, c)?;

// Create and compare topologies
let topology = Topology::new(builder.len(), builder.edges());
assert_eq!(topology, topology.clone());

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.