RouteBetweenNodes (_4_1)

RouteBetweenNodes.java

import java.util.LinkedList;

/**
 * Route Between Nodes: Given a directed graph, design an algorithm to find out
 * whether there is a route between two nodes.
 * Hints: #127
 */
public class RouteBetweenNodes {
    public static void main(String[] args) {
//        Node node8 = new Node("node8", new Node[]{});
//        Node node7 = new Node("node7", new Node[]{});
//
//        Node node6 = new Node("node6", new Node[]{});
//        Node node5 = new Node("node5", new Node[]{node8});
//
//        Node node4 = new Node("node4", new Node[]{node7});
//        Node node3 = new Node("node3", new Node[]{});
//
//        Node node2 = new Node("node2", new Node[]{node5, node6});
//        Node node1 = new Node("node1", new Node[]{node3, node4});
//
//        Node root = new Node("root", new Node[]{node1, node2});

        //                                  root
        //                  node1                               node2
        //          node3          node4            node5                   node6
        //                         node7            node8
        // DFS [root, node1, node3, node4, node7, node2, node5, node8, node6]
        // BFS

        SimpleNode node6 = new SimpleNode("node6", null);
        SimpleNode node5 = new SimpleNode("node5", node6);
        SimpleNode node4 = new SimpleNode("node4", node5);
        SimpleNode node3 = new SimpleNode("node3", node4);
        SimpleNode node2 = new SimpleNode("node2", node3);
        SimpleNode node1 = new SimpleNode("node1", node2);
        SimpleNode root = new SimpleNode("root", node1);
        node6.setNext(root);
//        System.out.println(solution1(root, node2, node5));


        // r > n1 > n2
        // n2 > n3||n4 > n10
        // n3 > n5 > n6 > n3
        // n4 > n7 > n8 > n9 > n4
        // n10 > r

        Node n10 = new Node("n10", new Node[]{null});

        Node n9 = new Node("n9", new Node[]{null});
        Node n8 = new Node("n8", new Node[]{n9});
        Node n7 = new Node("n7", new Node[]{n8});

        Node n6 = new Node("n6", new Node[]{null});
        Node n5 = new Node("n5", new Node[]{n6});

        Node n4 = new Node("n4", new Node[]{n7, n10});
        n9.getNext()[0] = n4;
        Node n3 = new Node("n3", new Node[]{n5, n10});
        n6.getNext()[0] = n3;

        Node n2 = new Node("n2",  new Node[]{n3, n4});
        Node n1 = new Node("n1", new Node[]{n2});
        Node r = new Node("r", new Node[]{n1, n2});
        n10.getNext()[0] = r;

        solution2(r, n1, n5);
    }

    private static boolean solution2(Node root, Node start, Node end) {
        if (start == end) return true;
        LinkedList<Node> unvisited = collectNodes(root);
        System.out.println(unvisited);

        while (!unvisited.isEmpty()) {
            Node n = unvisited.removeFirst();

        }

        return false;
    }

    public static boolean solution1(SimpleNode root, SimpleNode start, SimpleNode end) {
        if (start == end) return true;
        LinkedList<SimpleNode> unvisited = new LinkedList<>();

        while (!unvisited.contains(root)) {
            unvisited.add(root);
            root = root.getNext();
        }

        while (!unvisited.isEmpty()) {
            SimpleNode n = unvisited.removeFirst();
            SimpleNode v = n.getNext();
            while (v != root) {
                System.out.println("n:" + n + " start:" + start + "  &  v:" + v + " end:" + end);
                if (n == start && v == end) {
                    return true;
                }
                v = v.getNext();
            }
        }
        return false;
    }

    public static LinkedList<Node> collectNodes(Node root) {
        LinkedList<Node> collector = new LinkedList<>();
        collector.add(root);
        return collectNodes(root, collector);
    }

    public static LinkedList<Node> collectNodes(Node root, LinkedList<Node> collector) {
        for (Node n : root.getNext()) {
            if (!collector.contains(n)) {
                if (n.getName().equals("n2")) {
                    System.out.println();
                }
                collector.add(n);
                collectNodes(n, collector);
            } else {
                break;
            }
        }

        return collector;
    }
}

class SimpleNode {
    private SimpleNode next;
    private String name;

    public SimpleNode(String name, SimpleNode next) {
        this.next = next;
        this.name = name;
    }

    public SimpleNode getNext() {
        return next;
    }

    public void setNext(SimpleNode next) {
        this.next = next;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return name;
    }
}

class Node {
    private Node next[];
    private String name;

    public Node(String name, Node[] next) {
        this.next = next;
        this.name = name;
    }

    public Node[] getNext() {
        return next;
    }

    public void setNext(Node[] next) {
        this.next = next;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return name;
    }
}