A simple graph walk interception algorithm

In this post I will present a simple algorithm for intercepting a graph walk. Before that, I have to impose some definitions. A directed graph G is a pair (V, A), where V is the set of nodes in the graph and A \subseteq V \times V is the set of directed arcs. We choose to deal with directed graphs as they may be used to simulate undirected graphs simply by putting two directed arcs (u, v) and (v, u) into A in order to simulate an undirected edge \{u, v\}. However, we disallow self-loops in A. Also, we are given a weight function w \colon A \to \mathbb{R}^+, which gives a (non-negative) time cost for moving through an arc in the graph.

It is evident that we need at least two actors: the target actor that visits nodes at particular time points, and the intercepting actor (for short, interceptor) that aims to reach a node, where it may intercept the target. The input graph is given, however, only to constrain movement of the interceptor; we don’t require the target to obey arcs in the graph. All in all, a graph walk is a pair (P, f), where P = \langle u_1, u_2, \dots, u_k \rangle is the sequence of nodes visited from left to right, and f(i) gives the arrival time of the node u_i. We assume that the target actor does not spend any time in any node it is to visit, so for any node u_i \in V, we intercept the target actor at node u_i only if f(i) \geq \delta(s, u_i) + T, where s is the node where interceptor begins the chase, \delta(u, v) gives the shortest path time cost of moving from u to v, and T is the time point upon which the interceptor begins the chase.

Now the rest is simply doing a shortest path search for multiple goal nodes u_1, u_2, \dots, u_k. We terminate the search whenever all goal nodes are reached or whenever we crawl the entire graph. After that, we simply check whether there are intercepted nodes among the goal nodes, and if so, we choose among them the one that occurs earliest. The imlementation in Java follows:

GraphWalkInterceptor

package net.coderodde.graph.interception;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * This class implements a graph walk interception algorithm. Basically, this is
 * a Dijkstra algorithm which is executed until all possible graph walk nodes 
 * are reached and then computes the goal node that produces a shortest time
 * interception.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Sep 13, 2015)
 */
public class GraphWalkInterceptor {

    /**
     * The set of nodes in the search frontier.
     */
    private final BinaryHeap<DirectedGraphNode> OPEN = new BinaryHeap<>();

    /**
     * The set of nodes already settled.
     */
    private final Set<DirectedGraphNode> CLOSED = new HashSet<>();

    /**
     * Maps each node to its predecessor node on the shortest path so far.
     */
    private final Map<DirectedGraphNode, DirectedGraphNode> parentMap =
            new HashMap<>();

    /**
     * Maps each node to its best known cost.
     */
    private final Map<DirectedGraphNode, Double> distanceMap = new HashMap<>();

    /**
     * The set of nodes containing the goal nodes not reached so far.
     */
    private final Set<DirectedGraphNode> goalNodeSet = new HashSet<>();

    private final DirectedGraphNode source;
    private final DirectedGraphWeightFunction weightFunction;
    private final double startTime;
    private final GraphWalk walk;

    private GraphWalkInterceptor(DirectedGraphNode source,
                                 DirectedGraphWeightFunction weightFunction,
                                 double startTime,
                                 GraphWalk walk) {
        this.source         = source;
        this.weightFunction = weightFunction;
        this.startTime      = startTime;
        this.walk           = walk;
    }

    public static List<DirectedGraphNode> 
        intercept(DirectedGraphNode source,
                  DirectedGraphWeightFunction weightFunction,
                  double startTime,
                  GraphWalk walk) {
        checkWalk(walk);
        return new GraphWalkInterceptor(source,
                                        weightFunction,
                                        startTime,
                                        walk).intercept();
    }

