Skip to content

Instantly share code, notes, and snippets.

@Sharparam
Created December 9, 2015 19:21
Show Gist options
  • Save Sharparam/9da64bac6fbec5083c85 to your computer and use it in GitHub Desktop.
Save Sharparam/9da64bac6fbec5083c85 to your computer and use it in GitHub Desktop.
nodes = {}
add_node = (name) ->
return if nodes[name]
nodes[name] = {}
add_edge = (first, second, cost) ->
error 'One of the nodes do not exist' unless nodes[first] and nodes[second]
return if nodes[first][second]
nodes[first][second] = cost
get_all_except = (except) ->
if type(except) != 'table'
except = [except]: true
result = {}
for node, _ in pairs nodes
result[node] = true unless except[node]
result
is_empty = (tbl) ->
for node, _ in pairs nodes
return false if tbl[node]
true
min = (a, b) ->
return a < b and a or b
copy = (tbl) ->
if type(tbl) != 'table'
return tbl
result = {}
for k, v in pairs tbl
result[k] = copy v
result
count = (tbl) ->
total = 0
for k, _ in pairs nodes
total += 1 if tbl[k]
total
shortest_path = (start, visited = {}, cost = 0) ->
if not start
costs = [shortest_path name for name, _ in pairs nodes]
table.sort costs
return costs[1]
visited = [start]: true if is_empty visited
unvisited = get_all_except visited
if is_empty unvisited
return cost
costs = {}
for node, _ in pairs unvisited
v = copy visited
v[node] = true
costs[#costs + 1] = shortest_path(node, v, cost + nodes[start][node])
min = costs[1]
for i = 2, #costs
min = costs[i] if costs[i] < min
min
{
:add_node
:add_edge
:shortest_path
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment