Hey Satyaki, On 00:07 Thu 10 Mar , Satyaki Upadhyay wrote: > *Create a wrapper for Region class of LibGeoDecomp to be used with BGL* > I loved the idea of this project because it involves both C++ (the language > I'm most comfortable with) and graph theory (which I've been using regulary > for the past two years). As a consequence of my regular participation in > algorithmic programming competitions, I am reasonably familiar with graph > theory and its algorithms (eg BFS/DFS/Dijkstra/Floyd-WarshallTarjan's to > name a few). I would like to know how to get started with this and would > like to discuss what needs to be done in some more detail.
I'm happy to hear that this project idea sparked your interest. LibGeoDecomp's Region class could be used to store the list of vertices as well as the edge set in BGL. Depending on the scenario (properties of the graph and operations performed on it) this might be efficient, or not. Right now BGL relies on standard containers (std::vector in adjacency_matrix, std::list in adjacency_list) for these tasks. Some background info on LibGeoDecomp's Region: as our ideas page says it's a fast runlength-compressed set for 1D/2D/3D coordinates. It's a) very fast for iteration, b) logical operations (e.g. intersection, union), and c) has a low memory footprint. My suggestions to get started with this idea would be: - take a look at the BGL source, starting with examples and then dive into the library source. Your focus should be: which operations are performed on the standard containers? In which areas of the code are they used? - take a look at libgeodecomp/src/geometry/region.h and, more importantly, libgeodecomp/src/geometry/test/unit/region.h. The tests should give you an idea what Region is capable of and how it's used. libgeodecomp/src/geometry/test/unit/regionbasedadjacency.h and libgeodecomp/src/geometry/regionbasedadjacency.h should give you an idea how Region<2> can store an adjacency list. - finally: how can the operations performed on std::list/vector in BGL be translated into operations on Region? make a brief list of the required operations and their approxiamate counterparts in Region. Please feel free to ask further questions. Cheers -Andreas -- ========================================================== Andreas Schäfer HPC and Grid Computing Department of Computer Science 3 Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany +49 9131 85-27910 PGP/GPG key via keyserver http://www.libgeodecomp.org ========================================================== (\___/) (+'.'+) (")_(") This is Bunny. Copy and paste Bunny into your signature to help him gain world domination!
signature.asc
Description: Digital signature
_______________________________________________ hpx-users mailing list [email protected] https://mail.cct.lsu.edu/mailman/listinfo/hpx-users
