symbolic_dynamics.sofic.get_follower_equivalences

symbolic_dynamics.sofic.get_follower_equivalences(G)[source]

Gets the follower-equivalences of G.

In a deterministic labeled graph G, two vertices p and q are follower-equivalent if there is no word w such that dot(G, p, w) and dot(G, q, w) are not both None.

Returns a pair of dicts representing a partition of G, where two states are follower-equivalent iff they are in the same part of the partition.

Parameters
Gdeterministic label graph
Returns
partsdict

maps each part number to a part of the partition

part_lookupdict

maps each vertex of G to a part number

See also

is_follower_separated()
reduce()

Examples

>>> G = nx.MultiDiGraph()
>>> G.add_edge(1, 3, label="a")
>>> G.add_edge(2, 3, label="a")
>>> G.add_edge(1, 1, label="b")
>>> G.add_edge(2, 2, label="b")
>>> G.add_edge(3, 3, label="b")
>>> parts, part_lookup = sd.get_follower_equivalences(G)
>>> parts
{0: {1, 2}, 2: {3}}
>>> part_lookup
{1: 0, 3: 2, 2: 0}