Source: motifFinder/requestResponseFinder.js

/**
 * @classdesc
 * 
 * <p>
 * This class is responsible for finding Request-Response motifs.
 * </p>
 * 
 * <p>
 * Intuitively, a request response motif is a communication pattern between two
 * hosts where one host sends a message to a second host, and the receiving host
 * then sends something back to the first host.
 * </p>
 * 
 * <p>
 * More formally, a sequence S of k nodes n_1, n_2, n_3 ... n_k forms a
 * Request-Response motif if and only if:
 * <ul>
 * <li>k >= 3</li>
 * <li>n_1 and n_k belong to the same host (which we will call H_s)</li>
 * <li>Nodes n_2 to n_(k-1) inclusive belong to the same host (which we will
 * call H_r)</li>
 * <li>H_s != H_r</li>
 * <li>n_2 is the child of n_1</li>
 * <li>n_k is the child of n_(k-1)</li>
 * <li>Apart from the two family relations above, no nodes in S may have any
 * family</li>
 * <li>nodes n_2 to n_(k-1) inclusive are consecutive</li>
 * <li>The number of nodes between n_2 and n_(k-1) is less than or equal to the
 * parameter maxLEResponder</li>
 * <li>The number of nodes between n_1 and n_k (in the graph, not in S) is less
 * than or equal to the parameter maxLERequester</li>
 * </ul>
 * </p>
 * 
 * <p>
 * The motif itself comprises all nodes in S plus all edges that connect nodes
 * adjacent in the sequence S.
 * </p>
 * 
 * @constructor
 * @extends MotifFinder
 * @param {int} maxLERequester See above for the purpose of this parameter
 * @param {int} maxLEResponder See above for the purpose of this parameter
 */
function RequestResponseFinder(maxLERequester, maxLEResponder) {
    
    /** @private */
    this.maxLERequester = maxLERequester;
    
    /** @private */
    this.maxLEResponder = maxLEResponder;
}

// RequestResponseFinder extends MotifFinder
RequestResponseFinder.prototype = Object.create(MotifFinder.prototype);
RequestResponseFinder.prototype.constructor = RequestResponseFinder;

/**
 * Overrides {@link MotifFinder#find}
 */
RequestResponseFinder.prototype.find = function(graph) {
    var nodes = graph.getNodes();
    var motifGroup = new MotifGroup();
    var seen = {}; // Nodes already part of a motif
    var context = this;

    var traversal = new DFSGraphTraversal(); // define a strategy for traversing the graph

    traversal.setVisitFunction("startNode", function(gt, startNode, state, data) {

        var fail = seen[startNode.getId()] // node is already part of another motif
                || startNode.getChildren().length > 1 //
                || startNode.hasParents();

        if (fail) {
            return;
        }

        gt.addAllNodes(startNode.getChildren(), "responderChain", 0);

    });

    traversal.setVisitFunction("responderChain", function(gt, node, state, chainLength) {

        var fail = seen[node.getId()] // fail if node is already part of another motif
                || node.getParents().length > 1 //
                || (node.hasParents() && chainLength != 0) // or if node isn't the first node in the responder chain and has parents
                || node.isTail() //
                || node.getChildren().length > 1 //
                || chainLength > context.maxLEResponder; //

        if (fail) {
            return;
        }

        if(node.hasChildren()) {
            gt.addAllNodes(node.getChildren(), "endNode", null);
        }
        else {
            gt.addNode(node.getNext(), "responderChain", chainLength + node.getLogEventCount());
        }

    });

    traversal.setVisitFunction("endNode", function(gt, node, state, data) {

        var trail = gt.getTrail();
        var startNode = trail[trail.length - 1];

        var fail = seen[node.getId()] // fail if node is already part of another motif
                || node.hasChildren() //
                || node.getParents().length > 1 //
                || node.getHost() != startNode.getHost(); // start and end nodes must have same host

        if (fail) {
            return;
        }

        var dist = 0;
        while (node != startNode) {
            dist += node.getLogEventCount();
            node = node.getPrev();
        }

        if (dist > context.maxLERequester) {
            return;
        }

        var motif = new Motif();
        motif.addTrail(trail);
        motifGroup.addMotif(motif);

        for ( var i = 0; i < trail.length; i++) {
            seen[trail[i].getId()] = true;
        }

        gt.end();

    });

    for ( var i = 0; i < nodes.length; i++) {
        
        traversal.reset();
        traversal.addNode(nodes[i], "startNode", null);
        traversal.run();
    }

    return motifGroup;
};