cl-grph - GitLite

KO | EN

gitlite — search

#javascript #hacktoberfest #typescript #go #golang #machine-learning #rust #linux #macos #awesome #kubernetes #pytorch #security #ios

cl-grph

(★ 73)

In-Memory Immutable Graph Structure with Datalog Query Language in Common Lisp

File Explorer

Download Latest Version (.zip)

- grph-io.md
- grph.md
- xgrph.md
- datalog-queries.lisp
- export.lisp
- perf.lisp
- sample.grph
- simple.lisp
- spatial.lisp
- hyper.png
- lines.png
- config.lisp
- docs.lisp
- edge-set.lisp
- grph-queries.lisp
- grph-walk.lisp
- grph.lisp
- init.lisp
- macros.lisp
- packages.lisp
- qry-match.lisp
- qry-rules.lisp
- qry-runtime-2.lisp
- qry-runtime-par.lisp
- qry-runtime.lisp
- qry-utils.lisp
- qry.lisp
- utils.lisp
- xgrph-cycle.lisp
- xgrph-io.lisp
- xgrph-isect.lisp
- xgrph-triangulate.lisp
- xgrph.lisp
- grph-2.lisp
- grph-walk-cpnd.lisp
- grph-walk.lisp
- grph.lisp
- qry-2.lisp
- qry-3.lisp
- qry-runtime.lisp
- qry.lisp
- run.lisp
- utils.lisp
- xgrph.lisp
.dockerignore
.editorconfig
.gitignore
compile.sh
Dockerfile
grph.asd
LICENSE
README.md
run-tests.sh

# Installation Guide

1. Get the code

git clone https://github.com/inconvergent/cl-grph

Downloads the entire project code from GitHub to your computer.

cd cl-grph

Moves into the project folder you just downloaded.

2. Docker

Easy Recommended

Prerequisites

Git Needed to download the project code from GitHub.
Docker Desktop Needed to build and run containers. Install it and keep it running in the background.

docker build -t cl-grph .

Builds a runnable image based on the Dockerfile.

docker run -p 8080:80 cl-grph

Runs the built image as an actual container.

✅ Run docker compose ps to check the containers are Up. If the README mentions a port, open http://localhost:PORT in your browser.

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# GRPH

## About

`grph` is an in-memory immutable graph structure with
[Datalog](https://en.wikipedia.org/wiki/Datalog) query language. The data
structure and interfaces are generic, but it is primarily intended to
be used in my generative art experiments.

The main features is that the graph data structure builds on
[fset](https://fset.common-lisp.dev/) in order to be immutable. Furthermore, in
`grph` the edge properties (`props`) is a native part of the graph itself.  The
graph topology is separated from the spatial data, and the spatial data is also
immutable. Having a separation between the graph and the spatial information
makes it easier to work with higher dimensional data.

There are many benefits to having immutable data structures; perhaps the most
interesting being that it makes it trivial to to create transactions.

I have written about this library at

- https://inconvergent.net/2023/datalog-to-svg/
 - https://inconvergent.net/2022/graph-data-structure-with-datalog-ql/
 - https://inconvergent.net/2023/lets-write-a-dsl/
 - (more to come)

![Lines](https://raw.githubusercontent.com/inconvergent/cl-grph/master/img/lines.png)

## Components

The `grph` system has three packages:

1. `grph` contains the graph structure, as well as the query interface (Datalog
   compiler).
2. `xgrph` expands `grph` with spatial information.
3. `grph/io` for exporting and importing graph data.

See the [docs folder](docs) for auomatically generated docs (incomplete).

## Examples

The subset of Datalog currently supported in `grph` is the most basic pattern
matching using `and`, `or`, `not`, `or-join` and `not-join`. Rules/fixed-point
iteration is supported in `grph:rqry`. See examples.

Here is a small example that demonstrates a few supported Datalog queries for a
small graph:

Further examples and explanations are included in the [examples
folder](examples).

```lisp
(in-package :grph)

(let ((g (ingest-edges (grph)
         '((0 :A 1) (0 :C 1) (1 :A 0) (1 :A 2) (1 :A 3) (1 :C 0)
           (2 :A 1) (3 :A 1) (3 :B 4) (3 :B 5) (3 :C 5) (3 :C 7)
           (4 :B 3) (4 :B 5) (4 :E 5) (5 :B 3) (5 :B 4) (5 :C 3)
           (7 :C 3)))))

(veq:vpr (qry g :select (?x ?y)
                :where (and (?x :a ?y) (?x :c ?y))))
;> '((1 0) (0 1))

(veq:vpr (qry g :select (?x ?y)
                :where (and (?x :c ?y)
                            (not (or (?x :a 1) (?x :a 3))))))
;> '((7 3) (5 3))

(let ((?x 5))
  (veq:vpr (qry g :in ?x ; bind ?x to the "outside" value: 5
                  :select ?y
                  :where (or (?x :b ?y)
                             (?x :a ?y)))))
;> '((3) (4))

(veq:vpr (qry g :select ?r
                :where (or-join ?r
                         (and (?r :a ?a) (?a :b 5))
                         (?r :c 0)
                         (?r :e 5)))))
;> '((4) (1)))
```

![Hyper](https://raw.githubusercontent.com/inconvergent/cl-grph/master/img/hyper.png)

## Dependencies

- [cl-veq](https://github.com/inconvergent/cl-veq). Must be installed from
    the Github repo (not quicklisp).
  - [fset](https://fset.common-lisp.dev/). Automatically installed via
    quicklisp.
  - [lparallel](https://lparallel.org/). Installed via quicklisp.
  - [auxin](https://github.com/inconvergent/auxin). Some of the examples depend
    on `auxin`. But the `grph` system does not require `auxin` directly.

## Tests

Tests can be executed with `(asdf:test-system :grph)`. Or by executing
`./run-tests.sh`.