README
¶
graph
Simple graph with a parallel node walker
Usage
A graph is constructed using a series of linkers, each linker containing a single node. Each linker by default has one input and one output connector, which might be used to connect to other linkers:
linker1.Link(linker1)
or
linker1.Connect(linker2, linker1.Connector(graph.InputName), linker2.Connector(graph.OutputName, graph.OutputType))
Once a chain has been finalized, a starting linker can be selected to act as the first root to be used when walking over the graph. This root can be used to create a walker, which upon creation will find any other roots in the graph, and calculate the total number of nodes in it. Walking the graph will produce a channel, which will emit a new item for each node. Any processing of these items can be done concurrently, since nodes will wait for their dependencies to finish processing. The user has to notify the walker by closing the item once processing has finished. Once all nodes have been walked, the channel will be closed.
w := graph.NewWalker(root)
for wd := range w.Walk() {
go func(wd graph.WalkData) {
defer wd.Close()
// Do whatever operation can be identified by the current node
}(wd)
}
A complete example can be read here
Documentation
¶
Overview ¶
Example ¶
package main
import (
"fmt"
"math/rand"
"github.com/urandom/graph"
"github.com/urandom/graph/base"
)
type Processor interface {
Process(wd graph.WalkData, output chan<- int)
Result() int
}
type RandomNumberNode struct {
graph.Node
result int
}
type MultiplyNode struct {
graph.Node
result int
}
type SummingNode struct {
graph.Node
result int
}
func (n *RandomNumberNode) Process(wd graph.WalkData, output chan<- int) {
n.result = rand.Intn(50-10) + 10
wd.Close()
}
func (n RandomNumberNode) Result() int {
return n.result
}
func (n *MultiplyNode) Process(wd graph.WalkData, output chan<- int) {
parent := wd.Parents[0]
if p, ok := parent.Node.(Processor); ok {
n.result = p.Result()*rand.Intn(10-1) + 1
}
wd.Close()
}
func (n MultiplyNode) Result() int {
return n.result
}
func (n *SummingNode) Process(wd graph.WalkData, output chan<- int) {
for _, parent := range wd.Parents {
if p, ok := parent.Node.(Processor); ok {
n.result += p.Result()
}
}
wd.Close()
output <- n.result
}
func (n SummingNode) Result() int {
return n.result
}
func main() {
root := CreateGraph()
walker := graph.NewWalker(root)
data := walker.Walk()
output := make(chan int)
for wd := range data {
if p, ok := wd.Node.(Processor); ok {
go p.Process(wd, output)
} else {
wd.Close()
}
}
select {
case r := <-output:
fmt.Println(r)
}
}
/*
The produced graph:
0 - 2 - 3
1 - - /
*/
func CreateGraph() graph.Linker {
linkers := make([]graph.Linker, 4)
for i := range linkers {
l := base.NewLinker()
switch i {
case 0:
l.Data = &RandomNumberNode{Node: l.Data}
case 1:
l.Data = &RandomNumberNode{Node: l.Data}
case 2:
l.Data = &MultiplyNode{Node: l.Data}
l.Connect(linkers[0], l.Connector(graph.InputName), linkers[0].Connector(graph.OutputName, graph.OutputType))
case 3:
c := base.NewInputConnector("aux")
l.InputConnectors[c.Name()] = c
l.Data = &SummingNode{Node: l.Data}
l.Connect(linkers[1], l.Connector(graph.InputName), linkers[1].Connector(graph.OutputName, graph.OutputType))
l.Connect(linkers[2], l.Connector(c.Name()), linkers[2].Connector(graph.OutputName, graph.OutputType))
}
linkers[i] = l
}
return linkers[0]
}
Output:
Index ¶
Examples ¶
Constants ¶
const ( // InputType represents the input type of a connector InputType ConnectorType = iota // OutputType represents the output type of a connector OutputType // InputName is the name of the default input connector InputName ConnectorName = "Input" // OutputName is the name of the default output connector OutputName ConnectorName = "Output" )
Variables ¶
var ( ErrSameConnectorType = errors.New("Two connectors of the same type cannot be linked together") ErrInvalidConnector = errors.New("The given connector is invalid") )
Functions ¶
func RegisterLinker ¶
func RegisterLinker(name string, constructor LinkerJSONConstructor)
RegisterLinker allows the creation of Linkers by the given name. If it is called twice by the same name, or if the constructor is nil, it panics
Types ¶
type Connector ¶
type Connector interface {
// Type returns the connector's type
Type() ConnectorType
// Name returns the connector's name
Name() ConnectorName
// Target returns the linker and connector that are connected to this one
Target() (Linker, Connector)
// Connect connects the target linker and connector to this one. It only
// setups the link on its own end, the linker itself setups the reciprocal
// connection. It will return an error if the target connector is of the
// same type, or if the target connector is nil
Connect(target Linker, connector Connector) error
// Disconnect breaks a connection with any linker that's currently
// connected. Similarly to the connect method, it only removes the link on
// its own end
Disconnect()
}
Connector represents an input or output point via which a linker can connect to its siblings within a graph
type ConnectorName ¶
type ConnectorName string
type ConnectorType ¶
type ConnectorType int
ConnectorType is the type of connection a particular connector holds in relation to its linker
type JSONTemplateData ¶
type JSONTemplateData struct {
Args []string
}
The JSONTemplateData is the payload used by ProcessJSON when dealing with text/template data
type Linker ¶
type Linker interface {
// Node returns the underlying node
Node() Node
// Connect connects to the target linker, via the current's source
// connector and the target's sink connector. It returns an error if the
// sink connector is of the same type as the source connector, or if any
// one of them is nil
Connect(target Linker, source, sink Connector) error
// Disconnect breaks the connection to any linker that's currently
// connected to the source connector
Disconnect(source Connector)
// Link is a helper method that connects the linker to the target via the
// default output connector and the target's default input connector
Link(target Linker)
// Unlink disconnects any linker that's connected to default output
// connector
Unlink()
// Connector returns the linker's connector of the given name and type. If
// no type is provided, it returns the input connector for the given name
Connector(name ConnectorName, kind ...ConnectorType) Connector
// Connectors returns all connnectors of a given type. If no type is
// provided, it returns the input connectors
Connectors(kind ...ConnectorType) []Connector
// Connection is a helper method that returns the given connector's target
// linker and connector. If no connector is supplied, it uses the default
// input connector
Connection(source ...Connector) (Linker, Connector)
}
Linker is a node container that defines its position within its siblings in a graph
func ProcessJSON ¶
func ProcessJSON(input interface{}, templateData *JSONTemplateData) (roots []Linker, err error)
ProcessJSON converts the input into a graph and returns the root linkers, or an error. The input may be a string, byte array, io.Reader, or *json.Decoder. Any other type will cause a panic. If the input is not a json decoder, and JSONTemplateData is not nil, the input is parsed using text/template. JSONTemplateData serves as the payload when parsing.
The input is a list (not a json array) or one or more graph roots. A linker is represented using a json object. The "Name" property holds the name of a registered Linker type, and the "Options" value is passed to the constructor function. It contains an object of "Outputs", each key being an output connector name, and the value being the connected Linker. A json linker may contain a "ReferenceId", which may be used by another linker to link to it (useful when representing a separate branch). In such a case, the parent linker in the separate branch will have a linker is defined by "ReferenceTo", as oppsosed to a "Name" and "Options". The "ReferenceTo" value corresponds to the "ReferenceId" value of the joining linker. Finally, a json linker may contain an "Input" property, which designes the input connector its parent is connected to. It may be omitted when the default is used.
{
"Name": "Load",
"Options": {
"Path": "{{ index .Args 0 }}"
},
"Outputs": {
"Output": {
"Name": "Convolution",
"Options": {
"Kernel": [-1, -1, -1, -1, 8, -1, -1, -1, -1],
"Noralize": true
},
"Outputs": {
"Output": {
"Name": "Save",
"Options": {
"Path": "{{ if gt (len .Args) 1 }}{{ index .Args 1 }}{{ else }}/tmp/out.png{{ end }}"
}
}
}
}
}
}
type LinkerJSONConstructor ¶
type LinkerJSONConstructor func(opts json.RawMessage) (Linker, error)
A LinkerJSONConstructor creates a Linker by using the options defined by the raw json message
type Node ¶
type Node interface {
// Id returns the unique id of a node
Id() Id
}
Node is a basic work unit within a graph
type Parent ¶
type Parent struct {
// From is the name of the parent's connector
From ConnectorName
// To is the name of the connector of the current node's linker
To ConnectorName
// Node is the parent
Node Node
}
Parent is a simple representation of the connection between the node and its parent
type Visitor ¶
Visitor keeps track of which nodes have already been visited during a walk
type WalkData ¶
type WalkData struct {
// Node is the current node being visited
Node Node
// Parents contains the Parents of the node
Parents []Parent
// contains filtered or unexported fields
}
WalkData represents the data that will be sent through the walk channel
func NewWalkData ¶
NewWalkData creates a new data object. Used by the walker
type Walker ¶
type Walker struct {
// contains filtered or unexported fields
}
Walker helps traverse a graph
func NewWalker ¶
NewWalker creates a new walker with a given linker as a starting point of the traversal. If the starting point contains ancestors, they will not be taken into account when counting and traversing the graph. It will immediately find all other roots and count all nodes in the graph.
A new walker has to be created if the structure of the graph changes
Source Files
Directories