Re: Check for cycles in context defs - any length

[Han-Wen Nienhuys]

2007/11/17, Rune Zedeler <address@hidden>:
> (assuming you took this off the list on purpose)

No, on accident actually.

> > No, it's better that we don't do this. If you need marking of some
> > sort, pass a set<Context_def*> into the function. It would be even
> > nicer to do without, but I'm not sure if it is possible in this case,
> > but see
> >
> >   http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm
>
> Problem is that floyd's is meant for graphs where each node only has one
> outgoing edge. If nodes have more than one edge then the algorithm explodes.
>
> A totally different approach would be to simply mark cyclic contexts in
> engraver-init.ly. That is - StaffGroup and ChoirStaff must be marked as
> being cyclic. Furthermore we must require that all contexts that accept
> cyclic contexts also must accept anything that the cyclic context
> accepts. I.e. if Foo accepts StaffGroup and StaffGroup accepts Bar then
> Foo must also accept Bar.
> This way we can simply skip the cyclic contexts in
> Context_def::path_to_acceptable_context

I don't think that will work. We can change all these definitions on
the fly using

  \with {
    \accepts ..

  }


Even if this might not be working right now, but it should be in the future.

I think that you it will be trivially easy to use a set<> iso. writing
into the Context_def.   Modifying read-only data is a no, because it
will make our lives much more difficult if we ever want to share data
between different executions (eg. threading.)

> Perhaps we could even do this automatically during startup - doing one
> test for cyclic contexts is acceptable - doing it each time
> path_to_acceptable_context is called is not.

-- 
Han-Wen Nienhuys - address@hidden - http://www.xs4all.nl/~hanwen