OpenPRA Documentation

praxis / analysis / width

Module width ​

Contents ​

Quick Reference ​

ItemKindDescription
PdagDfsMetadatastruct
WidthReportstruct
ModuleWidthReportstruct
WidthsReportstruct
WidthOptionsstruct
IncidenceGraphstruct
ModuleKindenum
compute_dfs_metadata_pdagfn
maximal_modulesfn
build_incidence_graph_fullfn
build_incidence_graph_skeletonfn
min_fill_treewidthfn
greedy_vertex_separation_pathwidthfn
compute_widthsfn

Structs ​

PdagDfsMetadata ​

rust
struct PdagDfsMetadata {
    pub variable_order: Vec<crate::algorithms::pdag::NodeIndex>,
    pub var_of: std::collections::HashMap<crate::algorithms::pdag::NodeIndex, usize>,
    pub module_gates: std::collections::HashSet<crate::algorithms::pdag::NodeIndex>,
    pub gate_min_time: std::collections::HashMap<crate::algorithms::pdag::NodeIndex, usize>,
    pub gate_max_time: std::collections::HashMap<crate::algorithms::pdag::NodeIndex, usize>,
}

Trait Implementations ​

impl<ST> CastableFrom for PdagDfsMetadata ​
impl Clone for PdagDfsMetadata ​
  • <span id="pdagdfsmetadata-clone"></span>fn clone(&self) -> PdagDfsMetadata — PdagDfsMetadata
impl Debug for PdagDfsMetadata ​
  • <span id="pdagdfsmetadata-debug-fmt"></span>fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
impl Instrument for PdagDfsMetadata ​
impl IntoEither for PdagDfsMetadata ​
impl Pointable for PdagDfsMetadata ​

  • <span id="pdagdfsmetadata-pointable-const-align"></span>const ALIGN: usize

  • <span id="pdagdfsmetadata-pointable-type-init"></span>type Init = T

  • <span id="pdagdfsmetadata-pointable-init"></span>unsafe fn init(init: <T as Pointable>::Init) -> usize

  • <span id="pdagdfsmetadata-pointable-deref"></span>unsafe fn deref<'a>(ptr: usize) -> &'a T

  • <span id="pdagdfsmetadata-pointable-deref-mut"></span>unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

  • <span id="pdagdfsmetadata-pointable-drop"></span>unsafe fn drop(ptr: usize)

impl Read for PdagDfsMetadata ​
impl Same for PdagDfsMetadata ​
  • <span id="pdagdfsmetadata-same-type-output"></span>type Output = T
impl<SS> SupersetOf for PdagDfsMetadata ​

  • <span id="pdagdfsmetadata-supersetof-to-subset"></span>fn to_subset(&self) -> Option<SS>

  • <span id="pdagdfsmetadata-supersetof-is-in-subset"></span>fn is_in_subset(&self) -> bool

  • <span id="pdagdfsmetadata-supersetof-to-subset-unchecked"></span>fn to_subset_unchecked(&self) -> SS

  • <span id="pdagdfsmetadata-supersetof-from-subset"></span>fn from_subset(element: &SS) -> SP

impl<V> VZip for PdagDfsMetadata ​
  • <span id="pdagdfsmetadata-vzip"></span>fn vzip(self) -> V
impl WithSubscriber for PdagDfsMetadata ​

WidthReport ​

rust
struct WidthReport {
    pub upper_bound: usize,
    pub compute_time_ms: u128,
}

Trait Implementations ​

impl<ST> CastableFrom for WidthReport ​
impl Clone for WidthReport ​
  • <span id="widthreport-clone"></span>fn clone(&self) -> WidthReport — WidthReport
impl Debug for WidthReport ​
  • <span id="widthreport-debug-fmt"></span>fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
impl Deserialize for WidthReport ​
  • <span id="widthreport-deserialize"></span>fn deserialize<__D>(__deserializer: __D) -> _serde::__private229::Result<Self, <__D as >::Error>
