Re: query that Bob is descendant of Alice

>If there's a fixed set of bad_guys, do a depth-first search
>in reverse from that set to mark the set of nodes from which
>you can reach a bad_guy.  Then, for each good_guy you are
>worried about, you can check whether this good_guy is marked
>in O(1) time.  This takes a total of O(|V|+|E|) time.
>
>-- David

Bingo! Except, I was talking about set of pairs, not pair of sets. You solved easy version. I think I will be better telling you more. My original post was incomplete just to simplify things a bit.

I am going to do statistics and mass manipulation of source, configuration and structured data files. This means not one, but infinite number of possible operations. Before actualy doing anything, I tried to outline resources/algorithms I will need. During this, I stumbled into class of problems, that do deep search of graphs. The problem is not so much, that many are expensive, but that I have hard time predicting their properties (and finding red line between expensive ones and cheap ones) and expressing them in terms of basic algorithms. I was talking about set of pairs example, because it is most general and most painful problem.

Anyway, below is small list of questions/queries I could possibly ask. Don't read them all, only those which interest you. Please, help me with things I ask below them.

Note, I talk about transitive closure issue in other post.

Format:
(#) description (optional)

    logic/calculus expression (uncomputable)     program/algebra expression (computable)     notes (optional)

Legend:
<a,b> cond(a,b) : result is table/set with all a,b,

          that satisfy condition cond(a,b) G,G1 : graph (ie call tree)
G' : transitive closure of G
A,B,P : tables; use as A(x), P(a,b)
*,+,- : set intersection, union, difference RESTRICT(T,n) : returns n-th column of T

1. Quadratic
   (1) <a,b> P(a,b) & G'(a,b)
   P * G' >>>>This is my original question.<<<<
   (2) <bool> EXISTS ab: P(a,b) & G'(a,b)
   P * G' != 0
   (3) <bool> FORALL ab: P(a,b) -> G'(a,b)
   P SUBSET G'
   (4) <a> EXISTS b: P(a,b) & G'(a,b)
   RESTRICT( P * G', 1 )
   (5) <a,b> G1(a,b) & NOT G2'(a,b)
   G1 - G2'
   (6) <a,b> A(a) & B(b) & G'(a,b)
   ??? Should be linear to size of result, I think.
   (7) Others ...
   

Very bad, I need to transform these into linear algos. Note that all expressions with G' are automatically quadratic.

B) Linear
(1) <b> G'(a,b)

    walking graph from a to bottom
    I'll call it descendants(G,a).
(1b) <a> G'(a,b)

    Reverse of (1), ancestors(G,b).
(1c) <b> EXISTS a: A(a) & G'(a,b)

    walking graph
    Group version of (1), descendants(G,A).
(3) <bool> EXISTS ab: A(a) & B(b) & G'(a,b)

    descendants(G,A) * ancestors(G,B) != 0     David Wagner sent solution by email.
(4) <bool> FORALL ab: A(a) & B(b) -> G'(a,b)

    B SUBSET descendants(G,A) & A SUBSET ancestors(G,B)
(5) <a> A(a) & ( EXISTS b: B(b) & G'(a,b) )

    A * ancestors(G,B)
(6) Cascade some value.

    <a,n> n = max( {0} + V( ancestors(G,a) )     ???
    walking graph top-down
(6b) Cascade some value with addition.

    <V2> FORALL an: V2(a,n) <-> n = V(a) + max(     { 0 } + V2( predecessors(G,a) ) )
    ???
    walking graph top-down
(7) Give example of path from a to b.

    ???
    Uncertain (many correct answers). Restricting     graph to edges between a and b and walking.
(8) Complete to total ordering.

    ???
    Uncertain. Walking top-down.
(9) Many, many others ...

These are good, but I need some general way to deal with them. I was very impressed with relational algebra, that allowed composing complex calculations from few simple algorithms. I can do something like that with descendants(G,A), but it is not enough for
(6)-(8).

C) Complicated (and a bit more practical) stuff
(1) Given .c file and #include graph G, calculate

    order in which .h files are processed. .h file     is processed once, when its first #include     reference is found.
    Note, that order in which #includes appear in     file is significant. We have ordering O(m,a,b),     where b follows a in file m.
(2) Flatten #include hierarchy (ie. all #includes

    only in .c files but more-or-less same compilation     order).
    Maybe better recalculating hierarchy from scratch     using file content.

I cannot even express these in calculus, never thinking of calculating them.

/Robert Received on Tue Apr 24 2001 - 00:56:42 CEST