Message Boards Message Boards

GROUPS:

IGraph/M: igraph interface for Mathematica

Posted 3 years ago
6239 Views
|
16 Replies
|
31 Total Likes
|

The post below was written for the original release of IGraph/M. The current release is 0.3.0. See http://szhorvat.net/mathematica/IGraphM for more details.

It is compatible with Windows 64-bit, macOS 10.9 or later, Linux 64-bit and Raspbian Jessie (on the Raspberry Pi computer). It requires Mathematica 10.0.2 or later.


I would like to announce IGraph/M, a new igraph interface for Mathematica: http://szhorvat.net/mathematica/IGraphM

igraph is a graph manipulation and analysis package. IGraph/M makes its functionality available from Mathematica.

This initial release, version 0.1, covers only some igraph functions, as I focused on the things that I need personally. However the main framework is complete, and new functions can be added quickly. If anyone would like to contribute, please contact me.

Binary packages for OS X (10.9 or later) and Linux can be downloaded from GitHub. Unfortunately I was unable to compile the development version of igraph for Windows, so I cannot provide a Windows version. If you can help with compiling igraph itself (not IGraph/M) on Windows, please let me know!

Functionality in this release that is not built into Mathematica:

  • Vertex betweenness centrality for weighted graphs
  • Estimates of vertex betweenness, edge betweenness and closeness centrality; for large graphs
  • Minimum feedback arc set for weighted and unweighted graphs
  • Find all cliques (not just maximal ones)
  • Count 3- and 4-motifs
  • Rewire edges, keeping either the density or the degree sequence
  • Alternative algorithms for isomorphism testing: Bliss, VF2
  • Subgraph isomorphism
  • Test if a degree sequence is graphical
  • Alternative algorithms for generating random graphs with given degree sequence
  • Layout algorithms that take weights into account

Note that IGraph/M is not a replacement for Mathematica's graphs and networks functionality. It is meant to complement what is already available in Mathematica, thus it primarily focuses on adding functionality that is not already present.

Why did I release the package before covering most of the igraph functionality? I do not have time to work on things I do not personally need or use, so I am unlikely to extend it further unless the need comes up. I do think that the functions that are included in v0.1 can already be useful to others too. I would also like to give the opportunity for people to contribute to the project if they wish to. The groundwork has been laid, so further extensions should be quick and relatively easy.

Also check out a related project, IGraphR, which makes igraph available for Mathematica users through RLink. I wrote IGraph/M because I needed higher performance and greater reliability (especially for parallel computing) than what RLink could provide.


A request: If any of you have used IGraphR in the past to access igraph from Mathematica, please post a response to this thread and let me know which specific functions you were using.

16 Replies

Version 0.1.1 is now available.

Changes:

  • Windows 64 bit binaries are now included
  • New functions, polish and fixes
  • Basic documentation notebook with some examples. Evaluate IGDocumentation[] to open.

Try it and let me know if something doesn't work, especially on Windows!

https://github.com/szhorvat/IGraphM/releases

Hello, I did give it a spin on windows 7 64 and 10.1 kernel. All functions work in your documentation (manually opened) The only error appears when I use IGDocument[] to open the documentation.

FileNameJoin::optx: Unknown option Saveable in FileNameJoin[{E:\WolframApps\igraphmtest\IGraphM-0.1.1\IGraphM-0.1.1\IGraphM\,Documentation,IGDocumentation.nb},Saveable->False]. >>

nice work!

Thank you for letting me know! This is now fixed in version 0.1.2. There are few changes in this version; its main purpose was to fix a bug on Windows where some functions were not working at all.

IGraph/M version 0.1.3 is released now, with expanded coverage for igraph functions and a lot of polish for the already covered ones.

Highlights for this release:

  • Community detection algorithms
  • Automorphism group for vertex coloured graphs; multigraph isomorphism
  • Additional centrality measures with support for weighted graphs

IGraph/M 0.2.0 is released now with many improvements.

