Sequence and/or pattern matching

[Mike Meyer]

"Séb" <scapt at unil.ch> writes:
>> Essentially, if I understand correctly, you want to detect LOOPS given a
>> sequence of directed connections A->B.  "loop detection" and "graph"
>> would then be the keywords to search for, in this case.
>
> Exactly, but the sequence has to be discovered by the piece of code !
>
>> Does this "then" imply you're only interested in loops occurring in this
>> *sequence*, i.e., is order of connections important?  If the sequence of
>> directed connections was, say, in the different order:
>>
>> B->C
>> A->B
>> C->A
>>
>> would you want this detected as a loop, or not?
>
> Yes, it would be nice to detect it as a loop, with for example a
> threshold. Btw, it would be nice to ignore additional connections in
> such a way :
>
> B->C # Normal connection
> D->E # Additional connection to ignore
> A->B # Normal connection
> C->A # Normal connection
>
> Would it be possible ?

As Ben Sizer pointed out, this is a fairly well-known graph
algorithm. You just want to add information to add ordering
information to each edge, so you can verify that the an edge that is
further down the path is "older" than the last edge added. Given your
ordering requirement, simply numbering the edges and checking that the
"older" edge has a larger number than the previous edge should do.

With my admin hat on, I have to wonder - don't you really want to deal
with duration? I.e - each connection has a "start" and "end" time, and
you're really only interested in paths that happen while all the
connections actually exist? Just a wild ass guess, mind you. However,
it doesn't radically change the test. You now tag each edge with a
start and stop time, and check that all previous edges on the path
exist while the one you are adding exists.

        <mike
-- 
Mike Meyer <mwm at mired.org>			http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.