FindPath DFS BFS – Cyclic and Acyclic

public class MyGraph {
    //Adjacency List
    private final Map<String, LinkedHashSet<String>> graph
                                                 = new HashMap<>();

    public void addUniDirectionalEdge(String n1, String n2) {
        LinkedHashSet<String> adjNodes = graph.get(n1);

        if (adjNodes == null) {
            adjNodes = new LinkedHashSet();
            adjNodes.add(n2);
            graph.put(n1, adjNodes);
        } else {
            adjNodes.add(n2);
        }
    }

    public void addBiDirectionalEdge(String n1, String n2) {
        this.addUniDirectionalEdge(n1, n2);
        this.addUniDirectionalEdge(n2, n1);
    }

    public LinkedList<String> getAdjacentList(String node) {
        if (graph.get(node) == null) {
            return new LinkedList<String>();
        } else {
            return new LinkedList(graph.get(node));
        }
    }
}

public class FindPaths {

    private static final String START = "B";
    private static final String END = "E";
    private static final int MAX = 4;

    public static void main(String[] args) {
        MyGraph graph = new MyGraph();
        graph.addUniDirectionalEdge("A", "B");
        graph.addUniDirectionalEdge("A", "C");

        graph.addUniDirectionalEdge("B", "A");
        graph.addUniDirectionalEdge("B", "D");
        graph.addUniDirectionalEdge("B", "E");
        graph.addUniDirectionalEdge("B", "F");

        graph.addUniDirectionalEdge("C", "A");
        graph.addUniDirectionalEdge("C", "E");
        graph.addUniDirectionalEdge("C", "F");

        graph.addUniDirectionalEdge("D", "B");

        graph.addUniDirectionalEdge("E", "C");
        graph.addUniDirectionalEdge("E", "F");

        graph.addUniDirectionalEdge("F", "B");
        graph.addUniDirectionalEdge("F", "C");
        graph.addUniDirectionalEdge("F", "E");

        LinkedList<String> pathTracer = new LinkedList<>();
        pathTracer.add(START);
        findAcyclicPathsUsingDFS(graph, pathTracer);
        System.out.println(" ---- ");
        pathTracer = new LinkedList<>();
        pathTracer.add(START);
        findCyclicPathsUsingDFS(graph, pathTracer);

        System.out.println(" ---- ");
        findAcyclicPathsUsingBFS(graph);
        System.out.println(" ---- ");
        findCyclicPathsUsingBFS(graph);
    }

    private static void findAcyclicPathsUsingDFS(MyGraph graph,
                                    LinkedList<String> pathTracer) {
        String currentNode = pathTracer.getLast();
        LinkedList<String> adjacentList =
graph.getAdjacentList(currentNode);
        if (adjacentList == null) {
            return;
        }
        for (String adjacentNode : adjacentList) {
            if (pathTracer.contains(adjacentNode)) {
                continue;
            }
            pathTracer.add(adjacentNode);
            if (adjacentNode.equals(END)) {
                printPath(pathTracer);
            } else {
                findAcyclicPathsUsingDFS(graph, pathTracer);
            }
            pathTracer.removeLast();
        }
    }

    private static void findCyclicPathsUsingDFS(MyGraph graph,
                                   LinkedList<String> pathTracer) {
        String currentNode = pathTracer.getLast();
        LinkedList<String> adjacentList
                             = graph.getAdjacentList(currentNode);
        if (adjacentList == null) {
            return;
        }
        for (String adjacentNode : adjacentList) {
            if (pathTracer.size() < MAX) {
                pathTracer.add(adjacentNode);
                if (adjacentNode.equals(END)) {
                    printPath(pathTracer);
                }
                findCyclicPathsUsingDFS(graph, pathTracer);
                pathTracer.removeLast();
            }
        }
    }

    private static void printPath(LinkedList<String> pathTracer) {
        for (String string : pathTracer) {
            System.out.print(string + " ");
        }
        System.out.println("");
    }

    private static void findAcyclicPathsUsingBFS(MyGraph graph) {
        Queue<String> q = new LinkedList<String>();
        q.add(START);

        while(!q.isEmpty()){
            String currentPath = q.remove();
            String latestNode =
            currentPath.charAt(currentPath.length()-1)+"";
            LinkedList<String> adjacentList =
            graph.getAdjacentList(latestNode);
            if(adjacentList == null){
                continue;
            }
            for (String node : adjacentList) {
                if(node.equals(END)){
                    System.out.println(currentPath+node);
                    continue;
                }
                if(currentPath.contains(node)){
                    continue;
                }
                q.add(currentPath+node);
            }
        }
    }

    private static void findCyclicPathsUsingBFS(MyGraph graph) {
        Queue<String> q = new LinkedList<String>();
        q.add(START);
        while (!q.isEmpty()) {
            String currentPath = q.remove();
            if (currentPath.length() < MAX) {
                String latestNode =
                     currentPath.charAt(currentPath.length()-1) + "";
                LinkedList<String> adjacentList =
                                  graph.getAdjacentList(latestNode);
                if (adjacentList == null) { continue; }
                for (String node : adjacentList) {
                    if (node.equals(END)) {
                        System.out.println(currentPath + node);
                    }
                    q.add(currentPath + node);
                 }
            }
        }
    }
}

Advertisements