igraph

package
v0.1.3 Latest Latest
Warning

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

 Go to latest Published: Jun 4, 2023 License: AGPL-3.0 Imports: 14 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func MarshalTriple 

func MarshalTriple(triple IndexTriple) ([]byte, error)

func UnmarshalTriple 

func UnmarshalTriple(dest *IndexTriple, src []byte) error

Types

type DiskEngine 

type DiskEngine[Label comparable, Datum any] struct {
	imap.DiskEngine[Label]

	MarshalDatum   func(datum Datum) ([]byte, error)
	UnmarshalDatum func(dest *Datum, src []byte) error
}

DiskEngine represents an engine that stores everything on disk

func (DiskEngine[Label, Datum]) Data 

func (de DiskEngine[Label, Datum]) Data() (imap.KeyValueStore[imap.ID, Datum], error)

func (DiskEngine[Label, Datum]) Inverses 

func (de DiskEngine[Label, Datum]) Inverses() (imap.KeyValueStore[imap.ID, imap.ID], error)

func (DiskEngine[Label, Datum]) POSIndex 

func (de DiskEngine[Label, Datum]) POSIndex() (ThreeStorage, error)

func (DiskEngine[Label, Datum]) PSOIndex 

func (de DiskEngine[Label, Datum]) PSOIndex() (ThreeStorage, error)

func (DiskEngine[Label, Datum]) Triples 

func (de DiskEngine[Label, Datum]) Triples() (imap.KeyValueStore[imap.ID, IndexTriple], error)

type Engine 

type Engine[Label comparable, Datum any] interface {
	imap.Engine[Label]

	Data() (imap.KeyValueStore[imap.ID, Datum], error)
	Triples() (imap.KeyValueStore[imap.ID, IndexTriple], error)
	Inverses() (imap.KeyValueStore[imap.ID, imap.ID], error)
	PSOIndex() (ThreeStorage, error)
	POSIndex() (ThreeStorage, error)
}

Engine represents an object that creates storages for an IGraph

type IGraph 

type IGraph[Label comparable, Datum any] struct {
	// contains filtered or unexported fields
}

IGraph represents a searchable index of a directed labeled graph with optionally attached Data.

Labels are used for nodes and edges. This means that the graph is defined by triples of the form (subject Label, predicate Label, object Label). See [AddTriple].

Datum is used for data associated with the specific nodes. See [AddDatum].

The zero value represents an empty index, but is otherwise not ready to be used. To fill an index, it first needs to be [Reset], and then [Finalize]d.

IGraph may not be modified concurrently, however it is possible to run several queries concurrently.

func (*IGraph[Label, Datum]) AddData 

func (index *IGraph[Label, Datum]) AddData(subject, predicate Label, object Datum) error

AddData inserts a subject-predicate-data triple into the index. Adding multiple items to a specific subject with a specific predicate is supported.

Reset must have been called, or this function may panic. After all Add operations have finished, Finalize must be called.

func (*IGraph[Label, Datum]) AddTriple 

func (index *IGraph[Label, Datum]) AddTriple(subject, predicate, object Label) error

AddTriple inserts a subject-predicate-object triple into the index. Adding a triple more than once has no effect.

Reset must have been called, or this function may panic. After all Add operations have finished, Finalize must be called.

func (*IGraph[Label, Datum]) Close 

func (index *IGraph[Label, Datum]) Close() error

Close closes any storages attached to this storage

func (*IGraph[Label, Datum]) Finalize 

func (index *IGraph[Label, Datum]) Finalize() error

Finalize finalizes any adding operations into this graph.

Finalize must be called before any query is performed, but after any calls to the Add* methods. Calling finalize multiple times is valid.

func (*IGraph[Label, Datum]) IdentityMap 

func (index *IGraph[Label, Datum]) IdentityMap(storage imap.KeyValueStore[Label, Label]) error

IdentityMap writes all Labels for which has a semantically equivalent label. See imap.Storage.IdentityMap.

func (*IGraph[Label, Datum]) MarkIdentical 

func (index *IGraph[Label, Datum]) MarkIdentical(new, old Label) error

MarkIdentical identifies the new and old labels. See imap.IMap.MarkIdentical.

func (*IGraph[Label, Datum]) MarkInverse 

func (index *IGraph[Label, Datum]) MarkInverse(left, right Label) error

MarkInverse marks the left and right Labels as inverse properties of each other. After calls to MarkInverse, no more calls to MarkIdentical should be made.

Each label is assumed to have at most one inverse. A label may not be it's own inverse.

