1
\$\begingroup\$

I am currently working on optimizing my code. In order to do that, I have to make sure that my sequential BFS works perfectly. Then, I should I apply threads or executor service to run it in parallel. Will my BFS break if the graph is too big?

public void bfs(int rootNode, isvisited visitor)
{
// BFS uses Queue data structure
Queue<Integer> q = new LinkedList<Integer>();
int currentLevel = 0;

q.add(rootNode);
visitor.visit(rootNode, currentLevel);

while (!q.isEmpty())
{
    currentLevel++;
    Set<Integer> nextNodes = new LinkedHashSet<Integer>();
    q.forEach(currNode ->nextNodes.addAll(outgoingNeighbors(currNode)));
    q.clear();

    for (int child : nextNodes) 
    {
        visitor.visit(child, currentLevel);
        q.add(child);
    }
} }
\$\endgroup\$
2
\$\begingroup\$

... In order to do that, I have to make sure that my sequential BFS works perfectly. ...

Have you tried writing some unit-tests to prove or disprove that the function? On the whole it looks alright to me though it really depends on what the visitor.visit(...) does. Also, not clear what outgoingNeighbors does.

Minor comments :

  • q.forEach(currNode ->nextNodes.addAll(outgoingNeighbors(currNode))); is missing a space
  • for (int child : nextNodes)... can use a forEach as well.
  • If you dequeue instead of doing the forEach, you should not need to do the clear at the end.

... I should I apply threads or executor service to run it in parallel.

When using multi-threading, my advice is always to break things into non-dependent tasks. Currently the "visitor" object seems a bit suspect and possible cause of future troubles.

Do you have any code that does the multi-threading?

Will my BFS break if the graph is too big?

Sure. If you just mean can you call something with a 1000 nodes, should be fine. If you plan on creating a million threads on a chromebook, you may have some issues. It really depends on your definition of big and the limits you're working with.

Note that often issues of scale are solved by optimizing the code/solution or by solving problems in a distributed fashion. If you start hitting such problems, I'd recommend start with a debugger, figure out what's wrong and maybe then start working out a good solution for whatever issue you discover.

\$\endgroup\$
  • \$\begingroup\$ is there anyway to make it more simple (ie, not use 2 queues ) \$\endgroup\$ – questioner Mar 3 '17 at 10:52
  • \$\begingroup\$ public interface OnVisitedVertex { default void visit(int node, int currentLevel) { System.out.println("Node ->" + node + " level: " + currentLevel); }; } \$\endgroup\$ – questioner Mar 3 '17 at 10:54
0
\$\begingroup\$

Since Rishi already adressed your concerns, let me talk about the code you have there:

  1. A majority of java coding conventions has the opening brace on the same line as the block introducer:

    public void bfs(int rootNode, isvisited visitor) {
    
  2. Types are supposed to start with a majuscle letter. It's IsVisited accordingly. That said, this whole thing is pretty suspicious to me. The typename is very strange. Usually the is-prefix is reserved for booleans. As such the type would probably be better named BFSVisitor or something along these lines.

  3. There's no necessity whatsoever to shorten variable names to single letters: q should be queue

  4. You're completely ignoring the possibility of cycles in the graph traversed. The queue doesn't know about already visited nodes and accordingly can visit them multiple times, which results in an infinite loop.
    You can somewhat remedy this by keeping track of how many nodes you visited and break the loop when you visited all nodes in the graph (or entered a cycle)

  5. The traversal you do here seems really extremely strange.. a standard BFS traversal can be done with a single queue. You use two, one of them being used as intermediate storage for the "next level" in your traversal which just adds nodes back into the original queue.
    This seems to be because of the restriction to keep track of the current traversal level. If you can do away with that restriction, the code will automatically become significantly faster.

  6. "Incorrect" use of lambdas. For the preparation of the next level, consider something like the following:

    queue.stream().flatMap(this::outgoingNeighbors)
        .forEach(nextNodes::add);
    

    With a little squinting we can spot the following simplification:

    Set<Integer> nextNodes = queue.stream()
        .flatMap(this::outgoingNeighbors)
        .collect(Collectors.toSet());
    

    Note that this should already consume the elements from the queue. clear() should be unnecessary.

  7. Since you obviously are allowed to use streams, what about the following additional simplification:

    nextNodes.forEach(child -> {
        visitor.visit(child, currentLevel);
        queue.add(child);
    });
    
\$\endgroup\$
  • \$\begingroup\$ thank you in advance for you time , at the end should my code look something like this ? public void bfs(int rootNode, OnVisitedVertex visitor ) { // BFS uses Queue data structure Queue<Integer> queue = new LinkedList<Integer>(); int currentLevel = 0; queue.add(rootNode); visitor.visit(rootNode, currentLevel); Set<Integer> nextNodes = queue.stream().flatMap(this::outgoingNeighbors) .collect(Collectors.toSet()); nextNodes.forEach(child -> { visitor.visit(child, currentLevel); queue.add(child); }); } \$\endgroup\$ – questioner Mar 3 '17 at 16:57
  • \$\begingroup\$ i'm a getting some errors The type of outgoingNeighbors(int) from the type Graph<T> is List<Integer>, this is incompatible with the descriptor's return type: Stream<? extends R> - The method flatMap(Function<? super Integer,? extends Stream<? extends R>>) in the type Stream<Integer> is not applicable for the arguments (this::outgoingNeighbors) - The method visit(int, int) in the type OnVisitedVertex is not applicable for the arguments (int) \$\endgroup\$ – questioner Mar 3 '17 at 16:57

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.