Use one logical traversal token carrying the discovered vertex set and the active LIFO stack of vertices. The current vertex either discovers its first still-unvisited outgoing graph neighbour, or returns to its preceding stack entry. The former records both the child's parent in a rooted tree and the parent's child. Unlike concurrent flooding discovery, this visits one entire branch before the next, giving an actual depth-first search.
The important directed-graph detail is that a child's parent need not be an outgoing graph neighbour. Return the token by routing it through the original directed graph; a routing hop does not count as a traversal visit. The following duplicate-suppressed flooding route requires no previously known topology and sends only to immediate outgoing graph neighbours.
final case class Token(visited: Set[NodeId], stack: List[NodeId], serial: Int)
sealed trait Msg
final case class Route(serial: Int, target: NodeId, token: Token) extends Msg
case object Finished extends MsgHere
stack.head is the current vertex. Use the same paired toNode and fromNode ports as in (i), now with the new Msg type. Set mailbox capacity to , normalize neighbours with distinct, and again leave the mailboxes open until all processes have joined. The following helpers are local functions inside each node's generated process.def span: PROC = proc {
val adj = neighbours.distinct
val routed = scala.collection.mutable.Set[Int]()
var entered = false
var done = false
def flood(message: Msg): Unit =
for (w <- adj) toNode(w) ! message
def move(target: NodeId, state: Token): Unit = {
val s = state.serial + 1
routed += s
flood(Route(s, target, state.copy(serial = s)))
}
def step(t: Token): Unit = {
assert(t.stack.head == me)
if (!entered) {
entered = true
parent = if (t.stack.tail.isEmpty) me else t.stack.tail.head
children = Nil
}
adj.find(w => !t.visited(w)) match {
case Some(w) =>
children = children :+ w
move(w, Token(t.visited + w, w :: t.stack, t.serial))
case None =>
t.stack.tail match {
case p :: rest => move(p, t.copy(stack = p :: rest))
case Nil => flood(Finished); done = true
}
}
}
if (me == 0) step(Token(Set(0), List(0), 0))
while (!done) {
fromNode(me) ? () match {
case r @ Route(s, target, t) =>
if (!routed(s)) {
routed += s
if (target == me) step(t) else flood(r)
}
case Finished => flood(Finished); done = true
}
}
}Every route number is globally unique: there is one logical token, and its serial increases at every move. The sender inserts that serial in its own
routed set before flooding; this stops a returning copy from circulating again. Intermediate vertices forward the first copy of an envelope and ignore later copies. Its target consumes exactly one copy without forwarding it. Because the directed graph is strongly connected, a simple directed path from sender to target exists; its intermediate vertices eventually relay the envelope. Thus each move eventually finishes.A routed return can pass through a vertex not yet discovered by the depth-first search. That vertex only forwards the envelope: it does not run
step, change entered, or assign a parent. This distinction is essential. For the directed cycle , returning from two to one uses , while the logical traversal stack changes from to .
A depth-first search return follows a routed directed path when the child has no reverse directed edge
. Details. 
The discovered vertex set only grows. Each newly discovered vertex is pushed once and later popped once; an exhausted vertex can never acquire a new unvisited neighbour as this set grows. Consequently there are exactly downward moves and return moves. When the root exhausts its outgoing graph neighbours, every vertex has been visited, by the standard reachability argument for depth-first search. Each nonroot parent was recorded along the actual downward directed edge, and
children records exactly those assignments in discovery order.There are route envelopes, each forwarded at most once per outgoing directed edge, and one final
Finished flood. Each node forwards Finished before exiting; strong connectivity therefore delivers it everywhere. There are at most total messages into any mailbox, below the proposed capacity. Even a mailbox whose process has already exited cannot block later sends. All processes terminate withThis deliberately trades communication efficiency for a simple valid solution on a genuinely directed graph. A direct parent acknowledgement would instead require an additional bidirectional-edge assumption, which the question does not supply. Articles by others on the same topic
There are currently no matching articles.