2
$\begingroup$

The following Code highlights the breadth-first scan tree

g = GridGraph[{3, 5}, VertexSize -> {5 -> Medium}]
Reap[BreadthFirstScan[g, 5, {"FrontierEdge" -> Sow}]]

This produces the output (where <-> represents undirected edge).

{{2, 5, 2, 5, 5, 5, 4, 5, 6, 7, 8, 9, 10, 11, 12}, {{5 <-> 2, 5 <-> 4, 5 <-> 6, 5 <-> 8, 2 <-> 1, 2 <-> 3, 4 <-> 7, 6 <-> 9, 8 <-> 11, 7 <-> 10, 9 <-> 12, 11 <-> 14, 10 <-> 13, 12 <-> 15}}}

I have read up on reap and sow and understand the second list. The first list which is supposed to capture the final outcome of the compound expression however is not clear.

What do the vertices in this first list represent (in the context of reap and sow for this particular application)?

{2, 5, 2, 5, 5, 5, 4, 5, 6, 7, 8, 9, 10, 11, 12}

In a breadth first scan I would have expected the final outcomes to be more closely related to the order of visiting nodes in the scan.

Is this output consistent with what ought to be produced in a reap and sow context for this particular application? And if so, can you clarify how this is the case (in terms of reap and sow functioning)?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

This list is just the return value of BreadthFirstScan. It has absolutely nothing to do with Sow and Reap.

According to the documentation, it is the list of the predecessors of the BFS tree.

The first element of the list is 2. This means that 2 -> 1 belongs to the tree, where 1 is the first vertex. The second is 5, so 5 -> 2 also belong to the tree (where 2 is the second vertex). And so on.

The one tricky thing about this representation is that for those vertices that do not have a predecessor, the "predecessor" is given as the same vertex. This is always the case for the root vertex (the vertex where the search starts), and can happen for vertices that are not scanned at all (in non-connected graphs). The predecessor lists produced from a connected graph is compatible with TreeGraph (see below).

You can reconstruct the tree using TreeGraph:

g = GridGraph[{3, 5}, VertexSize -> {5 -> Medium}]

ps = BreadthFirstScan[g, 5]
(* {2, 5, 2, 5, 5, 5, 4, 5, 6, 7, 8, 9, 10, 11, 12} *)

HighlightGraph[g, TreeGraph[VertexList[g], ps], 
 GraphHighlightStyle -> "Thick"]

enter image description here

Improve this answer
$\endgroup$
7
  • $\begingroup$ Ok, I know it is the return value produced by reap as first argument for this application. It is nearly consistent with the list of predecessors in the bfs tree, however there are five occurrences of 5 in the first list, while there are only four edges that have 5 as first vertex in the second list. {{2, 5, 2, 5, 5, 5, 4, 5, 6, 7, 8, 9, 10, 11, 12}, {{5 <-> 2, 5 <-> 4, 5 <-> 6, 5 <-> 8, 2 <-> 1, 2 <-> 3, 4 <-> 7, 6 <-> 9, 8 <-> 11, 7 <-> 10, 9 <-> 12, 11 <-> 14, 10 <-> 13, 12 <-> 15}}} $\endgroup$
    – ExpressionCoder
    Commented Feb 21, 2019 at 6:27
  • 1
    $\begingroup$ @Mike That's because the "predecessor" of the root vertex (5) is given as the root itself. This is also how TreeGraph works. $\endgroup$
    – Szabolcs
    Commented Feb 21, 2019 at 9:35
  • $\begingroup$ Thanks. I used reference.wolfram.com/language/ref/BreadthFirstScan.html and checked out your treegraph link. Where would I find information such as your comment that the "predecessor" of the root vertex is given as the root vertex itself? $\endgroup$
    – ExpressionCoder
    Commented Feb 23, 2019 at 5:55
  • $\begingroup$ @Mike I don't remember where I learned about this. $\endgroup$
    – Szabolcs
    Commented Feb 23, 2019 at 10:42
  • 2
    $\begingroup$ @Mike You could suggest improvements to Wolfram. The online version of each documentation page has a Feedback link at the bottom. I regularly submit suggestions like this. $\endgroup$
    – Szabolcs
    Commented Feb 23, 2019 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.