Class: Router

Inherits:
Object
  • Object
show all
Defined in:
lib/simple_gate/router.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(paths = {}) ⇒ Router

Create a new Router for a network of interconnected servers. An example connections graph with three servers ‘foo’, ‘bar’ and ‘baz’:

router = Router.new
# Define a graph: foo -> bar -> baz
router.paths = {
  'foo' => %w[bar],
  'bar' => %w[baz]
}
router.find('foo', 'baz') #=> ['foo', 'bar', 'baz']

Parameters:

  • paths (Hash) (defaults to: {}) —

    Graph of server connections. It’s a Hash of Arrays, which contains strings. Keys are server names with a connection to other servers. Each of these servers is a string in the associated Array.



19
20
21
 
# File 'lib/simple_gate/router.rb', line 19

def initialize(paths={})
  @paths = paths
end

Instance Attribute Details

#paths ⇒ Object

Graph of server connections.



3
4
5
 
# File 'lib/simple_gate/router.rb', line 3

def paths
  @paths
end

Instance Method Details

#find(start, target, current_route = []) ⇒ Array?

A simple recursive pathfinder. Uses a very naieve depth-first recursive full-graph search to find the shortest route.

Parameters:

  • start (String) —

    The node to start searching from for target.

  • target (String) —

    The node to look for. Once it is found, return the shortest route to it.

  • current_route (Array) (defaults to: []) —

    Internal variable that holds the route so far. Helps in preventing cyclic routes from being checked an infinite amount of times.

Returns:

  • (Array) —

    The sequence of nodes that connect start to target.

  • (nil) —

    When no route was found.



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/simple_gate/router.rb', line 31

def find(start, target, current_route = [])
  return [target] if start == target
  return nil unless paths.has_key?(start)

  # Map all possible paths to the target.
  # Skip nodes we have already visited
  next_nodes = paths[start] - current_route
  routes = next_nodes.map do |next_node|
    find(next_node, target, current_route + [start])
  end

  # Reduce the collection to the shortest path
  shortest_route = routes.compact.inject(nil) {|shortest,possibility|
    next possibility if shortest.nil?
    possibility.size < shortest.size ? possibility : shortest
  }
  return [start] + shortest_route if shortest_route
  nil
end