[Back to the 30 Days of Programming Overview Page]

BFS in Java

So it turns out the current Wikipedia article's "pseudocode" for BFS totally sucks. This old version is pretty good, though, as is this hackerearth tutorial. Anyway, it's BFS, so it's pretty straightforward. Most of this Java code is actually I/O, because I went a bit overboard with the I/O.

Source Code (Graph.java)

[raw] [download]

import java.io.*;
import java.net.*;
import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class Graph<T> {
    public final Map<T, Collection<T>> adjacencies;
    public final Supplier<? extends Collection<T>> collectionSupplier;

    public Graph() {
        this(new LinkedHashMap<>(), ArrayList<T>::new);
    }

    public Graph(Map<T, Collection<T>> adjacencies,
            Supplier<? extends Collection<T>> collectionSupplier) {
        this.adjacencies = adjacencies;
        this.collectionSupplier = collectionSupplier;
    }

    public static String urlEncode(String str) {
        try {
            return URLEncoder.encode(str, "UTF-8");
        } catch (UnsupportedEncodingException e) {
            throw new RuntimeException("No UTF-8 support.", e);
        }
    }

    public static String urlDecode(String str) {
        try {
            return URLDecoder.decode(str, "UTF-8");
        } catch (UnsupportedEncodingException e) {
            throw new RuntimeException("No UTF-8 support.", e);
        }
    }

    public void fromString(String str, Function<String, T> parseTag) {
        int end = str.indexOf('{');
        int arrow;
        while ((arrow = str.indexOf("->", end + 1)) != -1) {
            T tag = parseTag.apply(urlDecode(
                str.substring(end + 1, arrow).trim()));
            int start = str.indexOf('{', arrow + 2) + 1;
            if (start == 0) {
                break;
            }
            end = str.indexOf('}', start);
            if (end == -1) {
                break;
            }
            Collection<T> collection;
            if (adjacencies.containsKey(tag)) {
                collection = adjacencies.get(tag);
            } else {
                collection = collectionSupplier.get();
                adjacencies.put(tag, collection);
            }
            Arrays.stream(str.substring(start, end).trim().split("\\s+"))
                .map(s -> s.trim())
                .filter(s -> !s.isEmpty())
                .map(s -> parseTag.apply(urlDecode(s)))
                .forEachOrdered(t -> {
                    collection.add(t);
                    if (!adjacencies.containsKey(t)) {
                        adjacencies.put(t, collectionSupplier.get());
                    }
                });
        }
    }

    public void fromBreadthFirstSearchTree(Graph<T> graph, T start) {
        Queue<T> queue = new ArrayDeque<>();
        adjacencies.put(start, collectionSupplier.get());
        queue.add(start);
        while (queue.peek() != null) {
            T tag = queue.remove();
            for (T adjacent : graph.adjacencies.get(tag)) {
                if (!adjacencies.containsKey(adjacent)) {
                    adjacencies.put(adjacent, collectionSupplier.get());
                    adjacencies.get(tag).add(adjacent);
                    queue.add(adjacent);
                }
            }
        }
    }

    @Override
    public String toString() {
        return "Graph {"
            + adjacencies.entrySet().parallelStream()
                .map(entry -> String.format("\n  %s -> { %s }",
                    urlEncode(entry.getKey().toString()),
                    entry.getValue().parallelStream()
                        .map(n -> urlEncode(n.toString()))
                        .collect(Collectors.joining(" "))))
                .reduce("", String::concat)
            + "\n}";
    }

    public static void main(String[] args) {
        try {
            String input = new String(System.in.readAllBytes());
            int startEnd = input.indexOf('{');
            String start = urlDecode(input.substring(0, startEnd).trim());
            Graph<String> graph = new Graph<>();
            graph.fromString(input, s -> s);
            System.out.println("Input graph: " + graph);
            System.out.println("Starting node: " + urlEncode(start));
            Graph<String> tree = new Graph<>();
            tree.fromBreadthFirstSearchTree(graph, start);
            System.out.println("Breadth-first order: {");
            for (String tag : tree.adjacencies.keySet()) {
                System.out.println("  " + urlEncode(tag));
            }
            System.out.println("}");
            System.out.println("Breadth-first tree: " + tree);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

Example Runs

$ cat test.graph
Frank {
  Frank -> {Mann Wurz Kassel}
  Mann -> {Frank Karls}
  Karls -> {Mann Augs}
  Augs -> {Karls Mun}
  Mun -> {Augs Nurn Kassel}
  Nurn -> {Wurz Stutt}
  Wurz -> {Frank Erf Nurn}
  Erf -> {Wurz}
  Stutt -> {Nurn}
  Kassel -> {Frank Mun}
}
$ java Graph < test.graph
Input graph: Graph {
  Frank -> { Mann Wurz Kassel }
  Mann -> { Frank Karls }
  Karls -> { Mann Augs }
  Augs -> { Karls Mun }
  Mun -> { Augs Nurn Kassel }
  Nurn -> { Wurz Stutt }
  Wurz -> { Frank Erf Nurn }
  Erf -> { Wurz }
  Stutt -> { Nurn }
  Kassel -> { Frank Mun }
}
Starting node: Frank
Breadth-first order: {
  Frank
  Mann
  Wurz
  Kassel
  Karls
  Erf
  Nurn
  Mun
  Augs
  Stutt
}
Breadth-first tree: Graph {
  Frank -> { Mann Wurz Kassel }
  Mann -> { Karls }
  Wurz -> { Erf Nurn }
  Kassel -> { Mun }
  Karls -> { Augs }
  Erf -> {  }
  Nurn -> { Stutt }
  Mun -> {  }
  Augs -> {  }
  Stutt -> {  }
}
$ cat tree.graph
a {
  a -> {b c}
  b -> {d e}
  e -> {h}
  c -> {f g}
}
$ java Graph < tree.graph
Input graph: Graph {
  a -> { b c }
  b -> { d e }
  c -> { f g }
  d -> {  }
  e -> { h }
  h -> {  }
  f -> {  }
  g -> {  }
}
Starting node: a
Breadth-first order: {
  a
  b
  c
  d
  e
  f
  g
  h
}
Breadth-first tree: Graph {
  a -> { b c }
  b -> { d e }
  c -> { f g }
  d -> {  }
  e -> { h }
  f -> {  }
  g -> {  }
  h -> {  }
}