3
\$\begingroup\$

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.

See the previous iteration. I have refactored the code as to lower down the cyclomatic complexity. What can I do more in order to improve the quality of my program?

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.618 (Sep 19, 2015)
 */
public class App {

    /**
     * This interface defines a command handler.
     */
    @FunctionalInterface
    private static interface CommandHandler {

        /**
         * Handles a command. This method requires two arguments which are 
         * basically the same, as some handlers are better implemented with a 
         * particular command representation.
         * 
         * @param command the actual line containing the entire command.
         * @param tokens  the whitespace delimited tokens of {@code command}.
         */
        void handle(String command, String[] tokens);
    }

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

    private final CommandHandler connectHandler = 
            (String command, String[] tokens) -> {
        handleConnect(tokens);
    };

    private final CommandHandler delHandler = 
            (String command, String[] tokens) -> {
        handleDel(tokens);
    };

    private final CommandHandler disconnectHandler = 
            (String command, String[] tokens) -> {
        handleDisconnect(tokens);
    };

    private final CommandHandler echoHandler = 
            (String command, String[] tokens) -> {
        handleEcho(command);
    };

    private final CommandHandler helpHandler = 
            (String command, String[] tokens) -> {
        handleHelp(tokens);
    };

    private final CommandHandler isHandler = 
            (String command, String[] tokens) -> {
        handleIs(tokens);
    };

    private final CommandHandler newHandler = 
            (String command, String[] tokens) -> {
        handleNew(tokens);
    };

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

    /**
     * Maps some command names to their respective handlers.
     */
    private final Map<String, CommandHandler> commandMap = 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;

    /**
     * The scanner for reading the commands.
     */
    private Scanner scanner;

    /**
     * The array of file names to execute.
     */
    private String[] fileNameArray;

    /**
     * The index of the file currently executed.
     */
    private int fileNameIndex;

    /**
     * If set to {@code true} the command prompt "> " will be printed.
     */
    private boolean allowPrompt;

    /**
     * If set to {@code true}, we are reading from standard input.
     */
    private boolean readingFromStdin;

    private App(String[] fileNameArray) {
        this.fileNameArray = fileNameArray;

        commandMap.put("new",        newHandler);
        commandMap.put("del",        delHandler);
        commandMap.put("connect",    connectHandler);
        commandMap.put("disconnect", disconnectHandler);
        commandMap.put("is",         isHandler);
        commandMap.put("echo",       echoHandler);
        commandMap.put("help",       helpHandler);

        if (fileNameArray.length > 0) {
            String fileName = fileNameArray[0];

            try {
                scanner = new Scanner(new FileReader(new File(fileName)));
                fileNameIndex++;
                readingFromStdin = false;
            } catch (FileNotFoundException ex) {
                System.out.println(
                        "ERROR: File \"" + fileName + "\" not found.");
                System.exit(1);
            }

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

    private boolean promptAllowed() {
        return allowPrompt;
    }

    private String read() {
        if (!scanner.hasNextLine()) {
            if (fileNameIndex == fileNameArray.length) {
                scanner = new Scanner(System.in);
                allowPrompt = true;
                readingFromStdin = true;
                System.out.print("> ");
            } else {
                try {
                    scanner = new Scanner(
                              new FileReader(
                              new File(fileNameArray[fileNameIndex])));
                    ++fileNameIndex;
                } catch (FileNotFoundException ex) {
                    error("File \"" + fileNameArray[fileNameIndex] + 
                          "\" is not found.");
                    System.exit(1);
                }
            }
        } 

        return scanner.nextLine();
    }

    /**
     * This method implements the actual REPL (Read, Evaluate, Print, Loop).
     */
    private void loop() {
        while (true) {
            if (promptAllowed()) {
                System.out.print("> ");
            }

            String command = read();

            if (command.isEmpty() || command.startsWith("#")) {
                // No text in the command or a line comment.
                continue;
            }

            if (command.equals("quit")) {
                if (readingFromStdin) {
                    System.out.println("Bye!");
                }

                // Print no 'Bye!' whenever executing from files.
                return;
            }

            handleCommand(command);
        }
    }

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

        if (commandMap.containsKey(words[0])) {
            commandMap.get(words[0]).handle(command, words);
        } else if (words[0].equals("list")) {
            handleList(true);
        } else if (handleQuery(command)) {
            // Once here, the command was recognized as a query. Do not go
            // to 'handlePrintNode'.
        } else {
            // No match whatsoever, possibly the user wants to query a node 
            // information.
            handlePrintNode(words);
        }
    }

    /**
     * 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 update probability) 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);
    }

    private Map<DirectedGraphNode, Boolean> 
        loadVariableMap(String command) {
        String[] variableStrings = command.split(",");
        Map<DirectedGraphNode, Boolean> map = new HashMap<>();

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

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

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

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

        return map;
    }

    /**
     * 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 =
                loadVariableMap(parts[0]);
        Map<DirectedGraphNode, Boolean> aprioriVariables = 
                loadVariableMap(parts[1]);

        try {
            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;
        }

        new App(args).loop();
    }
}
\$\endgroup\$
3
\$\begingroup\$

The App class groups a huge list of functionalities: it parses different commands ("new", "del", "connect" etc) and queries, executes them, produces output et alia. It looks like it is very much against the SRP and is just not easy to navigate into.

I'd suggest that each CommandHandler definition should represent a dedicated class outside App. All of these functionalities can be grouped within a shortened version of CommandHandler interface. Indeed, according to the current code, its arguments String command and String[] tokens represent one thing: the input and its split. So having

interface ExecutableCommand {

  // or this may be an abstract parent class for the commands,
  // with the input line split in the constructor

  void processCommand(String command);

}

would be enough to wrap the things like

class ConnectCommand implements ExecutableCommand {

  ...

  @Override
  void processCommand(String command) {

    // the logic of the handleConnect() method

  }

}

and so on for the other commands.

The handleList() method should also be put under this hierarchy. There is no reason to make it distinct from others; the boolean arg that it currently receives is used only to control the output, which may be triggered through a dedicated method.

Each concrete ExecutableCommand implementation may also host a method that returns the contents of the help section for the command: this will avoid to have the infinite switch clause while handling the help output.

Finally, commandMap is not a very comfortable container for the commands and their handlers. An enum would suit better, for example

public enum Command {

  CONNECT(new ConnectCommand()),

  ECHO(new EchoCommand()),

  ANOTHER_COMMAND(...);

  private final ExecutableCommand handler;

  private Commands(ExecutableCommand handler) {
    this.handler = handler;
  }

  public void execute(String input) {
    this.handler.processCommand(input);
  }

}

Changes of this kind will drastically separate distinct functionalities of the class and will make them more readable and easily maintainable.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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