ddnnife 0.10.0

d-DNNF toolkit
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

use crate::{Ddnnf, NodeType};
use serde::Serialize;

/// Various statistics about a d-DNNF.
#[derive(Clone, Copy, Debug, PartialEq, Serialize)]
pub struct Statistics {
    /// The amount of nodes in the d-DNNF per node type.
    pub nodes: NodeCount,
    /// The amount of child connections in a d-DNNF.
    pub child_connections: ChildConnections,
    /// Path length information.
    pub paths: Paths,
}

impl From<&Ddnnf> for Statistics {
    fn from(ddnnf: &Ddnnf) -> Self {
        Self {
            nodes: NodeCount::from(ddnnf),
            child_connections: ChildConnections::from(ddnnf),
            paths: Paths::from(ddnnf),
        }
    }
}

impl Ddnnf {
    /// Generates various statistics about this d-DNNF.
    pub fn statistics(&self) -> Statistics {
        Statistics::from(self)
    }
}

/// The amount of nodes in a d-DNNF per node type.
#[derive(Default, Clone, Copy, Debug, PartialEq, Eq, Serialize)]
pub struct NodeCount {
    pub total: usize,
    pub and: usize,
    pub or: usize,
    pub literal: usize,
    pub r#true: usize,
    pub r#false: usize,
}

impl From<&Ddnnf> for NodeCount {
    fn from(ddnnf: &Ddnnf) -> Self {
        let mut counts = Self {
            total: ddnnf.nodes.len(),
            ..Default::default()
        };

        ddnnf.nodes.iter().for_each(|node| match node.ntype {
            NodeType::And { .. } => counts.and += 1,
            NodeType::Or { .. } => counts.or += 1,
            NodeType::Literal { .. } => counts.literal += 1,
            NodeType::True => counts.r#true += 1,
            NodeType::False => counts.r#false += 1,
        });

        counts
    }
}

/// The amount of child connections in a d-DNNF.
#[derive(Default, Clone, Copy, Debug, PartialEq, Eq, Serialize)]
pub struct ChildConnections {
    /// The total amount of child connection.
    pub total: usize,
    /// The number of child connections from AND nodes.
    pub and: usize,
    /// The number of child connections from OR nodes.
    pub or: usize,
}

impl From<&Ddnnf> for ChildConnections {
    fn from(ddnnf: &Ddnnf) -> Self {
        let mut connections = Self::default();

        ddnnf.nodes.iter().for_each(|node| match &node.ntype {
            NodeType::And { children } => connections.and += children.len(),
            NodeType::Or { children } => connections.or += children.len(),
            _ => {}
        });

        connections.total = connections.and + connections.or;

        connections
    }
}

/// Path length information about a d-DNNF.
#[derive(Default, Clone, Copy, Debug, PartialEq, Serialize)]
pub struct Paths {
    /// The total amount of paths.
    pub amount: usize,
    /// The length of the shortest path.
    pub shortest: usize,
    /// The length of the longest path.
    pub longest: usize,
    /// The mean path length.
    pub mean: f64,
    /// The standard deviation of the path lengths.
    pub deviation: f64,
}

impl From<&Ddnnf> for Paths {
    fn from(ddnnf: &Ddnnf) -> Self {
        let depths = calculate_depths(ddnnf, ddnnf.nodes.len() - 1, 0);

        let amount = depths.len();
        let &shortest = depths.iter().min().unwrap();
        let &longest = depths.iter().max().unwrap();
        let mean = depths.iter().sum::<usize>() as f64 / amount as f64;

        let variance: f64 = depths
            .iter()
            .map(|&depth| (depth as f64 - mean).powi(2))
            .sum();
        let deviation = (variance / amount as f64).sqrt();

        Self {
            amount,
            shortest,
            longest,
            mean,
            deviation,
        }
    }
}

/// Calculates the depths of all possible paths starting from the given node.
fn calculate_depths(ddnnf: &Ddnnf, index: usize, current_depth: usize) -> Vec<usize> {
    match &ddnnf.nodes[index].ntype {
        NodeType::And { children } | NodeType::Or { children } => children
            .iter()
            .flat_map(|&child| calculate_depths(ddnnf, child, current_depth + 1))
            .collect(),
        _ => vec![current_depth],
    }
}