Finding shortest paths in a Wikipedia article graph using Java

Question

(See also Finding shortest paths in a Wikipedia article graph using Java - second attempt.)

I have this sort of a web crawler that asks for two (English) Wikipedia article titles (the source and the target), and proceeds to compute the shortest path between the two:

package net.coderodde.wikipedia.sp;

import com.google.gson.JsonArray;
import com.google.gson.JsonObject;
import com.google.gson.JsonParser;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.io.IOException;
import java.io.PrintStream;
import java.net.URL;
import java.net.URLEncoder;
import java.nio.charset.Charset;
import org.apache.commons.io.IOUtils;

/**
 * This class implements an unweighted shortest path finder in the Wikipedia 
 * article finder.
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 28, 2016)
 */
public class PathFinder {

    private static final Map<Character, String> ENCODING_MAP = new HashMap<>();

    static {
        ENCODING_MAP.put(' ', "_");
        ENCODING_MAP.put('"', "%22");
        ENCODING_MAP.put(';', "%3B");
        ENCODING_MAP.put('<', "%3C");
        ENCODING_MAP.put('>', "%3E");

        ENCODING_MAP.put('?', "%3F");
        ENCODING_MAP.put('[', "%5B");
        ENCODING_MAP.put(']', "%5D");
        ENCODING_MAP.put('{', "%7B");
        ENCODING_MAP.put('|', "%7C");

        ENCODING_MAP.put('}', "%7D");
        ENCODING_MAP.put('?', "%3F");
    }

    private static final String FORWARD_URL_FORMAT = 
            "https://en.wikipedia.org/w/api.php" +
            "?action=query" +
            "&titles=%s" + 
            "&prop=links" + 
            "&pllimit=max" + 
            "&format=json";

    private static final String BACKWARD_URL_FORMAT = 
            "https://en.wikipedia.org/w/api.php" +
            "?action=query" +
            "&list=backlinks" +
            "&bltitle=%s" + 
            "&bllimit=max" + 
            "&format=json";

    /**
     * Searches for the shortest path from the Wikipedia article with the title
     * {@code sourceTitle} to the article with the title {@code  targetTitle}.
     * The algorithm is bidirectional breadth-first search.
     * 
     * @param sourceTitle the title of the source article.
     * @param targetTitle the title of the target article.
     * @return the shortest path.
     * @throws IOException may be thrown.
     */
    public List<String> findShortestPath(String sourceTitle, 
                                         String targetTitle,
                                         PrintStream out) 
    throws IOException {
        sourceTitle = sourceTitle.trim();
        targetTitle = targetTitle.trim();

        if (sourceTitle.equals(targetTitle)) {
            return new ArrayList<>(Arrays.asList(sourceTitle));
        }

        Deque<String> QUEUEA = new ArrayDeque<>();
        Deque<String> QUEUEB = new ArrayDeque<>();

        Map<String, String> PARENTSA = new HashMap<>();
        Map<String, String> PARENTSB = new HashMap<>();

        Map<String, Integer> DISTANCEA = new HashMap<>();
        Map<String, Integer> DISTANCEB = new HashMap<>();

        String touchNode = null;
        int bestDistanceSoFar = Integer.MAX_VALUE;

        QUEUEA.add(sourceTitle);
        QUEUEB.add(targetTitle);

        PARENTSA.put(sourceTitle, null);
        PARENTSB.put(targetTitle, null);

        DISTANCEA.put(sourceTitle, 0);
        DISTANCEB.put(targetTitle, 0);

        while (!QUEUEA.isEmpty() && !QUEUEB.isEmpty()) {
            if (touchNode != null) {
                int distanceFromSource = DISTANCEA.get(QUEUEA.getFirst());
                int distanceFromTarget = DISTANCEB.get(QUEUEB.getFirst());

                if (bestDistanceSoFar < distanceFromSource + 
                                        distanceFromTarget) {
                    return tracebackPath(touchNode, PARENTSA, PARENTSB);
                }
            }

            if (DISTANCEA.size() < DISTANCEB.size()) {
                String current = QUEUEA.removeFirst();

                if (out != null) {
                    out.println("Forward:  " + current);
                }

                if (PARENTSB.containsKey(current) 
                        && bestDistanceSoFar > DISTANCEA.get(current) +
                                               DISTANCEB.get(current)) {
                    bestDistanceSoFar = DISTANCEA.get(current) +
                                        DISTANCEB.get(current);
                    touchNode = current;
                }

                for (String child : getChildArticles(current)) {
                    if (!PARENTSA.containsKey(child)) {
                        PARENTSA.put(child, current);
                        DISTANCEA.put(child, DISTANCEA.get(current) + 1);
                        QUEUEA.addLast(child);
                    }
                }
            } else {
                String current = QUEUEB.removeFirst();

                if (out != null) {
                    out.println("Backward: " + current);
                }

                if (PARENTSA.containsKey(current) 
                        && bestDistanceSoFar > DISTANCEA.get(current) + 
                                               DISTANCEB.get(current)) {
                    bestDistanceSoFar = DISTANCEA.get(current) +
                                        DISTANCEB.get(current);
                    touchNode = current;
                }

                for (String parent : getParentArticles(current)) {
                    if (!PARENTSB.containsKey(parent)) {
                        PARENTSB.put(parent, current);
                        DISTANCEB.put(parent, DISTANCEB.get(current) + 1);
                        QUEUEB.addLast(parent);
                    }
                }
            }
        }

        return new ArrayList<>();
    }

