11
\$\begingroup\$

I was working on the binary Bayesian network classifier I asked about earlier.

See also Part II/II.

See also the next iteration of Part I.

TERMINOLOGY We are given a directed acyclic graph (dag) \$G = (V, A)\$, where \$V\$ is the set of nodes and \$A \subseteq V \times V\$ is the set of directed arcs, and a weight function \$p \colon V \to [0, 1]\$. For any node \$u \in V\$, \$parents(u) =\{v \in V \colon (v, u) \in A\}\$, which is a set of parent (or incoming) nodes of \$u\$. Now, each node \$u\$ corresponds to some part that "works" with probability \$p(u)\$ and "fails" with probability \$1 - p(u)\$. However, if any such \$u\$ has a non-empty set of parents and at least one of the parents failed, \$u\$ fails unconditionally.

MISSION I wrote a REPL (read, evaluate, print, loop) program, which allows its users to build a binary Bayesian network and perform queries on it; for example, p(not Radio, Battery | not Moves, Ignition), or "what is the probability that radio does not work and battery does work if we know that ignition is in order and the car does not move.

SAMPLE INPUT

# Create nodes.
new Battery  0.9  # Comment
new Radio    0.9  
new Ignition 0.95
new Fuel     0.95
new Starts   0.99
new Moves    0.99

# Print a node.
Fuel
del Fuel
echo Removed Fuel
Fuel
new Fuel 0.95

# Create arcs.
connect Battery  to Radio
connect Battery  to Ignition
connect Ignition to Starts
connect Fuel     to Starts
connect Starts   to Moves

# Check a couple of arcs.
echo Battery connected to Radio?
is Battery connected to Radio   # Must be 'true'.
echo Radio connected to Battery?
is Radio   connected to Battery # Must be 'false'.

# Remove an arc (Battery, Radio).
disconnect Battery from Radio
echo Removed arc (Battery, Radio).
echo Is Battery connected to Radio?
is Battery connected to Radio
connect Battery to Radio

# Print a couple of nodes.
Battery
Starts
Radio

# List all possible system states with their probabilities.
list

# Try a couple of queries.
p(Battery|not Moves, not Starts)
p(not Battery| not Starts)

# Show help.
help
help is connected

# Make the graph disonnected.
disconnect Ignition from Starts
echo Here, the graph must not be connected.
list

quit
echo You must not see this message.

SAMPLE OUTPUT

"Fuel", probability 0.95, parents: <>, children: <>
Removed Fuel
ERROR: "Fuel": no such node.
Battery connected to Radio?
true
Radio connected to Battery?
false
Removed arc (Battery, Radio).
Is Battery connected to Radio?
false
"Battery", probability 0.9, parents: <>, children: <Ignition, Radio>
"Starts", probability 0.99, parents: <Ignition, Fuel>, children: <Moves>
"Radio", probability 0.9, parents: <Battery>, children: <>
Compiled the graph in 7 milliseconds.
Number of possible states: 14
(Battery, Fuel, Ignition, Radio, Starts, Moves)
(      0,    0,        0,     0,      0,     0): 0.005000000000000004
(      0,    1,        0,     0,      0,     0): 0.09499999999999997
(      1,    0,        0,     0,      0,     0): 2.2500000000000037E-4
(      1,    0,        0,     1,      0,     0): 0.002025000000000004
(      1,    0,        1,     0,      0,     0): 0.004275000000000003
(      1,    0,        1,     1,      0,     0): 0.03847500000000003
(      1,    1,        0,     0,      0,     0): 0.004275000000000003
(      1,    1,        0,     1,      0,     0): 0.03847500000000003
(      1,    1,        1,     0,      0,     0): 8.122500000000005E-4
(      1,    1,        1,     0,      1,     0): 8.041275000000005E-4
(      1,    1,        1,     0,      1,     1): 0.07960862249999998
(      1,    1,        1,     1,      0,     0): 0.007310250000000006
(      1,    1,        1,     1,      1,     0): 0.007237147500000006
(      1,    1,        1,     1,      1,     1): 0.7164776024999999
0.4894638093657867
0.5105361906342133
  help new
  help del
  help connect
  help is connected
  help disconnect
  help list
  help echo
  help #
  help <nodename>
  help p
  help quit
