Crate portgraph

Expand description

portgraph is a data structure library for graphs with node ports.

A port graph (as implemented by this library) consists of a collection of nodes, each equipped with an ordered sequence of input and output ports. A port can be linked to exactly one other port of the opposite direction or be left dangling.

The core data structure PortGraph implements a port graph which identifies nodes and ports via NodeIndex and PortIndex but does not attach any additional information to them. To keep track of weights the user of this library may accompany a PortGraph with a data structure which maps from indices to the weight type such as a SecondaryMap or a HashMap. This allows for more flexibility in how weights are stored and managed, for instance optimizing for cache locality or sparsity. The Weights struct offers a simple wrapper around two a SecondaryMaps to quickly encode port and node weights together.

Using the node and port indices also allows to impose additional structure to a PortGraph. This is exemplified via Hierarchy which arranges a port graph’s nodes into a forest so that it can represent a port graph in which nodes may be nested within each other.

§Example

use ::portgraph::*;
use ::portgraph::algorithms::{toposort, TopoSort};

// Create a graph with two nodes, each with two input and two output ports
let mut graph = PortGraph::new();
let node_a = graph.add_node(2, 2);
let node_b = graph.add_node(2, 2);

// Link the first output port of node A to the first input port of node B
graph.link_nodes(node_a, 0, node_b, 0).unwrap();

// Get globally unique indices for the ports, and link them directly
let port_a = graph.output(node_a, 1).unwrap();
let port_b = graph.input(node_b, 1).unwrap();
graph.link_ports(port_a, port_b).unwrap();

// Run a topological sort on the graph starting at node A.
let topo: TopoSort<_> = toposort(&graph, [node_a], Direction::Outgoing);
assert_eq!(topo.collect::<Vec<_>>(), [node_a, node_b]);

§Features

serde enables serialization and deserialization of PortGraphs and graph component structures.
pyo3 enables Python bindings.

Modules§

algorithms: Algorithm implementations for portgraphs.
boundary: Algorithms for handling port boundaries in a graph.
hierarchy: Hierarchical structure on top of a PortGraph. This is a separate relation from the graph’s adjacency.
multiportgraph: Wrapper around a portgraph providing multiports via implicit copy nodes.
portgraph: Main definition of the port graph data structure.
render: This module contains rendering logic from portgraphs into graphviz and mermaid diagrams.
secondary: Trait definition for secondary maps from keys to values with default elements.
unmanaged: A dense key-value map used to store graph weights.
view: Abstractions over portgraph representations.
weights: A graph component that encodes node and port weights. For more complex scenarios, it is recommended to use a SecondaryMap.

Structs§

Hierarchy: Hierarchical structure on top of a PortGraph.
IndexError: Error indicating a NodeIndex, PortIndex, or Direction is too large.
MultiPortGraph: An unlabelled port graph that allows multiple links to the same ports.
NodeIndex: Index of a node within a PortGraph.
PortGraph: An unlabelled port graph.
PortIndex: Index of a port within a PortGraph.
UnmanagedDenseMap: A dense map from keys to values with default fallbacks.
Weights: Graph component that encodes node and port weights. Based on two UnmanagedDenseMap containers.

Enums§

Direction: Direction of a port.
LinkError: Error generated when linking ports.
PortOffset: Port offset in a node

Traits§

LinkMut: Mutating operations pertaining the adjacency of nodes in a port graph.
LinkView: Operations pertaining the adjacency of nodes in a port graph.
MultiMut: Abstraction for mutating a portgraph that may have multiple connections per node.
MultiView: Abstraction over a portgraph that may have multiple connections per node.
PortMut: Core capabilities for mutating a graph containing nodes and ports.
PortView: Core capabilities for querying a graph containing nodes and ports.
SecondaryMap: A map from keys to values with default elements.