    private List<DirectedGraphNode> intercept() {
        initializeState();

        while (!OPEN.isEmpty()) {
            DirectedGraphNode current = OPEN.extractMinimum();

            if (goalNodeSet.contains(current)) {
                goalNodeSet.remove(current);

                if (goalNodeSet.isEmpty()) {
                    return findBestPath();
                }
            }

            CLOSED.add(current);

            for (DirectedGraphNode child : current.children()) {
                if (!CLOSED.contains(child)) {
                    double distance = distanceMap.get(current) +
                                      weightFunction.get(current, child);

                    if (!parentMap.containsKey(child)) {
                        OPEN.add(child, distance);
                        parentMap.put(child, current);
                        distanceMap.put(child, distance);
                    } else if (distance < distanceMap.get(child)) {
                        OPEN.decreasePriority(child, distance);
                        parentMap.put(child, current);
                        distanceMap.put(child, distance);
                    }
                }
            }
        }

        return findBestPath();
    }

    private void initializeState() {
        OPEN.add(source, startTime);
        parentMap.put(source, null);
        distanceMap.put(source, startTime);
        goalNodeSet.addAll(walk.getNodeList());
    }

    private static void checkWalk(GraphWalk walk) {
        if (walk.getNodeList().isEmpty()) {
            throw new IllegalArgumentException("The input walk is empty.");
        }
    }

    private List<DirectedGraphNode> findBestPath() {
        List<DirectedGraphNode> walkNodeList = walk.getNodeList();

        double bestDistance = Double.MAX_VALUE;
        DirectedGraphNode bestNode = null;

        for (int i = 0; i < walkNodeList.size(); ++i) {
            DirectedGraphNode node = walkNodeList.get(i);
            
            if (distanceMap.containsKey(node)) {
                double distance = distanceMap.get(node);
                double arrivalTime = walk.getArrivalTime(i);
                
                if (arrivalTime >= distance) {
                    // Once here, the node 'node' is a interception node.
                    if (bestDistance > arrivalTime) {
                        bestDistance = arrivalTime;
                        bestNode = node;
                    }
                }
            }

        }
        
        return bestNode == null ? 
                Collections.emptyList() : 
                tracebackPath(bestNode, parentMap);
    }

    private List<DirectedGraphNode> 
        tracebackPath(DirectedGraphNode node,
                      Map<DirectedGraphNode, DirectedGraphNode> parentMap) {
        List<DirectedGraphNode> path = new ArrayList<>();
        DirectedGraphNode current = node;

        while (current != null) {
            path.add(current);
            current = parentMap.get(current);
        }

        Collections.<DirectedGraphNode>reverse(path);
        return path;
    }
}

GraphWalk

package net.coderodde.graph.interception;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * This class implements a graph walk data structure.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Sep 13, 2015)
 */
public class GraphWalk {

    private final List<DirectedGraphNode> nodeList    = new ArrayList<>();
    private final Map<Integer, Double> arrivalTimeMap = new HashMap<>();

    public void addNode(DirectedGraphNode node, double arrivalTime) {
        arrivalTimeMap.put(nodeList.size(), arrivalTime);
        nodeList.add(node);
    }

    public List<DirectedGraphNode> getNodeList() {
        return Collections.<DirectedGraphNode>unmodifiableList(nodeList);
    }

    public double getArrivalTime(int index) {
        return arrivalTimeMap.get(index);
    }
}

DirectedGraphNode

package net.coderodde.graph.interception;

import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.Set;

/**
 * This class implements directed graph nodes.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Sep 13, 2015)
 */
public class DirectedGraphNode {

    private final String name;
    private final Set<DirectedGraphNode> childSet = new LinkedHashSet<>();

    public DirectedGraphNode(String name) {
        this.name = name;
    }

    public void addChild(DirectedGraphNode child) {
        childSet.add(child);
    }

    public boolean hasChild(DirectedGraphNode child) {
        return childSet.contains(child);
    }

    public Set<DirectedGraphNode> children() {
        return Collections.<DirectedGraphNode>unmodifiableSet(childSet);
    }

    @Override
    public int hashCode() {
        return name.hashCode();
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof DirectedGraphNode)) {
            return false;
        }

        return ((DirectedGraphNode) o).name.equals(name);
    }

    @Override
    public String toString() {
        return "[DirectedGraphNode " + name + "]";
    }
}

DirectedGraphWeightFunction

package net.coderodde.graph.interception;

import java.util.HashMap;
import java.util.Map;

/**
 * This class implements weight functions for directed graphs.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Sep 13, 2015)
 */
public class DirectedGraphWeightFunction {

    private final Map<DirectedGraphNode, Map<DirectedGraphNode, Double>> map =
            new HashMap<>();

    public void put(DirectedGraphNode tail, 
                    DirectedGraphNode head, 
                    double weight) {
        map.putIfAbsent(tail, new HashMap<>());
        map.get(tail).put(head, weight);
    }

    public double get(DirectedGraphNode tail, DirectedGraphNode head) {
        return map.get(tail).get(head);
    }
}

BinaryHeap

package net.coderodde.graph.interception;

import java.util.HashMap;
import java.util.Map;
import java.util.NoSuchElementException;

/**
 * This class implements the binary minimum heap (a priority queue type).
 *
 * @author  Rodion "rodde" Efremov
 * @version 1.618 (11.12.2013)
 * @param <E> the actual element type.
 */
public class BinaryHeap<E> {
    private static final float LOAD_FACTOR = 1.05f;
    private static final int DEFAULT_CAPACITY = 1024;

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private static class HeapNode<E> {
        E      element;
        double priority;
        int    index;

        HeapNode(E element, double priority) {
            this.element = element;
            this.priority = priority;
        }
    }

    /**
     * The amount of elements in this heap.
     */
    private int size;

    /**
     * The actual storage array.
     */
    private HeapNode<E>[] nodeArray;

    /**
     * Maps each element to the heap node holding it.
     */
    private Map<E, HeapNode<E>> map;

    /**
     * Constructs a binary heap with initial capacity <code>capacity</code>.
     *
     * @param capacity the initial capacity of this heap.
     */
    public BinaryHeap(int capacity) {
        capacity = checkCapacity(capacity);
        this.nodeArray = new HeapNode[capacity];
        this.map = new HashMap<>(capacity, LOAD_FACTOR);
    }

    /**
     * Construct a binary heap.
     */
    public BinaryHeap() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * Adds an element if not already present.
     *
     * @param e        the element to insert.
     * @param priority the priority of the element.
     */
    public void add(E e, double priority) {
        if (map.containsKey(e)) {
            return;
        }

        if (size == nodeArray.length) {
            extendArray();
        }

        int index = size;
        HeapNode<E> node = new HeapNode<>(e, priority);

        // Sift up the node containing the input element until min-heap property
        // is restored.
        while (index > 0) {
            int parent = (index - 1) >>> 1;
            HeapNode<E> p = nodeArray[parent];

            if (priority >= p.priority) {
                break;
            }

            nodeArray[index] = p;
            p.index = index;
            index = parent;
        }

        nodeArray[index] = node;
        node.index = index;
        map.put(e, node);
        ++size;
    }

    public void decreasePriority(E e, double newPriority) {
        HeapNode<E> node = map.get(e);

        if (node == null || node.priority <= newPriority) {
            return;
        }

        node.priority = newPriority;
        int index = node.index;
        int parentIndex = (index - 1) >> 1;

        for (;;) {
            if (parentIndex >= 0
                    && nodeArray[parentIndex].priority > node.priority) {
                nodeArray[index] = nodeArray[parentIndex];
                nodeArray[index].index = index;
                index = parentIndex;
                parentIndex = (index - 1) >> 1;
            } else {
                nodeArray[index] = node;
                node.index = index;
                return;
            }
        }
    }

    public E min() {
        if (size == 0) {
            throw new NoSuchElementException("Reading from an empty heap.");
        }

        return nodeArray[0].element;
    }

