- Boost - lists.boost.org

BGL Algorithm (Network Flow)
by Tanton Gibbs 06 Jul '04

06 Jul '04

I'm attempting to do a graph algorithm and am looking for a good BGL algorithm to do this -- any advice would be appreciated. Basically, I have a directed, weighted, bipartite graph. I'll call the two sets of nodes (V,W). Every node in V connects to one or more nodes in W. However, not every node in W is connected to. When the algorithm ends, I want every node in V to be connected to 0 or 1 node in W and no node in W should have more than one connection to it. I also want the total weight of all the edges to be minimized (basically, prune the most costly edges to create the graph), but no edge should be pruned unnecessarily (I want to maximize the number of connected nodes). It looks to me to be a pretty evil problem, but I'm hoping someone has a good suggestion. Thanks! Tanton H. Gibbs, Ph.D. Software Developer Acxiom Corporation

1 0

Re: [ublas-dev] Re: [boost] Re: Boost Mathematicians
by Jeremy Graham Siek 06 Jul '04

06 Jul '04

Hi Michael, On Jul 5, 2004, at 4:52 PM, Michael Stevens wrote: > Hi Jeremy, > > Thanks for chipping in on this. I don't think we have conversed > before, apart > from maybe a few patches I submitted for MTL. Although it would be > great for > everyone to work on uBLAS I think a revived MTL would also be a good > thing. > The design of MTL was very influential. Thanks! > I won't comment on the other issues as I have already posted a few > thoughts on > these matters. > > > > Mmmh, this open pitfalls concerning A*B*C in performance issues > for > > > non experts. > > > > No, the right way to handle this is to have the expression template > > machinery > > identify that a temporary is needed, and create one automatically. > > I wonder if you caught the discussion on this about 6 months ago. I > would > strongly argue that the automatic creation of temporaries in the > subexpression context is a bad thing... > > The roles of the expressions we declare (as in declarative > programming) is > twofold. a) to express the mathematical context b) to express how > this should > be computed. That is, to be able to express how the expression is to > be > evaluated. This gives us control over its numerical properties and > also of > the time and space complexity. > > In principle, uBLAS has a one to one relationship between an > expression and > how it is evaluated. Simply stated this is based on an element by > element > evaluation of assignment. There are shortcuts in the case of sparse > types but > the principle holds. > > An expression A+B+C can be evaluated in this manner trivially. > A*B*C can also be evaluated in this manner, although the element by > element > rule results in an O() that is not what many users expect. > To get the O() that users expect we could automagically insert > temporaries. I > fear this is a tar pit however. What temporary should be chosen? Each > of A B > or C could be a either dense, sparse, compressed, banded, symmetric or > combinations therefore. The type the user expects or is "the best" is > not at > all clear. Although automagically inserting temporaries in non-trivial (especially since it must all be done with template meta-programming) I do not think it is a tar pit. Here is the simply heuristic that I used for MTL 3 to decide where to put temporaries: 1. If an operation needs to read from an argument multiple times, evaluate the argument eagerly into a temporary. For example, a sparse matrix in compressed row format times the sum of two vectors: A * (x + y) In this case, the (x + y) would be evaluated into a temporary before evaluating the multiplication. 2. If an operation writes into its output in multiple passes, then perform the operation in an eager fashion. For example, the sum of a vector and the product of a sparse matrix in compressed column format and a vector. x + (A * y) In this case, the (A * y) would be evaluated into a temporary before evaluating the addition. > > I think the only correct solution is to force the user to specify > this type. > Incidently, the no temporary evaluation should also be an option as > in some > cases (small sizes) it is desirable. uBLAS currently disallows this > to avoid > confusing the user. I should be reinstated in some form however. > > All the best, > Michael > > -- > ___________________________________ > Michael Stevens Systems Engineering > > 34128 Kassel, Germany > Phone/Fax: +49 561 5218038 > > Navigation Systems, Estimation and > Bayesian Filtering > http://bayesclasses.sf.net > ___________________________________ > > _______________________________________________ Jeremy Siek <jsiek(a)osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Candidate, Indiana University Bloomington C++ Booster (http://www.boost.org) _______________________________________________

3 2

Re:Re: [boost] Re: 1.32 release preparation
by Robert Ramey 06 Jul '04

06 Jul '04