impl DeserializeOwned for WidthReport ​
impl Instrument for WidthReport ​
impl IntoEither for WidthReport ​
impl Pointable for WidthReport ​

  • <span id="widthreport-pointable-const-align"></span>const ALIGN: usize

  • <span id="widthreport-pointable-type-init"></span>type Init = T

  • <span id="widthreport-pointable-init"></span>unsafe fn init(init: <T as Pointable>::Init) -> usize

  • <span id="widthreport-pointable-deref"></span>unsafe fn deref<'a>(ptr: usize) -> &'a T

  • <span id="widthreport-pointable-deref-mut"></span>unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

  • <span id="widthreport-pointable-drop"></span>unsafe fn drop(ptr: usize)

impl Read for WidthReport ​
impl Same for WidthReport ​
  • <span id="widthreport-same-type-output"></span>type Output = T
impl Serialize for WidthReport ​
  • <span id="widthreport-serialize"></span>fn serialize<__S>(&self, __serializer: __S) -> _serde::__private229::Result<<__S as >::Ok, <__S as >::Error>
impl<SS> SupersetOf for WidthReport ​

  • <span id="widthreport-supersetof-to-subset"></span>fn to_subset(&self) -> Option<SS>

  • <span id="widthreport-supersetof-is-in-subset"></span>fn is_in_subset(&self) -> bool

  • <span id="widthreport-supersetof-to-subset-unchecked"></span>fn to_subset_unchecked(&self) -> SS

  • <span id="widthreport-supersetof-from-subset"></span>fn from_subset(element: &SS) -> SP

impl<V> VZip for WidthReport ​
  • <span id="widthreport-vzip"></span>fn vzip(self) -> V
impl WithSubscriber for WidthReport ​

ModuleWidthReport ​

rust
struct ModuleWidthReport {
    pub root_gate_idx: crate::algorithms::pdag::NodeIndex,
    pub root_gate_id: Option<String>,
    pub kind: ModuleKind,
    pub num_vertices: usize,
    pub num_edges: usize,
    pub treewidth: Option<WidthReport>,
    pub pathwidth: Option<WidthReport>,
}

Trait Implementations ​

impl<ST> CastableFrom for ModuleWidthReport ​
impl Clone for ModuleWidthReport ​
  • <span id="modulewidthreport-clone"></span>fn clone(&self) -> ModuleWidthReport — ModuleWidthReport
impl Debug for ModuleWidthReport ​
  • <span id="modulewidthreport-debug-fmt"></span>fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
impl Deserialize for ModuleWidthReport ​
  • <span id="modulewidthreport-deserialize"></span>fn deserialize<__D>(__deserializer: __D) -> _serde::__private229::Result<Self, <__D as >::Error>
impl DeserializeOwned for ModuleWidthReport ​
impl Instrument for ModuleWidthReport ​
impl IntoEither for ModuleWidthReport ​
impl Pointable for ModuleWidthReport ​

  • <span id="modulewidthreport-pointable-const-align"></span>const ALIGN: usize

  • <span id="modulewidthreport-pointable-type-init"></span>type Init = T

  • <span id="modulewidthreport-pointable-init"></span>unsafe fn init(init: <T as Pointable>::Init) -> usize

  • <span id="modulewidthreport-pointable-deref"></span>unsafe fn deref<'a>(ptr: usize) -> &'a T

  • <span id="modulewidthreport-pointable-deref-mut"></span>unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

  • <span id="modulewidthreport-pointable-drop"></span>unsafe fn drop(ptr: usize)

impl Read for ModuleWidthReport ​
impl Same for ModuleWidthReport ​
  • <span id="modulewidthreport-same-type-output"></span>type Output = T
impl Serialize for ModuleWidthReport ​
  • <span id="modulewidthreport-serialize"></span>fn serialize<__S>(&self, __serializer: __S) -> _serde::__private229::Result<<__S as >::Ok, <__S as >::Error>
impl<SS> SupersetOf for ModuleWidthReport ​

  • <span id="modulewidthreport-supersetof-to-subset"></span>fn to_subset(&self) -> Option<SS>

  • <span id="modulewidthreport-supersetof-is-in-subset"></span>fn is_in_subset(&self) -> bool

  • <span id="modulewidthreport-supersetof-to-subset-unchecked"></span>fn to_subset_unchecked(&self) -> SS

  • <span id="modulewidthreport-supersetof-from-subset"></span>fn from_subset(element: &SS) -> SP

