Struct ChainGraggle

pub struct ChainGraggle { /* private fields */ }

A version of a Graggle that has been decomposed into “chains” (for example, for prettier rendering).

Most graggles that you’ll see in practice don’t look like general directed graphs. Rather, they contain lots of long “chains,” i.e., sequences of nodes, each of which has exactly one in-neighbor (the previous in the sequence) and one out-neighbor (the next). For example, a totally ordered graggle (a.k.a. a file) just consists of one long chain.

This struct represents the same graph as a graggle, except that every chain has been “collapsed” into a single node. That is, you can think of a ChainGraggle as a graph in which every node represents a chain (possibly of length 1) in the original graph.

Implementations

impl ChainGraggle

pub fn num_chains(&self) -> usize

How many chains are there?

pub fn chain(&self, i: usize) -> &[NodeId]

Returns the sequence of NodeIds making up the chain at index i.

pub fn clusters(&self) -> impl Iterator<Item = &HashSet<usize>>

Returns an iterator over strongly connected components of the original graph.

pub fn from_graph<G: Graph<Node = NodeId>>(g: G) -> ChainGraggle

where G::Edge: Edge<NodeId>,

Given a graph, decompose it into a ChainGraggle.

Trait Implementations

impl Clone for ChainGraggle

fn clone(&self) -> ChainGraggle

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for ChainGraggle

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for ChainGraggle

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Graph for ChainGraggle

In this implementation of graph::Graph, the nodes are (semantically) chains in the original graggle. More precisely, they are usizes that you can use to get the chain with ChainGraggle::chain.

type Node = usize

type Edge = usize

fn nodes(&self) -> Box<dyn Iterator<Item = usize> + '_>

fn out_edges(&self, u: &usize) -> Box<dyn Iterator<Item = usize> + '_>

fn in_edges(&self, _u: &usize) -> Box<dyn Iterator<Item = usize> + '_>

fn out_neighbors<'a>( &'a self, u: &Self::Node, ) -> Map<Box<dyn Iterator<Item = Self::Edge> + 'a>, fn(Self::Edge) -> Self::Node>

fn in_neighbors<'a>( &'a self, u: &Self::Node, ) -> Map<Box<dyn Iterator<Item = Self::Edge> + 'a>, fn(Self::Edge) -> Self::Node>

fn dfs<'a>(&'a self) -> Dfs<'a, Self>

fn dfs_from<'a>(&'a self, root: &Self::Node) -> Dfs<'a, Self>

fn has_path(&self, u: &Self::Node, v: &Self::Node) -> bool

fn tarjan(&self) -> Partition<Self>

fn weak_components(&self) -> Partition<Self>

fn doubled<'a>(&'a self) -> Doubled<'a, Self>

Returns the graph that has edges in both directions for every edge that this graph has in one direction.

fn node_filtered<'a, F>(&'a self, predicate: F) -> NodeFiltered<'a, Self, F>

where F: Fn(&Self::Node) -> bool,

Returns the subgraph of this graph that is induced by the set of nodes for which predicate returns true.

fn edge_filtered<'a, F>(&'a self, predicate: F) -> EdgeFiltered<'a, Self, F>

where F: Fn(&Self::Node, &Self::Edge) -> bool,

Returns the subgraph of this graph containing all the edges for which the predicate returns true.

fn top_sort<'a>(&'a self) -> Option<Vec<Self::Node>>

If this graph is acyclic, returns a topological sort of the vertices. Otherwise, returns None.

fn linear_order<'a>(&'a self) -> Option<Vec<Self::Node>>

fn neighbor_set<'a, I>(&self, set: I) -> HashSet<Self::Node>

where I: Iterator<Item = &'a Self::Node>, Self::Node: 'a,

Returns the set of all nodes that are adjacent (either an in-neighbor or an out-neighbor) to something in set.

impl Serialize for ChainGraggle

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.