Johannes Brunen wrote: >> And if there are a large >> number of new things left out by that approach then we should plan >> another release sooner rather than waiting 4 months. >However, then you need new volunteers which have to spend the time for the >whole procedure again. The release procedure is too onerous. This isn't the problem, it's a symptom of a more subtle problem. If the source of this difficulty can be found can corrected, then releases can occur more frequently. My personal view is that it's a symptom of a development process that couples otherwise independent/orthogonal efforts. This is due to the fact that we're all working against a development tree that has experimental code in it. So minor issues ripple across all efforts. >I could think of a review process which accepts a library only after the >list of requested changes has been made. > I would prefere a review process which leads to final > acceptance only after a library is 'CVS' compatible i.e. does not yield to > any (known) regressions of the existing pool libraries and is equipted > with a working testing facility. The review process qualifies submissions for inclusion into boost. I don't think there are any libraries that have been accepted then suffered changes which made them unacceptable. It's not fair to ask a submitter to require that that he totally "finish" the package before submission when it cannot be guaranteed that it will be accepted. The review process isn't the problem, its working quite well. It's just that there is more effort than first meets the eye between the time a library is deemed acceptable and the time it is ready for inclusion into boost. The serialization library including code, headers, tests, html, jamfiles, *.bat, and shell scripts is has passed 25,0000 lines. This takes time and no changes in the review or release procedure can change that. There is the review package which seems to work pretty well. But I would be reluctant to check it in as it doesn't match the review acceptance conditions and I'm concerned about trying to maintain a package which I have now moved beyond. Robert Ramey

3 3

Re: [ublas-dev] Re: [boost] Re: Boost Mathematicians
by Jeremy Graham Siek 06 Jul '04

06 Jul '04

