state_transition_graphs¶

add_style_anonymous(stg: DiGraph)¶

Removes the labels and draws each state as a filled circle.

arguments:

stg: state transition graph

example:

>>> add_style_anonymous(stg)

add_style_default(primes: dict, stg: DiGraph)¶

A convenience function that adds styles for tendencies, SCCs and minimal trap spaces.

arguments:

primes: primes implicants
stg: state transition graph

example:

>>> add_style_default(stg)

add_style_mintrapspaces(primes: dict, stg: DiGraph, max_output: int = 100)¶

A convenience function that combines add_style_subspaces and trap_spaces. It adds a dot subgraphs for every minimal trap space to stg - subgraphs that already exist are overwritten.

arguments:

primes: prime implicants
stg: state transition graph
MaxOutput: maximal number of minimal trap spaces, see trap_spaces

example:

>>> add_style_mintrapspaces(primes, stg)

add_style_path(stg: DiGraph, path: Union[List[str], List[dict]], color: str, pen_width: int = 3)¶

Sets the color of all nodes and edges involved in the given path to color.

arguments:

stg: state transition graph
path: state dictionaries or state strings
color: color of the path
pen_width: width of nodes and edges involved in path in pt

example:

>>> path = ["001", "011", "101"]
>>> add_style_path(stg, path, "red")

add_style_sccs(stg: DiGraph)¶

Adds a subgraph for every non-trivial strongly connected component (SCC) to the dot representation of stg. Nodes that belong to the same dot subgraph are contained in a rectangle and treated separately during layout computations. Each subgraph is filled by a shade of gray that gets darker with an increasing number of SCCs that are above it in the condensation graph. Shadings repeat after a depth of 9.

arguments:

stg: state transition graph

example:

>>> add_style_sccs(stg)

add_style_subgraphs(stg: DiGraph, subgraphs)¶

Adds the subgraphs given in subgraphs to stg - or overwrites them if they already exist. Nodes that belong to the same dot subgraph are contained in a rectangle and treated separately during layout computations. subgraphs must consist of tuples of the form NodeList, Attributs where NodeList is a list of graph nodes and Attributes is a dictionary of subgraph attributes in dot format.

Note

subgraphs must satisfy the following property: Any two subgraphs have either empty intersection or one is a subset of the other. The reason for this requirement is that dot can not draw intersecting subgraphs.

arguments:

stg: state transition graph
subgraphs: pairs of lists and subgraph attributes

example:

>>> sub1 = (["001","010"], {"label":"critical states"})
>>> sub2 = (["111","011"], {})
>>> subgraphs = [sub1,sub2]
>>> add_style_subgraphs(stg, subgraphs)

add_style_subspaces(primes: dict, stg: DiGraph, subspaces)¶

Adds a dot subgraph for every subspace in subspace to stg - or overwrites them if they already exist. Nodes that belong to the same dot subgraph are contained in a rectangle and treated separately during layout computations. To add custom labels or fillcolors to a subgraph supply a tuple consisting of the subspace and a dictionary of subgraph attributes.

Note

subgraphs must satisfy the following property: Any two subgraphs have either empty intersection or one is a subset of the other. The reason for this requirement is that dot can not draw intersecting subgraphs.

arguments:

primes: prime implicants
stg: state transition graph
subspaces: list of subspaces in string or dict representation

example:

>>> subspaces = [{"v1":0},{"v1":0,"v3":1},{"v1":1,"v2":1}]
>>> add_style_subspaces(primes, stg, subspaces)
>>> subspaces = ["0--","0-1","11-"]
>>> add_style_subspaces(primes, stg, subspaces)

add_style_tendencies(stg: DiGraph)¶

Sets or overwrites the edge colors to reflect whether a transition increases values (black), decreases values (red), or both (blue) which is only possible for non-asynchronous transitions.

arguments:

stg: state transition graph

example:

>>> add_style_tendencies(stg)

best_first_reachability(primes: dict, initial_space: Union[str, dict], goal_space: Union[str, dict], memory: int = 1000)¶

Performs a best-first search in the asynchronous transition system defined by primes to answer the question whether there is a path from a random state in InitalSpace to a state in GoalSpace. Memory specifies the maximal number of states that can be kept in memory as “already explored” before the algorithm terminates. The search is guided by minimizing the Hamming distance between the current state of an incomplete path and the GoalSpace where variables that are free in GoalSpace are ignored.

Note