"is <tailnode> connected to <headnode>"
Asks whether <tailnode> has a child <headnode>.
Here, the graph must not be connected.
ERROR: The graph is not connected.

App.java:

package net.coderodde.ai.bayesiannetwork;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import static net.coderodde.ai.bayesiannetwork.BayesNetworkClassifier.classify;
import static net.coderodde.ai.bayesiannetwork.Utils.findEntireGraph;

/**
 * This class implements a console program for working on Bayes networks.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.61 (Sep 18, 2015)
 */
public class App {

    /**
     * This map maps each node name to its internal representation.
     */
    private final Map<String, DirectedGraphNode> nodeMap = new HashMap<>();

    /**
     * This map maps each node to its probability.
     */
    private final ProbabilityMap<DirectedGraphNode> probabilityMap =
            new ProbabilityMap<>();

    /**
     * Indicates whether the state of the graph was changed after last
     * compilation.
     */
    private boolean stateModified = true;

    /**
     * Caches the last classification result for queries.
     */
    private ClassificationResult result;

    /**
     * This method implements the actual REPL (Read, Evaluate, Print, Loop).
     * 
     * @param fileNames the array containing the names of the files to execute.
     *                  This array may be null, in which case the program reads
     *                  from the console. If array is not {@code null}, executes
     *                  the files in the order they appear in the array.
     */
    private void loop(String[] fileNames) {
        Scanner scanner;
        boolean turnOffPrompt;
        int fileNameIndex = 0;

        if (fileNames != null) {
            try {
                scanner = new Scanner(
                          new FileReader(
                          new File(fileNames[fileNameIndex])));

                fileNameIndex++;
            } catch (FileNotFoundException ex) {
                error("File \"" + fileNames[fileNameIndex] + "\" not found.");
                return;
            }

            turnOffPrompt = true;
        } else {
            scanner = new Scanner(System.in);
            turnOffPrompt = false;
        }

        for (;;) {
            if (!turnOffPrompt) {
                System.out.print("> ");
            }

            if (!scanner.hasNextLine()) {
                // Here, we possibly have that a file was read in its entirety.
                // What next? Proceed to executing the next file, or if there is 
                // no such, go read from the standard input.
                if (fileNames != null) {
                    if (fileNameIndex == fileNames.length) {
                        // Once here, we have executed all files on the command
                        // line. Switch to reading from stdin.
                        fileNames = null;
                        turnOffPrompt = false;
                        scanner = new Scanner(System.in);
                        System.out.print("> ");
                    } else {
                        try {
                            scanner = new Scanner(
                                      new FileReader(
                                      new File(fileNames[fileNameIndex])));
                            fileNameIndex++;
                        } catch (FileNotFoundException ex) {
                            error("File \"" + fileNames[fileNameIndex] + 
                                  "\" not found.");
                        }
                    }
                } else {
                    return;
                }
            }

            String command = scanner.nextLine().trim();

            if (command.isEmpty()) {
                // No text in the command.
                continue;
            }

            if (command.equals("quit")) {
                if (fileNames != null) {
                    // Print no 'Bye!' whenever executing from files.
                    return;
                }

                break;
            }

            if (command.startsWith("#")) {
                // A comment line.
                continue;
            }

            // Obtain whitespace delimited tokens.
            String[] words = command.split("\\s+");

            // Choose the command by the first token.
            switch (words[0]) {
                case "new": {
                    handleNew(words);
                    continue;
                }

                case "del": {
                    handleDel(words);
                    continue;
                }

                case "connect": {
                    handleConnect(words);
                    continue;
                }

                case "disconnect": {
                    handleDisconnect(words);
                    continue;
                }

                case "list": {
                    handleList(true);
                    continue;
                }

                case "is": {
                    handleIs(words);
                    continue;
                }

                case "echo": {
                    handleEcho(command);
                    continue;
                }

                case "help": {
                    handleHelp(words); 
                    continue;
                }
            }

            if (handleQuery(command)) {
                // Once here, the command was recognized as a query, so go 
                // reiterate the REPL loop.
                continue;
            }

            // No match whatsoever, possibly the user wants to query a node 
            // information.
            handlePrintNode(words);
        }

        System.out.println("Bye!");
    }

