Class: Stamina::Automaton

Inherits:
Object
  • Object
show all
Includes:
Walking, Classifier, Markable
Defined in:
lib/stamina/automaton.rb,
lib/stamina/automaton/walking.rb

Overview

Automaton data-structure.

Examples

The following example uses a lot of useful DRY shortcuts, so, if it does not fit you needs then, read on!):

# Building an automaton for the regular language a(ba)*
fa = Automaton.new do
  add_state(:initial => true)
  add_state(:accepting => true)
  connect(0,1,'a')
  connect(1,0,'b')
end

# It accepts 'a b a b a', rejects 'a b' as well as ''
puts fa.accepts?('? a b a b a')   # prints true
puts fa.accepts?('? a b')         # prints false
puts fa.rejects?('?')            # prints true

Four things you need to know

  1. Automaton, State and Edge classes implement a Markable design pattern, that is, you can read and write any key/value pair you want on them using the [] and []= operators. Note that the following keys are used by Stamina itself, with the obvious semantics (for automata and transducers):

    • :initial, :accepting, :error on State; expected to be true or false (nil and ommitted are considered as false). Shortcuts for querying and setting these attributes are provided by State.

    • :symbol on Edge, with shortcuts as well on Edge. The convention is to use nil for the epsilon symbol (aka non observable) on non deterministic automata.

    The following keys are reserved for future extensions:

    • :output on State and Edge.

    • :short_prefix on State.

    See also the “About states and edges” subsection of the design choices.

  2. Why using State methods State#step and State#delta ? The Automaton class includes the Walking module by default, which is much more powerful !

  3. The constructor of this class executes the argument block (between do and end) with instance_eval by default. You won’t be able to invoke the methods defined in the scope of your block in such a case. See new for details.

  4. This class has not been designed with efficiency in mind. If you experiment performance problems, read the “About Automaton modifications” sub section of the design choices.

Design choices

This section fully details the design choices that has been made for the implementation of the Automaton data structure used by Stamina. It is provided because Automaton is one of the core classes of Stamina, that probably all users (and contributors) will use. Automaton usage is really user-friendly, so you are normally not required to read this section in the first place ! Read it only if of interest for you, or if you experiment unexpected results.

One Automaton class only

One class only implements all kinds of automata: deterministic, non-deterministic, transducers, prefix-tree-acceptors, etc. The Markable design pattern on states and edges should allow you to make anything you could find useful with this class.

Adjacency-list graph

This class implements an automaton using a adjacent-list graph structure. The automaton has state and edge array lists and exposes them through the states and edges accessors. In order to let users enjoy the enumerability of Ruby’s arrays while allowing automata to be modified, these arrays are externaly modifiable. However, users are not expected to modify them! and future versions of Stamina will certainly remove this ability.

Indices exposed

State and Edge indices in these arrays are exposed by this class. Unless stated explicitely, all methods taking state or edge arguments support indices as well. Moreover, ith_state, ith_states, ith_edge and ith_edges methods provide powerful access to states and edges by indices. All these methods are robust to invalid indices (and raise an IndexError if incorrectly invoked) but do not allow negative indexing (unlike ruby arrays).

States and edges know their index in the corresponding array and expose them through the (read-only) index accessor. These indices are always valid; without deletion of states or edges in the automaton, they are guaranteed not to change. Indices saved in your own variables must be considered deprecated each time you perform a deletion ! That’s the only rule to respect if you plan to use indices.

Indices exposition may seem a strange choice and could be interpreted as breaking OOP’s best practice. You are not required to use them but, as will quiclky appear, using them is really powerful and leads to beautiful code! If you don’t remove any state or edge, this class guarantees that indices are assigned in the same order as invocations of add_state and add_edge (as well as their plural forms and aliases).

About states and edges

Edges know their source and target states, which are exposed through the source and target (read-only) accessors (also aliased as from and to). States keep their incoming and outgoing edges in arrays, which are accessible (in fact, a copy) using State#in_edges and State#out_edges. If you use them for walking the automaton in a somewhat standard way, consider using the Walking module instead!

Common attributes of states and edges are installed using the Markable pattern itself:

  • :initial, :accepting and :error on states. These attributes are expected to be true or false (nil and ommitted are also supported and both considered as false).

  • :symbol on edges. Any object you want as long as it responds to the <=> operator. Also, the convention is to use nil for the epsilon symbol (aka non observable) on non deterministic automata.

