Re: FYI: CSS3 modules dependencies graph

On Thursday 17 March 2005 16:54, Dominique Hazaël-Massieux wrote:
> Le jeudi 17 mars 2005 à 16:45 +0100, Bert Bos a écrit :
> > Can your tool output just the topological sort of the dependencies
>
> I'm sorry, I don't understand what this means.

There is a standard algorithm in computer science to sort a group of 
objects into one linear sequence, based on a set of pairwise relations 
between the objects. Say you have a set of objects {a, b, c, d, e} and 
relations such as 

    a must-come-after b
    a must-come-after c
    d must-come-after e
    etc.

then you can derive a sequence in which every object comes after all the 
objects it must come after, according to the given relations. E.g., e d 
c b a.

Of course, this assumes there are no cycles. Also, there may be more 
than one solution. (c b a d e works, too.)

Such a set of pairwise relations is a partial ordering (we only know the 
relations between certain pairs, not between all pairs), as opposed to 
a full ordering (we know the relation between any arbitrary pair). Our 
CSS modules are (hopefully) an example of a partial ordering. Natural 
numbers are an example of a set with a full ordering.

If the algorithm yields a sequence in this case, we know (1) that we 
have no cyclic dependencies and (2) a publication schedule that 
guarantees that no module is published after its dependents.

In fact, the RDF validator has an option to try and orient all arrows in 
one direction. Doing so shows that there are arrows in the wrong 
direction. In other words: there are cycles. Oh well...

(E.g., Selectors depends on UI, which depends on Color, which depends on 
Syntax, which depends on Selectors.)

>
> >  (or
> > arrange the graph so that all arrows point in roughly the same
> > direction)?
>
> The tool used to build the graph is "dot", which has many more
> options than I know; if you want to investigate this, the input file
> for the said tool is on the Web at:
> http://www.w3.org/2005/03/css-dep/css3deps.dot

Our server thinks a .dot file is a Microsoft Word file :-)

>
> (it was generated from the RDF validator output based on
> http://www.w3.org/2005/03/css-dep/css3deps.rdf and then hand massaged
> to make the image a bit nicer - but I'm sure someone knowing dot
> syntax/capabilities could get better results)
>
> Dom


Bert
-- 
  Bert Bos                                ( W 3 C ) http://www.w3.org/
  http://www.w3.org/people/bos                               W3C/ERCIM
  bert@w3.org                             2004 Rt des Lucioles / BP 93
  +33 (0)4 92 38 76 92            06902 Sophia Antipolis Cedex, France

Received on Thursday, 17 March 2005 17:01:58 UTC