reset password
Author Message
vsluong4
Posts: 87
Posted 01:04 Nov 11, 2014 |

 

Deadline has passed.  Below is one possible implementation of Kosaraju's algorithm using BFS on the 2nd pass.

import java.util.*;

......

public class Graph {

MAIN METHOD

    public static enum DirectedOrNot {
        DIRECTED, UNDIRECTED
    }

    public static void main(String[] args) {

        // Build a DIRECTED graph.
        Graph gr = new Graph();
        gr.addEdge("a", "b");
        gr.addEdge("b", "c");        
        gr.addEdge("c", "a");        
        gr.addEdge("b", "d");        
        gr.addEdge("d", "e");        
        gr.addEdge("e", "g");        
        gr.addEdge("g", "f");        
        gr.addEdge("f", "e");        
        gr.addEdge("d", "f");        
        gr.addEdge("c", "i");
        gr.addEdge("c", "h");        
        gr.addEdge("i", "j");        
        gr.addEdge("j", "k");        
        gr.addEdge("i", "k");        
        gr.addEdge("k", "h");
        gr.addEdge("h", "i");
        gr.addEdge("j", "g");        
        gr.addEdge("i", "f");

        System.out.println("Graph:\n" + gr);

        for(Graph g : gr.SCCs())
            System.out.println("An SCC:" + g);

    }

END MAIN METHOD

   ......................................

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("\t[");
        for (Node n : nodes.values())
            sb.append("\n\t " + n);
        return sb.toString() + "\n\t]";
    }

KOSARAJU'S IMPLEMENTATION
    //Preconditions: The caller object will have its SCCs returned
    //Postconditions: This method does not modify any data members
    //Returns the SCCs as Graphs
    //e.g. List<Graph> components = gr.SCCs();
    //components.get(0) will be an SCC, components.get(1) will be an SCC .......
    public List<Graph> SCCs()
    {
        //return this at the end
        LinkedList<Graph> theSCCs = new LinkedList<Graph>();
        
        //first pass with DFS to get the order to perform second pass
        FIRST PASS WITH DFS
        Stack<Node> theOrder = firstPass();
        
        SECOND PASS WITH BFS
        //a queue so it's a BFS instead of DFS

        //no c++ style queues in java ;(

        LinkedTransferQueue<Node> toVisit = new LinkedTransferQueue<Node>();
        //too many sets, these things don't work well with the native debugger
        Set<Node> explored = new HashSet<Node>();
        //outer loop of BFS-loop to check everything
        while(!theOrder.isEmpty())
        {
            //if the next element on stack has already been explored
            //remove it and do nothing else
            if(explored.contains(theOrder.peek()))
            {
                theOrder.poll();
                continue;
            }
            
            //add a new graph to populate unexplored SCCs
            theSCCs.add(new Graph());
            toVisit.add(theOrder.pop());
            
            // These are the nodes that we have looked at.
            // They have been added to the toVisit list.
            explored.add(toVisit.peek());
    
            //the below is the familiar BFS
            while (!toVisit.isEmpty()) {
                Node v = toVisit.poll();
                theSCCs.getLast().nodes.put(v.id, v);
                for (Node w : v.sinkNodes) {
                    if (!explored.contains(w)) {
                        explored.add(w);
                        toVisit.offer(w);
                    }
                }
            }
        }

         END 2ND PASS BFS
        
        return theSCCs;
    }

END KOSARAJU'S IMPLEMENTATION

   FIRST PASS W/ DFS CODE
    //perform the first pass DFS on the graph to return the order to BFS
    private Stack<Node> firstPass()
    {
        Stack<Node> theStack = new Stack<Node>();
        List<Node> explored = new LinkedList<Node>();
        
        for(Node n : nodes.values())
            DFS(n, theStack, explored);
        
        return theStack;
    }

    //helper function to the above
    private void DFS(Node theNode, Stack<Node> theStack, List<Node> exploredNodes)
    {
        if(!exploredNodes.contains(theNode))
        {
            exploredNodes.add(theNode);
            for(Node srcNode : theNode.sourceNodes)
                DFS(srcNode, theStack, exploredNodes);
            theStack.push(theNode);
        }
    }

    END 1ST PASS DFS

ANSWER TO THE QUESTION

Included in the EC assignment was to either provide a counter-example or explain why DFS and BFS produce same/different results.  We begin our answer with a quick review:
How are DFS and BFS different?

Well, BFS uses a Queue and explores the nodes in 'layers' that allow you to find the shortest distance between two nodes blazingly fast.  DFS uses a Stack and is the more aggressive of the algorithms and it can be easily rewritten using recursion.  DFS searches new nodes as quickly as it can and only back tracks.........

Essentially, DFS and BFS differ in the order that they explore the nodes.
How are DFS and BFS the same?

Put succinctly, they both explore everything explorable and nothing else.

Why does DFS work?

DFS does not automatically work.  See 7:00 of https://class.coursera.org/algo-006/lecture/53.  The question should be "why does DFS work on the second pass?"  All we need DFS to do is to start at the 'head node' of an SCC and explore every node in that SCC and nothing else.  But wait!   A BFS can accomplish just that.

Why Depth-First Search?

Compared to BFS, DFS usually uses less storage than an equivalent BFS.  BFS has the advantage of having the more useful (in some circumstances) search order.

Can we get BFS's search order with DFS-esque space complexity?
Yes!  With iterative deepening depth-first search.

Attachments:
Last edited by vsluong4 at 20:35 Nov 13, 2014.
vsluong4
Posts: 87
Posted 15:11 Nov 13, 2014 |

Used a custom C++-style queue in the code before.  It should probably work now.

Added the next part of the EC assignment.