Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite

I'd extremely grateful if someone could explain me what is made wrong. The output is not the one that should be. 

def bfs(g, s)
  color, d, p, q, res = [], [], [], [], []
  (0..g[0]).each do |el|
    color[el], d[el], p[el] = "white", "inf", nil if el != s
  end
  color[s], d[s], p[s] = "gray", 0, nil
  q << s
  until q.empty?
    u = q.shift
    adj = Array.new
    g[1].each do |x|
      adj << x[1] if x[0] == u
    end
    adj.each do |v|
      if color[v] == "white"
        color[v] = "gray"
        d[v] = d[u]+1
        p[v] = u
        q << v
      end
    end    
    color[u] = "black"
  end
  res = [p, d]
  return res
end

The input variables are the following:

e = [ [1,2], [2,1], [2,3], [3,2], [3,4], [4,3], [4,5], [4,6], [5,4], [5,6], [5,7], [6,4], [6,5], [6,7], [6,8], [7,5], [7,6], [7,8], [8,6], [8,7] ]
g = [n, e]
n, s = 3, 8
share|improve this question
1  
This question belong in stackoverflow, not here. It is off-topic because it about Trouble-shooting, debugging, or understanding code snippets. – ANeves Mar 23 '12 at 13:19

closed as off topic by Bobby, ANeves, sepp2k♦ Mar 24 '12 at 20:42

Questions on Code Review Stack Exchange are expected to relate to code review request within the scope defined in the FAQ. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about closed questions here.

1 Answer

up vote 1 down vote accepted

First, I looked at your code input.

e = [ [1,2], [2,1], [2,3], [3,2], [3,4], [4,3], [4,5], 
      [4,6], [5,4], [5,6], [5,7], [6,4], [6,5], [6,7], 
      [6,8], [7,5], [7,6], [7,8], [8,6], [8,7] ]
g = [n, e]
n, s = 3, 8

Does n comes after g = [n, e]. It would be NameError in Ruby. But If you mean that the order of the input is n, s = 3, 8 first, then I could continue it.

Now, why does n equals to 3. If it's the number of nodes in graph g. Then it should equal to 8 since e.flatten.max #=> 8. Maybe you want to write n, s = 8, 3.

Now, lets rewrite your code a bit.

def bfs(graph, searched_node)
  color, distance, parent, queue = [], [], [], []

  (0..graph[0]).each do |node|
    unless node == searched_node
      color[node]    = "white"
      distance[node] = "inf"
      parent[node]   = nil
    end
  end

  color[searched_node]    = "gray"
  distance[searched_node] = 0
  parent[searched_node]     = nil

  queue << searched_node
  until queue.empty?
    processed_node = queue.shift
    adj = []

    graph[1].each do |edge|
      adj << edge[1] if edge[0] == processed_node
    end

    adj.each do |v|
      if color[v] == "white"
        color[v]    = "gray"
        distance[v] = distance[processed_node] + 1
        parent[v]   = processed_node
        queue << v
      end
    end
    color[processed_node] = "black"
  end

  return [parent, distance]
end


e = [ [1,2], [2,1], [2,3], [3,2], [3,4], [4,3], [4,5], 
      [4,6], [5,4], [5,6], [5,7], [6,4], [6,5], [6,7],
      [6,8], [7,5], [7,6], [7,8], [8,6], [8,7] ]
n, s = 8, 3
g = [n, e]

p bfs(g, s)

And viola. The result is right--as I though. Here the result:

[[nil, 2, 3, nil, 3, 4, 4, 5, 6], ["inf", 2, 1, 0, 1, 2, 2, 3, 3]]

You can see it in action at ideone

share|improve this answer
Sorry for my mistype at the beginning. The result is what the question was about. It shouldn't be like that. There is "inf" element. There is "nil" on the left. If you imagine this graph you'll see that an output is wrong. Am I wright? – mac-r Mar 23 '12 at 14:47
No, the result is right. Since your nodes/vertices have 0 in it and there aren't any edges that incident with zero. So, 0 doesn't connected with any other node, have distance "inf" to the searched_node, and doesn't have parent (nil). – Mas Adit Mar 23 '12 at 16:42
Made a couple of changes at inputs: n, s = [1,2,3,4,5,6,7,8], 3 g = [n, e] and here: def bfs(graph, searched_node) color, distance, parent, queue = [], [], [], [] # array instead of a range graph[0].each do |node| unless node == searched_node color[node] = "white" Working version of this you can see here: [ideone.com/1ZW9C][1] There is no 0 in nodes, but the output is still strange: [[nil, 2, 3, nil, 3, 4, 4, 5, 6], [nil, 2, 1, 0, 1, 2, 2, 3, 3]] – mac-r Mar 23 '12 at 18:11
If you want exclude zero as node, you must exclude parent[0] and distance[0] too in return value. You could see that in your result: [[nil, 2, 3, nil, 3, 4, 4, 5, 6], [nil, 2, 1, 0, 1, 2, 2, 3, 3]], there are 9 elements in each array. My suggestion is using return [parent[1..-1], distance[1..-1]]. Here the link. And the result is: [[2, 3, nil, 3, 4, 4, 5, 6], [2, 1, 0, 1, 2, 2, 3, 3]] – Mas Adit Mar 24 '12 at 11:16

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