Erdos-Renyi - G(n,p), G(n,m) model generators

gephi / gephi-plugins

Repository for Gephi Plugins maintained by the team. Each plugin has it's branch.

269 stars 622 forks source link

Erdos-Renyi - G(n,p), G(n,m) model generators #208

Closed elwin013 closed 2 years ago

elwin013 commented 5 years ago

As in title - Erdos-Renyi generators (both G(n,p) and G(n,m)).

eduramiba commented 5 years ago

Thanks for the pull request, I will review as soon as possible.

mbastian commented 2 years ago

Hi and thanks @elwin013 for the submission. I've made some minor updates

Renamed folder as we prefer camel-case for plugin folder name
Update to the latest Gephi version (via plugin-parent update)
Removed some unnecessary dependencies
Added license.txt file for the MIT License
Fix cancellation as the call to cancel() was not properly setting up the boolean flag you had
Fixed progress ticket numbers

My only question is in ErdosRenyiGnm you do edgePairs.remove(pair); at some point. But that's done on an ArrayList so with O(N^2) complexity for each removal if I'm not mistaken given the number of pairs. This is very expensive and I wonder if there is a better solution?

elwin013 commented 2 years ago

Hi @mbastian! Thank you for looking into it, fixing issues and aligning with current state of Gephi! :-)

Your concerns are 100% valid - this will be something around O(N^2) where N is coupled with number of the edges.

But there is the second solution for that - I've pushed it to the branch. In that case we will select two nodes and checks if there is already edge between them - if not create edge, otherwise try again. It will also use a bit less memory as we do not

My only concern is what is the cost of the checking if edge exists - instead of N loop calls and N removes we could have a lot of more loop calls and calls to containerLoader.edgeExists (and Integer.toString) ;-)

Both solutions are good enough - feel free to select latest or revert to previous one

mbastian commented 2 years ago

Great thanks for the patch! I've merged it and the plugin is now accessible from Gephi and at https://gephi.org/plugins/#/plugin/er-generator

elwin013 commented 2 years ago

That's great! Thank you! :-)