    /**
     * Checks that an identifier is a valid Java identifier.
     * 
     * @param identifier the identifier to check.
     * @return {@code true} only if the input identifier is valid.
     */
    private static boolean isValidIdentifier(String identifier) {
        if (identifier.isEmpty()) {
            return false;
        }

        if (!Character.isJavaIdentifierStart(identifier.charAt(0))) {
            return false;
        }

        for (int i = 1; i < identifier.length(); ++i) {
            if (!Character.isJavaIdentifierPart(identifier.charAt(i))) {
                return false;
            }
        }

        return true;
    }

    /**
     * Handles the command starting with "new".
     * @param words the token array.
     */
    private void handleNew(String[] words) {
        if (words.length < 3) {
            error("Cannot parse 'new' command.");
            return;
        }

        if (words.length >= 4 && !words[3].startsWith("#")) {
            error("Bad comment format.");
            return;
        }

        String nodeName = words[1];
        String probabilityString = words[2];

        if (!isValidIdentifier(nodeName)) {
            error("\"" + nodeName + "\" is a bad node identifier.");
            return;
        }

        double probability;

        try {
            probability = Double.parseDouble(probabilityString);
        } catch (NumberFormatException ex) {
            error("Cannot parse \"" + probabilityString + 
                  "\" as a probability value.");
            return;
        }

        if (Double.isNaN(probability)) {
            error("Input probability is NaN.");
            return;
        }

        if (probability < 0.0) {
            error("Probability is too small.");
            return;
        }

        if (probability > 1.0) {
            error("Probability is too large.");
            return;
        }

        // Associate (or reassociate) the node with the probability value.
        DirectedGraphNode node;

        if (nodeMap.containsKey(nodeName)) {
            node = nodeMap.get(nodeName);
            probabilityMap.put(node, probability);
        } else {
            node = new DirectedGraphNode(nodeName);
            nodeMap.put(nodeName, node);
        }

        probabilityMap.put(node, probability);
    }

    /**
     * Handles the command for deleting a node.
     * 
     * @param words the array of tokens.
     */
    private void handleDel(String[] words) {
        if (words.length < 2) {
            error("Missing the name of the node to delete.");
            return;
        }

        String nodeName = words[1];

        if (!isValidIdentifier(nodeName)) {
            error("\"" + nodeName + "\" is not a valid node name.");
            return;
        }

        DirectedGraphNode removed = nodeMap.remove(nodeName);

        if (removed != null) {
            removed.clear();
            probabilityMap.remove(removed);
            stateModified = true;
        }
    }

    /**
     * Handles the command for creating arcs between nodes.
     * 
     * @param words the array of tokens.
     */
    private void handleConnect(String[] words) {
        if (words.length < 4) {
            error("Missing required tokens.");
            return;
        }

        if (!words[2].equals("to")) {
            error("Format error.");
            return;
        }

        String tailNodeName = words[1];
        String headNodeName = words[3];

        if (!isValidIdentifier(tailNodeName)) {
            error("Bad tail node name: \"" + tailNodeName + "\".");
            return;
        }

        if (!isValidIdentifier(headNodeName)) {
            error("Bad head node name: \"" + headNodeName + "\".");
            return;
        }

        if (!nodeMap.containsKey(tailNodeName)) {
            error("No node with name \"" + tailNodeName + "\".");
            return;
        }

        if (!nodeMap.containsKey(headNodeName)) {
            error("No node with name \"" + headNodeName + "\".");
            return;
        }

        if (tailNodeName.equals(headNodeName)) {
            error("Self-loops not allowed.");
            return;
        }

        DirectedGraphNode tail = nodeMap.get(tailNodeName);
        DirectedGraphNode head = nodeMap.get(headNodeName);

        if (!tail.hasChild(head)) {
            tail.addChild(head);
            stateModified = true;
        }
    }

