Crate portgraph

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