2 lin time alg_somenode.sd

UML text editor & user manual Dec2007

#!>>
#!A simple linear-time algorithm for exploring a graph, starting at "someNode". 
#!
#!Let u, v be two nodes of the graph. If the distance between "someNode" and u
#!is less than the distance between "someNode" and v, then u will be encountered
#!before v.
#!
#!When a node is encountered for the first time, its level attribute (denoting the
#!distance between "someNode" and the node) is set.
#!<<

#![SD breadth-first-search]
bfs:BFS[a]
/queue:FIFO
someNode:Node
node:Node
adjList:List
adj:Node


bfs:queue.new
bfs:someNode.setLevel(0)
bfs:queue.insert(someNode)
[c:loop while queue != ()]
  bfs:node=queue.remove()
  bfs:level=node.getLevel()
  bfs:adjList=node.getAdjacentNodes()
  [c:loop 0<=i<#adjList]
    bfs:adj=adjList.get(i)
    bfs:nodeLevel=adj.getLevel()
    [c:alt nodeLevel IS NOT defined]
      bfs:adj.setLevel(level+1)
      bfs:queue.insert(adj)
      --[else]
      bfs:nothing to do
    [/c]
  [/c]
[/c]
bfs:queue.destroy()