947 lines
28 KiB
Racket
947 lines
28 KiB
Racket
#lang scribble/manual
|
|
@(require scribble/example racket/sandbox
|
|
(for-label typed/racket/base
|
|
graph
|
|
(only-in typed/graph Graph)
|
|
(only-in racket/class send)
|
|
"../networks.rkt"
|
|
"../utils.rkt"
|
|
"../functions.rkt"
|
|
"../dynamics.rkt"))
|
|
|
|
@(define networks-evaluator
|
|
(parameterize ([sandbox-output 'string]
|
|
[sandbox-error-output 'string]
|
|
[sandbox-memory-limit 500])
|
|
(make-evaluator 'typed/racket #:requires '("networks.rkt"))))
|
|
|
|
@(define-syntax-rule (ex . args)
|
|
(examples #:eval networks-evaluator . args))
|
|
|
|
@(define-syntax-rule (deftypeform . args)
|
|
(defform #:kind "type" . args))
|
|
|
|
@(define-syntax-rule (deftype . args)
|
|
(defidform #:kind "type" . args))
|
|
|
|
@title[#:tag "networks"]{dds/networks: Formal Dynamical Networks}
|
|
|
|
@defmodule[dds/networks]
|
|
|
|
This module provides definitions for and analysing network models. A network
|
|
is a set of variables which are updated according to their corresponding update
|
|
functions. The variables to be updated at each step are given by the mode.
|
|
This model can generalise Boolean networks, TBANs, multivalued networks, etc.
|
|
|
|
@section[#:tag "networks-basics"]{Basic types}
|
|
|
|
@deftypeform[(State a)]{
|
|
|
|
An immutable mapping (a hash table) assigning elements of type @racket[a] to
|
|
the variables. A synonym of @racket[VariableMapping].
|
|
|
|
}
|
|
|
|
@deftypeform[(UpdateFunction a)]{
|
|
|
|
An update function is a function computing a value from the given
|
|
state. This is a synonym of the type @racket[(-> (State a) a)].
|
|
|
|
}
|
|
|
|
@deftypeform[(Domain a)]{
|
|
|
|
A domain which is a subset of the type @racket[a].
|
|
|
|
@racket[(Domain a)] is a synonym of @racket[(Listof a)].
|
|
|
|
}
|
|
|
|
@deftypeform[(DomainMapping a)]{
|
|
|
|
A domain mapping is a hash table mapping variables to the lists of values in
|
|
their domains.
|
|
|
|
}
|
|
|
|
@section{Common examples}
|
|
|
|
The examples in this document often use the same definitions, which are
|
|
therefore grouped here to avoid duplicating them.
|
|
|
|
These are two functions calculating an @italic{AND} and an @italic{OR} between
|
|
the variables @racket[a] and @racket[b]:
|
|
|
|
@ex[
|
|
(: or-func (UpdateFunction Boolean))
|
|
(define (or-func s)
|
|
(or (hash-ref s 'a) (hash-ref s 'b)))
|
|
|
|
(: and-func (UpdateFunction Boolean))
|
|
(define (and-func s)
|
|
(and (hash-ref s 'a) (hash-ref s 'b)))
|
|
]
|
|
|
|
These are two functions calculating an @italic{AND} and an @italic{OR} between
|
|
two variables @racket[a] and @racket[b] whose values are in @tt{{0,1}}:
|
|
|
|
@ex[
|
|
(require (only-in "utils.rkt" assert-type))
|
|
|
|
(: or-func/01 (UpdateFunction (U Zero One)))
|
|
(define (or-func/01 s)
|
|
(assert-type (max (hash-ref s 'a) (hash-ref s 'b))
|
|
(U Zero One)))
|
|
|
|
(: and-func/01 (UpdateFunction (U Zero One)))
|
|
(define (and-func/01 s)
|
|
(assert-type (min (hash-ref s 'a) (hash-ref s 'b))
|
|
(U Zero One)))
|
|
]
|
|
|
|
@section{Utilities}
|
|
|
|
@defproc[(01->boolean/state [s (State (U Zero One))]) (State Boolean)]{
|
|
|
|
Converts the values 0 and 1 in a state to @racket[#f] and
|
|
@racket[#t] respectively.
|
|
|
|
@ex[
|
|
(01->boolean/state (hash 'a 0 'b 1))
|
|
]}
|
|
|
|
@defproc[(make-same-domains [vars (Listof Variable)]
|
|
[domain (Domain a)])
|
|
(DomainMapping a)]{
|
|
|
|
Makes a hash set mapping all variables to a single domain.
|
|
|
|
@ex[
|
|
(make-same-domains '(a b) '(1 2))
|
|
]}
|
|
|
|
@defproc[(make-boolean-domains [vars (Listof Variable)])
|
|
(DomainMapping Boolean)]{
|
|
|
|
Makes a hash set mapping all variables to the Boolean domain.
|
|
|
|
@ex[
|
|
(make-boolean-domains '(a b))
|
|
]}
|
|
|
|
@defproc[(make-01-domains [vars (Listof Variable)])
|
|
(DomainMapping (U Zero One))]{
|
|
|
|
Makes a hash set mapping all variables to the Boolean domain, expressed as
|
|
@tt{{0,1}}.
|
|
|
|
@ex[
|
|
(make-01-domains '(a b))
|
|
]}
|
|
|
|
@section{Networks}
|
|
|
|
@defstruct*[network ([functions (VariableMapping (UpdateFunction a))]
|
|
[domains (DomainMapping a)])]{
|
|
|
|
A network consists of a mapping from its variables to its update variables, as
|
|
a well as of a mapping from its variables to their domains.
|
|
|
|
Instances of @racket[network] have the type @racket[Network].
|
|
|
|
}
|
|
|
|
@deftypeform[(Network a)]{
|
|
|
|
The type of the instances of @racket[network].
|
|
|
|
@ex[
|
|
(network (hash 'a or-func
|
|
'b and-func)
|
|
(hash 'a '(#f #t)
|
|
'b '(#f #t)))
|
|
]}
|
|
|
|
@defproc[(make-boolean-network [funcs (VariableMapping (UpdateFunction Boolean))])
|
|
(Network Boolean)]{
|
|
|
|
Builds a Boolean network from a given hash table assigning functions to
|
|
variables by attributing Boolean domains to every variable.
|
|
|
|
@ex[
|
|
(make-boolean-network (hash 'a or-func 'b and-func))
|
|
]}
|
|
|
|
@defproc[(make-01-network [funcs (VariableMapping (UpdateFunction (U Zero One)))])
|
|
(Network (U Zero One))]{
|
|
|
|
Build a network from a given hash table assigning functions to variables by
|
|
attributing the domain @tt{{0,1}} to every variable.
|
|
|
|
@ex[
|
|
(make-01-network (hash 'a or-func/01 'b and-func/01))
|
|
]}
|
|
|
|
@defproc[(update [network (Network a)] [s (State a)] [xs (Listof Variable)])
|
|
(State a)]{
|
|
|
|
Given a state @racket[s] updates all the variables of @racket[network] from
|
|
@racket[xs].
|
|
|
|
@ex[
|
|
(update (make-boolean-network (hash 'a or-func 'b and-func))
|
|
(hash 'a #f 'b #t)
|
|
'(a))
|
|
]}
|
|
|
|
@section{Syntactic description of networks}
|
|
|
|
@deftype[UpdateFunctionForm]{
|
|
|
|
An update function form is any form which can appear as a body of a function
|
|
and which can be evaluated with @racket[eval].
|
|
|
|
@ex[
|
|
(ann '(and x y (not z)) UpdateFunctionForm)
|
|
(ann '(+ 1 a (- b 10)) UpdateFunctionForm)
|
|
]
|
|
|
|
@racket[UpdateFunctionForm] is a synonym of @racket[Any].
|
|
|
|
}
|
|
|
|
@defstruct*[network-form ([functions (VariableMapping NetworkForm)]
|
|
[domains (DomainMapping a)])]{
|
|
|
|
A network form consists of a mapping from variables to the forms of their
|
|
update functions, together with a mapping from its variables to its
|
|
update functions.
|
|
|
|
The domain mapping does not have to assign domains to all variables (e.g., it
|
|
may be empty), but in this case the functions which need to know the domains
|
|
will not work.
|
|
|
|
Instances of @racket[network-form] have the type @racket[NetworkForm].
|
|
|
|
}
|
|
|
|
@deftypeform[(NetworkForm a)]{
|
|
|
|
The type of instances of @racket[network-form].
|
|
|
|
@ex[
|
|
(network-form (hash 'a '(and a b) 'b '(or a b))
|
|
(hash 'a '(#f #t) 'b '(#f #t)))
|
|
]}
|
|
|
|
@defproc[(update-function-form->update-function/any [func UpdateFunctionForm])
|
|
(UpdateFunction Any)]{
|
|
|
|
Builds an update function from an update function form.
|
|
|
|
@ex[
|
|
(define and-from-form (update-function-form->update-function/any '(and x y)))
|
|
(and-from-form (hash 'x #f 'y #f))
|
|
(and-from-form (hash 'x #f 'y #t))
|
|
(and-from-form (hash 'x #t 'y #f))
|
|
(and-from-form (hash 'x #t 'y #t))
|
|
]}
|
|
|
|
@defproc[(update-function-form->update-function/boolean [func UpdateFunctionForm])
|
|
(UpdateFunction Boolean)]{
|
|
|
|
Like @racket[update-function-form->update-function/any], but the resulting
|
|
function operates on Boolean states.
|
|
|
|
@ex[
|
|
(define and-from-form/boolean (update-function-form->update-function/boolean '(and x y)))
|
|
(and-from-form/boolean (hash 'x #f 'y #f))
|
|
(and-from-form/boolean (hash 'x #f 'y #t))
|
|
(and-from-form/boolean (hash 'x #t 'y #f))
|
|
(and-from-form/boolean (hash 'x #t 'y #t))
|
|
]}
|
|
|
|
@defproc[(update-function-form->update-function/01 [func UpdateFunctionForm])
|
|
(UpdateFunction (U Zero One))]{
|
|
|
|
Like @racket[update-function-form->update-function/01], but the resulting
|
|
function operates on Boolean states, with the domain @tt{{0,1}}.
|
|
|
|
@ex[
|
|
(define and-from-form/01 (update-function-form->update-function/01 '(min x y)))
|
|
(and-from-form/01 (hash 'x 0 'y 0))
|
|
(and-from-form/01 (hash 'x 0 'y 1))
|
|
(and-from-form/01 (hash 'x 1 'y 0))
|
|
(and-from-form/01 (hash 'x 1 'y 1))
|
|
]}
|
|
|
|
@defproc[(network-form->network/any [nf (NetworkForm Any)]) (Network Any)]{
|
|
|
|
Builds a network from a network form.
|
|
|
|
@ex[
|
|
(network-form->network/any
|
|
(network-form (hash 'a '(and a b)
|
|
'b '(not b))
|
|
(hash 'a '(#f #t)
|
|
'b '(#f #t))))
|
|
]}
|
|
|
|
@defproc[(network-form->network/boolean [nf (NetworkForm Boolean)]) (Network Boolean)]{
|
|
|
|
Like @racket[network-form->network/any], but builds a Boolean network.
|
|
|
|
@ex[
|
|
(network-form->network/boolean
|
|
(network-form (hash 'a '(and a b)
|
|
'b '(not b))
|
|
(hash 'a '(#f #t)
|
|
'b '(#f #t))))
|
|
]}
|
|
|
|
@defproc[(network-form->network/01 [nf (NetworkForm (U Zero One))]) (Network (U Zero One))]{
|
|
|
|
Like @racket[network-form->network/any], but builds a Boolean network, whose
|
|
domains are expressed as @tt{{0,1}}.
|
|
|
|
@ex[
|
|
(network-form->network/01
|
|
(network-form (hash 'a '(min a b)
|
|
'b '(- 1 b))
|
|
(hash 'a '(0 1)
|
|
'b '(0 1))))
|
|
]}
|
|
|
|
@defproc[(make-boolean-network-form [forms (VariableMapping UpdateFunctionForm)])
|
|
(NetworkForm Boolean)]{
|
|
|
|
Build a Boolean network form from a given mapping assigning forms to variables.
|
|
|
|
@ex[
|
|
(make-boolean-network-form (hash 'a '(and a b)
|
|
'b '(not b)))
|
|
]}
|
|
|
|
@defproc[(forms->boolean-network [forms (VariableMapping UpdateFunctionForm)])
|
|
(Network Boolean)]{
|
|
|
|
Build a Boolean network from a given mapping assigning forms to variables.
|
|
|
|
@ex[
|
|
(forms->boolean-network (hash 'a '(and a b)
|
|
'b '(not b)))
|
|
]}
|
|
|
|
@section{Dynamics of networks}
|
|
|
|
This section contains definitions for building and analysing the dynamics
|
|
of networks.
|
|
|
|
@defproc[(build-all-states [vars-domains (DomainMapping a)])
|
|
(Listof (State a))]{
|
|
|
|
Given a @racket[DomainMapping], constructs the list of all possible states.
|
|
|
|
@ex[
|
|
(build-all-states (make-boolean-domains '(a b)))
|
|
]}
|
|
|
|
@defproc[(build-all-boolean-states [vars (Listof Variable)])
|
|
(Listof (State Boolean))]{
|
|
|
|
Builds all Boolean states over a given list of variables.
|
|
|
|
@ex[
|
|
(build-all-boolean-states '(a b))
|
|
]}
|
|
|
|
@defproc[(build-all-01-states [vars (Listof Variable)])
|
|
(Listof (State Boolean))]{
|
|
|
|
Builds all Boolean states over a given set of variables, but with the Boolean
|
|
values represented as 0 and 1.
|
|
|
|
@ex[
|
|
(build-all-01-states '(a b))
|
|
]}
|
|
|
|
@deftype[Modality]{
|
|
|
|
A modality is a list of variables. This is a synonym of @racket[(Listof
|
|
Variable)].
|
|
|
|
}
|
|
|
|
@deftype[Mode]{
|
|
|
|
A mode is a list of modalities. This is a synonym of @racket[(Listof Modality)].
|
|
|
|
}
|
|
|
|
@defclass[dynamics% dds% ()]{
|
|
|
|
A model of dynamics of a network is a @racket[Network] with a @racket[Mode].
|
|
|
|
@defconstructor[([network (Network a)] [mode Mode])]{
|
|
|
|
Creates a new instance of @racket[dynamics%] from a @racket[network] and
|
|
a @racket[mode]. Both are available as public fields of the class.
|
|
|
|
}
|
|
|
|
@defmethod[(step/annotated [st (State a)]) (Listof (Pairof Modality (State a)))]{
|
|
|
|
Apply the network stored in this class to the state @racket[st] with all
|
|
modalities of the mode stored in this class.
|
|
|
|
This is the only method of @racket[dds%] overridden in this class.
|
|
|
|
@ex[
|
|
(let* ([n (forms->boolean-network (hash 'a '(and a b)
|
|
'b '(not b)))]
|
|
[syn '((a) (b))]
|
|
[syn-dynamics (new (inst dynamics% Boolean) [network n] [mode syn])]
|
|
[st (hash 'a #f 'b #f)])
|
|
(send syn-dynamics step/annotated st))
|
|
]}}
|
|
|
|
@deftypeform[(Dynamics% a)]{
|
|
|
|
The type of an instance of @racket[dynamics%] with values of type @racket[a].
|
|
|
|
@ex[
|
|
(let* ([n (forms->boolean-network (hash 'a '(and a b)
|
|
'b '(not b)))]
|
|
[syn '((a) (b))]
|
|
[syn-dynamics (new (inst dynamics% Boolean) [network n] [mode syn])])
|
|
(ann syn-dynamics (Dynamics% Boolean)))
|
|
]
|
|
|
|
Note that, as of 2022-09-15, Typed Racket does not seem to allow to pass type
|
|
parameters from a child class to a parent class. Therefore, @racket[dynamics%]
|
|
inherits in fact from a @racket[dds%] with its first type parameter set to
|
|
@racket[(State Any)]. This can be seen by examining the type of
|
|
@racket[dynamics%].
|
|
|
|
@ex[dynamics%]
|
|
|
|
The type constructor @racket[Dynamics%] takes this limitation into account.
|
|
|
|
}
|
|
|
|
@defproc[(make-asyn [vars (Listof Variable)]) Mode]{
|
|
|
|
Given a list of variables, builds the asynchronous mode, i.e. a set of
|
|
singleton sets of variables.
|
|
|
|
@ex[(make-asyn '(x y z))]
|
|
|
|
}
|
|
|
|
@defproc[(make-syn [vars (Listof Variable)]) Mode]{
|
|
|
|
Given a list of variables, builds the synchronous mode, i.e. a singleton set
|
|
containing the set of all variables.
|
|
|
|
@ex[(make-syn '(x y z))]
|
|
|
|
}
|
|
|
|
@defproc[(make-asyn-dynamics [network (Network a)]) (Dynamics% a)]{
|
|
|
|
Creates the asynchronous dynamics for a given network: an instance of
|
|
@racket[dynamics%] with @tt{network} as the network and the asynchronous
|
|
mode as @tt{mode}.
|
|
|
|
See @racket[build-full-state-graph/annotated] for an example.
|
|
|
|
}
|
|
|
|
@defproc[(make-syn-dynamics [network (Network a)]) (Dynamics% a)]{
|
|
|
|
Creates the synchronous dynamics for a given network: an instance of
|
|
@racket[dynamics%] with @tt{network} as the network and the synchronous mode as
|
|
@tt{mode}.
|
|
|
|
See @racket[build-full-state-graph] for an example.
|
|
|
|
}
|
|
|
|
@defproc[(build-full-state-graph [dyn (Dynamics% a)]) Graph]{
|
|
|
|
Builds the full state graph of the given dynamics.
|
|
|
|
@ex[
|
|
(require (only-in "utils.rkt" dotit))
|
|
|
|
(let* ([n (forms->boolean-network (hash 'a '(and a b)
|
|
'b '(not b)))]
|
|
[syn-dynamics (make-syn-dynamics n)])
|
|
(dotit ((inst build-full-state-graph Boolean) syn-dynamics)))
|
|
]
|
|
|
|
}
|
|
|
|
@defproc[(build-full-state-graph/annotated [dyn (Dynamics% a)]) Graph]{
|
|
|
|
Builds the full annotated state graph of the given dynamics.
|
|
|
|
@ex[
|
|
(require (only-in "utils.rkt" dotit))
|
|
|
|
(let* ([n (forms->boolean-network (hash 'a '(and a b)
|
|
'b '(not b)))]
|
|
[asyn-dynamics (make-asyn-dynamics n)])
|
|
(dotit ((inst build-full-state-graph/annotated Boolean) asyn-dynamics)))
|
|
]
|
|
|
|
}
|
|
|
|
@section[#:tag "networks_Pretty_printing"]{Pretty printing}
|
|
|
|
This section defines various functions for nicely formatting node and edge
|
|
labels in state graphs of networks.
|
|
|
|
@defproc[(pretty-print-state [s (State a)]) String]{
|
|
|
|
Pretty-prints a state of a network.
|
|
|
|
@ex[(pretty-print-state (hash 'a #f 'b 3 'c 4))]
|
|
|
|
}
|
|
|
|
@defproc[(pretty-print-state/01 [s (State a)]) String]{
|
|
|
|
Pretty-prints a state of a network, replacing all @racket[#f] values with 0 and
|
|
all other values with 1.
|
|
|
|
@ex[(pretty-print-state/01 (hash 'a #f 'b 3 'c '() 'd #t))]
|
|
|
|
}
|
|
|
|
@defproc[(pretty-print-state-graph-with [gr Graph] [pprinter (-> Any Any)]) Graph]{
|
|
|
|
Given a state graph @racket[gr] and the pretty-printer for states
|
|
@racket[pprinter], build a new state graph in which the nodes are
|
|
pretty-printed with @racket[pprinter] and the edges with
|
|
@racket[pretty-print-set-sets].
|
|
|
|
}
|
|
|
|
@defproc[(pretty-print-state-graph [gr Graph]) Graph]{
|
|
|
|
Calls @racket[pretty-print-state-graph-with] with @racket[pretty-print-state].
|
|
|
|
@ex[
|
|
(let* ([n (forms->boolean-network (hash 'a '(and a b)
|
|
'b '(not b)))]
|
|
[syn-dynamics (make-syn-dynamics n)])
|
|
(dotit (pretty-print-state-graph
|
|
((inst build-full-state-graph Boolean) syn-dynamics))))
|
|
]
|
|
|
|
}
|
|
|
|
@defproc[(ppsg [gr Graph]) Graph]{
|
|
|
|
A shortcut for @racket[pretty-print-state-graph].
|
|
|
|
}
|
|
|
|
@defproc[(pretty-print-state-graph/01 [gr Graph]) Graph]{
|
|
|
|
Calls @racket[pretty-print-state-graph-with] with @racket[pretty-print-state/01].
|
|
|
|
@ex[
|
|
(let* ([n (forms->boolean-network (hash 'a '(and a b)
|
|
'b '(not b)))]
|
|
[syn-dynamics (make-syn-dynamics n)])
|
|
(dotit (pretty-print-state-graph/01
|
|
((inst build-full-state-graph Boolean) syn-dynamics))))
|
|
]
|
|
|
|
}
|
|
|
|
@defproc[(ppsg01 [gr Graph]) Graph]{
|
|
|
|
A shortcut for @racket[pretty-print-state-graph/01].
|
|
|
|
}
|
|
|
|
|
|
@section{Inferring interaction graphs}
|
|
|
|
This section provides inference of both unsigned and signed interaction graphs.
|
|
Since the inference of signed interaction graphs is based on analysing the
|
|
dynamics of the networks, it may be quite resource-consuming, especially since
|
|
any syntactic forms are allowed in the definitions of the functions.
|
|
|
|
We use the term @emph{syntactic interaction graph} to refer to the graph in
|
|
which the presence of an arc from @tt{x} to @tt{y} is based on whether @tt{x}
|
|
appears in the form of @tt{y}. This is quite different from the canonical
|
|
definition of the @emph{interaction graph}, in which the arc from @tt{x} to
|
|
@tt{y} represents the fact that a change in the value of @tt{x} may lead to
|
|
a change in the value of @tt{y}. Thus the syntactic interaction graph may have
|
|
extra arcs if @tt{x} appears in the form of @tt{y}, but has no actual influence
|
|
on @tt{y}.
|
|
|
|
@defproc[(list-syntactic-interactions [nf (NetworkForm a)]
|
|
[x Variable])
|
|
(Listof Variable)]{
|
|
|
|
Lists the variables of the network form appearing in the update function form
|
|
for @racket[x].
|
|
|
|
The variables which are not part of the network are excluded from the listing.
|
|
|
|
@ex[
|
|
(list-syntactic-interactions
|
|
(make-boolean-network-form #hash((a . (+ a b))
|
|
(b . (- b))))
|
|
'a)
|
|
(list-syntactic-interactions
|
|
(make-boolean-network-form #hash((a . (+ a b c))
|
|
(b . (- b c))))
|
|
'a)
|
|
]}
|
|
|
|
@defproc[(build-syntactic-interaction-graph [n (NetworkForm a)])
|
|
Graph]{
|
|
|
|
Builds the graph in which the vertices are the variables of a given network,
|
|
and which contains an arrow from @racket[x] to @racket[y] whenever @racket[x]
|
|
appears in @racket[(list-interactions y)].
|
|
|
|
@ex[
|
|
(require (only-in "utils.rkt" dotit))
|
|
(dotit (build-syntactic-interaction-graph
|
|
(make-boolean-network-form #hash((a . (+ a b))
|
|
(b . (- b))))))
|
|
]}
|
|
|
|
@defproc[(interaction? [network (Network a)]
|
|
[x Variable]
|
|
[y Variable])
|
|
Boolean]{
|
|
|
|
Given two variables @racket[x] and @racket[y] of a @racket[network], verifies
|
|
if they interact, i.e. that there exists a pair of states @italic{s} and
|
|
@italic{s'} with the following properties:
|
|
|
|
@itemlist[
|
|
@item{@italic{s} and @italic{s'} only differ in the value of @racket[x];}
|
|
@item{running the network from @italic{s} and @italic{s'} yields different
|
|
values for @racket[y].}
|
|
]
|
|
|
|
@ex[
|
|
(let ([bn (forms->boolean-network #hash((a . (and a b))
|
|
(b . (not b))))])
|
|
(values (interaction? bn 'a 'b)
|
|
(interaction? bn 'b 'a)))
|
|
]}
|
|
|
|
@defproc[(get-interaction-sign [network (Network a)]
|
|
[x Variable]
|
|
[y Variable])
|
|
(Option Integer)]{
|
|
|
|
Given two variables @racket[x] and @racket[y] of @racket[network], checks
|
|
whether they interact, and if they interact, returns 1 if increasing @racket[x]
|
|
leads to an increase in @racket[y], -1 if it leads to a decrease in @racket[y],
|
|
and 0 if it can lead to both. If @racket[x] has no impact on @racket[y], returns @racket[#f].
|
|
|
|
The values in the domains are ordered according to the order in which they are
|
|
listed in @racket[network].
|
|
|
|
Since @racket[get-interaction-sign] needs to check all possible interactions
|
|
between @racket[x] and @racket[y], it is more costly than calling
|
|
@racket[interaction?].
|
|
|
|
@ex[
|
|
(let ([bn (forms->boolean-network #hash((a . (and a b))
|
|
(b . (not b))))])
|
|
(values (get-interaction-sign bn 'a 'b)
|
|
(get-interaction-sign bn 'b 'a)
|
|
(get-interaction-sign bn 'b 'b)))
|
|
]}
|
|
|
|
@defproc[(build-interaction-graph [network (Network a)]) Graph]{
|
|
|
|
Given a network, builds its interaction graph. The graph has variables as
|
|
nodes and has a directed edge from @italic{x} to @italic{y} if
|
|
@racket[interaction?] returns @racket[#t] for these variables, in this order.
|
|
|
|
@ex[
|
|
(dotit (build-interaction-graph
|
|
(forms->boolean-network #hash((a . (and a b))
|
|
(b . (not b))))))
|
|
]}
|
|
|
|
@defproc[(build-interaction-graph/form [nf (NetworkForm a)]) Graph]{
|
|
|
|
Like @racket[build-interaction-graph], but accepts a network form and
|
|
converts it a to @racket[(Network a)] first.
|
|
|
|
@ex[
|
|
(dotit (build-interaction-graph/form
|
|
(make-boolean-network-form #hash((a . (and a b))
|
|
(b . (not b))))))
|
|
]}
|
|
|
|
@defproc[(build-signed-interaction-graph [network (Network a)]) Graph]{
|
|
|
|
Given a network, builds its signed interaction graph. The graph has variables
|
|
as nodes and has a directed edge from @italic{x} to @racket{y} labelled by the
|
|
value @racket[get-interaction-sign] produces for these variables, in that
|
|
order, unless this value is @racket[#f].
|
|
|
|
@ex[
|
|
(dotit (build-signed-interaction-graph
|
|
(forms->boolean-network #hash((a . (and a b))
|
|
(b . (not b))))))
|
|
]}
|
|
|
|
@defproc[(build-signed-interaction-graph/form [nf (NetworkForm a)]) Graph]{
|
|
|
|
Like @racket[build-signed-interaction-graph], but takes a network form and
|
|
converts it to a network.
|
|
|
|
@ex[
|
|
(dotit (build-signed-interaction-graph/form
|
|
(make-boolean-network-form #hash((a . (and a b))
|
|
(b . (not b))))))
|
|
]}
|
|
|
|
@section{Tabulating functions and networks}
|
|
@defproc[(tabulate-state* [funcs (Listof (-> (State a) a))]
|
|
[domains (DomainMapping a)])
|
|
(Listof (Listof a))]{
|
|
|
|
Like @racket[tabulate*], but the functions operate on states.
|
|
|
|
This function will produce a joint truth table of the given functions—a list of
|
|
lists, in which the first columns list all possible combinations of the values
|
|
of the input values, and the last columns give the corresponding values of the
|
|
functions. @racket[domains] defines the domains of each of the component of
|
|
the states.
|
|
|
|
@ex[
|
|
(require (only-in "utils.rkt" λ/:))
|
|
(tabulate-state* (list (λ/: (State Integer) (+ :a :b))
|
|
(λ/: (State Integer) (- :a :b)))
|
|
(hash 'a '(1 2) 'b '(2 3)))
|
|
]}
|
|
|
|
@defproc[(tabulate-state*+headers [funcs (Listof (-> (State a) a))]
|
|
[domains (DomainMapping a)])
|
|
(Pairof (Listof Symbol) (Listof (Listof a)))]{
|
|
|
|
Like @racket[tabulate-state*], but the first line of the result lists the names
|
|
of the variables and the functions.
|
|
|
|
@ex[
|
|
(tabulate-state*+headers (list (λ/: (State Integer) (+ :a :b))
|
|
(λ/: (State Integer) (- :a :b)))
|
|
(hash 'a '(1 2) 'b '(2 3)))
|
|
]}
|
|
|
|
@defproc[(tabulate-state*/boolean [funcs (Listof (-> State Boolean) Boolean)]
|
|
[args (Listof Variable)])
|
|
(Listof (Listof Boolean))]{
|
|
|
|
Like @racket[tabulate-state*], but the functions operate on Boolean states.
|
|
The list @racket[args] is used to generate all possible Boolean states
|
|
containing the variables appearing on this list.
|
|
|
|
@ex[
|
|
(tabulate-state*/boolean (list (λ/: (State Boolean) (and :a :b))
|
|
(λ/: (State Boolean) (or :a :b)))
|
|
'(a b))
|
|
]}
|
|
|
|
@defproc[(tabulate-state*+headers/boolean
|
|
[funcs (Listof (-> State Boolean) Boolean)]
|
|
[args (Listof Variable)])
|
|
(Pairof (Listof Symbol) (Listof (Listof Boolean)))]{
|
|
|
|
Like @racket[tabulate-state*+headers], but the functions operate on Boolean
|
|
states, like @racket[tabulate-state*].
|
|
|
|
@ex[
|
|
(tabulate-state*+headers/boolean
|
|
(list (λ/: (State Boolean) (and :a :b))
|
|
(λ/: (State Boolean) (or :a :b)))
|
|
'(a b))
|
|
]}
|
|
|
|
@deftogether[(@defproc[(tabulate-state [func (-> (State a) a)]
|
|
[domains (DomainMapping a)])
|
|
(Listof (Listof a))]
|
|
@defproc[(tabulate-state+headers
|
|
[func (-> (State a) a)]
|
|
[domains (DomainMapping a)])
|
|
(Pairof (Listof Symbol) (Listof (Listof a)))]
|
|
@defproc[(tabulate-state/boolean [func (-> (State Boolean) Boolean)]
|
|
[args (Listof Variable)])
|
|
(Listof (Listof Boolean))]
|
|
@defproc[(tabulate-state+headers/boolean
|
|
[func (-> (State Boolean) Boolean)]
|
|
[args (Listof Variable)])
|
|
(Pairof (Listof Symbol) (Listof (Listof Boolean)))])]{
|
|
|
|
Like the starred versions @racket[tabulate-state*],
|
|
@racket[tabulate-state*+headers], @racket[tabulate-state/boolean], and
|
|
@racket[tabulate-state+headers/boolean], but only tabulate one
|
|
function instead of a list.
|
|
|
|
@ex[
|
|
(tabulate-state
|
|
(λ/: (State Boolean) (and :a :b))
|
|
(hash 'a '(#f #t) 'b '(#f #t)))
|
|
(tabulate-state+headers
|
|
(λ/: (State Boolean) (and :a :b))
|
|
(hash 'a '(#f #t) 'b '(#f #t)))
|
|
(tabulate-state/boolean
|
|
(λ/: (State Boolean) (and :a :b))
|
|
'(a b))
|
|
(tabulate-state+headers/boolean
|
|
(λ/: (State Boolean) (and :a :b))
|
|
'(a b))
|
|
]}
|
|
|
|
@defproc[(tabulate-network [network (Network a)]) (Listof (Listof a))]{
|
|
|
|
Tabulates all the functions of @racket[network], producing an output
|
|
similar to that of @racket[tabulate-state*].
|
|
|
|
@ex[
|
|
(tabulate-network (forms->boolean-network (hash 'a '(not a) 'b 'b)))
|
|
]}
|
|
|
|
@defproc[(tabulate-network+headers [network (Network a)]) (Listof (Listof a))]{
|
|
|
|
Tabulates all the functions of @racket[network], producing an output
|
|
similar to that of @racket[tabulate-state*+headers] , except that the
|
|
function names in the corresponding column headers are of the form
|
|
@tt{f-x}, where @tt{x} is the name of the corresponding variable.
|
|
|
|
@ex[
|
|
(tabulate-network+headers (forms->boolean-network (hash 'a '(not a) 'b 'b)))
|
|
]}
|
|
|
|
@section{Constructing functions and networks}
|
|
|
|
@defproc[(table+vars->network [var-names (Listof Variable)]
|
|
[table (Listof (Listof a))])
|
|
(Network a)]{
|
|
|
|
Given a @racket[table] like the one produced by
|
|
@racket[tabulate-network] and the list of variable names
|
|
@racket[var-names], constructs a network having this behaviour.
|
|
|
|
The columns defining the functions are taken to be in the same order
|
|
as the columns defining the variables. The domains of the network are
|
|
a mapping assigning to each variable the set of values which can
|
|
appear in the corresponding column in the table.
|
|
|
|
This function relies on @racket[table->unary-function], so the same
|
|
performance caveats apply.
|
|
|
|
This function does not check whether the table is complete.
|
|
|
|
@ex[
|
|
(let ([n (table+vars->network '(a b)
|
|
'((#f #f #f #f)
|
|
(#f #t #f #t)
|
|
(#t #f #t #f)
|
|
(#t #t #t #t)))])
|
|
(tabulate-network n))
|
|
]}
|
|
|
|
@defproc[(table->network [table (Listof (Listof a))]) (Network a)]{
|
|
|
|
Like @racket[table+vars->network], but generates variable names as
|
|
@tt{xi}, where 1 ≤ @tt{i} ≤ number of variables.
|
|
|
|
@ex[
|
|
(let ([n (table->network '((#f #f #f #f)
|
|
(#f #t #f #t)
|
|
(#t #f #t #f)
|
|
(#t #t #t #t)))])
|
|
(network-domains n))
|
|
]}
|
|
|
|
@defproc[(table+headers->network [table (Pairof (Listof Symbol) (Listof (Listof a)))])
|
|
(Network a)]{
|
|
|
|
Like @racket[table+vars->network], but the variable names are taken
|
|
from the first line of @racket[table].
|
|
|
|
The lines of @racket[table] are taken to be of the same length, so it
|
|
is assumed that half of the first line contain variable names, and the
|
|
other half function names. Function names are discarded.
|
|
|
|
@ex[
|
|
(let ([n (table+headers->network '((a b fa fb)
|
|
(#f #f #f #f)
|
|
(#f #t #f #t)
|
|
(#t #f #t #f)
|
|
(#t #t #t #t)))])
|
|
(network-domains n))
|
|
]}
|
|
|
|
@section{Random functions and networks}
|
|
|
|
@defproc[(random-function/state [arg-domains (DomainMapping a)]
|
|
[func-doman (Domain a)])
|
|
(-> (State a) a)]{
|
|
|
|
Generates a random function accepting a state over the domains given
|
|
by @racket[arg-domains] and producing values in @racket[func-domain].
|
|
|
|
@ex[
|
|
(let* ([doms (hash 'a '(1 2) 'b '(3 4))]
|
|
[f (random-function/state doms '(e f))])
|
|
(tabulate-state+headers f doms))
|
|
]}
|
|
|
|
@defproc[(random-boolean-function/state [args (Listof Variable)])
|
|
(-> (State a) a)]{
|
|
|
|
Generates a random Boolean function accepting states over the
|
|
variables in @racket[args].
|
|
|
|
@ex[
|
|
(tabulate-state+headers/boolean (random-boolean-function/state '(a b)) '(a b))
|
|
]}
|
|
|
|
@defproc[(random-network [domains (DomainMapping a)])
|
|
(Network a)]{
|
|
|
|
Generates a random network from the given domain mapping.
|
|
|
|
@ex[
|
|
(tabulate-network+headers (random-network (hash 'a '(1 2) 'b '(#f #t))))
|
|
]}
|
|
|
|
@defproc[(random-boolean-network [vars (Listof Variable)])
|
|
(Network Boolean)]{
|
|
|
|
Generates a random Boolean network with the given variables.
|
|
|
|
@ex[
|
|
(tabulate-network+headers (random-boolean-network '(x y z)))
|
|
]}
|
|
|
|
@defproc[(random-boolean-network/n [n Positive-Integer])
|
|
(Network Boolean)]{
|
|
|
|
Like @racket[random-boolean-network], but also generates the names of
|
|
the variables for the network. The variables have the names @tt{x0}
|
|
to @tt{xk}, where @italic{k = n - 1}.
|
|
|
|
@ex[
|
|
(tabulate-network+headers (random-boolean-network/n 3))
|
|
]}
|