If the number of variables is less than 40 you should use LTL or CTL model checking to answer questions of reachability. best_first_reachability is meant for systems with more than 40 variables. If best_first_reachability returns None then that does not prove that there is no path between InitialSpace and GoalSpace.

arguments:

primes: prime implicants
initial_space: initial subspace
goal_space: goal subspace
memory: maximal number of states memorized before search is stopped

returns:

path: a path from InitalSpace to GoalSpace if it was found, or None otherwise.

example:

>>> initspace = "1--0"
>>> goalspace = "0--1"
>>> path = best_first_reachability(primes, initialstate, goalspace)
>>> if path: print(len(path))
4

condensationgraph2dot(cgraph: DiGraph, fname_dot: Optional[str] = None)¶

Creates a dot file from a condensation graph.

arguments:

cgraph: state transition graph
fname_dot: name of dot file or None

returns:

text_dot: file as string if not FnameDOT is None, otherwise it returns None

example:

>>> condensationgraph2dot(cgraph, "mapk_cgraph.dot")

condensationgraph2image(cgraph: DiGraph, fname_image: str, layout_engine: str = 'dot')¶

Creates an image file from the condensation graph.

arguments:

cgraph: condensation graph
fname_image: name of output file
layout_engine: one of “dot”, “neato”, “fdp”, “sfdp”, “circo”, “twopi”

example:

>>> condensationgraph2image(cgraph, "dot", "mapk_cgraph.pdf")

copy_stg(stg: DiGraph) → DiGraph¶

Creates a copy of stg including all dot attributes.

arguments:

stg: state transition graph

returns:

stg_copy: new state transition graph

example:

>>> stg_copy = copy_stg(stg)

create_stg_image(primes: dict, update: str, fname_image: str, initial_states=<function <lambda>>, styles: ~typing.List[str] = [], layout_engine: str = 'dot')¶

A convenience function for drawing state transition graphs directly from the prime implicants. styles must be a sublist of [“tendencies”, “sccs”, “mintrapspaces”, “anonymous”].

arguments:

primes: prime implicants
fname_image: name of image
initial_states: a function, a subspace, a state or a list of states
styles: the styles to be applied
layout_engine: one of “dot”, “neato”, “fdp”, “sfdp”, “circo”, “twopi”

example:

>>> create_stg_image(primes, "asynchronous", "mapk_stg.pdf", styles=["interactionsigns", "anonymous"])

energy(primes: dict, state) → int¶

This integer valued energy function E for Boolean networks is decreasing with transitions. That is, E(x) >= E(y) holds for any transition x -> y. It is based on the number of free variables in the smallest trapspace that contains state. The energy is therefore n >= E(x) >= 0 and E(x)=0 for steady states holds.

arguments:

primes: prime implicants
state: a state

returns:

energy: number of free variables in smallest trapspace containing state

example:

>>> primes = Repository.get_primes("raf")
>>> StateTransitionGraphs.energy(primes, "000")
1
>>> StateTransitionGraphs.energy(primes, "010")
3
>>> StateTransitionGraphs.energy(primes, "001")
0

htg2dot(htg: DiGraph, fname_dot: Optional[str] = None) → str¶

Creates a dot file of the HTG.

arguments:

HTG: HTG
fname_dot: name of dot file or None

returns:

text_dot: text content of dot file

example:

>>> htg2dot(cgraph, "mapk_htg.dot")

htg2image(htg: DiGraph, fname_image: str, layout_engine: str = 'dot')¶

Creates an image file from the HTG.

arguments:

HTG: HTG
fname_image: name of output file
layout_engine: one of “dot”, “neato”, “fdp”, “sfdp”, “circo”, “twopi”

example:

>>> htg2image(cgraph, "mapk_htg.pdf")

list_reachable_states(primes: dict, update: str, initial_states: List[str], memory: int)¶

Performs a depth-first search in the transition system defined by primes and update to list all states that are reachable from the inital states. Memory specifies the maximum number of states that can be kept in memory as “already explored” before the algorithm terminates.

arguments:

primes: prime implicants
update: update strategy (either asynchronous or snchronous)
initial_states: a list of initial states
memory: maximal number of states memorized before search is stopped

returns:

reachable_states: a list of all states explored

example:

>>> initial_states = ["1000", "1001"]
>>> update = "asynchronous"
>>> memory = 1000
>>> states = list_reachable_states(primes, update, initial_states, memory)
>>> print(len(states))
287

primes2stg(primes: dict, update: str, initial_states=<function <lambda>>) → DiGraph¶