    public E extractMinimum() {
        if (size == 0) {
            throw new NoSuchElementException("Extracting from an empty queue.");
        }

        E element = nodeArray[0].element;
        map.remove(element);
        HeapNode<E> node = nodeArray[--size];
        nodeArray[size] = null;

        int nodeIndex = 0;
        int leftChildIndex = 1;
        int rightChildIndex = 2;

        for (;;) {
            int minChildIndex;

            if (leftChildIndex < size) {
                minChildIndex = leftChildIndex;
            } else {
                nodeArray[nodeIndex] = node;
                node.index = nodeIndex;
                return element;
            }

            if (rightChildIndex < size
                    && nodeArray[leftChildIndex].priority > 
                       nodeArray[rightChildIndex].priority) {
                minChildIndex = rightChildIndex;
            }

            if (node.priority > nodeArray[minChildIndex].priority) {
                nodeArray[nodeIndex] = nodeArray[minChildIndex];
                nodeArray[nodeIndex].index = nodeIndex;

                nodeIndex = minChildIndex;
                leftChildIndex = (nodeIndex << 1) + 1;
                rightChildIndex = leftChildIndex + 1;
            } else {
                nodeArray[nodeIndex] = node;
                node.index = nodeIndex;
                return element;
            }
        }
    }

    public void clear() {
        size = 0;
        map.clear();
    }

    public boolean contains(E element) {
        return map.containsKey(element);
    }

    public Double getPriority(E element) {
        if (map.containsKey(element) == false) {
            return null;
        }

        return map.get(element).priority;
    }

    private int checkCapacity(int capacity) {
        return capacity < 16 ? 16 : capacity;
    }

    private void extendArray() {
        int capacity = (size * 3) / 2;
        HeapNode[] array = new HeapNode[capacity];
        System.arraycopy(nodeArray, 0, array, 0, size);
        nodeArray = array;
    }
}

Demo

package net.coderodde.graph.interception;

import java.util.List;

public class Demo {

    public static void main(String[] args) {
        profile1();
        profile2();
    }

    private static void profile1() {
        System.out.println(title1("Tree"));

        DirectedGraphNode s = new DirectedGraphNode("s");
        DirectedGraphNode a = new DirectedGraphNode("a");
        DirectedGraphNode b = new DirectedGraphNode("b");
        DirectedGraphNode c = new DirectedGraphNode("c");
        DirectedGraphNode d = new DirectedGraphNode("d");
        DirectedGraphNode t = new DirectedGraphNode("t");
        DirectedGraphNode u = new DirectedGraphNode("u");
        DirectedGraphNode v = new DirectedGraphNode("v");
        DirectedGraphNode w = new DirectedGraphNode("w");
        DirectedGraphNode x = new DirectedGraphNode("x");
        DirectedGraphNode y = new DirectedGraphNode("y");
        DirectedGraphNode z = new DirectedGraphNode("z");

        DirectedGraphWeightFunction f = new DirectedGraphWeightFunction();

        z.addChild(x); f.put(z, x, 1);
        z.addChild(y); f.put(z, y, 10);
        x.addChild(u); f.put(x, u, 2);
        x.addChild(v); f.put(x, v, 2);
        y.addChild(v); f.put(y, v, 3);
        y.addChild(w); f.put(y, w, 4);

        s.addChild(a); f.put(s, a, 1); 
        a.addChild(b); f.put(a, b, 2);
        b.addChild(c); f.put(b, c, 3);
        c.addChild(d); f.put(c, d, 4);
        d.addChild(t); f.put(d, t, 5);

        t.addChild(d); f.put(t, d, 5);
        d.addChild(c); f.put(d, c, 4);
        c.addChild(b); f.put(c, b, 3);
        b.addChild(a); f.put(b, a, 2);
        a.addChild(s); f.put(a, s, 1);

        u.addChild(s); f.put(u, s, 8);
        u.addChild(a); f.put(u, a, 7);
        v.addChild(a); f.put(v, a, 2);
        v.addChild(c); f.put(v, c, 2);
        w.addChild(b); f.put(w, b, 5);
        w.addChild(d); f.put(w, d, 3);
        w.addChild(t); f.put(w, t, 5);

        GraphWalk walk = new GraphWalk();

        walk.addNode(s, 0);
        walk.addNode(a, 1);
        walk.addNode(b, 3);
        walk.addNode(c, 6);
        walk.addNode(d, 10);
        walk.addNode(t, 15);

        System.out.println(title2("Start at time 0.0"));

        List<DirectedGraphNode> path = 
                GraphWalkInterceptor.intercept(z, f, 0.0, walk);

        for (DirectedGraphNode node : path) {
            System.out.println(node);
        }

        System.out.println(title2("Start at time 0.9"));

        path = GraphWalkInterceptor.intercept(z, f, 0.9, walk);

        for (DirectedGraphNode node : path) {
            System.out.println(node);
        }

        System.out.println(title2("Start at time 1.0"));

        path = GraphWalkInterceptor.intercept(z, f, 1.0, walk);

        for (DirectedGraphNode node : path) {
            System.out.println(node);
        }

        System.out.println(title2("Start at time 1.2"));

        path = GraphWalkInterceptor.intercept(z, f, 1.2, walk);

        for (DirectedGraphNode node : path) {
            System.out.println(node);
        }
    }

