Re: [Boost-users] Boost-users Digest, Vol 3971, Issue 2

Subject: Re: [Boost-users] Boost-users Digest, Vol 3971, Issue 2
From: vibhor aggarwal (vibhor.aggarwal_at_[hidden])
Date: 2014-11-18 03:17:58

Thanks for the message Joaquin!

I am running the boost invariant checks for multi-index and something which took a minute is now taking a full day to run. Any how, I haven't had any of the assertions fail in 5 iterations which completed so far and I have moved to version 1.57.0

Will get back if I see any issues with this again.





On Thursday, 13 November 2014 10:30 PM, "boost-users-request_at_[hidden]" <boost-users-request_at_[hidden]> wrote:
 


Send Boost-users mailing list submissions to
    boost-users_at_[hidden]

To subscribe or unsubscribe via the World Wide Web, visit
    http://lists.boost.org/mailman/listinfo.cgi/boost-users
or, via email, send a message with subject or body 'help' to
    boost-users-request_at_[hidden]

You can reach the person managing the list at
    boost-users-owner_at_[hidden]

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Boost-users digest..."


Today's Topics:

   1. Re: [Mutli-Index,    InterProcess] Multi-index stability issue
      with interprocess? (Joaquin M Lopez Munoz)
   2. [Graph] A* with heterogeneous heuristics (Sensei)
   3. 1.57.0 link errors (missing ctor/dtor for
      boost::archive::detail::shared_ptr_helper) (David Abdurachmanov)
   4. [BGL] Shortest-Path subject to length constraint (Yun Liu)


----------------------------------------------------------------------

Message: 1
Date: Thu, 13 Nov 2014 10:41:08 +0000 (UTC)
From: Joaquin M Lopez Munoz <joaquin_at_[hidden]>
To: boost-users_at_[hidden]
Subject: Re: [Boost-users] [Mutli-Index,    InterProcess] Multi-index
    stability issue with interprocess?
Message-ID: <loom.20141113T111909-42_at_[hidden]>
Content-Type: text/plain; charset=utf-8

vibhor aggarwal <vibhor.aggarwal <at> yahoo.com> writes:

> 
> I am creating a multi-index [...] and storing that in a managed
> memory mapped file (boos::interprocess) [...]
> All the data is first inserted into the multi-index once and then it
> is read from the muti-index with a query [...]
> 
> boost::tie(l, u) = m_p_mi_ts->get<0>().
>   equal_range(boost::make_tuple(i, j));
> 
> We are testing this whole process over and over again (each iteration
> is a new run of the process), and once in every 50 or so iterations
> we get a segment fault inside boost on firing the query. Here is the
> boost part of the stack from the core dump:

With so little information, I can only guess: the crash is hapenning
at a very superficial level into equal_range, namely when dereferencing
the container's header node (the top of the rb-tree ordered indices are
based on). This suggests that the container layout is seriously screwed;
possible reasons:

* Memory overwrites from some adjacent structure
* File corruption (?)
* m_p_mi has been changed somewhere
* Some sort of overrun within the memory-mapped file

It'd be best if you could provide a testing case for this or some more
context. If this is not an option, you can activate Boost.MultiIndex
invariant-checking mode:

http://www.boost.org/libs/multi_index/doc/tutorial
/debug.html#invariant_check

which will assert as soon as some internal corruption is detected
(caveat: this mode will reduce performance drastically).

Joaqu?n M L?pez Mu?oz
Telef?nica



------------------------------

Message: 2
Date: Thu, 13 Nov 2014 12:41:32 +0100
From: Sensei <senseiwa_at_[hidden]>
To: boost-users_at_[hidden]
Subject: [Boost-users] [Graph] A* with heterogeneous heuristics
Message-ID: <546498EC.6070204_at_[hidden]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed

Dear all,

I haven't given up in trying to implement an A* algorithm with BGL. My 
problem is theoretically simple, as in some previous posts.

    Given a graph of letters, and a word, find the path in the
    graph that minimizes the distance between the letters of
    the word and the nodes in the graph.

It's best to show an example:

     /*
      *    B          H
      *   / \        /
      *  A---D---F---G---I
      *   \ /\
      *    C  E
      *
      *  input:  A E I O U
      *  result: A D F G I
      */

With that graph, my heuristic should take into account not just the 
letter in the graph per se, but the *corresponding* one in the input 
word. So, starting with "AEIOU" the search will:
- expand A (A in **A**EIOU)
- find B, C, D
- expand D (closest to E in A**E**IOU)
- find D, F
- expand F (closest to I in AE**I**OU)
- find G
- expand G (only one, closest to O in AEI**O**U)
- find H, I
- expand U (closest to U in AEIO**U**)

This settings could also be more complicated, adding weights to edges, 
but for now I am happy with this problem.

What I've done now? Implementing my own A* algorithm, by hand. Of course 
this might work, but I'd prefer using BGL's facilities.

I must say that I am quite confused about BGL's data structures, as for 
instance in the A* cities example (1), we need to create a weight map, 
so what if I don't need weights? Moreover, predecessors and distances 
are instantiated with a std::vector, but what happens if I need to 
operate on a very large graph, for instance 200M nodes? Moreover, what 
will happen when I will distribute the graph over a cluster with Boost 
Parallel Graph? ... Ok maybe this is too ahead of the time! :)


Basically, I'd need to replicate my A* ugly by-hand implementation with 
custom visitors and custom heuristics.

Below you may find my failed attempt. I need some help with this, 
because I find the documentation a little bit hard to understand, 
especially when some newbie like me approaches Boost :)

Failures in my code: I can't get to define a non-weighted graph, and the 
call to the A* search is cryptic: I don't have weights. Should I define 
fake ones for instance all equal to 1?


I really hope you guys can help me in this, my code works, but using BGL 
would be best!

Thanks!



(1) http://www.boost.org/doc/libs/1_57_0/libs/graph/example/astar-cities.cpp


#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <utility>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/astar_search.hpp>

typedef boost::adjacency_list<boost::vecS,
                               boost::vecS,
                               boost::bidirectionalS
                               > graph;

typedef boost::graph_traits<graph>::edge_iterator edge_iterator;



// Custom A* heuristic
template <class Graph, class CostType>
class bestmatch_heuristic : public boost::astar_heuristic<Graph, CostType>
{
public:
     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;

     bestmatch_heuristic() { };

     CostType operator()(Vertex u)
     {
         std::cout << ">>>> h(" << u << ") = " << 1 << std::endl;
         return 1;
     }

private:

};


// Used to end the A* search algorithm
struct end_astar { };

// Custom A* visitor
template <class Vertex>
class bestmatch_visitor : public boost::default_astar_visitor
{
public:
     bestmatch_visitor(Vertex goal) : destination_(goal) { };

     template<class Graph>
     void discover_vertex(Vertex u, const Graph &g)
     {
         std::cout << "discover " << u << std::endl;
     }


     template <class Graph>
     void examine_vertex(Vertex u, Graph& g)
     {
         std::cout << "examine " << u << std::endl;

         if (u == destination_) throw end_astar();
     }

private:
     Vertex destination_;
};


int main()
{
     /*
      *    B          H
      *   / \        /
      *  A---D---F---G---I
      *   \ /\
      *    C  E
      *
      *  input:  A E I O U
      *  result: A D F G I
      */

     std::unordered_map<char, std::size_t> letters;

     auto getletter = [](std::size_t i) -> char { return 'A' + i; };

     for (int i = 'A'; i <= 'I'; i++) letters[i] = i - 'A';

     graph g;

     boost::add_edge(letters['A'], letters['B'], g);
     boost::add_edge(letters['A'], letters['C'], g);
     boost::add_edge(letters['A'], letters['D'], g);

     boost::add_edge(letters['B'], letters['D'], g);

     boost::add_edge(letters['C'], letters['D'], g);

     boost::add_edge(letters['D'], letters['E'], g);
     boost::add_edge(letters['D'], letters['F'], g);

     boost::add_edge(letters['F'], letters['G'], g);

     boost::add_edge(letters['G'], letters['H'], g);
     boost::add_edge(letters['G'], letters['I'], g);

     edge_iterator ei, ee;

     for (boost::tie(ei, ee) = boost::edges(g); ei != ee; ei++)
     {
         std::cout << getletter(boost::source(*ei, g)) << " -> " << 
getletter(boost::target(*ei, g)) << std::endl;
     }

     // Heuristics
     bestmatch_heuristic<graph, int> h;

     // Predecessors
     std::vector<graph::vertex_descriptor> p(boost::num_vertices(g));

     try
     {
#if 0
         boost::astar_search_tree(// Graph
                                  g,
                                  // Start node
                                  letters['A'],
                                  // Heuristics
                                  bestmatch_heuristic<graph, int>(),
                                  // Predecessor map

boost::predecessor_map(boost::make_iterator_property_map(p.begin(), 
boost::get(boost::vertex_index, g))));
#endif
     }
     catch (end_astar e)
     {

     }

}



