Created
September 4, 2015 09:28
-
-
Save nazargulov/59ed8a8074f2c74299c8 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # Put unvisited nodes on a queue | |
| # Solves the shortest path problem: Find path from "source" to "target" | |
| # that uses the fewest number of edges | |
| # It's not recursive (like depth first search) | |
| # | |
| # The steps are quite simple: | |
| # * Put s into a FIFO queue and mark it as visited | |
| # * Repeat until the queue is empty: | |
| # - Remove the least recently added node n | |
| # - add each of n's unvisited adjacents to the queue and | |
| # mark them as visited | |
| class BreathFirstSearch | |
| def initialize(graph, source_node, end_node, max = 1) | |
| @graph = graph | |
| @node = source_node | |
| @end_node = end_node | |
| @visited = [] | |
| @edge_to = {} | |
| @edge1_to = {} | |
| @max_path = max | |
| if max > 1 | |
| bfs1(source_node) | |
| else | |
| bfs(source_node) | |
| end | |
| end | |
| def shortest_path_to(node) | |
| return unless has_path_to?(node) | |
| path = [] | |
| while(node != @node) do | |
| path.unshift(node) # unshift adds the node to the beginning of the array | |
| node = @edge_to[node] | |
| end | |
| path.unshift(@node) | |
| end | |
| def path_to | |
| @paths = {} | |
| @i = 1 | |
| @paths[@i] = [] | |
| paths(@end_node) | |
| @paths | |
| end | |
| def paths(node) | |
| @paths[@i].unshift(node) | |
| if @edge1_to[node] && node != @node | |
| @edge1_to[node].each do |edge| | |
| paths(edge) if @i <= @max_path | |
| end | |
| else | |
| @i += 1 | |
| @paths[@i] = [@end_node] | |
| end | |
| end | |
| private | |
| def bfs(node) | |
| # Remember, in the breath first search we always | |
| # use a queue. In ruby we can represent both | |
| # queues and stacks as an Array, just by using | |
| # the correct methods to deal with it. In this case, | |
| # we use the "shift" method to remove an element | |
| # from the beginning of the Array. | |
| # First step: Put the source node into a queue and mark it as visited | |
| queue = [] | |
| queue << node | |
| @visited << node | |
| # Second step: Repeat until the queue is empty: | |
| # - Remove the least recently added node n | |
| # - add each of n's unvisited adjacents to the queue and mark them as visited | |
| while queue.any? | |
| current_node = queue.shift # remove first element | |
| current_node.adjacents.each do |adjacent_node| | |
| next if @visited.include?(adjacent_node) | |
| queue << adjacent_node | |
| @visited << adjacent_node | |
| @edge_to[adjacent_node] = current_node | |
| end | |
| end | |
| end | |
| def bfs1(node) | |
| # Remember, in the breath first search we always | |
| # use a queue. In ruby we can represent both | |
| # queues and stacks as an Array, just by using | |
| # the correct methods to deal with it. In this case, | |
| # we use the "shift" method to remove an element | |
| # from the beginning of the Array. | |
| # First step: Put the source node into a queue and mark it as visited | |
| queue = [] | |
| queue << node | |
| @visited << node | |
| # Second step: Repeat until the queue is empty: | |
| # - Remove the least recently added node n | |
| # - add each of n's unvisited adjacents to the queue and mark them as visited | |
| while queue.any? | |
| current_node = queue.shift # remove first element | |
| current_node.adjacents.each do |adjacent_node| | |
| next if @visited.include?(adjacent_node) && adjacent_node != @end_node | |
| queue << adjacent_node | |
| @visited << adjacent_node | |
| push_edge(adjacent_node, current_node) | |
| end | |
| end | |
| end | |
| def push_edge(adjacent_node, current_node) | |
| @edge1_to[adjacent_node] = [] unless @edge1_to[adjacent_node] | |
| @edge1_to[adjacent_node].unshift(current_node) | |
| end | |
| # If we visited the node, so there is a path | |
| # from our source node to it. | |
| def has_path_to?(node) | |
| @visited.include?(node) | |
| end | |
| end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment