lpg

package module
v2.0.2 Latest Latest
Warning

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

 Go to latest Published: Oct 2, 2023 License: Apache-2.0 Imports: 10 Imported by: 23

README

GoDoc Go Report Card Build Status

Labeled property graphs

This labeled property graph package implements the openCypher model of labeled property graphs. A labeled property graph (LPG) contains nodes and directed edges between those nodes. Every node contains:

  • Labels: Set of string tokens that usually identify the type of the node,
  • Properties: Key-value pairs.

Every edge contains:

  • A label: String token that identifies a relationship, and
  • Properties: Key-value pairs.

A Graph objects keeps an index of the nodes and edges included in it. Create a graph using NewGraph function:

g := lpg.NewGraph()
// Create two nodes
n1 := g.NewNode([]string{"label1"},map[string]any{"prop": "value1" })
n2 := g.NewNode([]string{"label2"},map[string]any{"prop": "value2" })
// Connect the two nodes with an edge
edge:=g.NewEdge(n1,n2,"relatedTo",nil)

The LPG library uses iterators to address nodes and edges.

for nodes:=graph.GetNodes(); nodes.Next(); {
  node:=nodes.Node()
}
for edges:=graph.GetEdges(); edges.Next(); {
  edge:edges.Edge()
}

Every node knows its adjacent edges.

// Get outgoing edges
for edges:=node1.GetEdges(lpg.OutgoingEdge); edges.Next(); {
  edge:=edges.Edge
}

// Get all edges
for edges:=node1.GetEdges(lpg.AnyEdge); edges.Next(); {
  edge:=edges.Edge
}

The graph indexes nodes by label, so access to nodes using labels is fast. You can add additional indexes on properties:

g := lpg.NewGraph()
// Index all nodes with property 'prop'
g.AddNodePropertyIndex("prop")

// This access should be fast
nodes := g.GetNodesWithProperty("prop")

// This will go through all nodes
slowNodes:= g.GetNodesWithProperty("propWithoutIndex")

Pattern Searches

Graph library supports searching patterns within a graph. The following example searches for the pattern that match

(:label1) -[]->({prop:value})`

and returns the head nodes for every matching path:

pattern := lpg.Pattern{ 
 // Node containing label 'label1'
 {
   Labels: lpg.NewStringSet("label1"),
 },
 // Edge of length 1
 {
   Min: 1, 
   Max: 1,
 },
 // Node with property prop=value
 {
   Properties: map[string]interface{} {"prop":"value"},
 }}
nodes, err:=pattern.FindNodes(g,nil)

Variable length paths are supported:

pattern := lpg.Pattern{ 
 // Node containing label 'label1'
 {
   Labels: lpg.NewStringSet("label1"),
 },
 // Minimum paths of length 2, no maximum length
 {
   Min: 2, 
   Max: -1,
 },
 // Node with property prop=value
 {
   Properties: map[string]interface{} {"prop":"value"},
 }}

JSON Encoding

This graph library uses the following JSON representation:

{
  "nodes": [
     {
       "n": 0,
       "labels": [ "l1", "l2",... ],
       "properties": {
          "key1": value,
          "key2": value,
          ...
        },
        "edges": [
           {
             "to": "1",
             "label": "edgeLabel",
             "properties": {
               "key1": value,
               "key2": value,
               ...
             }
           },
           ...
        ]
     },
      ...
  ],
  "edges": [
     {
        "from": 0,
        "to": 1,
        "label": "edgeLabel",
        "properties": {
           "key1": value1,
           "key2": value2,
           ...
        }
     },
     ...
  ]
}

All graph nodes are under the nodes key as an array. The n key identifies the node using a unique index. All node references in edges use these indexes. A node may include all outgoing edges embedded in it, or edges may be included under a separate top-level array edges. If the edge is included in the node, the edge only has a to field that gives the target node index as the node containing the edge is assumed to be the source node. Edges under the top-level edges array include both a from and a to index.

Standard library JSON marshaler/unmarshaler does not work with graphs, because the edge and node property values are of type any. The JSON struct can be used to marshal and unmarshal graphs with custom property marshaler and unmarshalers.

This Go module is part of the Layered Schema Architecture.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func CheckIsomorphism 

func CheckIsomorphism(ctx context.Context, g1, g2 *Graph, nodeEquivalenceFunc func(n1, n2 *Node) bool, edgeEquivalenceFunc func(e1, e2 *Edge) bool) (bool, error)

CheckIsomoprhism checks to see if graphs given are equal as defined by the edge equivalence and node equivalence functions. The nodeEquivalenceFunction will be called for all pairs of nodes. The edgeEquivalenceFunction will be called for edges connecting equivalent nodes.

This is a potentially long running function. Cancel the context to stop. If the function returns because of context cancellation, error will be ctx.Err()

func CollectAllPaths 

func CollectAllPaths(graph *Graph, fromNode *Node, firstLeg EdgeIterator, edgeFilter func(*Edge) bool, dir EdgeDir, min, max int, accumulator func(*Path) bool)

CollectAllPaths iterates the variable length paths that have the edges in firstLeg. For each edge, it calls the edgeFilter function. If the edge is accepted, it recursively descends and calls accumulator.AddPath for each discovered path until AddPath returns false

func ComparePropertyValue 

func ComparePropertyValue(a, b interface{}) int

ComparePropertyValue compares a and b. They must be comparable. Supported types are 

int
string
[]int
[]string
[]interface

The []interface must have one of the supported types as its elements

If one of the values implement GetNativeValue() method, then it is called to get the underlying value

func CopyGraph 

func CopyGraph(source, target *Graph, clonePropertyFunc func(string, interface{}) interface{}) map[*Node]*Node

CopyGraph copies source graph into target, using clonePropertyFunc to clone properties

func CopyGraphf 

func CopyGraphf(source *Graph, copyNodeFunc func(*Node, map[*Node]*Node) *Node, copyEdgeFunc func(*Edge, map[*Node]*Node) *Edge) map[*Node]*Node

CopyGraphf copies source graph into target, using the copeNodeFunc func to clone nodes. copyNodeFunc may return nil to prevent copying a node

func CopySubgraph 

func CopySubgraph(sourceNode *Node, target *Graph, clonePropertyFunc func(string, interface{}) interface{}, nodeMap map[*Node]*Node)

CopySubgraph copies all nodes that are accessible from sourceNode to the target graph

func DefaultDOTEdgeRender 

func DefaultDOTEdgeRender(fromNode, toNode string, edge *Edge, w io.Writer) error

DefaultDOTEdgeRender renders the edge with a label if there is one, or without a label if there is not a label.

func DefaultDOTNodeRender 

func DefaultDOTNodeRender(ID string, node *Node, w io.Writer) error

DefaultDOTNodeRender renders the node with the given ID. If the node has a label, it uses that label, otherwise node is not labeled.

func ForEachNode 

func ForEachNode(g *Graph, predicate func(*Node) bool) bool

ForEachNode iterates through all the nodes of g until predicate returns false or all nodes are processed.

func GetEdgeFilterFunc 

func GetEdgeFilterFunc(labels StringSet, properties map[string]interface{}) func(*Edge) bool

GetEdgeFilterFunc returns a function that can be used to select edges that have at least one of the specified labels, with correct property values

func GetNodeFilterFunc 

func GetNodeFilterFunc(labels StringSet, properties map[string]interface{}) func(*Node) bool

GetNodeFilterFunc returns a filter function that can be used to select nodes that have all the specified labels, with correct property values

Types

type Cursor 

type Cursor struct {
	// contains filtered or unexported fields
}

Cursor is a convenience class to move around a graph

func (*Cursor) Backward 

func (c *Cursor) Backward() EdgeIterator

Backward returns an edge iterator for incoming edges of the current node. If the current node is invalid, returns an empty iterator

func (*Cursor) BackwardWith 

func (c *Cursor) BackwardWith(label string) EdgeIterator

BackwardWith returns an edge iterator for incoming edges of the current node with the given label. If the current node is invalid, returns an empty iterator

func (*Cursor) Edges 

func (c *Cursor) Edges(dir EdgeDir) EdgeIterator

Edges returns an iterator of edges of the current node. If the current node is invalid, returns an empty iterator

func (*Cursor) EdgesWith 

func (c *Cursor) EdgesWith(dir EdgeDir, label string) EdgeIterator

EdgesWith returns an iterator of edges of the current node with the given label. If the current node is invalid, returns an empty iterator

func (*Cursor) Forward 

func (c *Cursor) Forward() EdgeIterator

Forward returns an edge iterator for outgoing edges of the current node. If the current node is invalid, returns an empty iterator

func (*Cursor) ForwardWith 

func (c *Cursor) ForwardWith(label string) EdgeIterator

ForwardWith returns an edge iterator for outgoing edges of the current node with the given label. If the current node is invalid, returns an empty iterator

func (*Cursor) GetPath 

func (c *Cursor) GetPath() *Path

GetPath returns the recorded path. This is the internal copy of the path, so caller must clone if it changes are necessary

func (*Cursor) NextNodes 

func (c *Cursor) NextNodes() NodeIterator

NextNodes returns a node iterator that can be reached at one step from the current node. If current node is invalid, returns an empty iterator.

func (*Cursor) NextNodesWith 

func (c *Cursor) NextNodesWith(label string) NodeIterator

NextNodesWith returns a node iterator that can be reached at one step from the current node with the given label. If current node is invalid, returns an empty iterator.

func (*Cursor) Nodes 

func (c *Cursor) Nodes(dir EdgeDir) NodeIterator

Nodes returns an iterator over the nodes that are reachable by a single edge from the current node. If the current node is not valid, returns an empty iterator

func (*Cursor) NodesWith 

func (c *Cursor) NodesWith(dir EdgeDir, label string) NodeIterator

NodesWith returns an iterator over the nodes that are reachable by a single edge with the given label from the current node. If the current node is not valid, returns an empty iterator

func (*Cursor) PopFromPath 

func (c *Cursor) PopFromPath() *Cursor

PopFromPath removes the last edge from the path. This also moves the cursor to the previous node

func (*Cursor) PrevNodes 

func (c *Cursor) PrevNodes() NodeIterator

PrevNodes returns a node iterator that can be reached at one step backwards from the current node. If current node is invalid, returns an empty iterator.

func (*Cursor) PrevNodesWith 

func (c *Cursor) PrevNodesWith(label string) NodeIterator

PrevNodesWith returns a node iterator that can be reached at one step backwards from the current node with the given label. If current node is invalid, returns an empty iterator.

func (*Cursor) PushToPath 

func (c *Cursor) PushToPath(edge *Edge) *Cursor

PushToPath pushes the edge onto the path. The path must be started, and the pushed edge must be connected to the current node. This also advances the cursor to the target node.

func (*Cursor) Set 

func (c *Cursor) Set(node *Node) *Cursor

Sets the node cursor is pointing at.

func (*Cursor) StartPath 

func (c *Cursor) StartPath() *Cursor

StartPath starts a new path at the current node. Panics if the node is not valid.

type DOTRenderer 

type DOTRenderer struct {
	// NodeRenderer renders a node. If the node is to be excluded, returns false.
	NodeRenderer func(string, *Node, io.Writer) (bool, error)
	// EdgeRenderer renders an edge. The from and to nodes are rendered
	// if this is called. If the edge is to be excluded, returns false
	EdgeRenderer func(fromID string, toID string, edge *Edge, w io.Writer) (bool, error)
}

DOTRenderer renders a graph in Graphviz dot format

func (DOTRenderer) Render 

func (d DOTRenderer) Render(g *Graph, graphName string, out io.Writer) error

Render writes a DOT graph with the given name

func (DOTRenderer) RenderEdge 

func (d DOTRenderer) RenderEdge(fromID, toID string, edge *Edge, w io.Writer) (bool, error)

RenderEdge renders an edge. If edge renderer is not set, call the default rendeded

func (DOTRenderer) RenderNode 

func (d DOTRenderer) RenderNode(ID string, node *Node, w io.Writer) (bool, error)

RenderNode renders a node. If node renderer is not set, calls the default renderer

func (DOTRenderer) RenderNodesEdges 

func (d DOTRenderer) RenderNodesEdges(g *Graph, out io.Writer) error

type DefaultMatchAccumulator 

type DefaultMatchAccumulator struct {
	// Each element of the paths is either a Node or []Edge
	Paths   []*Path
	Symbols []map[string]interface{}
}

func (*DefaultMatchAccumulator) GetHeadNodes 

func (acc *DefaultMatchAccumulator) GetHeadNodes() []*Node

Returns the unique nodes in the accumulator that start a path

func (*DefaultMatchAccumulator) GetTailNodes 

func (acc *DefaultMatchAccumulator) GetTailNodes() []*Node

Returns the unique nodes in the accumulator that ends a path

func (*DefaultMatchAccumulator) StoreResult 

func (acc *DefaultMatchAccumulator) StoreResult(_ *MatchContext, path *Path, symbols map[string]interface{})

type Edge 

type Edge struct {
	// contains filtered or unexported fields
}

An Edge connects two nodes of a graph

func CloneEdge 

func CloneEdge(from, to *Node, edge *Edge, target *Graph, clonePropertyFunc func(string, interface{}) interface{}) *Edge

func CopyEdge 

func CopyEdge(edge *Edge, target *Graph, clonePropertyFunc func(string, interface{}) interface{}, nodeMap map[*Node]*Node) *Edge

CopyEdge copies the edge into graph

func EdgeSlice 

func EdgeSlice(in EdgeIterator) []*Edge

EdgeSlice reads all the remaining items of an edge iterator and returns them in a slice

func EdgesBetweenNodes 

func EdgesBetweenNodes(from, to *Node) []*Edge

EdgesBetweenNodes finds all the edges that go from 'from' to 'to'

func (*Edge) ForEachProperty 

func (edge *Edge) ForEachProperty(f func(string, interface{}) bool) bool

func (*Edge) GetFrom 

func (edge *Edge) GetFrom() *Node

GetFrom returns the source node

func (*Edge) GetGraph 

func (edge *Edge) GetGraph() *Graph

GetGraph returns the graph of the edge.

func (*Edge) GetID 

func (edge *Edge) GetID() int

GetID returns the unique identifier for the edge. The identifier is unique in this graph, and meaningless once the edge is disconnected.

func (*Edge) GetLabel 

func (edge *Edge) GetLabel() string

GetLabel returns the edge label

func (*Edge) GetProperty 

func (edge *Edge) GetProperty(key string) (interface{}, bool)

write public func for GetProperty, ForEachProperty

func (*Edge) GetTo 

func (edge *Edge) GetTo() *Node

GetTo returns the target node

func (*Edge) MarshalJSON 

func (edge *Edge) MarshalJSON() ([]byte, error)

func (*Edge) Remove 

func (edge *Edge) Remove()

Remove an edge

func (*Edge) RemoveProperty 

func (edge *Edge) RemoveProperty(key string)

RemoveProperty removes an edge property

func (*Edge) SetLabel 

func (edge *Edge) SetLabel(label string)

SetLabel sets the edge label

func (*Edge) SetProperty 

func (edge *Edge) SetProperty(key string, value interface{})

SetProperty sets an edge property

func (*Edge) String 

func (edge *Edge) String() string

Returns the string representation of an edge

type EdgeDir 

type EdgeDir int

EdgeDir is used to show edge direction 

const (
	IncomingEdge EdgeDir = -1
	AnyEdge      EdgeDir = 0
	OutgoingEdge EdgeDir = 1
)

Incoming and outgoing edge direction constants

type EdgeIterator 

type EdgeIterator interface {
	Iterator
	// Returns the current edge
	Edge() *Edge
}

EdgeIterator iterates the edges of an underlying list

type EdgeSet 

type EdgeSet struct {
	// contains filtered or unexported fields
}

EdgeSet keeps an unordered set of edges

func NewEdgeSet 

func NewEdgeSet() *EdgeSet

func (*EdgeSet) Add 

func (set *EdgeSet) Add(edge *Edge)

func (EdgeSet) Iterator 

func (set EdgeSet) Iterator() EdgeIterator

func (EdgeSet) Len 

func (set EdgeSet) Len() int

func (EdgeSet) Remove 

func (set EdgeSet) Remove(edge *Edge)

func (EdgeSet) Slice 

func (set EdgeSet) Slice() []*Edge

type ErrEdgeVariableExpected 

type ErrEdgeVariableExpected string

func (ErrEdgeVariableExpected) Error 

func (e ErrEdgeVariableExpected) Error() string

type ErrInvalidGraph 

type ErrInvalidGraph struct {
	Msg string
}

func (ErrInvalidGraph) Error 

func (e ErrInvalidGraph) Error() string

type ErrNodeVariableExpected 

type ErrNodeVariableExpected string

func (ErrNodeVariableExpected) Error 

func (e ErrNodeVariableExpected) Error() string

type Graph 

type Graph struct {
	// contains filtered or unexported fields
}

A Graph is a labeled property graph containing nodes, and directed edges combining those nodes.

Every node of the graph contains a set of labels, and a map of properties. Each node provides access to the edges adjacent to it. Every edge contains a from and to node, a label, and a map of properties.

Nodes and edges are "owned" by a graph object. Given a node or edge, you can always get its graph using `node.GetGraph()` or `edge.GetGraph()` method. You cannot use an edge to connect nodes of different graphs.

Zero value for a Graph is not usable. Use `NewGraph` to construct a new graph.

func NewGraph 

func NewGraph() *Graph

NewGraph constructs and returns a new graph. The new graph has no nodes or edges.

func (*Graph) AddEdgePropertyIndex 

func (g *Graph) AddEdgePropertyIndex(propertyName string, ix IndexType)

AddEdgePropertyIndex adds an index for the given edge property

func (*Graph) AddNodePropertyIndex 

func (g *Graph) AddNodePropertyIndex(propertyName string, ix IndexType)

AddNodePropertyIndex adds an index for the given node property

func (*Graph) FastNewEdge added in v2.0.1 

func (g *Graph) FastNewEdge(from, to *Node, label string, props map[string]any) *Edge

FastNewEdge creates a new edge between the two nodes of the graph. Both nodes must be nodes of this graph, otherwise this call panics. This version uses the given properties map directly without copying it.

func (*Graph) FastNewNode added in v2.0.1 

func (g *Graph) FastNewNode(labels StringSet, props map[string]interface{}) *Node

FastNewNode creates a new node with the given labels and properties. This version does not copy the labels and properties, but uses the given label set and map directly

func (*Graph) FindEdges 

func (g *Graph) FindEdges(labels StringSet, properties map[string]interface{}) EdgeIterator

FindEdges returns an iterator that will iterate through all the edges whose label is in the given labels and have all the properties. If labels is nil or empty, it does not look at the labels. If properties is nil or empty, it does not look at the properties

func (*Graph) FindNodes 

func (g *Graph) FindNodes(allLabels StringSet, properties map[string]interface{}) NodeIterator

FindNodes returns an iterator that will iterate through all the nodes that have all of the given labels and properties. If allLabels is nil or empty, it does not look at the labels. If properties is nil or empty, it does not look at the properties

func (*Graph) GetEdges 

func (g *Graph) GetEdges() EdgeIterator

GetEdges returns an edge iterator that goes through all the edges of the graph. The behavior of the returned iterator is undefined if during iteration edges are updated, new edges are added, or existing edges are deleted.

func (*Graph) GetEdgesWithAnyLabel 

func (g *Graph) GetEdgesWithAnyLabel(set StringSet) EdgeIterator

GetEdgesWithAnyLabel returns an iterator that goes through the edges of the graph that are labeled with one of the labels in the given set. The behavior of the returned iterator is undefined if during iteration edges are updated, new edges are added, or existing edges are deleted.

func (*Graph) GetEdgesWithProperty 

func (g *Graph) GetEdgesWithProperty(property string) EdgeIterator

GetEdgesWithProperty returns an iterator for the edges that has the property. If there is an index for the property, and iterator over that index is returned. Otherwise, an iterator that goes through all edges while filtering them is returned. The behavior of the returned iterator is undefined if during iteration edges are updated, new edges are added, or existing edges are deleted.

func (*Graph) GetNodes 

func (g *Graph) GetNodes() NodeIterator

GetNodes returns a node iterator that goes through all the nodes of the graph. The behavior of the returned iterator is undefined if during iteration nodes are updated, new nodes are added, or existing nodes are deleted.

func (*Graph) GetNodesWithAllLabels 

func (g *Graph) GetNodesWithAllLabels(labels StringSet) NodeIterator

GetNodesWithAllLabels returns an iterator that goes through the nodes that have all the nodes given in the set. The nodes may have more nodes than given in the set. The behavior of the returned iterator is undefined if during iteration nodes are updated, new nodes are added, or existing nodes are deleted.

func (*Graph) GetNodesWithProperty 

func (g *Graph) GetNodesWithProperty(property string) NodeIterator

GetNodesWithProperty returns an iterator for the nodes that has the property. If there is an index for the node property, and iterator over that index is returned. Otherwise, an iterator that goes through all nodes while filtering them is returned. The behavior of the returned iterator is undefined if during iteration nodes are updated, new nodes are added, or existing nodes are deleted.

func (*Graph) NewEdge 

func (g *Graph) NewEdge(from, to *Node, label string, props map[string]any) *Edge

NewEdge creates a new edge between the two nodes of the graph. Both nodes must be nodes of this graph, otherwise this call panics

func (*Graph) NewNode 

func (g *Graph) NewNode(labels []string, props map[string]interface{}) *Node

NewNode creates a new node with the given labels and properties

func (*Graph) NumEdges 

func (g *Graph) NumEdges() int

NumEdges returns the number of edges in the graph

func (*Graph) NumNodes 

func (g *Graph) NumNodes() int

NumNodes returns the number of nodes in the graph

type IndexType 

type IndexType int
const (
	BtreeIndex IndexType = 0
	HashIndex  IndexType = 1
)

type Interner 

type Interner interface {
	// Intern should return the interned copy of the string
	Intern(string) string
}

Interner is a string interface, that can be as simple as a map[string]string, that is used to intern property keys

type Iterator 

type Iterator interface {
	// Next moves to the next item in the iterator, and returns true if
	// move was successful. If there are no next items remaining, returns false
	Next() bool

	// Value returns the current item in the iterator. This is undefined
	// before the first call to Next, and after Next returns false.
	Value() interface{}

	// MaxSize returns an estimation of maximum number of elements. If unknown, returns -1
	MaxSize() int
}

An Iterator iterates the items of a collection

func MultiIterator 

func MultiIterator(iterators ...Iterator) Iterator

MultiIterator returns an iterator that contatenates all the given iterators

type JSON 

type JSON struct {
	Interner Interner

	// If false, dring marshaling edges are embedded in the source
	// nodes. If true, edges are marshaled separately as a JSON array.
	MarshalEdgesSeparately bool

	// PropertyUnmarshaler unmarshals a property value. The return
	// values are the key, value, and possible error. If the returned
	// key is empty, the property is not unmarshaled. If this is nil,
	// default json unmarshaler is used for property value.
	PropertyUnmarshaler func(key string, value json.RawMessage) (string, interface{}, error)

	// PropertyMarshaler marshals a property value. The return values
	// are the key, the marshaled value, and possible error. If the
	// returned key is empty, the property is not marshaled. If this is
	// nil, the default json marshaler is used for property value.
	PropertyMarshaler func(key string, value interface{}) (string, json.RawMessage, error)
}

JSON marshals/unmarshals a graph to/from JSON.

The JSON unmarshaling uses a string Interner if it is set. This allows reusing the strings for repeated keys. Setting this interner to an implementation will reduce memory footprint of the graph. If letf uninitialized, the unmarshaler still uses an interner, but this interner will not be shared between different graphs unmarshaled using this unmarshaler.

If PropertyMarshaler/PropertyUnmarshaler is set, these functions are called to marshal/unmarshal individual properties. These function can return an empty string for the key to skip the property.

If MarshalEdgesSeparately is set, graph edges are marshaled under the "edges" key. If this is false, the graph edges are included under the source node.

The JSON representation of nodes use a numeric node index. These indexes are used to refer to nodes in edges.

With MarshalEdgesSeparately=false: 

{
   "nodes": [
     {
        "n": 0,
        "labels": ["lbl1","lbl2"],
        "properties": {
          "key": "value"
        },
        "edges": [
           {
               "to": 1,
               "label": "edgeLabel"
           }
        ]
     },
     {
        "n": 1,
        "labels": ["lbl1"]
     }
  ]
}

With MarshalEdgesSeparately=true: 

{
   "nodes": [
     {
        "n": 0,
        "labels": ["lbl1","lbl2"],
        "properties": {
          "key": "value"
        }
     },
     {
        "n": 1,
        "labels": ["lbl1"]
     }
  ],
  "edges": [
       {
            "from": 0,
            "to": 1,
            "label": "edgeLabel"
      }
  ]
}

func (JSON) Decode 

func (j JSON) Decode(g *Graph, input *json.Decoder) error

Decode a graph in JSON

func (JSON) Encode 

func (j JSON) Encode(g *Graph, out io.Writer) error

Encode the graph in JSON

type MapInterner 

type MapInterner map[string]string

MapInterner is a basic interner that uses a map[string]string to intern strings

func (MapInterner) Intern 

func (i MapInterner) Intern(s string) string

Intern keeps the interned copy of s in the map

type MatchAccumulator 

type MatchAccumulator interface {
	// path is either a Node or []Edge, the matching path symbols
	// contains the current values for each symbol. The values of the
	// map is either Node or []Edge
	StoreResult(ctx *MatchContext, path *Path, symbols map[string]interface{})
}

type MatchContext 

type MatchContext struct {
	Graph *Graph
	// These are symbols that are used as constraints in the matching process.
	Symbols map[string]*PatternSymbol

	// localSymbols are symbols defined in the pattern.
	LocalSymbols map[string]*PatternSymbol
	// contains filtered or unexported fields
}

type MatchPlan 

type MatchPlan struct {
	// contains filtered or unexported fields
}

func (MatchPlan) CaptureSymbolValues 

func (plan MatchPlan) CaptureSymbolValues() map[string]interface{}

CaptureSymbolValues captures the current symbol values as nodes or []Edges

func (MatchPlan) GetCurrentPath 

func (plan MatchPlan) GetCurrentPath() *Path

GetCurrentPath returns the current path recoded in the stages of the pattern. The result is either a single node, or a path

func (MatchPlan) Run 

func (plan MatchPlan) Run(graph *Graph, symbols map[string]*PatternSymbol, result MatchAccumulator) error

type Node 

type Node struct {
	// contains filtered or unexported fields
}

A Node represents a graph node.

func CopyNode 

func CopyNode(sourceNode *Node, target *Graph, clonePropertyFunc func(string, interface{}) interface{}) *Node

CopyNode copies the sourceNode into target graph

func NextNodesWith 

func NextNodesWith(source *Node, label string) []*Node

NextNodesWith returns the nodes reachable from source with the given label at one step

func NodeSlice 

func NodeSlice(in NodeIterator) []*Node

NodeSlice reads all the remaining items of a node iterator and returns them in a slice

func PrevNodesWith 

func PrevNodesWith(source *Node, label string) []*Node

PrevNodesWith returns the nodes reachable from source with the given label at one step

func Sinks 

func Sinks(graph *Graph) []*Node

Sinks finds all the sink nodes in the graph

func SourceNodes 

func SourceNodes(in EdgeIterator) []*Node

SourceNodes returns the source nodes of all edges

func Sources 

func Sources(graph *Graph) []*Node

Sources finds all the source nodes in the graph

func TargetNodes 

func TargetNodes(in EdgeIterator) []*Node

TargetNodes returns the target nodes of all edges

func (*Node) Detach 

func (node *Node) Detach()

Remove all connected edges

func (*Node) DetachAndRemove 

func (node *Node) DetachAndRemove()

Remove all connected edges, and remove the node

func (*Node) ForEachProperty 

func (node *Node) ForEachProperty(f func(string, interface{}) bool) bool

func (*Node) GetEdges 

func (node *Node) GetEdges(dir EdgeDir) EdgeIterator

Returns an edge iterator for incoming or outgoing edges

func (*Node) GetEdgesWithAnyLabel 

func (node *Node) GetEdgesWithAnyLabel(dir EdgeDir, labels StringSet) EdgeIterator

Returns an edge iterator for incoming or outgoingn edges that has the given labels

func (*Node) GetEdgesWithLabel 

func (node *Node) GetEdgesWithLabel(dir EdgeDir, label string) EdgeIterator

Returns an edge iterator for incoming or outgoing edges with the given label

func (*Node) GetGraph 

func (node *Node) GetGraph() *Graph

GetGraph returns the graph owning the node

func (*Node) GetID 

func (node *Node) GetID() int

GetID returns the unique node ID. The ID is meaningless if the node is removed from the graph

func (*Node) GetLabels 

func (node *Node) GetLabels() StringSet

GetLabels returns a copy of the node labels

func (*Node) GetProperty 

func (node *Node) GetProperty(key string) (interface{}, bool)

GetProperty returns the property value in the string table

func (*Node) HasLabel 

func (node *Node) HasLabel(s string) bool

HasLabel returns true if the node has the given label

func (*Node) MarshalJSON 

func (node *Node) MarshalJSON() ([]byte, error)

func (*Node) RemoveProperty 

func (node *Node) RemoveProperty(key string)

RemoveProperty removes a node property

func (*Node) SetLabels 

func (node *Node) SetLabels(labels StringSet)

SetLabels sets the node labels

func (*Node) SetProperty 

func (node *Node) SetProperty(key string, value interface{})

SetProperty sets a node property

func (*Node) String 

func (node *Node) String() string

String returns the string representation of the node

type NodeIterator 

type NodeIterator interface {
	Iterator
	// Returns the current node
	Node() *Node
}

NodeIterator iterates nodes of an underlying list

func SinksItr 

func SinksItr(graph *Graph) NodeIterator

Sinks finds all the sink nodes in the graph

func SourcesItr 

func SourcesItr(graph *Graph) NodeIterator

Sources finds all the source nodes in the graph

type NodeMap 

type NodeMap struct {
	// contains filtered or unexported fields
}

An NodeMap stores nodes indexed by node labels

func NewNodeMap 

func NewNodeMap() *NodeMap

func (*NodeMap) Add 

func (nm *NodeMap) Add(node *Node)

func (NodeMap) IsEmpty 

func (nm NodeMap) IsEmpty() bool

func (NodeMap) Iterator 

func (nm NodeMap) Iterator() NodeIterator

func (NodeMap) IteratorAllLabels 

func (nm NodeMap) IteratorAllLabels(labels StringSet) NodeIterator

func (NodeMap) Remove 

func (nm NodeMap) Remove(node *Node)

func (*NodeMap) Replace 

func (nm *NodeMap) Replace(node *Node, oldLabels, newLabels StringSet)

type NodeSet 

type NodeSet struct {
	// contains filtered or unexported fields
}

func NewNodeSet 

func NewNodeSet() *NodeSet

func (*NodeSet) Add 

func (set *NodeSet) Add(node *Node)

func (NodeSet) Has 

func (set NodeSet) Has(node *Node) bool

func (NodeSet) Iterator 

func (set NodeSet) Iterator() NodeIterator

func (NodeSet) Len 

func (set NodeSet) Len() int

func (NodeSet) Remove 

func (set NodeSet) Remove(node *Node)

func (NodeSet) Slice 

func (set NodeSet) Slice() []*Node

type Path 

type Path struct {
	// contains filtered or unexported fields
}

A Path can be a node, or node-edge-node...-edge-node sequence.

func NewPathFromElements 

func NewPathFromElements(elements ...PathElement) *Path

func PathFromNode 

func PathFromNode(node *Node) *Path

PathFromNode creates a path containing a single node

func (*Path) Append 

func (p *Path) Append(path ...PathElement) *Path

Append an edge to the end of the path. The edge must be outgoing from the last node of the path

func (*Path) AppendPath 

func (p *Path) AppendPath(path *Path) *Path

AppendPath can append a single node or a path to the callers path. If the caller does not contain a path, the passed path is copied into the receiver

func (*Path) Clear 

func (p *Path) Clear() *Path

Clear the path

func (*Path) Clone 

func (p *Path) Clone() *Path

Clone returns a copy of the path

func (*Path) First 

func (p *Path) First() *Node

First returns the first node of the path

func (*Path) GetEdge 

func (p *Path) GetEdge(n int) *Edge

GetEdge returns the nth edge

func (*Path) GetNode 

func (p *Path) GetNode(n int) *Node

GetNode returns the nth node

func (*Path) HasPrefix 

func (p *Path) HasPrefix(p1 []PathElement) bool

HasPrefix return if all edges of p1 exist in path

func (*Path) HasPrefixPath 

func (p *Path) HasPrefixPath(p1 *Path) bool

HasPrefixPaths returns if all paths elements of p1 exist in path

func (*Path) IsEmpty 

func (p *Path) IsEmpty() bool

func (*Path) Last 

func (p *Path) Last() *Node

Last returns the last node of the path

func (*Path) NumEdges 

func (p *Path) NumEdges() int

func (*Path) NumNodes 

func (p *Path) NumNodes() int

func (*Path) RemoveFirst 

func (p *Path) RemoveFirst() *Path

RemoveFirst removes the first edge from the graph. If the path has only a node, path becomes empty

func (*Path) RemoveLast 

func (p *Path) RemoveLast() *Path

RemoveLast removes the last edge from the path. If the path has one edge, the path becomes a single node containing the source. If the path has only a node, path becomes empty

func (*Path) SetOnlyNode 

func (p *Path) SetOnlyNode(node *Node) *Path

SetOnlyNode sets the path to a single node

func (*Path) Slice 

func (p *Path) Slice(startNodeIndex, endNodeIndex int) *Path

Slice returns a copy of p partitioned by the args start and end index

func (*Path) String 

func (p *Path) String() string

String returns the path as a string

type PathElement 

type PathElement struct {
	Edge    *Edge
	Reverse bool
}

func NewPathElementsFromEdges 

func NewPathElementsFromEdges(edges []*Edge) []PathElement

func (PathElement) GetSourceNode 

func (p PathElement) GetSourceNode() *Node

func (PathElement) GetTargetNode 

func (p PathElement) GetTargetNode() *Node

type Pattern 

type Pattern []PatternItem

Pattern contains pattern items, with even numbered elements corresponding to nodes, and odd numbered elements corresponding to edges

func (Pattern) FindNodes 

func (pattern Pattern) FindNodes(graph *Graph, symbols map[string]*PatternSymbol) ([]*Node, error)

FindNodes runs the pattern with the given symbols, and returns all the head nodes found

func (Pattern) FindPaths 

func (pattern Pattern) FindPaths(graph *Graph, symbols map[string]*PatternSymbol) (DefaultMatchAccumulator, error)

func (Pattern) GetPlan 

func (pattern Pattern) GetPlan(graph *Graph, symbols map[string]*PatternSymbol) (MatchPlan, error)

GetPlan returns a match execution plan

func (Pattern) GetSymbolNames 

func (pattern Pattern) GetSymbolNames() StringSet

func (Pattern) Run 

func (pattern Pattern) Run(graph *Graph, symbols map[string]*PatternSymbol, result MatchAccumulator) error

type PatternItem 

type PatternItem struct {
	Labels     StringSet
	Properties map[string]interface{}
	// Min=-1 and Max=-1 for variable length
	Min int
	Max int
	// ToLeft is true if this is a relationship of the form <-
	ToLeft bool
	// Undirected is true if this is a relationship of the form --
	Undirected bool
	// Name of the variable associated with this processing node. If the
	// name is defined, it is used to constrain values. If not, it is
	// used to store values
	Name string
}

A PatternItem can be a node or an edge element of a pattern

type PatternSymbol 

type PatternSymbol struct {
	Nodes *NodeSet
	Edges *EdgeSet
}

A PatternSymbol contains either nodes, or edges.

func (*PatternSymbol) Add 

func (p *PatternSymbol) Add(item interface{}) bool

func (*PatternSymbol) AddNode 

func (p *PatternSymbol) AddNode(item *Node)

func (*PatternSymbol) AddPath 

func (p *PatternSymbol) AddPath(path *Path)

func (*PatternSymbol) EdgeSlice 

func (p *PatternSymbol) EdgeSlice() *Path

func (*PatternSymbol) NodeSlice 

func (p *PatternSymbol) NodeSlice() []*Node

type StringSet 

type StringSet struct {
	M map[string]struct{}
}

func NewStringSet 

func NewStringSet(s ...string) StringSet

func (*StringSet) Add 

func (set *StringSet) Add(s ...string) *StringSet

func (*StringSet) AddSet 

func (set *StringSet) AddSet(s StringSet) *StringSet

func (StringSet) Clone 

func (set StringSet) Clone() StringSet

func (StringSet) Has 

func (set StringSet) Has(s string) bool

func (StringSet) HasAll 

func (set StringSet) HasAll(s ...string) bool

func (StringSet) HasAllSet 

func (set StringSet) HasAllSet(s StringSet) bool

func (StringSet) HasAny 

func (set StringSet) HasAny(s ...string) bool

func (StringSet) HasAnySet 

func (set StringSet) HasAnySet(s StringSet) bool

func (StringSet) IsEqual 

func (set StringSet) IsEqual(s StringSet) bool

func (StringSet) Len 

func (set StringSet) Len() int

func (StringSet) MarshalJSON 

func (set StringSet) MarshalJSON() ([]byte, error)

func (*StringSet) Remove 

func (set *StringSet) Remove(s ...string) *StringSet

func (StringSet) Slice 

func (set StringSet) Slice() []string

func (StringSet) SortedSlice 

func (set StringSet) SortedSlice() []string

func (StringSet) String 

func (set StringSet) String() string

func (*StringSet) UnmarshalJSON 

func (set *StringSet) UnmarshalJSON(in []byte) error

type WithNativeValue 

type WithNativeValue interface {
	GetNativeValue() interface{}
}

WithNativeValue is used to return a native value for property values. If the property value implements this interface, the underlying native value for indexing and comparison is obtained from this interface.

type WithProperties 

type WithProperties interface {
	GetProperty(key string) (interface{}, bool)
}

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.