18 Feb
2021
18 Feb
'21
7:40 a.m.
Hi there,
In a preprocessing step, I want to flush a few states from a TωA. The one
method that seems to be available is defrag_states, the description of
which having the expected semantics.
However, after defrag, it sometimes happens that the dst of some
transitions points to delete states (-1U). The code of defrag_states in
graph.hh removes the outgoing transitions of deleted states but does not
seem to flush the transitions *pointing to* deleted states—is this the
expected behavior?
Cheers,
M.
18 Feb
18 Feb
12:01 p.m.
Hi Michaël!
Michaël Cadilhac <michael(a)cadilhac.name> writes:
In a preprocessing step, I want to flush a few states
from a TωA.
The one method that seems to be available is defrag_states, the
description of which having the expected semantics.
The intend of this function is to help removing unused entries from the
state vector, to make it less fragmented. So far it's only used
on states that are unreachable, I guess we should make that clear in the
documentation. (For me, the name "defrag" evokes the similar process
on file systems, where we do not remove anything that is used.)
What one want to do with the incoming edge when removing a reachable
state might differ according to the context. For instance in the case
of an alternating automaton, if a removed state is part of the
destination set of a universal edge, we might want to remove the
universal edge altogether (as if the removed state had an empty
language), or might want to just remove this state from the destination
set (as if the removed state had a universal language). So I'd rather
build some more user-friendly interface above defrag_state() rather than
extend this helper function.
What would be a nice interface for you? Two iterators to specify a
range of states to remove? Another idea would be to have a method that
simply removes all the outgoing edges of one state, let's say
aut->kill_state(s), so that multiple states could be killed this way
before eventually calling aut->purge_dead_states() to remove them for
good.
The functions mask_keep_states() and mask_keep_accessible_states() seem
close to your need. They just don't work in place.
However, after defrag, it sometimes happens that the
dst of some
transitions points to delete states (-1U).
I'm tempted to throw an exception in this case, but the automaton
will already be in a sad state :-(
6:09 p.m.
Salut Pollux,
Thanks for the prompt reply, that's much appreciated.
I did have a feeling that I was abusing the method, given its
"semi-internal" status. :)
As for terminology, "defrag" didn't clearly indicate to me that it could
only remove unreachable states. I agree that it shouldn't "*remove
anything that is used*", but since we pass as argument a use-vector and a
number of used states, I thought that the notion of "being used" was taken
from these args.
In my use case, I compute a vector v of size num_states() via a fix point
algorithm and every position above a given threshold corresponds to a state
that I'd want flushed. In code, I was doing:
std::vector<unsigned> v = compute_fp (aut);
std::vector<unsigned> defrag (aut->num_states ());
unsigned used = 0, delta = 0;
for (size_t q = 0; q < aut->num_states(); ++q)
if (v[q] > threshold) {
delta++;
defrag[q] = -1;
}
else {
defrag[q] = q - delta;
used++;
}
aut->defrag_states (std::move (defrag), used);
(By the way, not sure why defrag_states insists on receiving an rvalue.)
This is certainly pandering to the oddity of erasing using defrag. I like
your kill_state + purge suggestion, it seems to be more robust and less
condition-dependent. It also leaves renumbering to the internals, which
feels saner.
Cheers,
M.
On Thu, Feb 18, 2021 at 5:01 AM Alexandre Duret-Lutz <adl(a)lrde.epita.fr>
wrote:
Hi Michaël!
Michaël Cadilhac <michael(a)cadilhac.name> writes:
In a preprocessing step, I want to flush a few
states from a TωA.
The one method that seems to be available is defrag_states, the
description of which having the expected semantics.
The intend of this function is to help removing unused entries from the
state vector, to make it less fragmented. So far it's only used
on states that are unreachable, I guess we should make that clear in the
documentation. (For me, the name "defrag" evokes the similar process
on file systems, where we do not remove anything that is used.)
What one want to do with the incoming edge when removing a reachable
state might differ according to the context. For instance in the case
of an alternating automaton, if a removed state is part of the
destination set of a universal edge, we might want to remove the
universal edge altogether (as if the removed state had an empty
language), or might want to just remove this state from the destination
set (as if the removed state had a universal language). So I'd rather
build some more user-friendly interface above defrag_state() rather than
extend this helper function.
What would be a nice interface for you? Two iterators to specify a
range of states to remove? Another idea would be to have a method that
simply removes all the outgoing edges of one state, let's say
aut->kill_state(s), so that multiple states could be killed this way
before eventually calling aut->purge_dead_states() to remove them for
good.
The functions mask_keep_states() and mask_keep_accessible_states() seem
close to your need. They just don't work in place.
However, after defrag, it sometimes happens that
the dst of some
transitions points to delete states (-1U).
I'm tempted to throw an exception in this case, but the automaton
will already be in a sad state :-(
1594
days inactive
1594
days old
2 comments
2 participants
participants (2)
-
Alexandre Duret-Lutz -
Michaël Cadilhac