shortestpath.rb Finds the shortest path given tuples to represent the graph. For directed and directed.

shortestpath2.rb

=begin 
:mat utter, 10/19/2014
=end
class Graph
	def initialize()
		@graph = Array.new

	end
	def add(key,val)
		@graph.push( [key,val] )
	end

	def to_s
		return "#{@graph}\n#{@visit}"
	end

	def G
		@graph
	end

	def find( a, b )
		#there has to be a valid path
		if _check( a )
			vec = Array.new
			vec = _find( a, b, vec )

			shortest = @graph.size + 1
			for x in 0..vec.size-1 do
				shortest = x if vec[x][0] == b && vec[x][-1] == a && shortest > vec[x].size
			end
			return vec[shortest].reverse if shortest <= @graph.size
		end
		return false
	end

private

	def _check( x )
		@graph.each do | y |
			if y[0] == x
				return y[1]
			end
		end
	end

	def _find( a, b, vec )
=begin
		vec: 	is being used to represent the search tree
		queue: 	is being used to hold the nodes that have been discovered, not explored yet
				I shift off jobs from the queue resembles a BFS because I
				follow neighboring nodes, and not the graph as connected by
				its edges.
				It's good, in that partials left over inside of vec, can be quickly assessed for
				consecutive calls to Graph.find()
=end
		source = 1
		dest = 0
		queue = Array.new
		
		vec.push( Array.new )
		vec[0][0] = b
		queue.push( b )
		
		while queue.size > 0 do
			size, set = _branch(source, dest, queue[0])
			
			
			return vec if !set
			vec = _dup(vec) if vec.size < size
			vec = _expand( set, vec, queue[0] )
			return vec if set.include?(a)
			
			queue.shift
			queue.concat(set) 
		end
		vec
	end

	def _dup( ary )
		copy = _dup2( ary )
		ary.concat(copy)
	end

	def _dup2( ary )
		Marshal.load( Marshal.dump( ary ) )
	end

	def _expand( source, dest, criteria )
		# each part of the reverse traversal is perpended to
		# a set in the dest that satisfies the criteria
		#print "##{source}  to #{dest}  for #{criteria} \n \n "
		copy = _dup2( source )
		dest.each do | x |
			if x[-1] == criteria
				x.push( copy[0] )
				copy.shift
			end
		end
		#print "#{dest} \n"
	end


	def _branch( source, dest, criteria )
		# source should be 1 for us because we're
		# working in reverse, and that is how the graph
		# data is represented
		set = Array.new
		@graph.each do | x |
			if x[source] == criteria
				set.push( x[dest] )
			end
		end
		return set.size, set
	end


private
	def validates( path, a, b )
		path.each do | p |
			return p if p[0] == a && p[-1] == b
		end
		false
	end

	
end

g = Graph.new

g.add(:A,:B)
g.add(:A,:E)
g.add(:B,:C)
g.add(:C,:F)
g.add(:C,:D)
g.add(:E,:D)
g.add(:D,:B)
g.add(:D,:E)
g.add(:F,false)

#algorithm start

source = :F
dest = :E
g.G.each do | s |
	source = s[0]
	next if source == dest
	print "Shortest path for #{source} to #{dest} is "
	print g.find( source, dest ), "\n"
end