    /**
     * Assumed console width.
     */
    private static final int CONSOLE_WIDTH = 80;

    private static String title1(String text) {
        return title(text, '*');
    }

    private static String title2(String text) {
        return title(text, '-');
    }

    private static String title(String text, char c) {
        // Subtract 2 in order to have one space before and after the title.
        int leftBarLength = (CONSOLE_WIDTH - 2 - text.length()) / 2;
        int rightBarLength = CONSOLE_WIDTH - 2 - text.length() - leftBarLength;

        StringBuilder sb = new StringBuilder(80);

        for (int i = 0; i < leftBarLength; ++i) {
            sb.append(c);
        }

        sb.append(' ')
          .append(text)
          .append(' ');

        for (int i = 0; i < rightBarLength; ++i) {
            sb.append(c);
        }

        return sb.toString();
    }

    private static void profile2() {
        System.out.println(title1("Cycle"));

        DirectedGraphNode a = new DirectedGraphNode("a");
        DirectedGraphNode b = new DirectedGraphNode("b");
        DirectedGraphNode c = new DirectedGraphNode("c");
        DirectedGraphNode d = new DirectedGraphNode("d");
        DirectedGraphNode e = new DirectedGraphNode("e");

        DirectedGraphWeightFunction f = new DirectedGraphWeightFunction();

        a.addChild(b); f.put(a, b, 1);
        b.addChild(c); f.put(b, c, 2);
        c.addChild(d); f.put(c, d, 3);
        d.addChild(e); f.put(d, e, 4);
        e.addChild(a); f.put(e, a, 5);

        GraphWalk walk = new GraphWalk();

        walk.addNode(a, 10);
        walk.addNode(b, 11.5);

        System.out.println(title2("Start time at 10.0"));

        List<DirectedGraphNode> path = 
                GraphWalkInterceptor.intercept(c, f, 10.0, walk);

        for (DirectedGraphNode node : path) {
            System.out.println(node);
        }

        System.out.println(title2("Start time at -1.0"));

        path = GraphWalkInterceptor.intercept(c, f, -1.0, walk);

        for (DirectedGraphNode node : path) {
            System.out.println(node);
        }

        System.out.println(title2("Start time at -2.0"));

        path = GraphWalkInterceptor.intercept(c, f, -2.0, walk);

        for (DirectedGraphNode node : path) {
            System.out.println(node);
        }
    }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s