------------------------------

Message: 3
Date: Thu, 13 Nov 2014 10:07:07 +0100
From: David Abdurachmanov <david.abdurachmanov_at_[hidden]>
To: boost-users_at_[hidden]
Cc: amey_at_[hidden]
Subject: [Boost-users] 1.57.0 link errors (missing ctor/dtor for
    boost::archive::detail::shared_ptr_helper)
Message-ID: <C512A56C-8078-438E-BDBC-376A9EF590F9_at_[hidden]>
Content-Type: text/plain; charset="us-ascii"

Hi,

I am moving to Boost 1.57.0 and having issues with some code related to serialization.

https://github.com/cms-sw/cmssw/blob/CMSSW_7_3_X/CondFormats/Serialization/interface/eos/portable_oarchive.hpp
https://github.com/cms-sw/cmssw/blob/CMSSW_7_3_X/CondFormats/Serialization/interface/eos/portable_iarchive.hpp

In both cases the problem is here:

#if BOOST_VERSION >= 103500
#include <boost/archive/shared_ptr_helper.hpp>
#endif

[snip]

#if BOOST_VERSION >= 103500
// mix-in helper class for serializing shared_ptr
, public boost::archive::detail::shared_ptr_helper
#endif

A similar (or the same) problem is reported here: http://boost.2283326.n4.nabble.com/Serialization-link-error-in-1-56-td4666838.html#a4666853

It seems that ctor/dtor are not exported anymore:

/testSerializationDQMObjects.o: In function `eos::portable_oarchive::portable_oarchive(std::ostream&
, unsigned int)':
testSerializationDQMObjects.cpp:(.text._ZN3eos17portable_oarchiveC2ERSoj[_ZN3eos17portable_oarchiveC5ERSoj]+0x54): undefined reference to `boost::archive::detail::shared_ptr_helper:
:shared_ptr_helper()'
testSerializationDQMObjects.cpp:(.text._ZN3eos17portable_oarchiveC2ERSoj[_ZN3eos17portable_oarchiveC5ERSoj]+0x1c1): undefined reference to `boost::archive::detail::shared_ptr_helper
::~shared_ptr_helper()'

boost::serialization::shared_ptr_helper does not seem to be a drop-in replacement at first look.

There is also 'shared_ptr_helper_base', but is only available in the implementation file.

Is such mix-in class still available in a new Boost version?

Thanks,
david
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.boost.org/boost-users/attachments/20141113/36b06eaa/attachment.sig>

------------------------------

Message: 4
Date: Thu, 13 Nov 2014 09:48:27 -0500
From: Yun Liu <yunliu_at_[hidden]>
To: <boost-users_at_[hidden]>
Subject: [Boost-users] [BGL] Shortest-Path subject to length
    constraint
Message-ID: <5464C4BB.6040204_at_[hidden]>
Content-Type: text/plain; charset="utf-8"; format=flowed

Hi all, apologies in advance if this question is trivial; I couldn't 
find anything like it asked previously in the mailing list.

My question is, if I have a directed graph (with non-negative edge 
weights, to keep things simple for now), I would like to find the 
shortest-cost path from a source node to target node, but with the 
constraint on the maximum number of edges allowed.

For example, if I have the graph with vertices {A,B,C,D} and edges:
A->B (cost 1),
B->C (cost 1),
C->D (cost 1),
A->D (cost 1000),

but I have the constraint that my path should only be a maximum of 2 
edges, the correct solution would still be A->D with cost 1000.

Looking through the previous BGL examples, say with bellman-ford or 
Dijkstra, it did not seem immediately obvious how to enforce this 
stipulation.

Thanks again for any ideas!

-Yun


------------------------------

Subject: Digest Footer

_______________________________________________
Boost-users mailing list
Boost-users_at_[hidden]
http://lists.boost.org/mailman/listinfo.cgi/boost-users

------------------------------

End of Boost-users Digest, Vol 3971, Issue 2
********************************************