impl<V> VZip for ModuleWidthReport ​
  • <span id="modulewidthreport-vzip"></span>fn vzip(self) -> V
impl WithSubscriber for ModuleWidthReport ​

WidthsReport ​

rust
struct WidthsReport {
    pub coherent: bool,
    pub num_basic_events: usize,
    pub num_gates: usize,
    pub num_modules: usize,
    pub max_treewidth: Option<usize>,
    pub max_pathwidth: Option<usize>,
    pub treewidth_total_time_ms: u128,
    pub pathwidth_total_time_ms: u128,
    pub modules: Vec<ModuleWidthReport>,
}

Trait Implementations ​

impl<ST> CastableFrom for WidthsReport ​
impl Clone for WidthsReport ​
  • <span id="widthsreport-clone"></span>fn clone(&self) -> WidthsReport — WidthsReport
impl Debug for WidthsReport ​
  • <span id="widthsreport-debug-fmt"></span>fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
impl Deserialize for WidthsReport ​
  • <span id="widthsreport-deserialize"></span>fn deserialize<__D>(__deserializer: __D) -> _serde::__private229::Result<Self, <__D as >::Error>
impl DeserializeOwned for WidthsReport ​
impl Instrument for WidthsReport ​
impl IntoEither for WidthsReport ​
impl Pointable for WidthsReport ​

  • <span id="widthsreport-pointable-const-align"></span>const ALIGN: usize

  • <span id="widthsreport-pointable-type-init"></span>type Init = T

  • <span id="widthsreport-pointable-init"></span>unsafe fn init(init: <T as Pointable>::Init) -> usize

  • <span id="widthsreport-pointable-deref"></span>unsafe fn deref<'a>(ptr: usize) -> &'a T

  • <span id="widthsreport-pointable-deref-mut"></span>unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

  • <span id="widthsreport-pointable-drop"></span>unsafe fn drop(ptr: usize)

impl Read for WidthsReport ​
impl Same for WidthsReport ​
  • <span id="widthsreport-same-type-output"></span>type Output = T
impl Serialize for WidthsReport ​
  • <span id="widthsreport-serialize"></span>fn serialize<__S>(&self, __serializer: __S) -> _serde::__private229::Result<<__S as >::Ok, <__S as >::Error>
impl<SS> SupersetOf for WidthsReport ​

  • <span id="widthsreport-supersetof-to-subset"></span>fn to_subset(&self) -> Option<SS>

  • <span id="widthsreport-supersetof-is-in-subset"></span>fn is_in_subset(&self) -> bool

  • <span id="widthsreport-supersetof-to-subset-unchecked"></span>fn to_subset_unchecked(&self) -> SS

  • <span id="widthsreport-supersetof-from-subset"></span>fn from_subset(element: &SS) -> SP

impl<V> VZip for WidthsReport ​
  • <span id="widthsreport-vzip"></span>fn vzip(self) -> V
impl WithSubscriber for WidthsReport ​

WidthOptions ​

rust
struct WidthOptions {
    pub compute_treewidth: bool,
    pub compute_pathwidth: bool,
}

Trait Implementations ​

impl<ST> CastableFrom for WidthOptions ​
impl Clone for WidthOptions ​
  • <span id="widthoptions-clone"></span>fn clone(&self) -> WidthOptions — WidthOptions
impl Copy for WidthOptions ​
impl Debug for WidthOptions ​
  • <span id="widthoptions-debug-fmt"></span>fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
impl Instrument for WidthOptions ​
impl IntoEither for WidthOptions ​
impl Pointable for WidthOptions ​

  • <span id="widthoptions-pointable-const-align"></span>const ALIGN: usize

  • <span id="widthoptions-pointable-type-init"></span>type Init = T

  • <span id="widthoptions-pointable-init"></span>unsafe fn init(init: <T as Pointable>::Init) -> usize

  • <span id="widthoptions-pointable-deref"></span>unsafe fn deref<'a>(ptr: usize) -> &'a T

  • <span id="widthoptions-pointable-deref-mut"></span>unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

  • <span id="widthoptions-pointable-drop"></span>unsafe fn drop(ptr: usize)

