js/motifFinder/broadcastGatherFinder.js
// Alternate greedy solution. Used when O(n^2) dp is too slow
Alternate greedy solution. Used when O(n^2) dp is too slow
Alternate greedy solution . Used when O ( n^2 ) dp is too slow
function findGreedy(group, motif) {
        var bcCount = 0;
        var inBetween = 0;
        var inPattern = false;
        var currMotif = new Motif();
        var queued = [];
        var nodes = [];
        var seenHosts = {};
        group = group.concat([ new ModelNode([]) ]);
        for (var g = 0; g < group.length; g++) {
            var curr = group[g];
            queued.push(curr);
            var hasValidLink = false;
            var links = context.broadcast ? curr.getChildren() : curr.getParents();
            for (var i = 0; i < links.length; i++) {
                if (!seenHosts[links[i].getHost()]) {
                    hasValidLink = true;
                    break;
                }
            }
            var hasBadLink = context.broadcast ? curr.hasParents() : curr.hasChildren();
            var hasGoodLink = context.broadcast ? curr.hasChildren() : curr.hasParents();
            if (inBetween > context.maxInBetween || (g == group.length - 1) || hasBadLink || (hasGoodLink && !hasValidLink)) {
                if (bcCount >= context.minBroadcastGather) {
                    for (var i = 1; i < nodes.length; i++) {
                        currMotif.addEdge(nodes[i - 1], nodes[i]);
                    }
                    motif.merge(currMotif);
                }
                inPattern = false;
            }
            if (hasGoodLink && (context.broadcast || !hasBadLink)) {
                if (!inPattern) {
                    inPattern = true;
                    bcCount = 0;
                    inBetween = 0;
                    currMotif = new Motif();
                    queued = [ curr ];
                    seenHosts = {};
                    nodes = [];
                }
                currMotif.addAllNodes(links);
                for (var i = 0; i < links.length; i++) {
                    currMotif.addEdge(curr, links[i]);
                    var linkHost = links[i].getHost();
                    if (!seenHosts[linkHost]) {
                        bcCount++;
                        seenHosts[linkHost] = true;
                    }
                }
                currMotif.addAllNodes(queued);
                nodes = nodes.concat(queued);
                queued = [];
                inBetween = 1 - curr.getLogEventCount();
            }
            inBetween += curr.getLogEventCount();
        }
    }
function findGreedy ( group , motif ) { var bcCount = 0 ; var inBetween = 0 ; var inPattern = false ; var currMotif = new Motif ( ) ; var queued = [ ] ; var nodes = [ ] ; var seenHosts = { } ; group = group . concat ( [ new ModelNode ( [ ] ) ] ) ; for ( var g = 0 ; g < group . length ; g ++ ) { var curr = group [ g ] ; queued . push ( curr ) ; var hasValidLink = false ; var links = context . broadcast ? curr . getChildren ( ) : curr . getParents ( ) ; for ( var i = 0 ; i < links . length ; i ++ ) { if ( ! seenHosts [ links [ i ] . getHost ( ) ] ) { hasValidLink = true ; break ; } } var hasBadLink = context . broadcast ? curr . hasParents ( ) : curr . hasChildren ( ) ; var hasGoodLink = context . broadcast ? curr . hasChildren ( ) : curr . hasParents ( ) ; if ( inBetween > context . maxInBetween || ( g == group . length - 1 ) || hasBadLink || ( hasGoodLink && ! hasValidLink ) ) { if ( bcCount >= context . minBroadcastGather ) { for ( var i = 1 ; i < nodes . length ; i ++ ) { currMotif . addEdge ( nodes [ i - 1 ] , nodes [ i ] ) ; } motif . merge ( currMotif ) ; } inPattern = false ; } if ( hasGoodLink && ( context . broadcast || ! hasBadLink ) ) { if ( ! inPattern ) { inPattern = true ; bcCount = 0 ; inBetween = 0 ; currMotif = new Motif ( ) ; queued = [ curr ] ; seenHosts = { } ; nodes = [ ] ; } currMotif . addAllNodes ( links ) ; for ( var i = 0 ; i < links . length ; i ++ ) { currMotif . addEdge ( curr , links [ i ] ) ; var linkHost = links [ i ] . getHost ( ) ; if ( ! seenHosts [ linkHost ] ) { bcCount ++ ; seenHosts [ linkHost ] = true ; } } currMotif . addAllNodes ( queued ) ; nodes = nodes . concat ( queued ) ; queued = [ ] ; inBetween = 1 - curr . getLogEventCount ( ) ; } inBetween += curr . getLogEventCount ( ) ; } }
Alternate greedy solution.
Alternate greedy solution .