arangodag

package module
v0.6.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 22, 2022 License: BSD-3-Clause Imports: 7 Imported by: 2

README

arangoDag

Test Coverage Status PkgGoDev Go Report Card

Implementation of directed acyclic graphs (DAGs) on top of ArangoDB.

Quickstart

Compiling and running:

package main

import (
	"fmt"
	"github.com/arangodb/go-driver"
	"github.com/arangodb/go-driver/http"
	"github.com/heimdalr/arangodag"
	"strconv"
	"time"
)

type myDocument struct {
	Key  string `json:"_key"`
	Text string `json:"text"`
}

func main() {

	// new ArangoDB-connection
	conn, _ := http.NewConnection(http.ConnectionConfig{Endpoints: []string{"http://localhost:8529"}})

	// new ArangoDB client
	client, _ := driver.NewClient(driver.ClientConfig{Connection: conn})

	// connect to DAG (create a new one if necessary)
	uid := strconv.FormatInt(time.Now().UnixNano(), 10)
	d, _ := arangodag.NewDAG("test-"+uid, uid, client)

	// add some vertices (with explicit keys)
	_, _ = d.AddVertex(myDocument{"0", "blah"})
	_, _ = d.AddVertex(myDocument{"1", "foo"})
	_, _ = d.AddVertex(myDocument{"2", "bar"})

	// add some edges
	_, _ = d.AddEdge("0", "1")
	_, _ = d.AddEdge("0", "2")

	// get size
	order, _ := d.GetOrder()
	size, _ := d.GetSize()
	dot, _ := d.String()

	// print some DAG stats and the dot graph
	fmt.Printf("order: %d\nsize: %d\n%s", order, size, dot)

will result in something like:

order: 3
size: 2
digraph  {
	
	n1[label="0"];
	n2[label="1"];
	n3[label="2"];
	n1->n2;
	n1->n3;
	
}

(see: example_basic_test.go)

Documentation

Overview

Package arangodag implements directed acyclic graphs (DAGs) on top of ArangoDB.

Example 
package main

import (
	"fmt"
	"github.com/arangodb/go-driver"
	"github.com/arangodb/go-driver/http"
	"github.com/heimdalr/arangodag"
	"golang.org/x/net/context"
	"strconv"
	"strings"
	"time"
)

func main() {
	ctx := context.Background()

	// new ArangoDB-connection
	conn, _ := http.NewConnection(http.ConnectionConfig{Endpoints: []string{"http://localhost:8529"}})

	// new ArangoDB client
	client, _ := driver.NewClient(driver.ClientConfig{Connection: conn})

	// connect to DAG (create a new one if necessary)
	uid := strconv.FormatInt(time.Now().UnixNano(), 10)
	d, _ := arangodag.CreateDAG(ctx, "test-"+uid, uid, client)

	// add some vertices (with explicit keys)
	_, _ = d.AddNamedVertex(ctx, "0", "blah")
	_, _ = d.AddNamedVertex(ctx, "1", "foo")
	_, _ = d.AddNamedVertex(ctx, "2", "bar")

	// add some edges
	_, _ = d.AddEdge(ctx, "0", "1", nil, false)
	_, _ = d.AddEdge(ctx, "0", "2", nil, false)

	// get size
	order, _ := d.GetOrder(ctx)
	size, _ := d.GetSize(ctx)
	dot, _ := d.String(ctx)

	// print some DAG stats and the dot graph
	fmt.Printf("order: %d\nsize: %d\n%s", order, size, trimForOutput(dot))

}

// trimForOutput is only for test purposes to ensure matching results
func trimForOutput(s string) string {
	return strings.Replace(strings.Replace(s, "\t", " ", -1), "\n \n", "\n", -1)
}

Output:

order: 3
size: 2
digraph  {
 n1[label="0"];
 n2[label="1"];
 n3[label="2"];
 n1->n2;
 n1->n3;
}

Index

Examples

Constants

View Source 
const (
	DAGErrLoop     = 1000
	DAGErrNotFound = 1001
)

Variables

View Source 
var Cause = func(err error) error { return err }

Functions

func IsDAGError added in v0.4.0 

func IsDAGError(err error) bool

IsDAGError returns true when the given error is an DAGError.

func IsDAGErrorWithCode added in v0.4.0 

func IsDAGErrorWithCode(err error, status int) bool

func IsDAGErrorWithNumber added in v0.4.0 

func IsDAGErrorWithNumber(err error, number int) bool

Types

type DAG 

type DAG struct {
	DB       driver.Database
	Vertices driver.Collection
	Edges    driver.Collection
	// contains filtered or unexported fields
}

DAG implements the data structure of the DAG.

func ConnectDAG added in v0.6.1 

func ConnectDAG(ctx context.Context, dbName, collectionName string, client driver.Client) (*DAG, error)

ConnectDAG returns a DAG instance from the given DB and collection name. ConnectDAG returns an error if the DB does not exist or does not contain collections that provide for a valid DAG.

func CreateDAG added in v0.6.1 

func CreateDAG(ctx context.Context, dbName, collectionName string, client driver.Client) (*DAG, error)

CreateDAG creates and returns a new DAG. CreateDAG returns an error, if the given DB already exists.

func (*DAG) AddEdge 

func (d *DAG) AddEdge(ctx context.Context, srcKey, dstKey string, data interface{}, createVertices bool) (meta driver.DocumentMeta, err error)

AddEdge adds an edge from the vertex with the key srcKey (src) to the vertex with the key dstKey (dst) and returns the key of the new edge.

If createVertices is true, AddEdge creates missing vertices. Otherwise, it raises an error.

AddEdge prevents duplicate edges and loops (and thereby maintains a valid DAG).

func (*DAG) AddNamedVertex added in v0.3.0 

func (d *DAG) AddNamedVertex(ctx context.Context, key string, data interface{}) (meta driver.DocumentMeta, err error)

AddNamedVertex adds a vertex with the given key and data to the DAG.

Use the type json.RawMessage for data (i.e. []byte) to add "raw" JSON strings / byte slices.

AddVertex prevents duplicate keys.

func (*DAG) AddVertex 

func (d *DAG) AddVertex(ctx context.Context, data interface{}) (meta driver.DocumentMeta, err error)

AddVertex adds a new vertex to the DAG with the given data.

If the given data implements the KeyInterface, then the key for the new vertex will be taken from the data. If not, a key will be generated.

Note, only exported fields in data (i.e. capital first letter), will be stored.

AddVertex prevents duplicate keys.

func (*DAG) DelEdge added in v0.1.7 

func (d *DAG) DelEdge(ctx context.Context, srcKey, dstKey string) (meta driver.DocumentMeta, err error)

DelEdge removes the edge from the vertex with the key srcKey (src) to the vertex with the key dstKey (dst).

DelEdge returns an error, if such an edge doesn't exist.

func (*DAG) DelVertex added in v0.1.4 

func (d *DAG) DelVertex(ctx context.Context, srcKey string) (count int64, err error)

DelVertex removes the vertex with the key srcKey (src). DelVertex also removes any inbound and outbound edges. In case of success, DelVertex returns the Number of edges that were removed.

If src doesn't exist, DelVertex returns an error.

func (*DAG) DotGraph added in v0.1.7 

func (d *DAG) DotGraph(ctx context.Context, g *dot.Graph) (nodeMapping map[driver.DocumentID]dot.Node, err error)

DotGraph returns a (dot-) graph of the DAG.

func (*DAG) EdgeExists 

func (d *DAG) EdgeExists(ctx context.Context, srcKey, dstKey string) (bool, error)

EdgeExists returns true, if an edge between the vertex with the key srcKey (src) and the vertex with the key dstKey (dst) exists. If src, dst or an edge between the two doesn't exist, GetEdge returns an error.

func (*DAG) GetAllVertices added in v0.3.0 

func (d *DAG) GetAllVertices(ctx context.Context) (driver.Cursor, error)

GetAllVertices executes the query to retrieve all vertices of the DAG. GetAllVertices returns a cursor that may be used retrieve the vertices one-by-one.

It is up to the caller to close the cursor, if no longer needed.

func (*DAG) GetAncestors 

func (d *DAG) GetAncestors(ctx context.Context, srcKey string, dfs bool) (driver.Cursor, error)

GetAncestors executes the query to retrieve all ancestors of the vertex with the key srcKey (src). GetAncestors returns a cursor that may be used retrieve the vertices one-by-one.

By default, GetAncestors returns vertices in BFS order, if dfs is set to true, it will be in DFS order.

If src doesn't exist, the cursor doesn't return any vertex (i.e. no error is returned).

It is up to the caller to close the cursor, if no longer needed.

func (*DAG) GetChildCount added in v0.1.5 

func (d *DAG) GetChildCount(ctx context.Context, srcKey string) (count int64, err error)

GetChildCount returns the Number child-vertices of the vertex with the key srcKey.

If src doesn't exist, GetChildCount returns 0.

func (*DAG) GetChildren added in v0.1.2 

func (d *DAG) GetChildren(ctx context.Context, srcKey string) (driver.Cursor, error)

GetChildren executes the query to retrieve all children of the vertex with the key srcKey. GetChildren returns a cursor that may be used retrieve the vertices one-by-one.

If src doesn't exist, the cursor doesn't return any vertex (i.e. no error is returned).

It is up to the caller to close the cursor, if no longer needed.

Example 
ctx := context.Background()

// new arangoDB connection
conn, _ := http.NewConnection(http.ConnectionConfig{Endpoints: []string{"http://localhost:8529"}})

// new arangoDB client
client, _ := driver.NewClient(driver.ClientConfig{Connection: conn})

// connect to DAG (create a new one if necessary)
uid := strconv.FormatInt(time.Now().UnixNano(), 10)
d, _ := arangodag.CreateDAG(ctx, "test-"+uid, uid, client)

// add some vertices and edges
_, _ = d.AddNamedVertex(ctx, "0", nil)
for i := 1; i < 10; i++ {
	dstKey := strconv.Itoa(i)
	_, _ = d.AddNamedVertex(ctx, dstKey, nil)
	_, _ = d.AddEdge(ctx, "0", dstKey, nil, false)
}

// get order and size
order, _ := d.GetOrder(ctx)
size, _ := d.GetSize(ctx)
fmt.Printf("order: %d\nsize: %d\n", order, size)

fmt.Printf("children:\n")
cursor, _ := d.GetChildren(ctx, "0")
defer func() {
	_ = cursor.Close()
}()
for {
	meta, errRead := cursor.ReadDocument(ctx, &struct{}{})
	if driver.IsNoMoreDocuments(errRead) {
		break
	}
	if errRead != nil {
		panic(errRead)
	}
	fmt.Printf("- %s\n", meta.Key)
}

Output:

order: 10
size: 9
children:
- 8
- 7
- 6
- 3
- 5
- 9
- 1
- 2
- 4

func (*DAG) GetDescendants 

func (d *DAG) GetDescendants(ctx context.Context, srcKey string, dfs bool) (driver.Cursor, error)

GetDescendants executes the query to retrieve all descendants of the vertex with the key srcKey. GetDescendants returns a cursor that may be used retrieve the vertices one-by-one.

By default, GetDescendants returns vertices in BFS order, if dfs is set to true, it will be in DFS order.

If src doesn't exist, the cursor doesn't return any vertex (i.e. no error is returned).

It is up to the caller to close the cursor, if no longer needed.

func (*DAG) GetEdge added in v0.3.0 

func (d *DAG) GetEdge(ctx context.Context, srcKey, dstKey string, data interface{}) (driver.DocumentMeta, error)

GetEdge returns the edge between the vertex with the key srcKey (src) and the vertex with the key dstKey (dst), if such exists. If src, dst or an edge between the two doesn't exist, GetEdge returns an error.

func (*DAG) GetEdges added in v0.1.3 

func (d *DAG) GetEdges(ctx context.Context) (driver.Cursor, error)

GetEdges executes the query to retrieve all edges of the DAG. GetEdges returns a cursor that may be used retrieve the edges one-by-one.

It is up to the caller to close the cursor, if no longer needed.

func (*DAG) GetLeaves 

func (d *DAG) GetLeaves(ctx context.Context) (driver.Cursor, error)

GetLeaves executes the query to retrieve all leaves of the DAG. GetLeaves returns a cursor that may be used retrieve the vertices one-by-one.

It is up to the caller to close the cursor, if no longer needed.

func (*DAG) GetOrder 

func (d *DAG) GetOrder(ctx context.Context) (int64, error)

GetOrder returns the Number of vertices in the graph.

func (*DAG) GetParentCount added in v0.1.5 

func (d *DAG) GetParentCount(ctx context.Context, srcKey string) (count int64, err error)

GetParentCount returns the Number parent-vertices of the vertex with the key srcKey (src).

If src doesn't exist, GetParentCount returns 0.

func (*DAG) GetParents 

func (d *DAG) GetParents(ctx context.Context, srcKey string) (driver.Cursor, error)

GetParents executes the query to retrieve all parents of the vertex with the key srcKey (src). GetParents returns a cursor that may be used retrieve the vertices one-by-one.

If src doesn't exist, the cursor doesn't return any vertex (i.e. no error is returned).

It is up to the caller to close the cursor, if no longer needed.

func (*DAG) GetRoots 

func (d *DAG) GetRoots(ctx context.Context) (driver.Cursor, error)

GetRoots executes the query to retrieve all roots of the DAG. GetRoots returns a cursor that may be used retrieve the vertices one-by-one.

It is up to the caller to close the cursor, if no longer needed.

func (*DAG) GetShortestPath 

func (d *DAG) GetShortestPath(ctx context.Context, srcKey, dstKey string) (driver.Cursor, error)

GetShortestPath executes the query to retrieve the vertices on the shortest path between the vertex with the key srcKey (src) and the vertex with the key dstKey (dst). GetShortestPath returns a cursor that may be used retrieve the vertices one-by-one. The result includes the src and dst.

If src and dst are equal, the cursor will return a single vertex.

If src or dst don't exist, the cursor doesn't return any vertex (i.e. no error is returned).

It is up to the caller to close the cursor, if no longer needed.

func (*DAG) GetSize 

func (d *DAG) GetSize(ctx context.Context) (int64, error)

GetSize returns the Number of edges in the DAG.

func (*DAG) GetVertex 

func (d *DAG) GetVertex(ctx context.Context, srcKey string, data interface{}) (driver.DocumentMeta, error)

GetVertex returns the vertex with the key srcKey.

If src doesn't exist, GetVertex returns an error.

func (*DAG) Info added in v0.6.1 

func (d *DAG) Info(ctx context.Context) (Info, error)

Info returns information about the DAG.

func (*DAG) LogQuery added in v0.4.0 

func (d *DAG) LogQuery(query string, bindVars map[string]interface{})

func (*DAG) ReplaceVertex added in v0.5.0 

func (d *DAG) ReplaceVertex(ctx context.Context, key string, data interface{}) (meta driver.DocumentMeta, err error)

ReplaceVertex replaces the data of the vertex with the given key.

func (*DAG) SetQueryLogging added in v0.4.0 

func (d *DAG) SetQueryLogging(queryLogging bool)

SetQueryLogging enables or disables query logging.

func (*DAG) String added in v0.1.3 

func (d *DAG) String(ctx context.Context) (result string, err error)

String returns a (graphviz) dot representation of the DAG.

func (*DAG) UpdateVertex added in v0.4.0 

func (d *DAG) UpdateVertex(ctx context.Context, key string, data interface{}) (meta driver.DocumentMeta, err error)

UpdateVertex updates the data of the vertex with the given key.

type DAGError added in v0.4.0 

type DAGError struct {
	Code    int
	Number  int
	Message string
}

func (DAGError) Error added in v0.4.0 

func (e DAGError) Error() string

Error returns the error Message of an ArangoError.

type Info added in v0.6.1 

type Info struct {
	Nodes     int64 `json:"nodes"`
	Relations int64 `json:"relations"`
}

Info contains basic information about the DAG.

type KeyInterface added in v0.3.0 

type KeyInterface interface {
	Key() string
}

KeyInterface describes the interface a type must implement in order to explicitly specify the vertex key.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.