This means that each call to AddTriple(s, left, o) will also result in a call to AddTriple(o, right, s).

func (*IGraph[Label, Datum]) PathsStarting 

func (index *IGraph[Label, Datum]) PathsStarting(predicate, object Label) (*Paths[Label, Datum], error)

PathsStarting creates a new [PathSet] that represents all one-element paths starting at a vertex which is connected to object with the given predicate

func (*IGraph[Label, Datum]) Reset 

func (index *IGraph[Label, Datum]) Reset(engine Engine[Label, Datum]) (err error)

Reset resets this index and prepares all internal structures for use.

func (*IGraph[Label, Datum]) Stats 

func (index *IGraph[Label, Datum]) Stats() Stats

Stats returns statistics from this graph

func (*IGraph[Label, Datum]) Triple 

func (index *IGraph[Label, Datum]) Triple(id imap.ID) (triple Triple[Label, Datum], err error)

Triple returns the triple with the given

func (*IGraph[Label, Datum]) TripleCount 

func (index *IGraph[Label, Datum]) TripleCount() (count uint64, err error)

TripleCount returns the total number of (distinct) triples in this graph. Triples which have been identified will only count once.

type IndexTriple 

type IndexTriple struct {
	Role              // Why was this triple stored?
	Items  [3]imap.ID // What were the *original* items in this triple
	SItems [3]imap.ID // What were the *semantic* items in this triple
}

IndexTriple represents a triple stored inside the index

type MemoryEngine 

type MemoryEngine[Label comparable, Datum any] struct {
	imap.MemoryEngine[Label]
}

MemoryEngine represents an engine that stores everything in memory

func (MemoryEngine[Label, Datum]) Data 

func (MemoryEngine[Label, Datum]) Data() (imap.KeyValueStore[imap.ID, Datum], error)

func (MemoryEngine[Label, Datum]) Inverses 

func (MemoryEngine[Label, Datum]) Inverses() (imap.KeyValueStore[imap.ID, imap.ID], error)

func (MemoryEngine[Label, Datum]) POSIndex 

func (MemoryEngine[Label, Datum]) POSIndex() (ThreeStorage, error)

func (MemoryEngine[Label, Datum]) PSOIndex 

func (MemoryEngine[Label, Datum]) PSOIndex() (ThreeStorage, error)

func (MemoryEngine[Label, Datum]) Triples 

func (MemoryEngine[Label, Datum]) Triples() (imap.KeyValueStore[imap.ID, IndexTriple], error)

type Path 

type Path[Label comparable, Datum any] struct {
	// contains filtered or unexported fields
}

Path represents a path inside a GraphIndex

func (*Path[Label, Datum]) Datum 

func (path *Path[Label, Datum]) Datum() (datum Datum, ok bool, err error)

Datum returns the datum attached to the last node of this path, if any.

func (*Path[Label, Datum]) Edges 

func (path *Path[Label, Datum]) Edges() ([]Label, error)

Edges returns the labels of the edges this path consists of.

func (*Path[Label, Datum]) Node 

func (path *Path[Label, Datum]) Node(index int) (Label, error)

Node returns the label of the node at the given index of path.

func (*Path[Label, Datum]) Nodes 

func (path *Path[Label, Datum]) Nodes() ([]Label, error)

Nodes returns the nodes this path consists of, in order.

func (*Path[URI, Datum]) String 

func (result *Path[URI, Datum]) String() string

String turns this result into a string

NOTE(twiesing): This is for debugging only, and ignores all errors. It should not be used in producion code.

func (*Path[Label, Datum]) Triples 

func (path *Path[Label, Datum]) Triples() ([]Triple[Label, Datum], error)

Triples returns the triples that this Path consists of. Triples are guaranteed to be returned in query order, that is in the order they were required for the query to be fullfilled.

type Paths 

type Paths[Label comparable, Datum any] struct {
	// contains filtered or unexported fields
}

Paths represents a set of paths in a related GraphIndex. It implements a very simple sparql-like query engine.

A Paths object is stateful. A Paths object should only be created from a GraphIndex; the zero value is invalid. It can be further refined using the [Connected] and [Ending] methods.

func (*Paths[Label, Datum]) Connected 

func (set *Paths[Label, Datum]) Connected(predicate Label) error

Connected extends the sets of in this PathSet by those which continue the existing paths using an edge labeled with predicate.

func (*Paths[URI, Datum]) Ending 

func (set *Paths[URI, Datum]) Ending(predicate URI, object URI) error

Ending restricts this set of paths to those that end in a node which is connected to object via predicate.

func (*Paths[Label, Datum]) Paths 

func (set *Paths[Label, Datum]) Paths() iterator.Iterator[Path[Label, Datum]]

Paths returns an iterator over paths contained in this Paths. It may only be called once, afterwards further calls may be invalid.

func (*Paths[Label, Datum]) Size 

func (set *Paths[Label, Datum]) Size() (int, error)

Size returns the number of elements in this path.

NOTE(twiesing): This potentially takes a lot of memory, because we need to expand the stream.

type Role 

type Role uint8

Role represents the role of the triple 

const (
	// Regular represents a regular (non-infered) triple
	Regular Role = iota

	// Inverse represents an infered inverse triple
	Inverse

	// Data represents a data triple
	Data
)

type Stats 

type Stats struct {
	DirectTriples   int64
	DatumTriples    int64
	InverseTriples  int64
	ConflictTriples int64
}

Stats holds statistics about triples in the index

func (Stats) String 

func (stats Stats) String() string

type ThreeDiskHash 

type ThreeDiskHash struct {
	DB *leveldb.DB
}

ThreeHash implements ThreeStorage in memory

func (*ThreeDiskHash) Add 

func (tlm *ThreeDiskHash) Add(a, b, c imap.ID, l imap.ID, conflict func(old, new imap.ID) (imap.ID, error)) (conflicted bool, err error)

func (*ThreeDiskHash) Close 

func (tlm *ThreeDiskHash) Close() (err error)

func (*ThreeDiskHash) Count 

func (tlm *ThreeDiskHash) Count() (total int64, err error)

func (*ThreeDiskHash) Fetch 

func (tlm *ThreeDiskHash) Fetch(a, b imap.ID, f func(c imap.ID, l imap.ID) error) error

func (ThreeDiskHash) Finalize 

func (tlm ThreeDiskHash) Finalize() error

func (*ThreeDiskHash) Has 

func (tlm *ThreeDiskHash) Has(a, b, c imap.ID) (id imap.ID, ok bool, err error)

type ThreeHash 

type ThreeHash map[imap.ID]map[imap.ID]*ThreeItem

ThreeHash implements ThreeStorage in memory

func (ThreeHash) Add 

func (tlm ThreeHash) Add(a, b, c imap.ID, l imap.ID, conflict func(old, new imap.ID) (imap.ID, error)) (conflicted bool, err error)

func (*ThreeHash) Close 

func (tlm *ThreeHash) Close() error

func (ThreeHash) Count 

func (tlm ThreeHash) Count() (total int64, err error)

func (ThreeHash) Fetch 

func (tlm ThreeHash) Fetch(a, b imap.ID, f func(c imap.ID, l imap.ID) error) error

func (ThreeHash) Finalize 

func (tlm ThreeHash) Finalize() error

func (ThreeHash) Has 

func (tlm ThreeHash) Has(a, b, c imap.ID) (imap.ID, bool, error)

type ThreeItem 

type ThreeItem struct {
	Keys []imap.ID
	Data map[imap.ID]imap.ID
}

type ThreeStorage 

type ThreeStorage interface {
	io.Closer

	// Add adds a new mapping for the given (a, b, c).
	//
	// l acts as a label for the insert.
	// when the given edge already exists, the conflict function should be called to resolve the conflict
	Add(a, b, c imap.ID, l imap.ID, conflict func(old, new imap.ID) (imap.ID, error)) (conflicted bool, err error)

	// Count counts the overall number of entries in the index
	Count() (int64, error)

	// Finalize informs the storage that no more mappings will be made
	Finalize() error

	// Fetch iterates over all triples (a, b, c) in c-order.
	// l is the last label that was created for the triple.
	// If an error occurs, iteration stops and is returned to the caller
	Fetch(a, b imap.ID, f func(c imap.ID, l imap.ID) error) error

	// Has checks if the given mapping exists and returns the label (if any)
	Has(a, b, c imap.ID) (imap.ID, bool, error)
}

func NewDiskHash 

func NewDiskHash(path string) (ThreeStorage, error)

type Triple 

type Triple[Label comparable, Datum any] struct {
	// ID uniquely identifies this triple.
	// Two Triples are identical iff their IDs are identical.
	ID imap.ID

	Role Role

	Subject, Predicate, Object    Label
	SSubject, SPredicate, SObject Label // the "semantic" version of the datum

	Datum Datum
}

Triple represents a triple found inside a graph

func (Triple[Label, Datum]) Inferred 

func (triple Triple[Label, Datum]) Inferred() bool

Inferred returns if this triple has been infered

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.