gnu/packages/graph.scm

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