[Graph][parallel] Scale-free graph generator without self-loops
Hello, Does anyone knows if there is possible to generate a scale-free graph that does not generate self-loops (edges with the same vertex for source and target)? I am using the unique_rmat_iterator, but it generates some self-loops. I could remove them, but for the graph remains inconsistent because of a bug. I will apreciate your help. -- View this message in context: http://boost.2283326.n4.nabble.com/Graph-parallel-Scale-free-graph-generator... Sent from the Boost - Users mailing list archive at Nabble.com.
On Thu, 7 Mar 2013, bminano wrote:
Hello,
Does anyone knows if there is possible to generate a scale-free graph that does not generate self-loops (edges with the same vertex for source and target)? I am using the unique_rmat_iterator, but it generates some self-loops. I could remove them, but for the graph remains inconsistent because of a bug.
I will apreciate your help.
One option would be to use a filter_iterator from Boost.Iterator to remove the self-loops before you create the graph. -- Jeremiah Willcock
Hello Jeremiah, I have been looking for information and I have seen there is a filtered_graph, maybe it is another option. I don't understand very well how the filter_iterator remove the self-loops before creating the graph. Don't you refer after creating it? Thank you El 07/03/13 16:17, Jeremiah Willcock escribió:
On Thu, 7 Mar 2013, bminano wrote:
Hello,
Does anyone knows if there is possible to generate a scale-free graph that does not generate self-loops (edges with the same vertex for source and target)? I am using the unique_rmat_iterator, but it generates some self-loops. I could remove them, but for the graph remains inconsistent because of a bug.
I will apreciate your help.
One option would be to use a filter_iterator from Boost.Iterator to remove the self-loops before you create the graph.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Un saludo, Borja Miñano IAC3 - Universitat de les Illes Balears ParcBit - Edifici 17 (Disset); Local D7 Cra. Valldemossa km. 7,4 E-07121 Palma de Mallorca. Balears. Spain. Phone: +34 871 967 434
Hello again, Following your advise I started trying with filter_iterator. I could them filter in a in_edge iterator. But I was thinking on filtering the unique_rmat_iterator that I use to generate the graph (so I now understand why you said before creating the graph). Unfortunately I got a compilation error that cannot figure out how to solve. My filter is simple: struct no_self_loops { no_self_loops() {} bool operator()(const std::pair<int,int>& e) { return e.first != e.second; } }; And the the use is: Graph g( boost::make_filter_iterator<no_self_loops>(RMATGen(gen, 100, 1000, 0.57, 0.19, 0.19, 0.05), RMATGen()), boost::make_filter_iterator<no_self_loops>(RMATGen(), RMATGen()), 100); and also tried with: typedef boost::filter_iterator<no_self_loops, RMATGen > FilterIter; no_self_loops predicate; FilterIter filter_iter_first(predicate, RMATGen(gen, 100, 1000, 0.57, 0.19, 0.19, 0.05), RMATGen()); FilterIter filter_iter_last(predicate, RMATGen(), RMATGen()); But the result is the same, the compilation errors are as follows: ... /opt/boost_snap/include/boost/iterator/iterator_facade.hpp: En la instanciación de ‘boost::iterator_facade<boost::filter_iterator<no_self_loops, boost::unique_rmat_iterator<boost::random::linear_congruential_engine<unsigned int, 48271u, 0u, 2147483647u>, boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS>, boost::bidirectionalS, VertexProperties, EdgeProperties> >
, std::pair<long unsigned int, long unsigned int>, boost::single_pass_traversal_tag, const std::pair<long unsigned int, long unsigned int>&, void>’: /opt/boost_snap/include/boost/iterator/iterator_adaptor.hpp:261:9: instanciado desde ‘boost::iterator_adaptor<boost::filter_iterator<no_self_loops, boost::unique_rmat_iterator<boost::random::linear_congruential_engine<unsigned int, 48271u, 0u, 2147483647u>, boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS>, boost::bidirectionalS, VertexProperties, EdgeProperties> > , boost::unique_rmat_iterator<boost::random::linear_congruential_engine<unsigned int, 48271u, 0u, 2147483647u>, boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS>, boost::bidirectionalS, VertexProperties, EdgeProperties> , boost::use_default, boost::use_default, boost::use_default, boost::use_default>’ /opt/boost_snap/include/boost/iterator/filter_iterator.hpp:44:9: instanciado desde ‘boost::filter_iterator<no_self_loops, boost::unique_rmat_iterator<boost::random::linear_congruential_engine<unsigned int, 48271u, 0u, 2147483647u>, boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS>, boost::bidirectionalS, VertexProperties, EdgeProperties> > >’ filtro.cpp:235:112: instanciado desde aquí /opt/boost_snap/include/boost/iterator/iterator_facade.hpp:584:7: error: tipo de parámetro ‘boost::iterator_facade<boost::filter_iterator<no_self_loops, boost::unique_rmat_iterator<boost::random::linear_congruential_engine<unsigned int, 48271u, 0u, 2147483647u>, boost::adjacency_list<boost::vecS, boost::distributedS<boost::graph::distributed::mpi_process_group, boost::vecS>, boost::bidirectionalS, VertexProperties, EdgeProperties> > , std::pair<long unsigned int, long unsigned int>, boost::single_pass_traversal_tag, const std::pair<long unsigned int, long unsigned int>&, void>::difference_type {aka void}’ inválido ...
I couldn't change the language for the errors but its says something like " Parameter type 'boost::iterator_facade<boost...>::difference_type {aka void}’ invalid. I cannot imagine where is my problem, could you help me? El 08/03/13 10:03, Borja Miñano escribió:
Hello Jeremiah,
I have been looking for information and I have seen there is a filtered_graph, maybe it is another option. I don't understand very well how the filter_iterator remove the self-loops before creating the graph. Don't you refer after creating it?
Thank you
El 07/03/13 16:17, Jeremiah Willcock escribió:
On Thu, 7 Mar 2013, bminano wrote:
Hello,
Does anyone knows if there is possible to generate a scale-free graph that does not generate self-loops (edges with the same vertex for source and target)? I am using the unique_rmat_iterator, but it generates some self-loops. I could remove them, but for the graph remains inconsistent because of a bug.
I will apreciate your help.
One option would be to use a filter_iterator from Boost.Iterator to remove the self-loops before you create the graph.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Un saludo, Borja Miñano IAC3 - Universitat de les Illes Balears ParcBit - Edifici 17 (Disset); Local D7 Cra. Valldemossa km. 7,4 E-07121 Palma de Mallorca. Balears. Spain. Phone: +34 871 967 434
On Fri, 8 Mar 2013, Borja Miñano wrote:
Hello again,
Following your advise I started trying with filter_iterator. I could them filter in a in_edge iterator. But I was thinking on filtering the unique_rmat_iterator that I use to generate the graph (so I now understand why you said before creating the graph). Unfortunately I got a compilation error that cannot figure out how to solve. My filter is simple:
struct no_self_loops { no_self_loops() {} bool operator()(const std::pair<int,int>& e) { return e.first != e.second; } };
And the the use is:
(snip)
I couldn't change the language for the errors but its says something like " Parameter type 'boost::iterator_facade<boost...>::difference_type {aka void}’ invalid. I cannot imagine where is my problem, could you help me?
Could you please try the trunk version of Boost.Graph? I just committed (r83366) a change that might have fixed the errors you're getting. If you are using a release version of Boost, you only need to download <boost/graph/rmat_iterator.hpp> from the trunk to test. -- Jeremiah Willcock
Hi, I downloaded the file, actually <boost/graph/rmat_graph_generator.hpp> if anyone read the post, and worked perfectly. Now I can filter the rmat generator before generating the graph. Thanks a lot for helping me, Jeremiah. El 08/03/13 18:31, Jeremiah Willcock escribió:
On Fri, 8 Mar 2013, Borja Miñano wrote:
Hello again,
Following your advise I started trying with filter_iterator. I could them filter in a in_edge iterator. But I was thinking on filtering the unique_rmat_iterator that I use to generate the graph (so I now understand why you said before creating the graph). Unfortunately I got a compilation error that cannot figure out how to solve. My filter is simple:
struct no_self_loops { no_self_loops() {} bool operator()(const std::pair<int,int>& e) { return e.first != e.second; } };
And the the use is:
(snip)
I couldn't change the language for the errors but its says something like " Parameter type 'boost::iterator_facade<boost...>::difference_type {aka void}' invalid. I cannot imagine where is my problem, could you help me?
Could you please try the trunk version of Boost.Graph? I just committed (r83366) a change that might have fixed the errors you're getting. If you are using a release version of Boost, you only need to download <boost/graph/rmat_iterator.hpp> from the trunk to test.
-- Jeremiah Willcock
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Un saludo, Borja Miñano IAC3 - Universitat de les Illes Balears ParcBit - Edifici 17 (Disset); Local D7 Cra. Valldemossa km. 7,4 E-07121 Palma de Mallorca. Balears. Spain. Phone: +34 871 967 434
participants (3)
-
bminano -
Borja Miñano
-
Jeremiah Willcock