impl Read for WidthOptions ​
impl Same for WidthOptions ​
  • <span id="widthoptions-same-type-output"></span>type Output = T
impl<SS> SupersetOf for WidthOptions ​

  • <span id="widthoptions-supersetof-to-subset"></span>fn to_subset(&self) -> Option<SS>

  • <span id="widthoptions-supersetof-is-in-subset"></span>fn is_in_subset(&self) -> bool

  • <span id="widthoptions-supersetof-to-subset-unchecked"></span>fn to_subset_unchecked(&self) -> SS

  • <span id="widthoptions-supersetof-from-subset"></span>fn from_subset(element: &SS) -> SP

impl<V> VZip for WidthOptions ​
  • <span id="widthoptions-vzip"></span>fn vzip(self) -> V
impl WithSubscriber for WidthOptions ​

IncidenceGraph ​

rust
struct IncidenceGraph {
    // [REDACTED: Private Fields]
}

Implementations ​

  • <span id="incidencegraph-new"></span>fn new() -> Self

  • <span id="incidencegraph-add-vertex"></span>fn add_vertex(&mut self, v: NodeIndex) — NodeIndex

  • <span id="incidencegraph-add-edge"></span>fn add_edge(&mut self, u: NodeIndex, v: NodeIndex) — NodeIndex

  • <span id="incidencegraph-num-vertices"></span>fn num_vertices(&self) -> usize

  • <span id="incidencegraph-num-edges"></span>fn num_edges(&self) -> usize

  • <span id="incidencegraph-vertices"></span>fn vertices(&self) -> impl Iterator<Item = NodeIndex> + '_ — NodeIndex

  • <span id="incidencegraph-neighbors"></span>fn neighbors(&self, v: NodeIndex) -> Option<&BTreeSet<NodeIndex>> — NodeIndex

Trait Implementations ​

impl<ST> CastableFrom for IncidenceGraph ​
impl Clone for IncidenceGraph ​
  • <span id="incidencegraph-clone"></span>fn clone(&self) -> IncidenceGraph — IncidenceGraph
impl Debug for IncidenceGraph ​
  • <span id="incidencegraph-debug-fmt"></span>fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
impl Default for IncidenceGraph ​
  • <span id="incidencegraph-default"></span>fn default() -> Self
impl Instrument for IncidenceGraph ​
impl IntoEither for IncidenceGraph ​
impl Pointable for IncidenceGraph ​

  • <span id="incidencegraph-pointable-const-align"></span>const ALIGN: usize

  • <span id="incidencegraph-pointable-type-init"></span>type Init = T

  • <span id="incidencegraph-pointable-init"></span>unsafe fn init(init: <T as Pointable>::Init) -> usize

  • <span id="incidencegraph-pointable-deref"></span>unsafe fn deref<'a>(ptr: usize) -> &'a T

  • <span id="incidencegraph-pointable-deref-mut"></span>unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

  • <span id="incidencegraph-pointable-drop"></span>unsafe fn drop(ptr: usize)

impl Read for IncidenceGraph ​
impl Same for IncidenceGraph ​
  • <span id="incidencegraph-same-type-output"></span>type Output = T
impl<SS> SupersetOf for IncidenceGraph ​

  • <span id="incidencegraph-supersetof-to-subset"></span>fn to_subset(&self) -> Option<SS>

  • <span id="incidencegraph-supersetof-is-in-subset"></span>fn is_in_subset(&self) -> bool

  • <span id="incidencegraph-supersetof-to-subset-unchecked"></span>fn to_subset_unchecked(&self) -> SS

  • <span id="incidencegraph-supersetof-from-subset"></span>fn from_subset(element: &SS) -> SP

impl<V> VZip for IncidenceGraph ​
  • <span id="incidencegraph-vzip"></span>fn vzip(self) -> V
impl WithSubscriber for IncidenceGraph ​