Highlights for this release:

  • Significant performance improvements for many functions
  • New and extended functions for shortest path calculations (extended IGDistanceMatrix, IGDistanceCounts, IGDistanceHistogram, IGDiameter, IGFindDiameter)
  • Support for weighted clique calculations (IGWeightedCliques, IGMaximalWeightedCliques, IGLargestWeightedCliques, IGWeightedCliqueNumber)
  • Additional new functions
  • Syntax highlighting for functions
  • Raspberry Pi support
  • Compatibility with Mathematica 10.4 on OS X.
  • Bug fixes

I would appreciate any testing people can do on platforms I didn't have access to (priorities in decreasing order: Linux, Windows, OS X, pre-10.3 Mathematica versions).

IGraph/M 0.2.0 is released now with many improvements. It can be downloaded from https://github.com/szhorvat/IGraphM/releases as usual.

Highlights for this release:

  • Significant performance improvements for many functions
  • New and extended functions for shortest path calculations (extended IGDistanceMatrix, IGDistanceCounts, IGDistanceHistogram, IGDiameter, IGFindDiameter)
  • Support for weighted clique calculations (IGWeightedCliques, IGMaximalWeightedCliques, IGLargestWeightedCliques, IGWeightedCliqueNumber)
  • Additional new functions
  • Syntax highlighting for functions
  • Raspberry Pi support
  • Compatibility with Mathematica 10.4 on OS X.
  • Bug fixes

I would appreciate any testing people can do on platforms I didn't have access to (priorities in decreasing order: Linux, Windows, OS X, pre-10.3 Mathematica versions).

IGraph/M 0.2.1 is now released. This is a bugfix release. It can be downloaded from https://github.com/szhorvat/IGraphM/releases as usual.

Two bugs which could cause wrong results to be returned are fixed. If you use any of the affected functions, please upgrade.

