the stability of breadth_first_visit in BGL

newer
Boost.DLL formal review is ongoing

breadbread1984

28 Apr 2015 28 Apr '15

1:36 p.m.

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

Show replies by date

Marcin Zalewski

28 Apr 28 Apr

8:50 p.m.

I think it should be stable. Do you see any results to the contrary? On Tue, Apr 28, 2015 at 9:40 AM breadbread1984 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

Nick Edmonds

14 Jul 14 Jul

6:59 p.m.

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 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 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

Jeremiah Willcock

29 Apr 29 Apr

2:31 a.m.

...

________________________________ From: breadbread1984 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

3423

Age (days ago)

3500

Last active (days ago)

List overview

Download

3 comments

4 participants

participants (4)

breadbread1984
Jeremiah Willcock
Marcin Zalewski
Nick Edmonds