# Module Circuit

`module Circuit: `sig` .. `end``
The Circuit module provides an interface for working with arithmetic circuits, so that learning and inference algorithms can be built on top of this data structure/inference representation.

##### Node

`type ndetails = `Node.ndetails` = `
 `|` `TimesNode` `(*` Represents products in the circuits `*)` `|` `PlusNode` `(*` Represents sums in the circuits `*)` `|` `VarNode of int * int` `(*` Indicator variable for (var,value) pair `*)` `|` `ConstNode of float` `(*` Represents parameters (log-space) `*)` `|` `NullNode` `(*` Represents dummy nodes `*)`
Different types of nodes in arithmetic circuits
`type node = `Node.node` = {`
 `  ` `hashid : int;` `(*` Unique auto-increment id `*)` `  ` `mutable id : int;` `(*` Shows the index of node in the `citcuit.nodes`. `*)` `  ` `mutable parents : node list;` `(*` List of parent nodes in the circuit graph. `*)` `  ` `mutable children : node list;` `(*` List of children nodes in the circuit graph. `*)` `  ` `mutable details : ndetails;` `(*` Type of the node. `*)`
}
Each element in an arithmetic circuit is a node (including parameters, plus, times, and indicators), which has a unique hashid. Node maintains a list of its parent and its children nodes in the circuit graph.

###### Node operations

`val null_node : `node``
Creates a node with type NullNode, and its parent and children lists are empty.
`val create_node : `ndetails -> node list -> node``
Creates a node with the given node specification and children.
`val ncopy : `node -> node``
Copy constructor.
`val create_var : `int -> int -> node``
Creates an indicator node.
`val create_const : `float -> node``
Creates a constant node (parameter node).
`val create_times : `node list -> node``
Creates a times (product) node.
`val create_plus : `node list -> node``
Creates a plus (sum) node.
`val is_times : `node -> bool``
Checks whether the node is a times (product) node.
`val is_plus : `node -> bool``
Checks whether the node is a plus (sum) node.
`val is_var : `node -> bool``
Checks whether the node is an indicator node.
`val is_const : `node -> bool``
Checks whether the node is a constant (parameter) node.
`val is_null : `node -> bool``
Checks whether the node is a null node.
`val const_value : `node -> float``
Gets the parameter value stored in the constant node
`val var_details : `node -> int * int``
`var_details node` returns the variable-value pair if `node` is an indicator variable node
`val var_var : `node -> int``
`var_var node` returns the variable if `node` is a variable node
`val var_value : `node -> int``
`var_value node` returns the value if `node` is a variable node
`val is_var_product : `node -> bool``
`is_var_product node` returns true if `node` is a product of a constant and an indicator variable.
`val is_sot_dist : `node -> bool``
`is_sot_dist node` returns true if `node` is a sum of variable products (constants times indicator variables). Nodes with this structure are used to represent marginal distributions over individual variables.
`val set_const : `node -> float -> unit``
`set_const node wt` sets the value of const node `node` to `wt`.
`val add_child : `node -> node -> unit``
`add_child parent child` appends `child` to the children of `parent` and updates the parent of `child` accordingly.
`val remove_child : `node -> node -> unit``
`remove_child parent child` removes `child` from the children of `parent` and updates `child` accordingly.
`val remove_all_children : `node -> unit``
`remove_all_children parent` removes all children of `parent`.
`val remove_all_parents : `node -> unit``
`remove_all_parents child` removes all parents of `child`.
`val unlink : `node -> unit``
`unlink node` removes all parents and children of `node`.
`val id : `node -> int``
`id node` returns the id of `node`.
`val parents : `node -> node list``
`parents node` returns the parents of `node`.
`val children : `node -> node list``
`children node` returns the children of `node`.
`val num_children : `node -> int``
`num_children node` returns the number of children of `node`.

###### Printing and debugging operations

`val node_name : `node -> string``
`node_name` returns the name of node `node`, e.g., "n5".
`val string_of_node : `node -> string``
`string_of_node node` returns a string representation of node `node`.
`val output_node : `Pervasives.out_channel -> node -> unit``
`output_node out node` writes node `node` to the output channel `out`.
`val output_root : `Pervasives.out_channel -> int array -> node -> unit``
`output_root out schema root` recursively writes circuit to output channel `out`, starting at the root.
`val print_node : `node -> unit``
Prints a single node to stdout.
`val print_node_endline : `node -> unit``
Prints a single node to stdout, including a newline at the end.

