dominators

[![Coveralls Status][coveralls-image]][coveralls-url] [![Build Status][travis-image]][travis-url] [![Dependency Status][depstat-image]][depstat-url] [![npm version][npm-image]][npm-url] [![License][license-image]][license-url] [![Known Vulnerabilities][snyk-image]][snyk-url] [![david-dm][david-dm-image]][david-dm-url]

Various dominator tree generators.

It implements two different methods for finding the immediate dominators of a graph.

1. Implements a near-linear time iterative dominator generator based on the paper A Simple, Fast Dominance Algorithm using an iterative method<a href="#chk" id="chkref">¹</a>

2. Yet another Lengauer & Tarjan implementation with variations. From this paper<a href="#lt" id="ltref">²</a> which you can find a link to it here (and many other places, in case this link goes bad): A fast algorithm for finding dominators in a flowgraph

Install

npm i dominators

Usage

const 
    { 
        iterative, 
        lt, 
        frontiers_from_preds, 
        frontiers_from_succs,
        reverse_graph
    } = require( 'dominators' ),
    
    someGraph = [
                        [ 1, 8 ],    // start
                        [ 2, 3 ],    // a
                        [ 3 ],       // b
                        [ 4, 5 ],    // c
                        [ 6 ],       // d
                        [ 6 ],       // e
                        [ 7, 2 ],    // f
                        [ 8 ],       // g
                        []           // end
                    ],
    immediateDominators = iterative( someGraph ),
    //  idoms = [ null, 0, 1, 1, 3, 3, 3, 6, 0 ],

    df = frontiers_from_succs( someGraph, immediateDominators ),
    // df = [ [], [ 8 ], [ 3 ], [ 2, 8 ], [ 6 ], [ 6 ], [ 2, 8 ], [ 8 ], [] ]
    // or
    same = frontiers_from_preds( reverse_graph( someGraph ), immediateDominators ),
    // df = [ [], [ 8 ], [ 3 ], [ 2, 8 ], [ 6 ], [ 6 ], [ 2, 8 ], [ 8 ], [] ]

    // See the explanation of parameters below.
    ltDoms = lt( someGraph, 0, true ),
    //  ltDoms = [ null, 0, 1, 1, 3, 3, 3, 6, 0 ],
    
    // The first parameter is your graph, an array of arrays of successor indices.
    // The second parameter is the start node, defaults to 0. This is optional and defaults to 0.
    // The last parameter is an optional boolean for whether to run it flat or not.
    // If it runs flat (set to true) then it will not use recursion for the DFS or the compress
    // function. The default is true.
    ltDomsSame = lt( someGraph, 0, true );
    //  ltDoms = [ null, 0, 1, 1, 3, 3, 3, 6, 0 ],

// Read full API documentation below
const myGraph = make_dom( graph );

myGraph.forStrictDominators( n => console.log( `${n} is a strict dominator of 9` ), 9 );

if ( myGraph.strictlyDominates( 7, 9 ) )
    console.log( `7 strictly dominates 9` );

console.log( `Node at index 7 strictly dominates these: ${myGraph.strictlyDominates( 7 ).join( ', ' )}` );
console.log( `The strict dominators of 7 are ${myGraph.strictDominators( 7 ).join( ', ' )}` );

Fast Lengauer-Tarjan LINK procedure

For the sake of completeness, below is the fast balanaced version of link, which is not included in the current module code for two reasons:

1. The LT algorithm with this LINK only becomes faster than the normal implementation when we're dealing with 10s or 100s of thousands of nodes, in which cases you shouldn't be using JavaScript anyway.
2. I don't have test graph large enough to get proper coverage so, since it's not really useful, I decided to remove it.

This implementation uses arrays rather then an object. That's how I originally implemented this algorithm but that makes it incompatible with the current implementation. I won't convert it since it's not used, however, because it is interesting, I've included it here, for interested parties, of which there will probably be at least zero but not more.

    balanced_link = ( w ) => {
        let s = w,
            v = parent[ w ];

        do
        {
            let cs  = child[ s ],
                bcs = cs !== null ? best[ cs ] : null;

            if ( cs !== null && semi[ best[ w ] ] < semi[ bcs ] )
            {
                let ccs  = child[ cs ],
                    ss   = size[ s ],
                    scs  = size[ cs ],
                    sccs = ccs !== null ? size[ ccs ] : 0;

                if ( ss - scs >= scs - sccs )
                    child[ s ] = ccs;
                else
                {
                    size[ cs ] = ss;
                    ancestor[ s ] = cs;
                    s = cs;
                }
            }
            else
                break;
        }
        while ( true );

        best[ s ] = best[ w ];
        if ( size[ v ] < size[ w ] )
        {
            let t = s;
            s = child[ v ];
            child[ v ] = t;
        }
        size[ v ] += size[ w ];
        while ( s !== null )
        {
            ancestor[ s ] = v;
            s = child[ s ];
        }
    }