Creates the state transition graph (STG) of a network defined by primes and update. The initial_states are either a list of states (in dict or str representation), a function that flags states that belong to the initial states, or a subspace (in dict or str representation). If initial_states is a function then it must take a single parameter state in dict representation and return a Boolean value that indicates whether it belongs to the initial states or not.

The STG is constructed by a depth first search (DFS) starting from the given initial states. The default for initial_states is lambda x: True, i.e., every state is initial. For a single initial state, say “100” use initial_states=”100”, for a set of initial states use initial_states=[“100”, “101”] and for a initial subspace use initial_states=”1–” or the dict representation of subspaces.

arguments:

primes: prime implicants
update: either “asynchronous” or “synchronous”
initial_states: a function, a subspace, a state or a list of states

returns:

stg: state transition graph

example:

>>> primes = FEX.read_primes("mapk.primes")
>>> update = "asynchronous"
>>> init = lambda x: x["ERK"]+x["RAF"]+x["RAS"]>=2
>>> stg = primes2stg(primes, update, init)

>>> stg.order()
32

>>> stg.edges()[0]
('01000','11000')

>>> init = ["00100", "00001"]
>>> stg = primes2stg(primes, update, init)

>>> init = {"ERK":0, "RAF":0, "RAS":0, "MEK":0, "p38":1}
>>> stg = primes2stg(primes, update, init)

random_successor_asynchronous(primes: dict, state: Union[dict, str]) → dict¶

Returns a random asynchronous successor of state in the transition system defined by primes.

arguments:

primes: prime implicants
state: a state

returns:

successor: a random asynchronous successor of state

random_successor_mixed(primes: dict, state: Union[dict, str]) → dict¶

Returns a random successor of state in the mixed transition system defined by primes. The mixed update contains the synchronous and asynchronous STGs but it also allows transitions in which an arbitrary number of unstable components (but at least one) are updated.

Note

The reason why this function returns a random mixed transition rather than all mixed successors is that there are up to 2^n mixed successors for a state (n is the number of variables).

arguments:

primes: prime implicants
state: a state

returns:

successor: a random successor of state using the mixed update

example:

>>> state = "100"
>>> random_successor_mixed(primes, state)
{'v1':1, 'v2':1, 'v3':1}

random_walk(primes: dict, update: str, initial_state: Union[dict, str], length: int)¶

Returns a random walk of length many states in the transition system defined by primes and update starting from a state defined by initial_state. If initial_state is a subspace then random_state will be used to draw a random state from inside it.

arguments:

primes: prime implicants
update: the update strategy, one of “asynchronous”, “synchronous”, “mixed”
initial_state: an initial state or subspace
length: length of the random walk

returns:

path: sequence of states

example:

>>> path = random_walk(primes, "asynchronous", "11---0", 4)

sccgraph2dot(scc_graph: DiGraph, fname_dot: Optional[str] = None)¶

Creates a dot file from a SCC graph.

arguments:

scc_graph: state transition graph
fname_dot: name of dot file or None

returns:

text_dot: file as string if not FnameDOT is None, otherwise it returns None

example:

>>> sccgraph2dot(sccg, "sccgraph.dot")

sccgraph2image(scc_graph: DiGraph, fname_image: str, layout_engine: str = 'dot')¶

Creates an image file from a SCC graph.

arguments:

scc_graph: SCC graph
fname_image: name of output file
layout_engine: one of “dot”, “neato”, “fdp”, “sfdp”, “circo”, “twopi”

example:

>>> sccgraph2image(sccgraph, "mapk_sccgraph.pdf")

stg2condensationgraph(stg: DiGraph) → DiGraph¶

Converts the stg into the condensation graph, for a definition see Klarner2015(b).

arguments:

stg: state transition graph

returns:

cgraph: the condensation graph of stg

example:

>>> cgraph = stg2condensationgraph(stg)

stg2dot(stg: DiGraph, fname_dot: Optional[str] = None) → str¶

Creates a dot file from a state transition graph. Graph, node and edge attributes are passed to the dot file by adding the respective key and value pairs to the graph, node or edge data. Node and edge defaults are set by the specials graph keys “node” and “edge” and must have attribute dictionaries as values. For a list of attributes see http://www.graphviz.org/doc/info/attrs.html.

arguments:

stg: state transition graph
fname_dot: name of dot file or None

returns:

text_dot: content of dot file

example:

>>> stg = primes2stg(primes, update, init)
>>> stg.graph["label"] = "IRMA Network - State Transition Graph"
>>> stg.graph["node"] = {"style":"filled", "color":"red"}
>>> stg.graph["edge"] = {"arrowsize": 2.0}
>>> stg.nodes["001000"]["fontsize"] = 20
>>> stg.adj["001110"]["001010"]["style"] = "dotted"
>>> stg2image(stg, "irma_stg.pdf")

stg2htg(stg: DiGraph)¶

Computes the HTG of the stg. For a definition see Berenguier2013.

arguments:

stg: state transition graph

returns:

htg: the HTG of stg

example:

>>> htg = stg2htg(stg)

stg2image(stg: DiGraph, fname_image: str, layout_engine: str = 'fdp')¶

Creates an image file from a state transition graph using Graphviz and the layout_engine. Use dot -T? to find out which output formats are supported on your installation.

arguments:

stg: state transition graph
fname_image: name of output file
layout_engine: one of “dot”, “neato”, “fdp”, “sfdp”, “circo”, “twopi”

example:

>>> stg2image(stg, "mapk_stg.pdf")
>>> stg2image(stg, "mapk_stg.jpg", "neato")
>>> stg2image(stg, "mapk_stg.svg", "dot")

stg2sccgraph(stg: DiGraph) → DiGraph¶

Computes the SCC graph of the stg. For a definition see Sec. 3.1 of Tournier2009.

arguments:

stg: state transition graph

returns:

scc_graph: the SCC graph of stg

example:

>>> sccgraph = stg2sccgraph(stg)

successor_synchronous(primes: dict, state: Union[dict, str]) → dict¶

Returns the successor of state in the fully synchronous transition system defined by primes. See Klarner2015(b) Sec. 2.2 for a formal definition.

arguments:

primes: prime implicants
state: a state

returns:

successor: the synchronous successor of state

example::

>>> primes = {
'v1': [[{'v2': 0}], [{'v2': 1}]],
'v2': [[{'v3': 0}, {'v1': 0}], [{'v1': 1, 'v3': 1}]],
'v3': [[{'v1': 1, 'v2': 0}], [{'v2': 1}, {'v1': 0}]]
}
>>> state = "100"
>>> successor_synchronous(primes, state)
{'v1': 0, 'v2': 0, 'v3': 0}

successors_asynchronous(primes: dict, state: Union[dict, str]) → List[dict]¶

Returns the successors of state in the fully asynchronous transition system defined by primes. See Klarner2015(b) Sec. 2.2 for a formal definition.

arguments:

primes: prime implicants
state: a state

returns:

successors: the asynchronous successors of state

example::

>>> primes = {
'v1': [[{'v2': 0}], [{'v2': 1}]],
'v2': [[{'v3': 0}, {'v1': 0}], [{'v1': 1, 'v3': 1}]],
'v3': [[{'v1': 1, 'v2': 0}], [{'v2': 1}, {'v1': 0}]]}
>>> state = "101"
>>> successors_asynchronous(primes, state)
[{'v1': 0, 'v2': 0, 'v3': 1}, {'v1': 1, 'v2': 1, 'v3': 1}, {'v1': 1, 'v2': 0, 'v3': 0}]

successors_mixed(primes: dict, state: Union[dict, str]) → List[dict]¶

Returns the successors of state in the mixed transition system defined by primes. The mixed update contains the synchronous and asynchronous STGs but it also allows transitions in which an arbitrary number of unstable components (but at least one) are updated.

Note

There are up to 2^n mixed successors for a state (n is the number of variables).

arguments:

primes: prime implicants
state: a state

returns:

successors: the mixed successors of state

example::

>>> primes = {
'v1': [[{'v2': 0}], [{'v2': 1}]],
'v2': [[{'v3': 0}, {'v1': 0}], [{'v1': 1, 'v3': 1}]],
'v3': [[{'v1': 1, 'v2': 0}], [{'v2': 1}, {'v1': 0}]]
}
>>> state = "010"
>>> successors_mixed(primes, state)
[{'v1': 1, 'v2': 1, 'v3': 0},
 {'v1': 0, 'v2': 0, 'v3': 0},
 {'v1': 0, 'v2': 1, 'v3': 1},
 {'v1': 1, 'v2': 0, 'v3': 0},
 {'v1': 1, 'v2': 1, 'v3': 1},
 {'v1': 0, 'v2': 0, 'v3': 1},
 {'v1': 1, 'v2': 0, 'v3': 1}]