On Jul 5, 2004, at 11:54 AM, Peter Schmitteckert wrote: > Salut, > > (note that I only use the dense matrices of ublas) > > On Mon, 5 Jul 2004, Toon Knapen wrote: > > > > This is just a matter of documentation. AFAIK there is no accepted > > concept that demands 'num_rows' and 'num_columns'. The '1' and '2' > refer > > to the first and second index which is also a nice convention IMO. > > I prefer size1 and size2, since it fits to the sheme of having a > tensor > structure with a size3. Mixing up abstractions is not a good idea. Matrices and tensors are different creatures. True, sometimes it is useful to think of a tensor as a matrix, and having adaptors or views that allow for this is a good thing. The names we use for operations should match the common terminology from the problem domain. In this case, the common terminology is rows and columns. When we create concepts for tensors, we can use size1, etc. > Columns and Rows can lead to confusion concernig storage layout. I disagree. > > > > > > > > * iterator1 and iterator2 should be named column_iterator and > > > row_iterator or something memnonic. > > same as above. > > same as above. > > > > > > > > > * prod should be named operator*; this is a linear algebra library > > > after all. > > Mmmh, this open pitfalls concerning A*B*C in performance issues for > non experts. No, the right way to handle this is to have the expression template machinery identify that a temporary is needed, and create one automatically. Cheers, Jeremy _______________________________________________ Jeremy Siek <jsiek(a)osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Candidate, Indiana University Bloomington C++ Booster (http://www.boost.org) _______________________________________________

7 12

unresolved externtal symbol with .Net 2003
by Brian Carlson 06 Jul '04

06 Jul '04

I have a project that worked fine with .Net 2002 (7.0.9466). But when I open it up on .Net 2003 (7.1.3088) it compiles, but when it links I get the following warning: CDlgcEventProcessor.obj : error LNK2019: unresolved external symbol "public: __thiscall boost::thread::thread(class boost::function0<void,struct boost::empty_function_policy,struct boost::empty_function_mixin,class std::allocator<class boost::function_base> > const &)" (??0thread@boost@@QAE@ABV?$function0@XUempty_function_policy@boost@@Uemp ty_function_mixin@2@V?$allocator@Vfunction_base@boost@@@std@@@1@@Z) referenced in function "protected: int __thiscall DlgcFW2::CDlgcEventProcessor::StartThread(void)" (?StartThread@CDlgcEventProcessor@DlgcFW2@@IAEHXZ) Anyone have this kind of problem before?

2 1

RE: [boost] Boost.Test, failed assert output
by Rozental, Gennadiy 06 Jul '04

06 Jul '04

I will see what I can do about it. If I remember correctly, the problem is that I do not know where the error occurred. So I have no way to print line pointing there. I could print only line pointing where the error was caught/detected. I am not sure it is what you want. Regards, Gennadiy.

1 0

Question about stdlib in gcc-2.95.3-linux toolset
by Joaquín Mª López Muñoz 06 Jul '04

06 Jul '04

A test of mine is failing in the gcc-2.95.3-linux toolset with the following: ostream: No such file or directory which, I guess, indicates that the std library used by this toolset does not have a <ostream> header. Digging through the regression logs, seems like the library being used is SGI's. Now, there is not defect macro in config/stdlib/sgi.hpp indicating that <ostream> is not available, so my question is: * Is this defect in gcc 2.95 known, and not an installation artifact? * If so, is there any way to figure it out from Boost.Config defect macros or some combination of these and SGI-specific macros? Maybe I'm missing something obvious and this lack of standard headers by gcc 2.95 is common knowledge, I just happen not to have dealt with this compiler ever. Thanks Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

3 2

Does anyone have an is_virtual_base_and_derived ?
by Robert Ramey 06 Jul '04

06 Jul '04

Type traits includes: ::boost::is_base_and_derived<T,U> Does anyone have a version that might be called is_virtual_base_and_derived<B, D> which would return true iff D is derived virtually from B ? Robert Ramey

1 0

Re: [utility] boost::reset
by jhopkin＠reflectionsinteractive.com 06 Jul '04

06 Jul '04

Daniel Frey wrote: > > Gennaro Prota wrote: > > > Does the swap trick necessarily free the memory? > > AFAIK, yes. See <http://www.gotw.ca/gotw/054.htm>. > The STL implementation I have been using seems to allocate a buffer on first insertion into any container of a given type, and frees it only when it feels like it (often on program shut-down). I don't know if it's a strictly conforming implementation in that respect, although I can't see anything in the standard prohibiting this behaviour. James Hopkin

3 2

Re: Boost Mathematicians
by Michael Stevens 06 Jul '04

06 Jul '04

On Monday 05 July 2004 22:59, David Abrahams <dave(a)boost-consulting.com> wrote: > > Almost all the major reference works on BLAS and Matrices > > simply state elements are either Real or Complex and are therefore > > implicitly a field. > > We're not just concerned about the elements of matrices, but the > vectors and matrices themselves. OK I was assuming you were looking for a clear concept definition for the element types. > This becomes a real issue when you > have to write algorithms that might operate on matrices of reals or > matrices of matrices -- yes, these things do come up in real > applications. This is very odd. In linear algebra there is no such thing as a matrix of matrices. This impacts on the while prod/operator* controversy. That is, the primary advantage of not defining operator*. It prevents you passing matrix to an algorithm (not necessarily part of the uBLAS itself) that uses operator* and not unreasonably makes the assumption that operator* is commutative. The assumption is not unreasonable as all built in types operator* is exactly commutative. That said I have also argued in favour of operator* instead of prod in the past. It's central role in LA certainly argues in favour of using operator*. This involves so much peoples expectation as for algebraic notation, programming practice and just personal taste. > >> * Redundant specification of element type in matrix/vector storage. > > See my reply to Toon. Ah yes value_type is specified in both the matrix vector and storage type parameter list. In itself this is not good as the storage type should parameterise the matrix/vector with the value_type. It is simply there to make the syntax in the default case simple without the need for a type generator as in MTL. > > For std::slice (valarray) compatibility stride should be last. Not sure why > > this was not picked up on a long time ago!! > > valarray (and uBLAS) use size (not end) for good reason however. > > ...which is...? The begin end definition fails when stride==0. Slices of finite size with stride==0 are very useful. Similarly when (end-begin) *stride <0 the behaviour would have to be defined. > > Interesting solution. Agreed, the current implementation is closed to other > > objects because of the intrusive base class. Sadly uBLAS was designed before > > enable_if. Any pointers to compile/runtime effects of the enable_if solution? > > I can't really imagine what you're asking for here. I was looking for any publications/links to compare how compilers do between the two solutions. Anyone have any pointers? Thanks, Michael -- ___________________________________ Michael Stevens Systems Engineering Navigation Systems, Estimation and Bayesian Filtering http://bayesclasses.sf.net ___________________________________

4 5