portgraph 0.16.1

Data structure library for directed graphs with first-level ports.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

#![warn(missing_docs)]
//! `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 [`SecondaryMap`]s 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.
//!
//! [`HashMap`]: std::collections::HashMap
//!
//! # Example
//!
//! ```
//! use ::portgraph::*;
//! use ::portgraph::algorithms::{toposort, TopoSort};
//!
//! type PortGraph = ::portgraph::PortGraph<u32, u32, u16>;
//!
//! // Create a graph with two nodes, each with two input and two output ports
//! let mut graph: PortGraph = 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 `PortGraph`s and
//!   graph component structures.
//! - `pyo3` enables Python bindings.
//!

pub mod algorithms;
pub mod boundary;
pub mod hierarchy;
pub mod index;
pub mod multiportgraph;
pub mod portgraph;
pub mod render;
pub mod secondary;
pub mod unmanaged;
pub mod view;
pub mod weights;

#[cfg(feature = "proptest")]
pub mod proptest;

#[doc(inline)]
pub use crate::hierarchy::Hierarchy;
#[doc(inline)]
pub use crate::index::{IndexError, NodeIndex, PortIndex, PortOffset};
#[doc(inline)]
pub use crate::multiportgraph::MultiPortGraph;
#[doc(inline)]
pub use crate::portgraph::{LinkError, PortGraph};
#[doc(inline)]
pub use crate::secondary::SecondaryMap;
#[doc(inline)]
pub use crate::unmanaged::UnmanagedDenseMap;
#[doc(inline)]
pub use crate::view::{LinkMut, LinkView, MultiMut, MultiView, PortMut, PortView};
#[doc(inline)]
pub use crate::weights::Weights;

/// Direction enum and related impls.
#[allow(deprecated)] // pyclass requires a `from_py_object` method on `pyo3` 0.28+
mod direction {
    use super::IndexError;

    #[cfg(feature = "pyo3")]
    use pyo3::prelude::*;

    #[cfg(feature = "serde")]
    use serde::{Deserialize, Serialize};

    /// Direction of a port.
    #[cfg_attr(feature = "pyo3", pyclass(eq, eq_int))]
    #[derive(Clone, Copy, Debug, PartialEq, PartialOrd, Eq, Ord, Hash, Default)]
    #[cfg_attr(feature = "serde", derive(Deserialize, Serialize))]
    pub enum Direction {
        /// Input to a node.
        #[default]
        Incoming = 0,
        /// Output from a node.
        Outgoing = 1,
    }

    impl Direction {
        /// Incoming and outgoing directions.
        pub const BOTH: [Direction; 2] = [Direction::Incoming, Direction::Outgoing];

        /// Returns the opposite direction.
        #[inline(always)]
        pub fn reverse(self) -> Direction {
            match self {
                Direction::Incoming => Direction::Outgoing,
                Direction::Outgoing => Direction::Incoming,
            }
        }
    }

    impl From<Direction> for usize {
        #[inline(always)]
        fn from(dir: Direction) -> Self {
            dir as usize
        }
    }

    impl TryFrom<usize> for Direction {
        type Error = IndexError;

        #[inline(always)]
        fn try_from(dir: usize) -> Result<Self, Self::Error> {
            match dir {
                0 => Ok(Direction::Incoming),
                1 => Ok(Direction::Outgoing),
                index => Err(IndexError { index }),
            }
        }
    }
}

#[doc(inline)]
pub use direction::Direction;