New Release of the Gephi Minimum Spanning Tree Plugin

after-running-minimum-spanning-treeAt the end of 2015 the Gephi team released version 0.9. Version 0.9 contained many important core innovations that necessarily broke backwards compatibility, and with it, some plugins. The Minimum Spanning Tree plugin broke. I recently fixed it to work with the new API, and the new plugin submission process. I also added a suite of automated tests. Now the Minimum Spanning Tree plugin can function correctly in Gephi version 0.9+ and can be installed like any other plugin.

I changed the name of the plugin from “Spanning Tree” to “Minimum Spanning Tree” to better express the intent of the plugin. However, the id of the attribute that the plugin adds to all edges has remained the same (“spanningtree”) to retain backwards compatibility.

Going forward, I hope to increase my response time to breaking changes in Gephi. I plan to achieve that goal by reading Gephi news more often, and by refactoring the plugin to reflect contemporary Java best practices.

At a minimum of once every quarter I will be consulting the following Gephi resources:

In the third quarter of 2017 I hope to refactor the plugin. I wrote the core of the plugin during an undergraduate Algorithms course. I made decisions at the time that I would not make now after several years developing enterprise Java web apps for the USGS Office of Water Information. Bringing the plugin in compliance with best practices will ease future upgrades, further ensure correctness, and provide a better foundation on which to introduce new features. The recently-added tests will ensure that correctness is preserved during refactoring.

A big shout-out to Eduardo Ramos and the Gephi team for their help. I also thank the maintainers of the Cobertura projects (coremaven plugin, netbeans plugin) for providing code coverage visualization that helped catch bugs in my test utilities.

I welcome feedback, bug reports, pull requests, stories of how you used the plugin, etc. on Github. Graph on!

Computing, ProjectsPermalink

6 Responses to New Release of the Gephi Minimum Spanning Tree Plugin

  1. Brenda Mendoza says:

    Hi Carl,

    I need to run Kruskal algorithm for a newtork on gephi 9.1 but I downloaded the new release and I can’t figure out how to run it.

    Maybe I am missing a step on how to use it, as I see on the image it is by a filter but it is not clear to me.

    Please feel free to contact me here or by email… Thanks!

    • carl says:

      Hi Brenda,

      After you install the plugin, it is available as a statistic. See the right hand side of this screenshot. After you run the statistic, you can apply a filter to visualize which edges are a part of the minimum spanning tree.

      Does that help? Please let me know if there’s more I can do.

      • Brenda Mendoza says:

        Thanks Carl, it was really helpful!

        What would you recommend to do if then I need to run a MAXIMUM spanning tree? As all my values are between 0-1 I thought I could do a simple mathematical operation 1-value to transform the field. Or is it something I can try as a sort before running the minimum spanning tree?

        I appreciate your help.

        • carl says:

          Hi Brenda,

          The plugin does not currently support finding a maximum spanning tree, but you should be able to achieve the same thing in most cases by transforming your edge weights. The transformation that you proposed ((f(n) = 1 – n) would indeed work for edge weights between one and zero. I think a more generally-applicable transformation would be the reciprocal of the original weight.
          f(n) = 1/n

          If some edge weights are zero, you could transform them to a very small constant like 1*10^-10 to prevent divide-by-zero errors.

          I have added a feature request on GitHub for finding a maximum spanning tree:
          https://github.com/carlschroedl/gephi-plugins/issues/9

          Thanks!

  2. John D Kromkowski says:

    I recently started using your plugin on a network of 435 nodes and 94395 edges. I happened to notice an edge chosen as part of minimum spanning tree which didn’t look correct. Upon closer examination, it was clearly wrong. So to test your plugin, I deleted all edges that were not mst edges. Then I added an edge which clearly would have been a better (minimum) edge. Then, I ran mst. But this new edge was not chosen. So something doesn’t seem correct.

Leave a Reply

Your email address will not be published. Required fields are marked *