In addition, useful shortcuts are available:

  • s.initial? is a shortcut for s[:initial] if s is a State

  • s.initial! is a shortcut for s[:initial]=true if s is a State

  • Similar shortcuts are available for :accepting and :error

  • e.symbol is a shortcut for e[:symbol] if e is an Edge

  • e.symbol='a' is a shortcut for e[:symbol]='a' if e is an Edge

Following keys should be considered reserved by Stamina for future extensions:

  • :output on State and Edge.

  • :short_prefix on State.

About Automaton modifications

This class has not been implemented with efficiency in mind. In particular, we expect the vast majority of Stamina core algorithms considering automata as immutable values. For this reason, the Automaton class does not handle modifications really efficiently.

So, if you experiment performance problems, consider what follows:

  1. Why updating an automaton ? Building a fresh one is much more clean and efficient ! This is particularly true for removals.

  2. If you can create multiples states or edges at once, consider the plural form of the modification methods: add_n_states and drop_states. Those methods are optimized for multiple updates.

Detailed API

Defined Under Namespace

Modules: Walking Classes: Edge, State

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Classifier

#correctly_classify?, #signature

Methods included from Walking

#accepts?, #delta, #dfa_delta, #dfa_reached, #dfa_split, #dfa_step, #label_of, #parses?, #reached, #rejects?, #split, #step

Methods included from Markable

#[], #[]=, #data, #remove_mark

Constructor Details

#initialize(onself = true, &block) ⇒ Automaton

Creates an empty automaton and executes the block passed as argument. The onself argument dictates the way block is executed:

  • when set to false, the block is executed traditionnally (i.e. using yield). In this case, methods invocations must be performed on the automaton object passed as block argument.

  • when set to true (by default) the block is executed in the context of the automaton itself (i.e. with instance_eval), allowing call of its methods without prefixing them by the automaton variable. The automaton still passes itself as first block argument. Note that in this case, you won’t be able to invoke a method defined in the scope of your block.

Example:

# The DRY way to do:
Automaton.new do |automaton|     # automaton will not be used here, but it is passed
  add_state(:initial => true)
  add_state(:accepting => true) 
  connect(0, 1, 'a')             
  connect(1, 0, 'b')

  # method_in_caller_scope()     # commented because not allowed here !!
end

# The other way:
Automaton.new(false) do |automaton|      # automaton MUST be used here
  automaton.add_state(:initial => true)
  automaton.add_state(:accepting => true) 
  automaton.connect(0, 1, 'a')             
  automaton.connect(1, 0, 'b')

  method_in_caller_scope()               # allowed in this variant !!
end



546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
 
# File 'lib/stamina/automaton.rb', line 546

def initialize(onself=true, &block) # :yields: automaton
  @states = []
  @edges = []
  @initials = nil
  @alphabet = nil
  @deterministic = nil

  # if there's a block, execute it now!
  if block_given?
    if onself
      if RUBY_VERSION >= "1.9.0"
        instance_exec(self, &block)
      else
        instance_eval(&block)
      end
    else
      block.call(self)
    end
  end
end

Instance Attribute Details

#edges ⇒ Object (readonly)

State list and edge list of the automaton



511
512
513
 
# File 'lib/stamina/automaton.rb', line 511

def edges
  @edges
end

#states ⇒ Object (readonly)

State list and edge list of the automaton



511
512
513
 
# File 'lib/stamina/automaton.rb', line 511

def states
  @states
end

Instance Method Details

#add_automaton(what, clear_names = true) ⇒ Object

Adds all states and transitions (as copies) from a different automaton. Returns the initial state of the added part. In order to ensure that names of the new states do not clash with names of existing states, state names may have to be removed from added states; this is the case if clear_names is set to true. None of the added states are made initial.



881
882
883
884
885
886
887
888
889
890
891
892
 
# File 'lib/stamina/automaton.rb', line 881

def add_automaton(what,clear_names=true)
  map_what_self = {}
  what.states.each do |state|
    map_what_self[state]=add_state(state.data)
    map_what_self[state][:name]=nil if clear_names
    map_what_self[state][:initial]=false
  end
  what.edges.each do |edge|
    add_edge(map_what_self[edge.from],map_what_self[edge.to],edge.data)
  end
  map_what_self[what.initial_state]
end

#add_edge(from, to, data) ⇒ Object Also known as: create_edge, connect

