unofficial mirror of guix-devel@gnu.org 
 help / color / mirror / code / Atom feed
* Extracting a reachability path out of a (package) DAG
@ 2018-07-17  8:10 Björn Höfling
  2018-07-17  8:22 ` Pierre Neidhardt
                   ` (3 more replies)
  0 siblings, 4 replies; 12+ messages in thread
From: Björn Höfling @ 2018-07-17  8:10 UTC (permalink / raw)
  To: guix-devel


[-- 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 --]

^ permalink raw reply	[flat|nested] 12+ messages in thread
end of thread, other threads:[~2018-08-04  3:54 UTC | newest]

Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-07-17  8:10 Extracting a reachability path out of a (package) DAG Björn Höfling
2018-07-17  8:22 ` Pierre Neidhardt
2018-07-17 10:29   ` Björn Höfling
2018-07-17  8:24 ` Nils Gillmann
2018-07-17 10:32   ` Björn Höfling
2018-07-17 15:09     ` Gábor Boskovits
2018-07-21 21:55       ` Pierre Neidhardt
2018-07-22 18:53         ` Alex Kost
2018-07-22 18:59           ` Pierre Neidhardt
2018-07-22 19:18             ` Björn Höfling
2018-07-23 13:09 ` Ludovic Courtès
2018-08-04  3:54 ` Chris Marusich

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/guix.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).