License

MIT © Julian Jensen

API

Functions

<dl> <dt><a href="#make_dom">make_dom(opts)</a> ⇒ <code>Object</code></dt> <dd><p>This will associated a graph with a number of useful utility functions. It will return an object with a variety of functions that operate on the graphs.</p> <p>You might notice that many of these functions I took from the WebKit <code>dominators.h</code> file, which I really liked, and, although I re-wrote the code completely (obviously, since it was in <code>C++</code>), I decided to keep their comments with a few small alterations or corrections. I decided to not use their iterated dominance frontier code, because it was as efficient as it could be. Instead, I implemented one that uses a DJ-graph that I found in Chapter 4 of &quot;The SSA Book,&quot; called &quot;Advanced Contruction Algorithms for SSA&quot; by <em>D. Das</em>, <em>U. Ramakrishna</em>, <em>V. Sreedhar</em>. That book doesn&#39;t seem to be published or, if it has, I&#39;ve missed it. You can build the book yourself, supposedly, (I couldn&#39;t make that work, though) from here: <a href="https://gforge.inria.fr/scm/?group_id=1950">SSA Book</a> or you can probably find a PDF version of it somewhere on the web, which is what I did.</p> </dd> <dt><a href="#iterative">iterative(succs, [startIndex], [flat])</a> ⇒ <code>Array.&lt;number&gt;</code></dt> <dd><p>Implements a near-linear time iterative dominator generator based on this paper: (A Simple, Fast Dominance Algorithm)[<a href="https://www.cs.rice.edu/~keith/Embed/dom.pdf">https://www.cs.rice.edu/~keith/Embed/dom.pdf</a>] Citation: Cooper, Keith &amp; Harvey, Timothy &amp; Kennedy, Ken. (2006). A Simple, Fast Dominance Algorithm. Rice University, CS Technical Report 06-33870</p> </dd> <dt><a href="#check">check(vertices, idoms)</a></dt> <dd><p>Find dominance frontiers</p> </dd> <dt><a href="#frontiers_from_preds">frontiers_from_preds(preds, idoms)</a></dt> <dd><p>Find dominance frontiers</p> </dd> <dt><a href="#frontiers_from_succs">frontiers_from_succs(succs, idoms)</a></dt> <dd><p>Find dominance frontiers</p> </dd> <dt><a href="#lt">lt(nodes, [startIndex], [flat])</a></dt> <dd></dd> <dt><a href="#normalize">normalize(nodes)</a> ⇒ <code>Array.&lt;Array.&lt;number&gt;&gt;</code></dt> <dd></dd> <dt><a href="#condRefToSelf">condRefToSelf(seed, [chk], [dest])</a> ⇒ <code>Array.&lt;Array.&lt;number&gt;&gt;</code></dt> <dd></dd> <dt><a href="#simpleRefToSelf">simpleRefToSelf(seed, [dest])</a> ⇒ <code>Array.&lt;Array.&lt;number&gt;&gt;</code></dt> <dd></dd> <dt><a href="#create_j_edges">create_j_edges(_nodes, [domLevels], [domTree], [idoms])</a> ⇒ <code>*</code></dt> <dd><p>This will create and return the J-edges of a graph. The J-edges, or Join edges, make up one-half of the DJ-graph. For more information read the documentation for the DJ-graph.</p> <p>You need only pass the nodes of the graph to this function. The rest of the parameters are optional and will be computed if not provided. I allow the options to pass them in case you already have them calculated from elsewhere, just to make things a bit faster. If no arguments are provided other than the basic vertices, it will compute the immediate dominators, create the dominator tree, and compute the levels, and discard all of those results. Not a big deal unless you&#39;re dealing with very large graphs, in which case you should calculate those separately and provide them as inputs here.</p> </dd> <dt><a href="#create_levels">create_levels(nodes)</a> ⇒ <code>Array.&lt;number&gt;</code></dt> <dd><p>Calculate the level of each node in terms of how many edges it takes to reach the root. For the sake of simplicity, this uses a BFS to compute depth values.</p> </dd> <dt><a href="#create_nodes">create_nodes(_nodes, [idoms])</a></dt> <dd><p>A convenience method. It returns an array of object, one for each nodes in the graph, and in that order, that holds most of the information you could want for working with graphs.</p> <p>Specifically, each node looks as descibed in the typedef for GraphNode.</p> </dd> <dt><a href="#create_dj_graph">create_dj_graph(nodes, [idoms], [domTree])</a></dt> <dd><p>Returns a DJ-graph which is a graph that consts of the dominator tree and select join edges from the input graph.</p> </dd> </dl>

Typedefs

<dl> <dt><a href="#DomWalkerOptions">DomWalkerOptions</a> : <code>object</code></dt> <dd></dd> <dt><a href="#GraphNode">GraphNode</a> : <code>object</code></dt> <dd></dd> </dl>

<a name="ma