    /**
     * Handles the command for removing arcs between nodes.
     * 
     * @param words the array of tokens.
     */
    private void handleDisconnect(String[] words) {
        if (words.length < 4) {
            error("Missing required tokens.");
            return;
        }

        if (!words[2].equals("from")) {
            error("Format error.");
            return;
        }

        String tailNodeName = words[1];
        String headNodeName = words[3];

        if (!isValidIdentifier(tailNodeName)) {
            error("Bad tail node name: \"" + tailNodeName + "\".");
            return;
        }

        if (!isValidIdentifier(headNodeName)) {
            error("Bad head node name: \"" + headNodeName + "\".");
            return;
        }

        if (!nodeMap.containsKey(tailNodeName)) {
            error("No node with name \"" + tailNodeName + "\".");
            return;
        }

        if (!nodeMap.containsKey(headNodeName)) {
            error("No node with name \"" + headNodeName + "\".");
            return;
        }

        if (tailNodeName.equals(headNodeName)) {
            return;
        }

        DirectedGraphNode tail = nodeMap.get(tailNodeName);
        DirectedGraphNode head = nodeMap.get(headNodeName);

        if (tail.hasChild(head)) {
            tail.removeChild(head);
            stateModified = true;
        }
    }

    /**
     * Handles the command for querying the existence of arcs between particular
     * nodes.
     * 
     * @param words the array of tokens.
     */
    private void handleIs(String[] words) {
        if (words.length < 5
                || !words[2].equals("connected")
                || !words[3].equals("to")) {
            error("Bad format.");
            return;
        }

        String tailNodeName = words[1];
        String headNodeName = words[4];

        if (!isValidIdentifier(tailNodeName)) {
            error("Bad tail node name \"" + tailNodeName + "\".");
            return;
        }

        if (!isValidIdentifier(headNodeName)) {
            error("Bad head node name \"" + headNodeName + "\".");
            return;
        }

        if (!nodeMap.containsKey(tailNodeName)) {
            error("No node \"" + tailNodeName + "\"");
            return;
        }

        if (!nodeMap.containsKey(headNodeName)) {
            error("No node \"" + headNodeName + "\"");
            return;
        }

        DirectedGraphNode tail = nodeMap.get(tailNodeName);
        DirectedGraphNode head = nodeMap.get(headNodeName);

        System.out.println(tail.hasChild(head));
    }

    /**
     * Handles the command for listing the system states.
     * 
     * @param showList whether to show the actual state list after successful
     *                 compilation.
     */
    private void handleList(boolean showList) {
        if (stateModified) {
            List<DirectedGraphNode> network = new ArrayList<>(nodeMap.values());

            if (network.isEmpty()) {
                error("You have no nodes.");
                return;
            }

            List<DirectedGraphNode> component = findEntireGraph(network.get(0));

            if (component.size() < network.size()) {
                error("The graph is not connected.");
                return; 
            }

            try {
                long startTime = System.currentTimeMillis();
                result = BayesNetworkClassifier.classify(network, 
                                                         probabilityMap);
                long endTime = System.currentTimeMillis();
                stateModified = false;

                System.out.println("Compiled the graph in " + 
                                  (endTime - startTime) + " milliseconds.");
                if (Math.abs(1.0 - result.getSumOfProbabilities()) > 0.0001) {
                    throw new IllegalStateException(
                    "The sum of probabilities over all possible states does " + 
                    "not sum to 1.0");
                }

                System.out.println("Number of possible states: " +
                                   result.getNumberOfStates());
            } catch (Exception ex) {
                error(ex.getMessage());
                return;
            }
        }

        if (result == null) {
            error("No network built yet.");
        } else if (showList) {
            System.out.print(result);
        }
    }

    /**
     * Handles the command for printing to the console.
     * 
     * @param command the command.
     */
    private void handleEcho(String command) {
        String leftovers = command.substring(4).trim();
        System.out.println(leftovers);
    }

    /**
     * Handles the commands for making queries on the network.
     * 
     * @param command the command.
     * @return {@code true} if command prefix is that of query commands.
     */
    private boolean handleQuery(String command) {
        if (!command.startsWith("p(")) {
            return false;
        }

        if (stateModified) {
            handleList(false);

            if (stateModified) {
                // If 'handleList' could not update the state, we have a problem
                // with the graph: it is either disconnected or contains cycles.
                return true;
            }
        }

        if (!command.endsWith(")")) {
            error("No trailing \")\".");
            return true;
        }

        String innerContent = command.substring(2, command.length() - 1).trim();
        String[] parts = innerContent.split("\\|");

        if (parts.length != 2) {
            error("No single delimeter bar |");
            return true;
        }

        Map<DirectedGraphNode, Boolean> posterioriVariables = new HashMap<>();
        Map<DirectedGraphNode, Boolean> aprioriVariables = new HashMap<>();

        String[] posterioriVarStrings = parts[0].split(",");
        String[] aprioriVarStrings = parts[1].split(",");

        try {
            for (int i = 0; i < posterioriVarStrings.length; ++i) {
                posterioriVarStrings[i] = posterioriVarStrings[i].trim();
                boolean negate = false;
                String varName;

                if (posterioriVarStrings[i].startsWith("not ")) {
                    negate = true;
                    varName = posterioriVarStrings[i].substring(4);
                } else {
                    varName = posterioriVarStrings[i];
                }

                if (!nodeMap.containsKey(varName)) {
                    error("No node \"" + varName + "\".");
                    return true;
                } 

                posterioriVariables.put(nodeMap.get(varName), !negate);
            }

            for (int i = 0; i < aprioriVarStrings.length; ++i) {
                aprioriVarStrings[i] = aprioriVarStrings[i].trim();
                boolean negate = false;
                String varName;

                if (aprioriVarStrings[i].startsWith("not ")) {
                    negate = true;
                    varName = aprioriVarStrings[i].substring(4);
                } else {
                    varName = aprioriVarStrings[i];
                }

                if (!nodeMap.containsKey(varName)) {
                    error("No node \"" + varName + "\".");
                    return true;
                }

                aprioriVariables.put(nodeMap.get(varName), !negate);
            }

            if (stateModified) {
                try {
                    result = classify(new ArrayList<>(nodeMap.values()), 
                                      probabilityMap);

                    if (result != null) {
                        stateModified = false;
                    }
                } catch (Exception ex) {
                    error(ex.getMessage());
                    return true;
                }
            }

            System.out.println(result.query(posterioriVariables, 
                                            aprioriVariables));
        } catch (Exception ex) {
            error(ex.getMessage());
            return true;
        }

        return true;
    }

    /**
     * Handles the command for printing a node information.
     * 
     * @param words the array of tokens.
     */
    private void handlePrintNode(String[] words) {
        if (words.length > 1 && !words[1].startsWith("#")) {
            error("Bad command.");
            return;
        }

        if (!nodeMap.containsKey(words[0])) {
            error("\"" + words[0] + "\": no such node.");
            return;
        }

        DirectedGraphNode node = nodeMap.get(words[0]);
        StringBuilder sb = new StringBuilder();
        int i = 0;

        // Get parent node names.
        for (DirectedGraphNode parent : node.parents()) {
            sb.append(parent);

            if (i++ < node.parents().size() - 1) {
                sb.append(", ");
            }
        }

        String parentListString = sb.toString();

        sb.delete(0, sb.length());
        i = 0;

        // Get child node names.
        for (DirectedGraphNode child : node.children()) {
            sb.append(child);

            if (i++ < node.children().size() - 1) {
                sb.append(", ");
            }
        }

        String childListString = sb.toString();

        System.out.println(
                "\"" + words[0] + "\", probability " + 
                probabilityMap.get(node) + ", parents: <" + parentListString +
                ">, children: <" + childListString + ">");
    }

