3
\$\begingroup\$

I have that girl whose graph walk I want to intercept, but because I am not good at running algorithms in my head, I had to program my computer to do that for me. I would not consider the problem to be a problem in its own right, but can be thought of as an extension of the shortest path problem.

Edit: I am not quite sure what the actual graph-theoretic terminology might be, yet by a graph walk I simply mean a sequence of nodes visited + the times describing the arrival moment for each visited node. By interception I mean the situation where an intercepting actor reaches a node \$u\$ no later than the target actor arrives to it.

Edit 2: The intercepting actor starts moving through the graph at time startTime and it must obey the graph topology. The target actor (the girl) is not required to obey arcs/weights; all we know about it is when she is passing each node of her walk. Given any node that the girl visits, we want to reach it no later than she, and if there is more than one such nodes, we choose the one at which interception happens earlier.

See what I have:

GraphWalkInterceptor.java:

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.java:

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.java:

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.java:

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.java (please ignore):

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.java:

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);
        }
    }
}

So what do you think? Am I getting anywhere?

\$\endgroup\$
7
  • \$\begingroup\$ Can you explain why you mean by a "graph walk" and "intercepting" a graph walk? Is a graph walk a Eulerian path (or a Hamiltonian path)? I've googled "graph walk intercept", but I really can't find anything that looks like what you might be talking about. \$\endgroup\$
    – ErikR
    Commented Sep 13, 2015 at 15:17
  • \$\begingroup\$ @ErikR Rephrased the terminology in my own words. \$\endgroup\$
    – coderodde
    Commented Sep 13, 2015 at 15:23
  • \$\begingroup\$ So, A wanders the graph ([D][A|C]G?) and B wants to catch A. How fast is A going? How fast is B going? How much time / nodes pass between A and B start moving? Are their starting points random or same or...? And how do we define "getting somewhere"? ;-) \$\endgroup\$ Commented Sep 14, 2015 at 20:25
  • \$\begingroup\$ @LIttleAncientForestKami I don't understand what you are asking. :P \$\endgroup\$
    – coderodde
    Commented Sep 15, 2015 at 4:22
  • \$\begingroup\$ @coderodde, well, my comment was born from similar sentiments! :-D you "have that girl whose graph walk you want to intercept". Let's call her A. Let's call you B. How many edges/nodes she(A) "visits" before you(B) start your interception? Does A and B travel at same speeds? Does the graph has cycles? Can you both travel in any directions between the nodes, or just some (one way, two way, mixed)? Clearer now? \$\endgroup\$ Commented Sep 15, 2015 at 13:14

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.