README
¶
arangoDag
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 Example() {
// 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"
"strconv"
"strings"
"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, 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 ¶
- type DAG
- func (d *DAG) AddEdge(srcKey, dstKey string) (key string, err error)
- func (d *DAG) AddEdgeUnchecked(srcKey, dstKey string) (key string, err error)
- func (d *DAG) AddVertex(vertex interface{}) (key string, err error)
- func (d *DAG) DelEdge(srcKey, dstKey string) (err error)
- func (d *DAG) DelVertex(srcKey string) (edgeCount int64, err error)
- func (d *DAG) DotGraph(g *dot.Graph) (nodeMapping map[string]dot.Node, err error)
- func (d *DAG) EdgeExists(srcKey, dstKey string) (result bool, err error)
- func (d *DAG) GetAncestors(srcKey string, dfs bool) (driver.Cursor, error)
- func (d *DAG) GetChildCount(srcKey string) (count int64, err error)
- func (d *DAG) GetChildren(srcKey string) (driver.Cursor, error)
- func (d *DAG) GetDescendants(srcKey string, dfs bool) (driver.Cursor, error)
- func (d *DAG) GetEdges() (driver.Cursor, error)
- func (d *DAG) GetLeaves() (driver.Cursor, error)
- func (d *DAG) GetOrder() (count int64, err error)
- func (d *DAG) GetParentCount(srcKey string) (count int64, err error)
- func (d *DAG) GetParents(srcKey string) (driver.Cursor, error)
- func (d *DAG) GetRoots() (driver.Cursor, error)
- func (d *DAG) GetShortestPath(srcKey, dstKey string) (driver.Cursor, error)
- func (d *DAG) GetSize() (int64, error)
- func (d *DAG) GetVertex(srcKey string, vertex interface{}) (err error)
- func (d *DAG) GetVertices() (driver.Cursor, error)
- func (d *DAG) String() (result string, err error)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DAG ¶
type DAG struct {
DB driver.Database
Vertices driver.Collection
Edges driver.Collection
}
DAG implements the data structure of the DAG.
func (*DAG) AddEdge ¶
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.
AddEdge returns an error, if src or dst don't exist.
AddEdge prevents duplicate edges and loops (and thereby maintains a valid DAG).
func (*DAG) AddEdgeUnchecked ¶ added in v0.1.7
AddEdgeUnchecked 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.
AddEdgeUnchecked does NOT return an error, if src or dst don't exist.
AddEdgeUnchecked prevents duplicate edges and loops (and thereby maintains a valid DAG).
func (*DAG) AddVertex ¶
AddVertex adds the given vertex to the DAG and returns its key.
If the given vertex contains a `_key` field, this will be used as key. A new key will be created otherwise.
AddVertex prevents duplicate keys.
func (*DAG) DelEdge ¶ added in v0.1.7
DelEdge removes the edge from the vertex with the key srcKey (src) to the vertex with the key dstKey (dst).
DelEdge does NOT return an error, if such an edge doesn't exist.
func (*DAG) DelVertex ¶ added in v0.1.4
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) EdgeExists ¶
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 or dst don't exist, EdgeExists returns false.
func (*DAG) GetAncestors ¶
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
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
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 ¶
// 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)
// vertex type with self selected key
type idVertex struct {
Key string `json:"_key"`
}
// add some vertices and edges
_, _ = d.AddVertex(idVertex{"0"})
for i := 1; i < 10; i++ {
dstKey := strconv.Itoa(i)
_, _ = d.AddVertex(idVertex{dstKey})
_, _ = d.AddEdge("0", dstKey)
}
// get order and size
order, _ := d.GetOrder()
size, _ := d.GetSize()
fmt.Printf("order: %d\nsize: %d\n", order, size)
fmt.Printf("children:\n")
cursor, _ := d.GetChildren("0")
defer func() {
_ = cursor.Close()
}()
ctx := context.Background()
var vertex idVertex
for {
_, errRead := cursor.ReadDocument(ctx, &vertex)
if driver.IsNoMoreDocuments(errRead) {
break
}
if errRead != nil {
panic(errRead)
}
fmt.Printf("- %s\n", vertex.Key)
}
Output: order: 10 size: 9 children: - 8 - 7 - 6 - 3 - 5 - 9 - 1 - 2 - 4
func (*DAG) GetDescendants ¶
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) GetEdges ¶ added in v0.1.3
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 ¶
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) GetParentCount ¶ added in v0.1.5
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 ¶
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 ¶
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 ¶
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) GetVertex ¶
GetVertex returns the vertex with the key srcKey.
If src doesn't exist, GetVertex returns an error.
func (*DAG) GetVertices ¶
GetVertices executes the query to retrieve all vertices of the DAG. GetVertices 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.
Source Files