    /**
     * Constructs the shortest path.
     * 
     * @param touchNode the article where the two search frontiers "meet" each
     * o                other.
     * @param PARENTSA the parent map of the forward search.
     * @param PARENTSB the parent map of the backward search.
     * @return a shortest path.
     */
    private List<String> tracebackPath(String touchNode, 
                                       Map<String, String> PARENTSA, 
                                       Map<String, String> PARENTSB) {
        List<String> path = new ArrayList<>();
        String node = touchNode;

        while (node != null) {
            path.add(node);
            node = PARENTSA.get(node);
        }

        Collections.reverse(path);
        node = PARENTSB.get(touchNode);

        while (node != null) {
            path.add(node);
            node = PARENTSB.get(node);
        }

        return path;
    }

    /**
     * Implements the neighbor function. 
     * 
     * @param current the current URL.
     * @param forward if is set to {@code true}, this method return all the 
     *                child URLs of {@code current}.
     * @return the list of child URLs.
     * @throws IOException may be thrown.
     */
    private static List<String> baseGetNeighbors(String currentTitle, 
                                                 boolean forward) 
    throws IOException{
        String jsonDataUrl = 
                String.format(forward ? 
                                    FORWARD_URL_FORMAT : 
                                    BACKWARD_URL_FORMAT,
                              URLEncoder.encode(currentTitle, "UTF-8"));

        String jsonText = 
                IOUtils.toString(new URL(jsonDataUrl), 
                                 Charset.forName("UTF-8"));

        return forward ?
               extractForwardLinkTitles(jsonText) : 
               extractBackwardLinkTitles(jsonText);
    }

    /**
     * Returns all the child articles that are linked from URL {@code current}.
     * 
     * @param current the URL of the current Wikipedia article.
     * @return the list of URLs that are pointed by {@code current}.
     * @throws IOException may be thrown.
     */
    private static List<String> getChildArticles(String current) 
    throws IOException {
        return baseGetNeighbors(current, true);
    }

    /**
     * Returns all the parent articles that are linking to {@code current}.
     * 
     * @param current the URL of the current Wikipedia article.
     * @return the list of URLs that are pointing to {@code current}.
     * @throws IOException may be thrown.
     */
    private static List<String> getParentArticles(String current) 
    throws IOException {
        return baseGetNeighbors(current, false);
    }

    /**
     * Returns all the Wikipedia article titles that the current article links 
     * to.
     * 
     * @param jsonText the data in JSON format.
     * @return a list of Wikipedia article titles parsed from {@code jsonText}.
     */
    private static List<String> extractForwardLinkTitles(String jsonText) {
        List<String> linkNameList = new ArrayList<>();
        JsonArray linkNameArray = null;

        try {
            JsonObject root = new JsonParser().parse(jsonText).getAsJsonObject();
            JsonObject queryObject = root.get("query").getAsJsonObject();
            JsonObject pagesObject = queryObject.get("pages").getAsJsonObject();
            JsonObject mainObject  = pagesObject.entrySet()
                                                .iterator()
                                                .next()
                                                .getValue()
                                                .getAsJsonObject();

            linkNameArray = mainObject.get("links") .getAsJsonArray();
        } catch (NullPointerException ex) {
            return linkNameList;
        }

        linkNameArray.forEach((element) -> {
            int namespace = element.getAsJsonObject().get("ns").getAsInt();

            if (namespace == 0) {
                String title = element.getAsJsonObject()
                                      .get("title")
                                      .getAsString();

                linkNameList.add(encodeWikipediaStyle(title));
            }
        });

        return linkNameList;
    }

    /**
     * Returns all the Wikipedia article titles that link to the current
     * article.
     * 
     * @param jsonText the data in JSON format.
     * @return a list of Wikipedia article titles parsed from {@code jsonText}.
     */
    private static List<String> extractBackwardLinkTitles(String jsonText) {
        List<String> linkNameList = new ArrayList<>();
        JsonArray backLinkArray = null;

        try {
            JsonObject root = new JsonParser().parse(jsonText).getAsJsonObject();
            JsonObject queryObject = root.get("query").getAsJsonObject();
            backLinkArray = queryObject.get("backlinks").getAsJsonArray();
        } catch (NullPointerException ex) {
            return linkNameList;
        }

        backLinkArray.forEach((element) -> {
            int namespace = element.getAsJsonObject()
                                   .get("ns")
                                   .getAsInt();

            if (namespace == 0) {
                String title = element.getAsJsonObject()
                                      .get("title")
                                      .getAsString();

                linkNameList.add(encodeWikipediaStyle(title));
            }
        });

        return linkNameList;
    }