    /**
     * Handles the command for printing the help information.
     * 
     * @param words the array of tokens.
     */
    private void handleHelp(String[] words) {
        if (words.length > 3) {
            error("The syntax for \"help\" command is \"help [keywords]\".");
            return;
        } else if (words.length == 3) {
            if (!words[1].equals("is") || !words[2].equals("connected")) {
                error("The syntax for \"help\" command is " +
                      "\"help [keywords]\".");
                return;
            }
        }

        if (words.length == 1) {
            System.out.println("  help new");
            System.out.println("  help del");
            System.out.println("  help connect");
            System.out.println("  help is connected");
            System.out.println("  help disconnect");
            System.out.println("  help list");
            System.out.println("  help echo");
            System.out.println("  help #");
            System.out.println("  help <nodename>");
            System.out.println("  help p");
            System.out.println("  help quit");
            return;
        }

        switch (words[1]) {
            case "new": {
                System.out.println("\"new <nodename> <probability>\"");
                System.out.println("Creates a new node with name <nodename> " +
                                   "and probability <probability>.");
                break;
            }

            case "del": {
                System.out.println("\"del <nodename>\"");
                System.out.println("Deletes the node with name <nodename>.");
                break;
            }

            case "connect": {
                System.out.println("\"connect <tailnode> to <headnode>\"");
                System.out.println("Creates an arc from <tailnode> to " +
                                   "<headnode>.");
                break;
            }

            case "is": {
                if (words.length != 3) {
                    System.out.println(
                            "ERROR: No help topic. Did you mean " +
                            "\"help is connected\"?");
                } else {
                    System.out.println(
                            "\"is <tailnode> connected to <headnode>\"");
                    System.out.println("Asks whether <tailnode> has a child " +
                                       "<headnode>.");
                }

                break;
            }

            case "disconnect": {
                System.out.println("\"disconnect <tailnode> from <headnode>\"");
                System.out.println("Removes an arc from <tailnode> to " +
                                   "<headnode>.");
                break;
            }

            case "list": {
                System.out.println("\"list\"");
                System.out.println("Lists all the possible system states.");
                break;
            }

            case "echo": {
                System.out.println("\"echo [<text>]\"");
                System.out.println("Prints <text> to the console.");
                break;
            }

            case "#": {
                System.out.println("\"# [<text>]\"");
                System.out.println("Starts a line comment.");
                break;
            }

            case "p": {
                System.out.println(
                        "\"p(<posterioriVariables> | " +
                        "<aprioriVariables>)\"");
                System.out.println("Makes a query.");
                System.out.println("EXAMPLE 1: p(not var1 | var2, not var3)");
                System.out.println("EXAMPLE 2: p(var 1 | var2)");
                System.out.println(".");
                System.out.println(".");
                System.out.println(".");
                break;
            }

            case "<nodename>": {
                System.out.println("\"<nodename>\"");
                System.out.println("Print the node information.");
                break;
            }

            case "quit": {
                System.out.println("\"quit\"");
                System.out.println("Quits the program.");
                break;
            }

            default: {
                System.out.println(
                        "ERROR: Unknown topic: \"" + words[1] + "\"");
                break;
            }
        }
    }

    /**
     * Returns {@code true} if at least one of the input strings is "-h".
     * 
     * @param args the strings to check.
     * @return {@code true} if at least one of the strings is "-h".
     */
    private static boolean hasHelpFlag(String[] args) {
        for (String argument : args) {
            if (argument.trim().equals("-h")) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        if (hasHelpFlag(args)) {
            System.out.println(
                    "java -jar <PROGRAM.jar> [-h] [FILE1 FILE2 ... FILEN]");
            return;
        }

        App app = new App();

        if (args.length == 0) {
            app.loop(null);
        } else {
            app.loop(args);
        }
    }

    private static void error(String message) {
        System.err.println("ERROR: " + message);
    }
}

CRITIQUE REQUEST In what ways can I improve my code?

\$\endgroup\$
0

1 Answer 1

12
\$\begingroup\$

I like comments. I like Javadoc. But comments that say what are suspicious - good comments say why, not what. Given self-explanatory code, Javadoc on private members is overkill: you have Javadoc everywhere, and it's distracting.


/**
 * This method implements the actual REPL (Read, Evaluate, Print, Loop).
 * 
 * @param fileNames the array containing the names of the files to execute.
 *                  This array may be null, in which case the program reads
 *                  from the console. If array is not {@code null}, executes
 *                  the files in the order they appear in the array.
 */
private void loop(String[] fileNames) {

The method has outrageous cyclomatic complexity, is breaking the Single Responsibility Principle (SRP) by design, and is poorly named - granted, naming a method that's doing 4 things is certainly a hard thing to do. But given read, evaluate, print and loop, I really wonder why a method that does all 4 would simply be called loop.

Speaking of loops:

for (;;) {

Clearly you're abusing the for construct here. A more idiomatic "infinite loop" would be while (true).

\$\endgroup\$
0

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.