##### Arithmetic circuits

`exception Unknown_child of `string * string``
Parse error: Node references a child that has not yet been defined.
`exception NonConstantFeatureWeight of `int``
Parse error: Node used for feature weight is not a const node.
`exception UnsupportedNodeType`
Type error: Given node type is not supported by this function.

###### Auxilary types

`type evidence_t = `float array array` `
Evidence data structure that specifies value of each indicator variable.
`type schema_t = `Data.schema_t` `
Data types from Data module.
`type example_t = `Data.example_t` `

###### Circuit type

``type circuit = {``
 `  ` `schema : schema_t;` `(*` Data schema specifies the range of each variable. `*)` `  ` `vnodes : node array array;` `(*` Array of arrays of indicator nodes. `vnodes.(i).(j)` is the indicator variable node for state `j` of variable `i`. `*)` `  ` `vnodes_l : node list array;` `(*` Array of lists of indicator nodes. Redundant with vnodes, but maintained for convenience. `*)` `  ` `flat_vnodes : node array;` `(*` Array of all indictator variables. Redundant with vnodes, but maintained for convenience. `*)` `  ` `mutable nodes : node array;` `(*` All nodes in the circuit. `*)` `  ` `mutable root : node;` `(*` The circuit root node. `*)` `  ` `mutable size : int;` `(*` The number of nodes in the circuit. `*)`
}
Data structure for arithmetic circuits. Fields are mutable so that the circuit can be updated in place.

###### Circuit operations

`val load : `Pervasives.in_channel -> circuit``
Reads an arithmetic circuit from a file description.
`val output : `Pervasives.out_channel -> circuit -> unit``
Stores an arithmetic circuit in the regular plain text format.
`val output_js : `Pervasives.out_channel -> circuit -> unit``
Stores an arithmetic circuit in the javascript format for visualizing using Digraph.
`val output_dot : `Pervasives.out_channel -> circuit -> unit``
Stores an arithmetic circuit in the dot format (for visualizing).
`val print : `circuit -> unit``
Prints an arithmetic circuit to stdout.
`val schema : `circuit -> schema_t``
Returns the schema of an arithmetic circuit.
`val numvars : `circuit -> int``
Returns the number of variables in an arithmetic circuit.
`val node : `circuit -> int -> node``
Returns the node at a specific index.
`val all_var_dists : `circuit -> node list``
`all_var_dists circ` returns all plus nodes in the circuit `circ` that represent distributions.
`val dist_var : `node -> int``
`dist_var n` returns the index of the random variable being modeled given the node `n` representing a multinomial distribution.
`val all_vars : `circuit -> node array array``
Returns all indicator nodes (variable nodes).
`val sibling_vars : `circuit -> node -> node list``
`sibling_vars circ n` returns a list of all indicator nodes for all values of the same variable given the indicator node `n` for a particular variable/value combination. For example, given the indicator node for `x_5=1`, it returns indicators for `x_5=0, x_5=1, ..., x_5=k`.
`val var : `circuit -> int -> node array``
`var circ i` returns the array of indicator nodes for the given random variable index `i` and the circuit `circ`.
`val flat_vars : `circuit -> node array``
Returns a flat array of all indicator nodes for all random variables.
`val order : `circuit -> unit``
Puts all nodes in the circuit into a topological partial order.
`val make_vnodes : `schema_t -> node array array``
Creates an indicator variable for each state of every variable based on the given schema
`val rebuild : `circuit -> unit``
Rebuilds the circuit data structure from the root node. Fixes inconsistent parent/child relationships and removes orphaned nodes, leading to a compact and consistent node array.
`val of_graph : `schema_t ->       node array array ->       node list array -> node -> circuit``
`of_graph schema vn vnl root` constructs a new circuit from `schema` and `root` node and places it in topological order. `vn` is node
`val depth : `circuit -> int``
Returns the depth of an arithmetic circuit
`val update_parents : `circuit -> unit``
Update parent references for all nodes to be consistent.
`val num_edges : `circuit -> int``
Return the number of edges in an arithmetic circuit.
`val num_params : `circuit -> int``
Return the number of parameters in an arithmetic circuit.