The following changes require special mention:

  • IGFeedbackArcSet could return wrong results for some graphs. This is now fixed.
  • The "RemovedEdges" property returned by IGCommunitiesEdgeBetweenness could be incorrect for some graphs. This is now fixed. Other properties were not affected.
  • The Hierarchical Clustering package is no longer auto-loaded by IGraph/M to avoid shadowing DistanceMatrix, a new builtin added in Mathematica 10.3. Load this package manually (<<HierarchicalClustering`) to work with the "HierarchicalClusters" property of IGClusterData objects.

A number of other small bugs were also fixed.

IGraph/M 0.3.0 is now available.

This release fixes compatibility with Mathematica 11.1.

It also introduces new functions, performance improvements, bug fixes and polish. Upgrading is recommended for all users.

Pre-release 0.3.90, leading up to 0.4, is now available:

Let me know if you find any problems, or have any suggestions.

This release has several utility functions for working with graph properties and weighted graphs.

Posted 1 year ago

Hi Szabolcs, Your package looks really awesome! I just installed the latest on my Windows 10 with MM11.1.1.0 and it runs fine. The documentation is also very nice. What an effort and work! The warnings are all correct and documented (I ran the whole documentation). The only unexpected "red" was:

DendrogramPlot[cl1["HierarchicalClusters"], 
 LeafLabels -> (Rotate[#, Pi/2] &), ImageSize -> 750, 
 AspectRatio -> 1/2]

enter image description here

Can't wait to play with this Package!

Don't worry about the red colouring here. This is only because the builtin HierarchicalClustering package hasn't been updated to make use of SyntaxInformation. These options work correctly. The highlighting can be safely ignored.

Prerelease 0.3.91 is now available. If you tried the previous prerelease, please upgrade.

This release includes bug fixes, documentation improvements, and a few new functions.

Let me know if you find any problems, or have any suggestions.

Prerelease 0.3.92 is now available. If you are using Mathematica 11.2, please do upgrade! The previous prerelease may cause problems with the M11.2 documentation centre.

Download it from GitHub:

This release is still marked as a "prerelease" because not all features I planned are ready. However, at this point, I strongly recommend using it instead of the older 0.3.0.

IGraph/M 0.3.94 is now available! Please upgrade to this version if you are still using 0.3.0.

Notable improvements since the previous prerelease: functions for working with bipartite incidence matrices, converting geometrical meshes to graphs (thank you to Henrik Schumacher!), improvements to community detection, improvements to isomorphism functions, improvements to random walk functionality, and of course bug fixes. A full list of changes since v0.3.0 is in the README.

If you are just mildly curious about the package, you can check out the PDF version of the documentation (and the many examples within) here:

If you happen to be using Mathematica 11.2.0 on Windows, and are annoyed that the graph isomorphism functionality is broken in that version, note that IGraph/M provides a full replacement of (and many extensions to) that functionality area. ;-)

Update: 0.3.95 is out now with performance improvements and a few new functions.

Update: 0.3.96.1 is out now. Please upgrade.

Update: 0.3.97.2 is out now. Please upgrade. You can use the upgrade script on the project's GitHub page. This release introduces more functions for working with weighted graphs.

IGraph/M 0.3.99 is now released, with a simplified installation procedure. Now it only takes a single line of Mathematica code to automatically download and install the package (please click through to the website so I can keep the installation instructions in a central location).

This release brings many features developed specifically for IGraph/M, and not previously available in the core igraph library. It also includes several new features exclusive to IGraph/M (not available in other igraph interfaces). At this point, IGraph/M also provides alternatives for most Combinatorica feature that do not yet have built-in equivalents in Mathematica.

Some highlights:

Efficient minimum graph colouring and chromatic number computation (implemented in almost pure WL code!). Here's a little demo:

We apply a Mycelski construction to a cycle graph twice, then compute a minimum colouring, and finally visualize this colouring.

Nest[IGMycielskian, CycleGraph[4], 2] // 
  Graph[#, GraphStyle -> "BasicBlack", VertexSize -> Large] & //
  IGVertexMap[ColorData[101], VertexStyle -> IGMinimumVertexColoring]

Mathematica graphics

Computing the chromatic number would have been as easy as

IGChromaticNumber[%]
(* 4 *)

Also check that it's triangle free:

IGTriangleFreeQ[%%]
(* True *)

We now have easy and flexible lattice generation:

IGLatticeMesh["CairoPentagonal"]

Mathematica graphics

Improved mesh-graph conversion. Let's compute the face-face adjacency graph (i.e. the dual lattice) while keeping vertex coordinates.

IGMeshCellAdjacencyGraph[%, 2, VertexCoordinates -> Automatic]

Mathematica graphics

Let's take that graph and find a random spanning tree to generate a nice maze.

IGRandomSpanningTree[%, GraphStyle -> "Web", 
 VertexCoordinates -> GraphEmbedding[%]]

Mathematica graphics

Now take the degree sequence of that tree and generate another tree (i.e. connected graph) with the same degree sequence.

IGRealizeDegreeSequence[VertexDegree[%]] // TreeGraphQ
(* True *)

Compute a minimum colouring of a pinwheel tiling.

mesh = IGLatticeMesh["Pinwheel", {3, 3}, MeshCellStyle -> {1 -> White}];
SetProperty[{mesh, {2, All}}, MeshCellStyle -> ColorData[11] /@ IGMinimumVertexColoring@IGMeshCellAdjacencyGraph[mesh, 2]]

Mathematica graphics

Compute the chromatic index (edge chromatic number) of a large graph.

IGChromaticIndex@RandomGraph[{100, 200}] // Timing
(* {0.040686, 10} *)

There are many more examples in the documentation, and many more new functions. Here I chose to show a few visually interesting ones.

As always, all feedback is welcome, and any help with the package is appreciated: testing, editing the documentation, contributing examples, or if you're feeling up to it, adding new functions.

New version released with a critical fix for IGBlissIsomorphicQ for coloured graphs. Please update.

See the release page for a list of changes:

UPDATE: There's a new release that improves compatibility with various Linux distributions, and also has other fixes. Please upgrade! Remember that it's always easy with the auto-upgrade script.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract