Re: [Boost-users] the stability of breadth_first_visit in BGL

Subject: Re: [Boost-users] the stability of breadth_first_visit in BGL
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2015-04-28 22:31:49

>________________________________
> From: breadbread1984 <breadbread1984_at_[hidden]>
>To: boost-users_at_[hidden] 
>Sent: Tuesday, April 28, 2015 7:36 AM
>Subject: [Boost-users] the stability of breadth_first_visit in BGL
> 
>
>I am wondering if breadth_first_visit can always get the same sequence of 
>vertex no matter whether the graph is serialized and deserialized again. Thx

It depends on your graph type -- a faithful serialization algorithm will preserve the order of elements in vectors (but perhaps not hash tables), and the breadth-first search algorithm is deterministic if given the same inputs.  The algorithm iterates through the out edges of various vertices, and the order used for that is the order that the edges are stored in the graph.  I believe that breadth_first_visit will give the same results given a serialized and then deserialized graph as long as the graph type does not use a hash table for edge storage (e.g., hash_setS).

-- Jeremiah Willcock