Extracting a reachability path out of a (package) DAG

["Björn Höfling" <bjoern.hoefling@bjoernhoefling.de>]

[-- Attachment #1.1: Type: text/plain, Size: 1556 bytes --]

Hi Guix,

we have this nice `guix graph` tool which outputs DAGs of the packages
(or even derivations,bags, ...). This is cool if you look at simple
packages like the "hello" package with little to no dependencies. If
you look at "real" packages like qt or maven the information is just
overwhelming and you are scrolling around the image for just getting a
headache. 

Often the only think I want to know is something like: Why is "goodbye"
a dependency of "hello"?

To answer this, I want to extract from hello's package graph the path
(more precisely: the sub-DAG) leading from the root "hello" to the
target node (or even nodes) "goodbye".

After several attempts and failures, I wrote a script for gvpr from
the GraphViz suite that does the job.

Example 1: In bug #30710 Hartmut Goebel asked why qt depends on two
different autoconf-wrapper packages. To answer that, you can find out
the two node names from the .dot file and then call:

gvpr -f markpath.g -a "ex 64168128 64167936" < qt-thing/qt.package.dot
>qt-acw.dot

This extracts (ex) the path (sub-DAG) to the two seed nodes and outputs
it in a new graph. This result is quite compact with only 12 nodes (attached).

Example 2: How/Why is glib a dependency of maven? The extracted graph
has about 50 nodes, so I don't attach it here. You will see that
java-logback-classic depends on a groovy-cluster that finally mounts
into antlr. That depends on a gtk/pango/cairo-cluster that finally
sinks into glib.

Hope that is useful to someone else,

Björn



[-- Attachment #1.2: markpath.g --]
[-- Type: application/octet-stream, Size: 4193 bytes --]

/*

dotscripts --- Scripts for GraphViz

Copyright © 2018 Björn Höfling <bjoern.hoefling@bjoernhoefling.de>

This file is part of dotscripts.

dotscripts is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or (at
your option) any later version.

dotscripts is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with dotscripts.  If not, see <http://www.gnu.org/licenses/>.
*/


/******************************************************************************* 
Extract/Highlight path in a DAG from root to specific node.
*******************************************************************************/

BEGIN {

    // gvpr has no scope. So we define one global loop variable here:
    int i;

    // True(>0) if you want to extract the graph. False(=0) for highlighting.
    int extract;
    
    int numSeeds = ARGC-1;

    // Array of nodes that should be reached from the root node.
    // They act as seeds for the search algorithm.
    node_t seedNodes[];

    //Map of nodes/edges->0/1: indicating weather or not a node/edge is marked.
    int nodesMarked[obj_t];

    graph_t outGraph;

    void showUsage() {
        printf("Usage: gvpr -f markpath.g -a \"<cmd> node1 node2 ... \"\n");
        printf("where <cmd> is one of:\n");
        printf("ex - extract path.\n");
        printf("hl - highlight path.\n");
        printf("\n");
        printf("node1 node2 ... are the seed nodes\n");
        exit(1);    
    }





    if(ARGC<2) {
        showUsage();
    }
    
    if(ARGV[0]=="ex") {
        extract = 1;
    } else if(ARGV[0]=="hl") {
        extract=0;
    } else {
        showUsage();
    }

    /** Marks the object (edge or node) as highlighted/visited.
     */
    void mark(obj_t obj) {
        nodesMarked[obj]=1;

        if(extract) {
            clone(outGraph, obj);
        } else {
        obj.color="red";
        obj.style="filled";
        }
    }

    /**
      Returns true, if s is a seedNode, false otherwise.
    */
    int isSeedNode(node_t s) {
        
        int ii;
        for(ii=0; ii<numSeeds; ii++) {
            if(s==seedNodes[ii]) {
                return 1;
            }
        }
        return 0;
    }
    
    /**
      Traverses over all outEdges of node n.
      If any of those outEdges was already marked,
      return true.
      If no marked Edge is found, return false.
    */
    int anyEdgeMarked(node_t n) {
        edge_t e = fstout(n);
        while(e!=NULL) {
            if(nodesMarked[(obj_t)e]) {
                return 1;
            }
            e = nxtout(e);
        }
        return 0;
    }

    /** Returns true if head node of edge e is marked */
    int headIsMarked(edge_t e) {
        return nodesMarked[(obj_t)e.head];
    }
}

BEG_G {
    // If we want to extract, we create a new graph.
    // Else we use the input graph.
    if(extract) {
        outGraph = graph(sprintf("Extract of %s",$.name), "DS");
    } else {
        outGraph=$;
    }
    
    // Initialize seedNodes. We have to do it here in BEG_G, because only here
    // the graph is availabe.
    for(i=0; i< numSeeds; i++) {
        seedNodes[i]=isNode($, ARGV[i+1]);
        if(seedNodes[i]==NULL) {
            printf("Error: Argument %d is not a node!\n", i+1);
            exit(1);
         }
    }

    // Set traversal order to reverse, going into direction of the root node.
    $tvtype = TV_rev;

    // Setting the start node as one of the seed Nodes.
    // Variable is called "$tvnext", because it usually is ment to go to the next
    // connected component (CC), though we have only one CC here.
    $tvnext = seedNodes[0];
}

// The logic is extracted into functions, so this part looks rather trivial:

N [isSeedNode($)] {
    mark($);
}

N[anyEdgeMarked($)]{
    mark($);
}

E[headIsMarked($)] {
    mark($);
}

END_G {
    $O=outGraph;
}

[-- Attachment #1.3: qt-subdag-autoconf-wrapper.png --]
[-- Type: image/png, Size: 50516 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 181 bytes --]