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
I think it should be stable. Do you see any results to the contrary? On Tue, Apr 28, 2015 at 9:40 AM breadbread1984 <breadbread1984@163.com> wrote:
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
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
The answer here depends on what you mean by serialized and deserialized. The Graphviz reader/writer for example doesn't preserve vertex indices so you may get different iteration orders if you run BFS on a graph, write it to Graphviz, read it back in, and run BFS again. At least I remember being bitten by this and writing special handling to use stable node ids rather than vertex indices at some point, YMMV depending on version and use case. If you want stable iteration orders across (de)serialization events, make sure that whatever serialization you're using ensures that the graph constructed has consistent vertex indices. On Tue, Apr 28, 2015 at 1:50 PM, Marcin Zalewski <marcin.zalewski@gmail.com> wrote:
I think it should be stable. Do you see any results to the contrary?
On Tue, Apr 28, 2015 at 9:40 AM breadbread1984 <breadbread1984@163.com> wrote:
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
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
________________________________ From: breadbread1984 <breadbread1984@163.com> To: boost-users@lists.boost.org 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
participants (4)
-
breadbread1984 -
Jeremiah Willcock -
Marcin Zalewski -
Nick Edmonds