Enums ​

ModuleKind ​

rust
enum ModuleKind {
    Skeleton,
    Module,
}

Trait Implementations ​

impl<ST> CastableFrom for ModuleKind ​
impl Clone for ModuleKind ​
  • <span id="modulekind-clone"></span>fn clone(&self) -> ModuleKind — ModuleKind
impl Copy for ModuleKind ​
impl Debug for ModuleKind ​
  • <span id="modulekind-debug-fmt"></span>fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
impl Deserialize for ModuleKind ​
  • <span id="modulekind-deserialize"></span>fn deserialize<__D>(__deserializer: __D) -> _serde::__private229::Result<Self, <__D as >::Error>
impl DeserializeOwned for ModuleKind ​
impl Eq for ModuleKind ​
impl Instrument for ModuleKind ​
impl IntoEither for ModuleKind ​
impl PartialEq for ModuleKind ​
  • <span id="modulekind-partialeq-eq"></span>fn eq(&self, other: &ModuleKind) -> bool — ModuleKind
impl Pointable for ModuleKind ​

  • <span id="modulekind-pointable-const-align"></span>const ALIGN: usize

  • <span id="modulekind-pointable-type-init"></span>type Init = T

  • <span id="modulekind-pointable-init"></span>unsafe fn init(init: <T as Pointable>::Init) -> usize

  • <span id="modulekind-pointable-deref"></span>unsafe fn deref<'a>(ptr: usize) -> &'a T

  • <span id="modulekind-pointable-deref-mut"></span>unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

  • <span id="modulekind-pointable-drop"></span>unsafe fn drop(ptr: usize)

impl Read for ModuleKind ​
impl Same for ModuleKind ​
  • <span id="modulekind-same-type-output"></span>type Output = T
impl Scalar for ModuleKind ​
impl Serialize for ModuleKind ​
  • <span id="modulekind-serialize"></span>fn serialize<__S>(&self, __serializer: __S) -> _serde::__private229::Result<<__S as >::Ok, <__S as >::Error>
impl StructuralPartialEq for ModuleKind ​
impl<SS> SupersetOf for ModuleKind ​

  • <span id="modulekind-supersetof-to-subset"></span>fn to_subset(&self) -> Option<SS>

  • <span id="modulekind-supersetof-is-in-subset"></span>fn is_in_subset(&self) -> bool

  • <span id="modulekind-supersetof-to-subset-unchecked"></span>fn to_subset_unchecked(&self) -> SS

  • <span id="modulekind-supersetof-from-subset"></span>fn from_subset(element: &SS) -> SP

impl<V> VZip for ModuleKind ​
  • <span id="modulekind-vzip"></span>fn vzip(self) -> V
impl WithSubscriber for ModuleKind ​

Functions ​

compute_dfs_metadata_pdag ​

rust
fn compute_dfs_metadata_pdag(pdag: &crate::algorithms::pdag::Pdag) -> crate::error::Result<PdagDfsMetadata>

maximal_modules ​

rust
fn maximal_modules(meta: &PdagDfsMetadata) -> Vec<crate::algorithms::pdag::NodeIndex>

build_incidence_graph_full ​

rust
fn build_incidence_graph_full(pdag: &crate::algorithms::pdag::Pdag, root: crate::algorithms::pdag::NodeIndex) -> IncidenceGraph

build_incidence_graph_skeleton ​

rust
fn build_incidence_graph_skeleton(pdag: &crate::algorithms::pdag::Pdag, root: crate::algorithms::pdag::NodeIndex, leaves: &std::collections::HashSet<crate::algorithms::pdag::NodeIndex>) -> IncidenceGraph

min_fill_treewidth ​

rust
fn min_fill_treewidth(graph: &IncidenceGraph) -> WidthReport

greedy_vertex_separation_pathwidth ​

rust
fn greedy_vertex_separation_pathwidth(graph: &IncidenceGraph) -> WidthReport

compute_widths ​

rust
fn compute_widths(pdag: &crate::algorithms::pdag::Pdag, options: WidthOptions) -> crate::error::Result<WidthsReport>