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