Adds a new edge, connecting from and to states of the automaton.

Arguments:

  • from: either a State or a valid state index (Integer).

  • to: either a State or a valid state index (Integer).

  • data: user data to attach to the created edge (see Automaton documentation).

Raises:

  • IndexError if from is an Integer but not in [0..state_count)

  • IndexError if to is an Integer but not in [0..state_count)

  • ArgumentError if from is not a valid state for this automaton.

  • ArgumentError if to is not a valid state for this automaton.

  • ArgumentError if data is not a valid edge data.



858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
 
# File 'lib/stamina/automaton.rb', line 858

def add_edge(from, to, data)
  from, to, data = to_state(from), to_state(to), to_valid_edge_data(data)

  # create edge, install it, add it to edge-list
  edge = Edge.new(self, edge_count, data, from, to)
  @edges << edge
  from.send(:add_outgoing_edge, edge)
  to.send(:add_incoming_edge, edge)

  # let automaton know that something has changed
  state_changed(:edge_added, edge)

  # return created edge
  edge
end

#add_n_states(n, data = {}) ⇒ Object Also known as: create_n_states

Adds n new states in the automaton. Created states are returned as an ordered array (order of states according to their index in state list).

data is duplicated for each created state.



834
835
836
837
838
839
840
 
# File 'lib/stamina/automaton.rb', line 834

def add_n_states(n, data={})
  created = []
  n.times do |i|
    created << add_state(data.dup)
  end
  created
end

#add_state(data = {}) ⇒ Object Also known as: create_state

Adds a new state.

Arguments:

  • data: user-data to attach to the state (see Automaton documentation).

Raises:

  • ArgumentError if data is not a valid state data.



813
814
815
816
817
818
819
820
821
822
823
824
825
 
# File 'lib/stamina/automaton.rb', line 813

def add_state(data={})
  data = to_valid_state_data(data)

  # create new state, add it to state-list
  state = State.new(self, state_count, data)
  @states <<  state

  # let the automaton know that something has changed
  state_changed(:state_added, state)

  # return created state
  state
end

#adjacent_states(state) ⇒ Object

Returns an array with adjacent states (along incoming and outgoing edges) of state. Returned array does not contain duplicates; it may be modified.

If state is an Integer, this method returns the adjacent states of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state (not a state or not from this automaton)



738
 
# File 'lib/stamina/automaton.rb', line 738

def adjacent_states(state) to_state(state).adjacent_states() end

#alphabet ⇒ Object

Returns the alphabet of the automaton.



1123
1124
1125
 
# File 'lib/stamina/automaton.rb', line 1123

def alphabet
  @alphabet || deduce_alphabet
end

#alphabet=(alph) ⇒ Object

Sets the aphabet of the automaton. alph is expected to be an array without nil nor duplicated. This method raises an ArgumentError otherwise. Such an error is also raised if a symbol used on the automaton edges is not included in alph.

Raises:

  • (ArgumentError) 


1131
1132
1133
1134
1135
 
# File 'lib/stamina/automaton.rb', line 1131

def alphabet=(alph)
  raise ArgumentError, "Invalid alphabet" unless alph.uniq.compact.size==alph.size
  raise ArgumentError, "Invalid alphabet" unless deduce_alphabet.reject{|s| alph.include?(s)}.empty?
  @alphabet = alph.sort
end

#deterministic? ⇒ Boolean

Returns true if the automaton is deterministic, false otherwise

Returns:

  • (Boolean) 


1107
1108
1109
1110
 
# File 'lib/stamina/automaton.rb', line 1107

def deterministic?
  @deterministic = @states.reject{|s| s.deterministic?}.empty? if @deterministic.nil?
  @deterministic
end

#drop_edge(edge) ⇒ Object Also known as: delete_edge

Drops an edge in the automaton. If edge is an integer, the edge-th edge of the edge list is removed. This method returns the automaton itself.

Raises:

  • IndexError if edge is an Integer but not in [0..edge_count)

  • ArgumentError if edge is not a valid edge for this automaton.



980
981
982
983
984
985
986
987
988
989
990
991
 
# File 'lib/stamina/automaton.rb', line 980

def drop_edge(edge)
  edge = to_edge(edge)
  @edges.delete_at(edge.index)
  edge.from.send(:drop_outgoing_edge,edge)
  edge.to.send(:drop_incoming_edge,edge)
  edge.index.upto(edge_count-1) do |i|
    @edges[i].send(:index=, i)
  end
  edge.send(:index=,-1)
  state_changed(:edge_dropped, edge)
  self
