gnu/packages/graph.scm

   1 ;;; GNU Guix --- Functional package management for GNU
   2 ;;; Copyright © 2017, 2018, 2019, 2020 Ricardo Wurmus <rekado@elephly.net>
   3 ;;; Copyright © 2018 Joshua Sierles, Nextjournal <joshua@nextjournal.com>
   4 ;;; Copyright © 2018 Tobias Geerinckx-Rice <me@tobias.gr>
   5 ;;; Copyright © 2019 Efraim Flashner <efraim@flashner.co.il>
   6 ;;; Copyright © 2019 Andreas Enge <andreas@enge.fr>
   7 ;;; Copyright © 2020 Alexander Krotov <krotov@iitp.ru>
   8 ;;;
   9 ;;; This file is part of GNU Guix.
  10 ;;;
  11 ;;; GNU Guix is free software; you can redistribute it and/or modify it
  12 ;;; under the terms of the GNU General Public License as published by
  13 ;;; the Free Software Foundation; either version 3 of the License, or (at
  14 ;;; your option) any later version.
  15 ;;;
  16 ;;; GNU Guix is distributed in the hope that it will be useful, but
  17 ;;; WITHOUT ANY WARRANTY; without even the implied warranty of
  18 ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19 ;;; GNU General Public License for more details.
  20 ;;;
  21 ;;; You should have received a copy of the GNU General Public License
  22 ;;; along with GNU Guix.  If not, see <http://www.gnu.org/licenses/>.
  23
  24 (define-module (gnu packages graph)
  25   #:use-module (guix download)
  26   #:use-module (guix git-download)
  27   #:use-module (guix packages)
  28   #:use-module (guix utils)
  29   #:use-module (guix build-system cmake)
  30   #:use-module (guix build-system gnu)
  31   #:use-module (guix build-system python)
  32   #:use-module (guix build-system r)
  33   #:use-module ((guix licenses) #:prefix license:)
  34   #:use-module (gnu packages)
  35   #:use-module (gnu packages gcc)
  36   #:use-module (gnu packages autotools)
  37   #:use-module (gnu packages bioconductor)
  38   #:use-module (gnu packages bioinformatics)
  39   #:use-module (gnu packages check)
  40   #:use-module (gnu packages compression)
  41   #:use-module (gnu packages cran)
  42   #:use-module (gnu packages gd)
  43   #:use-module (gnu packages graphviz)
  44   #:use-module (gnu packages maths)
  45   #:use-module (gnu packages multiprecision)
  46   #:use-module (gnu packages pkg-config)
  47   #:use-module (gnu packages python)
  48   #:use-module (gnu packages python-science)
  49   #:use-module (gnu packages python-web)
  50   #:use-module (gnu packages python-xyz)
  51   #:use-module (gnu packages statistics)
  52   #:use-module (gnu packages swig)
  53   #:use-module (gnu packages time)
  54   #:use-module (gnu packages xml))
  55
  56 (define-public igraph
  57   (package
  58     (name "igraph")
  59     (version "0.8.0")
  60     (source
  61      (origin
  62        (method url-fetch)
  63        (uri (string-append "https://github.com/igraph/igraph/releases/"
  64                            "download/" version "/igraph-" version ".tar.gz"))
  65        (sha256
  66         (base32
  67          "0jcnfvahrlj08y46vnax5y5bb294v4b9n00qsy7pbx0cc0sp6qvj"))))
  68     (build-system gnu-build-system)
  69     (arguments
  70      `(#:configure-flags
  71        (list "--with-external-glpk"
  72              "--with-external-blas"
  73              "--with-external-lapack")))
  74     (inputs
  75      `(("gmp" ,gmp)
  76        ("glpk" ,glpk)
  77        ("libxml2" ,libxml2)
  78        ("lapack" ,lapack)
  79        ("openblas" ,openblas)
  80        ("zlib" ,zlib)))
  81     (home-page "http://igraph.org")
  82     (synopsis "Network analysis and visualization")
  83     (description
  84      "This package provides a library for the analysis of networks and graphs.
  85 It can handle large graphs very well and provides functions for generating
  86 random and regular graphs, graph visualization, centrality methods and much
  87 more.")
  88     (license license:gpl2+)))
  89
  90 (define-public python-igraph
  91   (package (inherit igraph)
  92     (name "python-igraph")
  93     (version "0.7.1.post6")
  94     (source
  95      (origin
  96        (method url-fetch)
  97        (uri (pypi-uri "python-igraph" version))
  98        (sha256
  99         (base32
 100          "0xp61zz710qlzhmzbfr65d5flvsi8zf2xy78s6rsszh719wl5sm5"))))
 101     (build-system python-build-system)
 102     (arguments '())
 103     (inputs
 104      `(("igraph" ,igraph)))
 105     (native-inputs
 106      `(("pkg-config" ,pkg-config)))
 107     (home-page "http://pypi.python.org/pypi/python-igraph")
 108     (synopsis "Python bindings for the igraph network analysis library")))
 109
 110 (define-public r-igraph
 111   (package
 112     (name "r-igraph")
 113     (version "1.2.4.2")
 114     (source
 115      (origin
 116        (method url-fetch)
 117        (uri (cran-uri "igraph" version))
 118        (sha256
 119         (base32
 120          "0scrbqb26pam8akblb4g9rkz888s0xffw3gcly78s4ijj67barxd"))))
 121     (build-system r-build-system)
 122     (native-inputs
 123      `(("gfortran" ,gfortran)))
 124     (inputs
 125      `(("gmp" ,gmp)
 126        ("glpk" ,glpk)
 127        ("libxml2" ,libxml2)
 128        ("zlib" ,zlib)))
 129     (propagated-inputs
 130      `(("r-magrittr" ,r-magrittr)
 131        ("r-matrix" ,r-matrix)
 132        ("r-pkgconfig" ,r-pkgconfig)))
 133     (home-page "http://igraph.org")
 134     (synopsis "Network analysis and visualization")
 135     (description
 136      "This package provides routines for simple graphs and network analysis.
 137 It can handle large graphs very well and provides functions for generating
 138 random and regular graphs, graph visualization, centrality methods and much
 139 more.")
 140     (license license:gpl2+)))
 141
 142 (define-public r-diffusionmap
 143   (package
 144     (name "r-diffusionmap")
 145     (version "1.2.0")
 146     (source
 147      (origin
 148        (method url-fetch)
 149        (uri (cran-uri "diffusionMap" version))
 150        (sha256
 151         (base32
 152          "1rvk7069brlm1s9kqj4c31mwwr3mw4hmhay95cjjjfmw5xclff2j"))))
 153     (properties `((upstream-name . "diffusionMap")))
 154     (build-system r-build-system)
 155     (propagated-inputs
 156      `(("r-igraph" ,r-igraph)
 157        ("r-matrix" ,r-matrix)
 158        ("r-scatterplot3d" ,r-scatterplot3d)))
 159     (home-page "https://www.r-project.org")
 160     (synopsis "Diffusion map")
 161     (description "This package implements the diffusion map method of data
 162 parametrization, including creation and visualization of diffusion maps,
 163 clustering with diffusion K-means and regression using the adaptive regression
 164 model.")
 165     (license license:gpl2)))
 166
 167 (define-public r-rgraphviz
 168   (package
 169     (name "r-rgraphviz")
 170     (version "2.30.0")
 171     (source
 172      (origin
 173        (method url-fetch)
 174        (uri (bioconductor-uri "Rgraphviz" version))
 175        (sha256
 176         (base32
 177          "00lrkbgbb4payybckcmazsv8skysgdlglyqbl7yjb37vv3gnfc6c"))))
 178     (properties `((upstream-name . "Rgraphviz")))
 179     (build-system r-build-system)
 180     ;; FIXME: Rgraphviz bundles the sources of an older variant of
 181     ;; graphviz.  It does not build with the latest version of graphviz, so
 182     ;; we do not add graphviz to the inputs.
 183     (inputs `(("zlib" ,zlib)))
 184     (propagated-inputs
 185      `(("r-graph" ,r-graph)))
 186     (native-inputs
 187      `(("pkg-config" ,pkg-config)))
 188     (home-page "https://bioconductor.org/packages/Rgraphviz")
 189     (synopsis "Plotting capabilities for R graph objects")
 190     (description
 191      "This package interfaces R with the graphviz library for plotting R graph
 192 objects from the @code{graph} package.")
 193     (license license:epl1.0)))
 194
 195 (define-public r-rbiofabric
 196   (let ((commit "666c2ae8b0a537c006592d067fac6285f71890ac")
 197         (revision "1"))
 198     (package
 199       (name "r-rbiofabric")
 200       (version (string-append "0.3-" revision "." (string-take commit 7)))
 201       (source (origin
 202                 (method git-fetch)
 203                 (uri (git-reference
 204                       (url "https://github.com/wjrl/RBioFabric.git")
 205                       (commit commit)))
 206                 (file-name (string-append name "-" version "-checkout"))
 207                 (sha256
 208                  (base32
 209                   "1yahqrcrqpbcywv73y9rlmyz8apdnp08afialibrr93ch0p06f8z"))))
 210       (build-system r-build-system)
 211       (propagated-inputs
 212        `(("r-igraph" ,r-igraph)))
 213       (home-page "http://www.biofabric.org/")
 214       (synopsis "BioFabric network visualization")
 215       (description "This package provides an implementation of the function
 216 @code{bioFabric} for creating scalable network digrams where nodes are
 217 represented by horizontal lines, and edges are represented by vertical
 218 lines.")
 219       (license license:expat))))
 220
 221 (define-public python-plotly
 222   (package
 223     (name "python-plotly")
 224     (version "2.4.1")
 225     (source
 226       (origin
 227         (method url-fetch)
 228         (uri (pypi-uri "plotly" version))
 229         (sha256
 230          (base32
 231           "0s9gk2fl53x8wwncs3fwii1vzfngr0sskv15v3mpshqmrqfrk27m"))))
 232     (build-system python-build-system)
 233     (arguments
 234      '(#:tests? #f)) ; The tests are not distributed in the release
 235     (propagated-inputs
 236      `(("python-decorator" ,python-decorator)
 237        ("python-nbformat" ,python-nbformat)
 238        ("python-pandas" ,python-pandas)
 239        ("python-pytz" ,python-pytz)
 240        ("python-requests" ,python-requests)
 241        ("python-six" ,python-six)))
 242     (home-page "https://plot.ly/python/")
 243     (synopsis "Interactive plotting library for Python")
 244     (description "Plotly's Python graphing library makes interactive,
 245 publication-quality graphs online.  Examples of how to make line plots, scatter
 246 plots, area charts, bar charts, error bars, box plots, histograms, heatmaps,
 247 subplots, multiple-axes, polar charts, and bubble charts. ")
 248     (license license:expat)))
 249
 250 (define-public python2-plotly
 251   (package-with-python2 python-plotly))
 252
 253 (define-public python-louvain
 254   (package
 255     (name "python-louvain")
 256     (version "0.6.1")
 257     ;; The tarball on Pypi does not include the tests.
 258     (source (origin
 259               (method git-fetch)
 260               (uri (git-reference
 261                     (url "https://github.com/vtraag/louvain-igraph.git")
 262                     (commit version)))
 263               (file-name (git-file-name name version))
 264               (sha256
 265                (base32
 266                 "0w31537sifkf65sck1iaip5i6d8g64pa3wdwad83d6p9jwkck57k"))))
 267     (build-system python-build-system)
 268     (propagated-inputs
 269      `(("python-ddt" ,python-ddt)
 270        ("python-igraph" ,python-igraph)))
 271     (inputs
 272      `(("igraph" ,igraph)))
 273     (native-inputs
 274      `(("pkg-config" ,pkg-config)
 275        ("python-pytest" ,python-pytest)))
 276     (home-page "https://github.com/vtraag/louvain-igraph")
 277     (synopsis "Algorithm for methods of community detection in large networks")
 278     (description
 279      "This package provides an implementation of the Louvain algorithm for use
 280 with igraph.  Louvain is a general algorithm for methods of community
 281 detection in large networks.
 282
 283 This package has been superseded by the @code{leidenalg} package and should
 284 not be used for new projects.")
 285     (license license:gpl3+)))
 286
 287 (define-public faiss
 288   (package
 289     (name "faiss")
 290     (version "1.5.0")
 291     (source (origin
 292               (method git-fetch)
 293               (uri (git-reference
 294                     (url "https://github.com/facebookresearch/faiss.git")
 295                     (commit (string-append "v" version))))
 296               (file-name (git-file-name name version))
 297               (sha256
 298                (base32
 299                 "0pk15jfa775cy2pqmzq62nhd6zfjxmpvz5h731197c28aq3zw39w"))
 300               (modules '((guix build utils)))
 301               (snippet
 302                '(begin
 303                   (substitute* "utils.cpp"
 304                     (("#include <immintrin.h>")
 305                      "#ifdef __SSE__\n#include <immintrin.h>\n#endif"))
 306                   #t))))
 307     (build-system cmake-build-system)
 308     (arguments
 309      `(#:configure-flags
 310        (list "-DBUILD_WITH_GPU=OFF"  ; thanks, but no thanks, CUDA.
 311              "-DBUILD_TUTORIAL=OFF") ; we don't need those
 312        #:phases
 313        (modify-phases %standard-phases
 314          (add-after 'unpack 'prepare-build
 315            (lambda _
 316              (let ((features (list ,@(let ((system (or (%current-target-system)
 317                                                        (%current-system))))
 318                                        (cond
 319                                         ((string-prefix? "x86_64" system)
 320                                          '("-mavx" "-msse2" "-mpopcnt"))
 321                                         ((string-prefix? "i686" system)
 322                                          '("-msse2" "-mpopcnt"))
 323                                         (else
 324                                          '()))))))
 325                (substitute* "CMakeLists.txt"
 326                  (("-m64") "")
 327                  (("-mpopcnt") "") ; only some architectures
 328                  (("-msse4")
 329                   (string-append
 330                    (string-join features)
 331                    " -I" (getcwd)))
 332                  ;; Build also the shared library
 333                  (("ARCHIVE DESTINATION lib")
 334                   "LIBRARY DESTINATION lib")
 335                  (("add_library.*" m)
 336                   "\
 337 add_library(objlib OBJECT ${faiss_cpu_headers} ${faiss_cpu_cpp})
 338 set_property(TARGET objlib PROPERTY POSITION_INDEPENDENT_CODE 1)
 339 add_library(${faiss_lib}_static STATIC $<TARGET_OBJECTS:objlib>)
 340 add_library(${faiss_lib} SHARED $<TARGET_OBJECTS:objlib>)
 341 install(TARGETS ${faiss_lib}_static ARCHIVE DESTINATION lib)
 342 \n")))
 343
 344              ;; See https://github.com/facebookresearch/faiss/issues/520
 345              (substitute* "IndexScalarQuantizer.cpp"
 346                (("#define USE_AVX") ""))
 347
 348              ;; Make header files available for compiling tests.
 349              (mkdir-p "faiss")
 350              (for-each (lambda (file)
 351                          (mkdir-p (string-append "faiss/" (dirname file)))
 352                          (copy-file file (string-append "faiss/" file)))
 353                        (find-files "." "\\.h$"))
 354              #t))
 355          (replace 'check
 356            (lambda _
 357              (invoke "make" "-C" "tests"
 358                      (format #f "-j~a" (parallel-job-count)))))
 359          (add-after 'install 'remove-tests
 360            (lambda* (#:key outputs #:allow-other-keys)
 361              (delete-file-recursively
 362               (string-append (assoc-ref outputs "out")
 363                              "/test"))
 364              #t)))))
 365     (inputs
 366      `(("openblas" ,openblas)))
 367     (native-inputs
 368      `(("googletest" ,googletest)))
 369     (home-page "https://github.com/facebookresearch/faiss")
 370     (synopsis "Efficient similarity search and clustering of dense vectors")
 371     (description "Faiss is a library for efficient similarity search and
 372 clustering of dense vectors.  It contains algorithms that search in sets of
 373 vectors of any size, up to ones that possibly do not fit in RAM.  It also
 374 contains supporting code for evaluation and parameter tuning.")
 375     (license license:bsd-3)))
 376
 377 (define-public python-faiss
 378   (package (inherit faiss)
 379     (name "python-faiss")
 380     (build-system python-build-system)
 381     (arguments
 382      `(#:phases
 383        (modify-phases %standard-phases
 384          (add-after 'unpack 'chdir
 385            (lambda _ (chdir "python") #t))
 386          (add-after 'chdir 'build-swig
 387            (lambda* (#:key inputs #:allow-other-keys)
 388              (with-output-to-file "../makefile.inc"
 389                (lambda ()
 390                  (let ((python-version ,(version-major+minor (package-version python))))
 391                    (format #t "\
 392 PYTHONCFLAGS =-I~a/include/python~am/ -I~a/lib/python~a/site-packages/numpy/core/include
 393 LIBS = -lpython~am -lfaiss
 394 SHAREDFLAGS = -shared -fopenmp
 395 CXXFLAGS = -fpermissive -fopenmp -fPIC
 396 CPUFLAGS = ~{~a ~}~%"
 397                            (assoc-ref inputs "python*") python-version
 398                            (assoc-ref inputs "python-numpy") python-version
 399                            python-version
 400                            (list ,@(let ((system (or (%current-target-system)
 401                                                      (%current-system))))
 402                                      (cond
 403                                        ((string-prefix? "x86_64" system)
 404                                         '("-mavx" "-msse2" "-mpopcnt"))
 405                                        ((string-prefix? "i686" system)
 406                                         '("-msse2" "-mpopcnt"))
 407                                        (else
 408                                          '()))))))))
 409              (substitute* "Makefile"
 410                (("../libfaiss.a") ""))
 411              (invoke "make" "cpu"))))))
 412     (inputs
 413      `(("faiss" ,faiss)
 414        ("openblas" ,openblas)
 415        ("python*" ,python)
 416        ("swig" ,swig)))
 417     (propagated-inputs
 418      `(("python-matplotlib" ,python-matplotlib)
 419        ("python-numpy" ,python-numpy)))
 420     (description "Faiss is a library for efficient similarity search and
 421 clustering of dense vectors.  This package provides Python bindings to the
 422 Faiss library.")))
 423
 424 (define-public python-leidenalg
 425   (package
 426     (name "python-leidenalg")
 427     (version "0.7.0")
 428     (source
 429      (origin
 430        (method url-fetch)
 431        (uri (pypi-uri "leidenalg" version))
 432        (sha256
 433         (base32
 434          "15fwld9hdw357rd026mzcwpah5liy4f33vc9x9kwy37g71b2rjf1"))))
 435     (build-system python-build-system)
 436     (arguments '(#:tests? #f)) ; tests are not included
 437     (native-inputs
 438      `(("pkg-config" ,pkg-config)))
 439     (inputs
 440      `(("igraph" ,igraph)))
 441     (propagated-inputs
 442      `(("python-igraph" ,python-igraph)))
 443     (home-page "https://github.com/vtraag/leidenalg")
 444     (synopsis "Community detection in large networks")
 445     (description
 446      "Leiden is a general algorithm for methods of community detection in
 447 large networks.  This package implements the Leiden algorithm in C++ and
 448 exposes it to Python.  Besides the relative flexibility of the implementation,
 449 it also scales well, and can be run on graphs of millions of nodes (as long as
 450 they can fit in memory).  The core function is @code{find_partition} which
 451 finds the optimal partition using the Leiden algorithm, which is an extension
 452 of the Louvain algorithm, for a number of different methods.")
 453     (license license:gpl3+)))
 454
 455 (define-public edge-addition-planarity-suite
 456   (package
 457     (name "edge-addition-planarity-suite")
 458     (version "3.0.0.5")
 459     (source
 460      (origin
 461        (method git-fetch)
 462        (uri (git-reference
 463               (url (string-append "https://github.com/graph-algorithms/"
 464                                   name))
 465               (commit (string-append "Version_" version))))
 466        (file-name (git-file-name name version))
 467        (sha256
 468         (base32
 469          "01cm7ay1njkfsdnmnvh5zwc7wg7x189hq1vbfhh9p3ihrbnmqzh8"))))
 470     (build-system gnu-build-system)
 471     (native-inputs
 472      `(("autoconf" ,autoconf)
 473        ("automake" ,automake)
 474        ("libtool" ,libtool)))
 475     (synopsis "Embedding of planar graphs")
 476     (description "The package provides a reference implementation of the
 477 linear time edge addition algorithm for embedding planar graphs and
 478 isolating planarity obstructions.")
 479     (license license:bsd-3)
 480     (home-page
 481       "https://github.com/graph-algorithms/edge-addition-planarity-suite")))
 482
 483 (define-public rw
 484   (package
 485     (name "rw")
 486     ;; There is a version 0.8, but the tarball is broken with symlinks
 487     ;; to /usr/share.
 488     (version "0.7")
 489     (source (origin
 490               (method url-fetch)
 491               (uri (string-append "mirror://sourceforge/rankwidth/"
 492                                   "rw-" version ".tar.gz"))
 493        (sha256
 494         (base32
 495          "1rv2v42x2506x7f10349m1wpmmfxrv9l032bkminni2gbip9cjg0"))))
 496     (build-system gnu-build-system)
 497     (native-inputs
 498      `(("pkg-config" ,pkg-config)))
 499     (inputs
 500      `(("igraph" ,igraph)))
 501     (home-page "https://sourceforge.net/projects/rankwidth/")
 502     (synopsis "Rank-width and rank-decomposition of graphs")
 503     (description "rw computes rank-width and rank-decompositions
 504 of graphs.")
 505     (license license:gpl2+)))
 506
 507 (define-public mscgen
 508   (package
 509     (name "mscgen")
 510     (version "0.20")
 511     (source
 512      (origin
 513        (method url-fetch)
 514        (uri (string-append "http://www.mcternan.me.uk/mscgen/software/mscgen-src-"
 515                            version ".tar.gz"))
 516        (sha256
 517         (base32
 518          "08yw3maxhn5fl1lff81gmcrpa4j9aas4mmby1g9w5qcr0np82d1w"))))
 519     (build-system gnu-build-system)
 520     (inputs
 521      `(("gd" ,gd)))
 522     (home-page "http://www.mcternan.me.uk/mscgen/")
 523     (synopsis "Message Sequence Chart Generator")
 524     (description "Mscgen is a small program that parses Message Sequence Chart
 525 descriptions and produces PNG, SVG, EPS or server side image maps (ismaps) as
 526 the output.  Message Sequence Charts (MSCs) are a way of representing entities
 527 and interactions over some time period and are often used in combination with
 528 SDL.  MSCs are popular in Telecoms to specify how protocols operate although
 529 MSCs need not be complicated to create or use.  Mscgen aims to provide a simple
 530 text language that is clear to create, edit and understand, which can also be
 531 transformed into common image formats for display or printing.")
 532     (license license:gpl2+)))