###### Create, set evidence

`val create_evidence_s : `schema_t -> evidence_t``
`create_evidence schema` creates an matrix of ones as the values of indicator variables. Each column corresponds to a variable in the schema.
`val create_evidence : `circuit -> evidence_t``
Returns `create_evidence_s` of the `circuit.schema`.
`val ev_true : `evidence_t -> int -> int -> unit``
`val ev_false : `evidence_t -> int -> int -> unit``
`val set_evidence : `'a array -> circuit -> 'a array array -> unit``

###### Other evidence related operations

`val example_to_ev : `schema_t -> example_t -> evidence_t``
`val ev_intersect : `evidence_t -> evidence_t -> bool``
`ev_intersect e1 e2` returns `true` when evidence `e1` and `e2` are not mutually exclusive.
`val ev_subset : `evidence_t -> evidence_t -> bool``
`ev_subset e1 e2` returns `true` if evidence `e1` is subset of evidence `e2` (i.e. pr(e1|e2) = 1.0 )
`val ev_intersect2 : `evidence_t -> evidence_t -> bool``
`val ev_union : `circuit ->       evidence_t -> evidence_t -> evidence_t``
`ev_union circuit ev1 ev2` creates another evidence `e` such that `e` is the union of `ev1` and `ev2`. `ev_union` suppose that `ev1` and `ev2` are not mutualy exclusive.
`val print_ev : `evidence_t -> unit``
Print evidence data structure to stdout.

##### Arithmetic circuits for Markov networks

`type condition = `bool * int * int` `
`condition` represents a variable value combination in features. For example, `(true,5,1)` means that variable 5 has state 1, and `(false, 5, 1)` means that variable 5 does not have state 1.
``type feature = {``
 `  ` `acnode : node;` `(*` Node containing the feature weight `*)` `  ` `mutable weight : float;` `(*` The feature weight `*)` `  ` `cond : condition list;` `(*` The set of conditions that creates a feature, e.g. `+v3_1 +v4_2 +v6_0` `*)` `  ` `ev : evidence_t;`
}
Represents feature and its weight in the coresponding log-linear model of the arithmetic circuit.
`val feature_node : `feature -> node``
`feature_node f` returns the acnode related to the feature `f`.
`val feature_value : `feature -> float``
`feature_value f` returns the value of feature `f` when its condition is satisfied.
`val set_feature_value : `feature -> float -> unit``
`set_feature_value f wt` sets the value of feature `f` to `wt`, modifying the associated constant node.
`val feature_contains_var : `feature -> node -> bool``
`feature_contains_var f v` returns true if feature `f` has a condition of variable `v`.
`val prune_for_evidence : `circuit -> example_t -> unit``
Prunes a circuit conditioned on evidence. May leave the parent references for some nodes in an inconsistent state - use `update_parents` to fix.
`val c_satisfied : `example_t -> condition -> bool``
`c_satisfied x cond` returns true if `x` satisfies `cond`.
`val f_satisfied : `example_t -> feature -> bool``
`f_satisfied x f` returns true if an instance `x` satisfies all conditions of feature `f`.
`val prune_features : `feature list -> example_t -> feature list``
Prunes features by removing empty, redundant, and contradictory circuit features. Returns shortened list of simplified features.
`val conditions_to_ev : `schema_t -> condition array -> evidence_t``
Converts a condition to evidence.
`val cond_intersect : `schema_t ->       condition array -> condition array -> bool``
Returns true when two given conditions are not mutually exclusive.

`val string_of_feature : `feature -> string``
Converts the given feature to a string
`val output_feature : `Pervasives.out_channel -> feature -> unit``
`output_feature out f` writes feature `f` to the output channel `out`.
`val output_with_features : `Pervasives.out_channel -> circuit -> feature list -> unit``
Stores the given arithmetic circuit and feature list in `.ac` format.
`val output_root_with_features : `Pervasives.out_channel ->       schema_t -> node -> feature list -> unit``
Stores the given arithmetic circuit and feature list in `.ac` format, given the circuit schema, root node, and feature list.
`val output_features : `Pervasives.out_channel -> node -> feature list -> unit``
Stores the feature list given the circuit root.
`val load_with_features : `Pervasives.in_channel -> circuit * feature list``
Reads an arithmetic circuits and log-linear features from `.ac` file. Used for arithmetic circuts that represent log-linear models.

###### Circuit derivatives

``type deriv_scratch = {``
 `  ` `dr : float array;` `(*` Derivative of root with respect to each node. `*)` `  ` `vr : float array;` `(*` Log value of each node. `*)` `  ` `vr_nz : float array;` `  ` `bit1 : bool array;` `  ` `bit2 : bool array;` `  ` `cids : int array array;`
}
Data structure for computing the derivatives of circuits with respect to features.
`val create_deriv_scratch : `circuit -> deriv_scratch``
Initializes the data structure for computing the derivatives. Reusing this data structure is much more efficient than creating it for every single query.
`val get_derivatives_raw : `circuit -> deriv_scratch -> evidence_t -> unit``
Computes derivatives of an arithmetic circuit with respect to all features conditioned on evidence. Updates the deriv_scratch data structure in place.

##### Inference using arithmetic circuits

`type scratch_t = `float array * int array array` `
Helper data structure for circuit inference. Caches node values and child ids for each node. Reusing it over multiple queries is much faster than recreating it each time.
`val create_scratch : `circuit -> scratch_t``
Create helper data structure.
`val logvalues : `scratch_t -> circuit -> float array``
Maps `Circuit.circuit.nodes` to their logvalues after the evaluation of the `circuit`.
`val logprob_ev : `scratch_t -> circuit -> evidence_t -> float``
`logprob_ev scratch circ ev` returns the log probability of evidence structure `ev` in circuit `circ`. For arithmetic circuits that represent Bayesian networks the log probability is normalized, but for circuits representing Markov networks it is unnormalized. `scratch` can be constructed using `Circuit.create_scratch`.
`val logprob_x : `scratch_t -> circuit -> example_t -> float``
`logprob_x scratch circ x` returns the log probability of example `x` in circuit `circ`. For arithmetic circuits that represent Bayesian networks the log probability is normalized, but for circuits representing Markov networks it is unnormalized. `scratch` can be created using `Circuit.create_scratch`.
`val get_logmarginals : `circuit ->       deriv_scratch -> example_t -> float array array``
`get_logmarginals circ ds ev` returns the log-marginals of all variables in circuit `circ` given evidence `ev`. `ds` can be created using `Circuit.create_deriv_scratch`.
`val get_marginals : `circuit ->       deriv_scratch -> example_t -> float array array``
`get_marginals circ ds ev` return the marginals of all variables in circuit `circ` given evidence `ev`. `ds` can be created using `Circuit.create_deriv_scratch`.
`val compute_z : `scratch_t -> circuit -> float``
Returns the log partition function.
`val get_mpe : `circuit -> deriv_scratch -> example_t -> int array``
`get_mpe circ ds e` computes the MPE state of variables given the circuit `circ`, its empty derivative data structure `ds`, and the evidence `ev`.

##### Map and Set modules for Node (based on Hashtbl)

`module NSet: `sig` .. `end``
`module NMap: `sig` .. `end``
`val node_iter : `(node -> 'a) -> node -> unit``
`node_iter f root` applies function `f` to every node in the circuit rooted at `root`.
`val node_map : `(node -> 'a) -> node -> 'a list``
`node_map f root` applies function `f` to every node in the circuit rooted at `root` and creates a list of the results.
`val root_to_list : `node -> node list``
`root_to_list root` generates a list of all nodes reachable from `root`.
`val relatedl_a : `int -> (node -> node list) -> node list -> bool array``
`relatedl_a size rel nl` returns an array in which the `i`th element is true if the node with id `i` is reachable from some node in `nl` through relation `rel`. Useful for generating lists of ancestor or descendant nodes, represented as bit vectors.
`val a_mem : `'a array -> node -> 'a``
`a_mem a n` returns the `i`th element of array `a`, where `i` is the id of node `n`. Similar to NMap.find but faster.