end

#drop_edges(*edges) ⇒ Object Also known as: delete_edges

Drops all edges passed as parameters. Arguments may be edge objects, as well as valid edge indices. Duplicates are even supported. This method has no effect on the automaton and raises an error if some edge argument is not valid.

Raises:

  • ArgumentError if one edge in edges is not a valid edge of this automaton.



1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
 
# File 'lib/stamina/automaton.rb', line 1003

def drop_edges(*edges)
  # check edges first
  edges = edges.collect{|e| to_edge(e)}.uniq

  # remove all edges
  edges.each do |e|
    @edges.delete(e)
    e.from.send(:drop_outgoing_edge,e)
    e.to.send(:drop_incoming_edge,e)
    e.send(:index=, -1)
    state_changed(:edge_dropped, e)
  end
  @edges.each_with_index do |e,i|
    e.send(:index=,i)
  end

  self
end

#drop_state(state) ⇒ Object Also known as: delete_state

Drops a state of the automaton, as well as all connected edges to that state. If state is an integer, the state-th state of the state list is removed. This method returns the automaton itself.

Raises:

  • IndexError if edge is an Integer but not in [0..edge_count)

  • ArgumentError if edge is not a valid edge for this automaton.



913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
 
# File 'lib/stamina/automaton.rb', line 913

def drop_state(state)
  state = to_state(state)
  # remove edges first: drop_edges ensures that edge list is coherent
  drop_edges(*(state.in_edges + state.out_edges).uniq)

  # remove state now and renumber
  @states.delete_at(state.index)
  state.index.upto(state_count-1) do |i|
    @states[i].send(:index=, i)
  end
  state.send(:index=, -1)

  state_changed(:state_dropped, state)
  self
end

#drop_states(*states) ⇒ Object

Drops all states passed as parameter as well as all their connected edges. Arguments may be state instances, as well as valid state indices. Duplicates are even supported. This method has no effect on the automaton and raises an error if some state argument is not valid.

Raises:

  • ArgumentError if one state in states is not a valid state of this automaton.



940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
 
# File 'lib/stamina/automaton.rb', line 940

def drop_states(*states)
  # check states first
  states = states.collect{|s| to_state(s)}.uniq.sort
  edges  = states.collect{|s| (s.in_edges + s.out_edges).uniq}.flatten.uniq.sort

  # Remove all edges, we do not use drop_edges to avoid spending too much 
  # time reindexing edges. Moreover, we can do it that way because we take 
  # edges in reverse indexing order (has been sorted previously)
  until edges.empty?
    edge = edges.pop
    edge.source.send(:drop_outgoing_edge,edge)
    edge.target.send(:drop_incoming_edge,edge)
    @edges.delete_at(edge.index)
    edge.send(:index=, -1)
    state_changed(:edge_dropped, edge)
  end

  # Remove all states, same kind of hack is used
  until states.empty?
    state = states.pop
    @states.delete_at(state.index)
    state.send(:index=, -1)
    state_changed(:state_dropped, state)
  end

  # sanitize state and edge lists
  @states.each_with_index {|s,i| s.send(:index=,i)}
  @edges.each_with_index {|e,i| e.send(:index=,i)}

  self
end

#dup ⇒ Object

Constructs a replica of this automaton and returns a copy. This copy can be modified in whatever way without affecting the original automaton.



897
898
899
900
901
902
 
# File 'lib/stamina/automaton.rb', line 897

def dup
  Automaton.new(false) do |fa|
    initial = fa.add_automaton(self,false)
    initial[:initial] = true unless initial.nil?
  end
end

#each_edge ⇒ Object

Calls block for each edge of the automaton edge list. Edges are enumerated in index order.



666
 
# File 'lib/stamina/automaton.rb', line 666

def each_edge() @edges.each {|e| yield e if block_given?} end

#each_state ⇒ Object

Calls block for each state of the automaton state list. States are enumerated in index order.



660
 
# File 'lib/stamina/automaton.rb', line 660

def each_state() @states.each {|s| yield s if block_given?} end

#edge_count ⇒ Object

Returns the number of edges



588
 
# File 'lib/stamina/automaton.rb', line 588

def edge_count() @edges.size end

#get_state(name) ⇒ Object

Returns state associated with the supplied state name, throws an exception if no such state can be found.

Raises:

  • (ArgumentError) 


608
609
610
611
612
613
614
615
616
617
 
# File 'lib/stamina/automaton.rb', line 608

def get_state(name)
  raise(ArgumentError, "String expected, #{name} found.", caller)\
    unless String === name
    result = states.find do |s|
      name == s[:name]
    end
  raise(ArgumentError, "State #{name} was not found", caller)\
    if result.nil?
  result
end

#in_adjacent_states(state) ⇒ Object

Returns an array with adjacent states (along incoming edges) of state. Returned array does not contain duplicates; it may be modified.

If state is an Integer, this method returns the incoming adjacent states of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state (not a state or not from this automaton)



752
 
# File 'lib/stamina/automaton.rb', line 752

def in_adjacent_states(state) to_state(state).in_adjacent_states() end

#in_edges(state, sorted = false) ⇒ Object

Returns an array with incoming edges of state. Edges are sorted by symbols if sorted is set to true. If two incoming edges have same symbol, no order is guaranteed between them. Returned array may be modified.

If state is an Integer, this method returns the incoming edges of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state for this automaton.



680
 
# File 'lib/stamina/automaton.rb', line 680

def in_edges(state, sorted=false) to_state(state).in_edges(sorted) end

#in_symbols(state, sorted = false) ⇒ Object

Returns an array with the different symbols appearing on incoming edges of state. Returned array does not contain duplicates and may be modified; it is sorted if sorted is set to true.

If state is an Integer, this method returns the incoming symbols of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state for this automaton.



709
 
# File 'lib/stamina/automaton.rb', line 709

def in_symbols(state, sorted=false) to_state(state).in_symbols(sorted) end

#initial_state ⇒ Object

Returns the initial state of the automaton. This method is expected to used on deterministic automata only. Unlike initial_states, it returns one State

instance instead of an Array.

When used with a non deterministic automaton, it returns one of the states tagged as initial. Which one is returned must be considered a non deterministic choice. This method is not epsilon symbol aware.



791
792
793
 
# File 'lib/stamina/automaton.rb', line 791

def initial_state
  initial_states[0]
end

#initial_states ⇒ Object

Collects all initial states of this Automaton and returns it. Returned array does not contain duplicates and may be modified.

This method is epsilon symbol aware (represented with nil) on non-deterministic automata, meaning that it actually computes the set of reachable states from an initial state through strings respecting the eps* regular expression, where eps is the epsilon symbol.



777
778
779
780
 
# File 'lib/stamina/automaton.rb', line 777

def initial_states
  @initials = compute_initial_states if @initials.nil? or @initials.empty?
  @initials
end

#ith_edge(i) ⇒ Object

Returns the i-th edge of the edge list.

Raises:

  • ArgumentError unless i is an Integer

  • IndexError if i is not in [0..state_count)

Raises:

  • (ArgumentError) 


637
638
639
640
641
642
643
 
# File 'lib/stamina/automaton.rb', line 637

def ith_edge(i)
  raise(ArgumentError, "Integer expected, #{i} found.", caller)\
    unless Integer === i
  raise(ArgumentError, "Invalid edge index #{i}", caller)\
    unless i>=0 and i<edge_count
  @edges[i]
end

#ith_edges(*i) ⇒ Object

Returns the i-th edges of the edge list.

Raises:

  • ArgumentError unless all i are integers

  • IndexError unless all i are in [0..edge_count)



652
653
654
 
# File 'lib/stamina/automaton.rb', line 652

def ith_edges(*i)
  i.collect{|j| ith_edge(j)}
end

#ith_state(i) ⇒ Object

Returns the i-th state of the state list.

Raises:

  • ArgumentError unless i is an Integer

  • IndexError if i is not in [0..state_count)

Raises:

  • (ArgumentError) 


597
598
599
600
601
602
603
 
# File 'lib/stamina/automaton.rb', line 597

def ith_state(i)
  raise(ArgumentError, "Integer expected, #{i} found.", caller)\
    unless Integer === i
  raise(ArgumentError, "Invalid state index #{i}", caller)\
    unless i>=0 and i<state_count
  @states[i]
end

#ith_states(*i) ⇒ Object

Returns the i-th states of the state list.

Raises:

  • ArgumentError unless all i are integers

  • IndexError unless all i are in [0..state_count)



626
627
628
 
# File 'lib/stamina/automaton.rb', line 626

def ith_states(*i)
  i.collect{|j| ith_state(j)}
end

#order_states(&block) ⇒ Object

Uses a comparator block to reorder the state list.

Raises:

  • (ArgumentError) 


1214
1215
1216
1217
1218
1219
1220
 
# File 'lib/stamina/automaton.rb', line 1214

def order_states(&block)
  raise ArgumentError, "A comparator block must be given" unless block_given?
  raise ArgumentError, "A comparator block of arity 2 must be given" unless block.arity==2
  @states.sort!(&block)
  @states.each_with_index{|s,i| s.send(:index=, i)}
  self
end

#out_adjacent_states(state) ⇒ Object

Returns an array with adjacent states (along outgoing edges) of state. Returned array does not contain duplicates; it may be modified.

If state is an Integer, this method returns the outgoing adjacent states of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state (not a state or not from this automaton)



766
 
# File 'lib/stamina/automaton.rb', line 766

def out_adjacent_states(state) to_state(state).out_adjacent_states() end

#out_edges(state, sorted = false) ⇒ Object

Returns an array with outgoing edges of state. Edges are sorted by symbols if sorted is set to true. If two incoming edges have same symbol, no order is guaranteed between them. Returned array may be modified.

If state is an Integer, this method returns the outgoing edges of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state (not a state or not from this automaton)



695
 
# File 'lib/stamina/automaton.rb', line 695

def out_edges(state, sorted=false) to_state(state).out_edges(sorted) end

#out_symbols(state, sorted = false) ⇒ Object

Returns an array with the different symbols appearing on outgoing edges of state. Returned array does not contain duplicates and may be modified; it is sorted if sorted is set to true.

If state is an Integer, this method returns the outgoing symbols of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state (not a state or not from this automaton)



724
 
# File 'lib/stamina/automaton.rb', line 724

def out_symbols(state, sorted=false) to_state(state).out_symbols(sorted) end

#state_count ⇒ Object

Returns the number of states



585
 
# File 'lib/stamina/automaton.rb', line 585

def state_count() @states.size end

#symbols_comparator ⇒ Object

Returns a symbols comparator taking epsilon symbols into account. Comparator is provided as Proc instance which is a lambda function.



574
575
576
577
578
579
580
581
582
 
# File 'lib/stamina/automaton.rb', line 574

def symbols_comparator
  @symbols_comparator ||= Kernel.lambda do |a,b|
    if a==b then 0
    elsif a.nil? then -1
    elsif b.nil? then 1
    else a <=> b
    end
  end
end

#to_dot(&rewriter) ⇒ Object

Generates a dot output from an automaton. The rewriter block takes two arguments: the first one is a Markable instance (graph, state or edge), the second one indicates which kind of element is passed (through :automaton, :state or :edge symbol). The rewriter is expected to return a hash-like object providing dot attributes for the element.

When no rewriter is provided, a default one is used by default, providing the following behavior:

  • on :automaton

    => “LR”

  • on :state

    => “doublecircle/circle” (following accepting?),

    :style => "filled",
:fillcolor => "green/red/white" (if initial?/error?/else, respectively)

  • on edge

    {:label => “#{edge.symbol}”}



1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
 
# File 'lib/stamina/automaton.rb', line 1179

def to_dot(&rewriter)
  unless rewriter
    to_dot do |elm, kind|
      case kind
        when :automaton
          {:rankdir => "LR"}
        when :state
          {:shape => (elm.accepting? ? "doublecircle" : "circle"),
           :style => "filled",
           :color => "black",
           :fillcolor => (elm.initial? ? "green" : (elm.error? ? "red" : "white"))}
        when :edge
          {:label => elm.symbol.nil? ? '' : elm.symbol.to_s}
      end
    end
  else
    buffer = "digraph G {\n"
    attrs = attributes2dot(rewriter.call(self, :automaton))
    buffer << "  graph [#{attrs}];\n"
    states.each do |s|
      attrs = attributes2dot(rewriter.call(s, :state))
      buffer << "  #{s.index} [#{attrs}];\n"
    end
    edges.each do |e|
      attrs = attributes2dot(rewriter.call(e, :edge))
      buffer << "  #{e.source.index} -> #{e.target.index} [#{attrs}];\n"
    end
    buffer << "}\n"
  end
end