    private static String encodeWikipediaStyle(String s) {
        StringBuilder sb = new StringBuilder();

        for (char c : s.toCharArray()) {
            String encoder = ENCODING_MAP.get(c);

            if (encoder != null) {
                sb.append(encoder);
            } else {
                sb.append(c);
            }
        }

        return sb.toString();
    }

    public static void main(String[] args) throws IOException {
        List<String> path = new PathFinder()
                .findShortestPath("Disc_jockey", 
                                  "Daft_Punk",
                                  System.out);

        System.out.println();
        System.out.println("The shortest article path:");
        path.forEach(System.out::println);
    }
}

If you want to run the hardcoded demo, please reserve around two minutes for the search to complete.

The Maven project lives here.

Answer 1

Naming

QUEUEA, QUEUEB, DISTANCEA, DISTANCEB, PARENTSA, PARENTSB

Should be:

queueA, queueB, distanceA, distanceB, parentsA, parentsB

baseGetNeighbors is a strange name. I understand it's the 'base' method for getChildArticles/getParentArticles, but what is wrong with getNeighbors?

Also the reuse and the articulation between those three methods seem a bit naive to me, because tho base method only has three instructions, and only one is strictly identical: the other two use ternary operator... There is little profit in extracting this.

This is more straightforward, as it has no branching:

private static final String CHARSET_NAME =  "UTF-8";
private static final Charset UTF8 =  Charset.forName(CHARSET_NAME);

private static List<String> getChildArticles(String currentTitle) throws IOException {
     String jsonDataUrl = String.format(FORWARD_URL_FORMAT, URLEncoder.encode(currentTitle, CHARSET_NAME ));
    String jsonText = IOUtils.toString(new URL(jsonDataUrl), UTF8);
    return extractForwardLinkTitles(jsonText);
}

private static List<String> getParentArticles(String current) throws IOException {
    String jsonDataUrl = String.format(BACKWARD_URL_FORMAT, URLEncoder.encode(currentTitle, CHARSET_NAME));
    String jsonText = IOUtils.toString(new URL(jsonDataUrl), UTF8);
    return extractBackwardLinkTitles(jsonText);
}

---

Unconventional logging

You require a nullable PrintStream as input, for logging. This is a bad practice because you force the user to worry about it. Worse, you request it in a business method, which could be called in multiple places by the user, so you propagate the problem to those many places.

I you don't want a big re-write, one simple solution is to provide the PrintStream in a setter method. This way the user worries about it once (on creation), not at every usage.

---

Pathfinder` is a Helper in disguise

You have a bunch of static, and non-static method.

Try this: declare all methods static. No compile error? Then your entire class is not an Object, it's a merely Helper.

Why is it so? Your only two public methods are:

• findShortestPath
• The default Constructor

The former merely calls static methods on method-scope variables, it is non-mutating. The latter does nothing since the Object has no field. So constructing is a useless interaction forced down on your user. You have two choices:

• Make the whole class a true Helper (all methods static, private Constructor, final class). This gives minimal code change and is better than the existing, but I do not recommend it. Objects are useful!
• Make the class a true Object with a useful state.

I'll explore what goods the second option brings.

1. Remember the annoying logging? Make it part of the State, provide a Setter.
2. Provide iteration control. MAke iteration state part of Object state. Then you can provide iterate(timeout), iterate(iterationsLimit), iterateOnce(), etc.
3. Reuse the results. Say the user wants to graph a piece of wikipedia. He wants the distance between any two nodes. You're ditching all results after each computation, but after you do search(nodeA, nodeB), you hsould be able to do search(nodeA, nodeC) AND be able to reuse queueA, parentsA, distanceA, etc. If nodeC is already known you just return it. This is out of scope for now obviously, but it would make sense, and having a true Object model is enabling this possibility.

---

Separation of concerns

Your (single) class does:

• Exctract URLS from web pages
• Perform BBFS
• URL encoding/decoding

That is too much. Split it in several sub-classes. This will allow you later to swap the m with more pewerful functionalities (caching result, A* star - although I don't know with which heuristic ^^ - etc.).

---

Algorithm pitfall

Be careful about how you find the touchNode. There could be several touchNodes, and the first one encountered is not necessarily the best.

It is in your case, because all distances are equal to 1. In general in bidirectional search it is not the case, you could find a touchNode1 which links up both BFS with a cost of 2.5 + 3.5, and miss a touchNode2 which links us with a cost of 3.5 + 0.2 (which is better, but evaluated later because its first link is more expensive, so it was later in the QueueA).

You're fine, just keep this in mind in future implementations (e.g. if you want to make you bidirectional pathfinder generic).