graph/encoding/dot: improve documentation and add more examples

[umarcor]

What are you trying to do?

I am reading a simple directed graph with graph/encoding/dot:

package main

import (
	"fmt"

	"gonum.org/v1/gonum/graph/encoding/dot"
	"gonum.org/v1/gonum/graph/simple"
)

func main() {
	g:= `strict digraph {
		// Node definitions.
		A [label="foo 2"];
		B [label="bar 2"];
		// Edge definitions.
		A -> B [label="baz 2"];
	}`

	dst := simple.NewDirectedGraph()
	err := dot.Unmarshal([]byte(g), dst)
	if err != nil {
		fmt.Println(err)
	}
	fmt.Println(dst)

Now, I would like to build a map[string]int with the labels of the Nodes, i.e.:

"foo 2": <ID of A>
"bar 2": <ID of B>

What did you try?

i := dst.Nodes()
i.Next()
fmt.Println(i.Node())
i.Next()
fmt.Println(i.Node())

Which generates:

&{map[1:1 0:0] map[0:map[1:0xc0000468e0] 1:map[]] map[0:map[] 1:map[0:0xc0000468e0]] {1 map[0:{} 1:{}] map[]}}
1
0

How does Gonum not allow you to achieve your goal?

I'd expect attributes, such as the labels, to be accesible from type Node.

What version of Go and Gonum are you using?

I tried docker image golang:alpine and natively on a Win10 host:

# go version
go version go1.11.4 windows/amd64
# (cd $(go env GOPATH)/src/gonum.org/v1/gonum && git rev-parse HEAD)
ca4d35bc590a993218319fd6db3a0238fd20e3cc

Is this feature absent from the current master?

I don't know. I'd expect it to be supported, but I cannot find any reference or example about how to do it.

Are you able to help contribute the feature?

I think that this is either lack of knowledge on my side, or lack of documentation.

[kortschak]

Thank you for the report. Yes, the encoding/dot documentation could be improved here, and some examples added.

The graphs in simple do not provide the hooks necessary for dot to annotate them with attributes or DOT IDs. These hooks must be added to your graph. You can either implement the entire graph with them, or use embedding to achieve the same thing. There are many example in the test code that show how this works, but here is a working example that does what your example tries to achieve.

package main

import (
	"fmt"
	"log"

	"gonum.org/v1/gonum/graph"
	"gonum.org/v1/gonum/graph/encoding"
	"gonum.org/v1/gonum/graph/encoding/dot"
	"gonum.org/v1/gonum/graph/simple"
)

type dotEncodingGraph struct {
	*simple.DirectedGraph
}

func (g dotEncodingGraph) NewNode() graph.Node {
	return &dotNode{Node: g.DirectedGraph.NewNode(), attrs: make(map[string]string)}
}

type dotNode struct {
	graph.Node
	dotID string
	attrs map[string]string
}

// SetDOTID sets a DOT ID.
func (n *dotNode) SetDOTID(id string) {
	n.dotID = id
}

// SetAttribute sets a DOT attribute.
func (n *dotNode) SetAttribute(attr encoding.Attribute) error {
	n.attrs[attr.Key] = attr.Value
	return nil
}

func (g dotEncodingGraph) NewEdge(from, to graph.Node) graph.Edge {
	return &dotEdge{Edge: g.DirectedGraph.NewEdge(from, to), attrs: make(map[string]string)}
}

type dotEdge struct {
	graph.Edge
	attrs map[string]string
}

// SetAttribute sets a DOT attribute.
func (e *dotEdge) SetAttribute(attr encoding.Attribute) error {
	e.attrs[attr.Key] = attr.Value
	return nil
}

func main() {
	g := `strict digraph {
		// Node definitions.
		A [label="foo 2"];
		B [label="bar 2"];
		// Edge definitions.
		A -> B [label="baz 2"];
	}`

	dst := simple.NewDirectedGraph()
	err := dot.Unmarshal([]byte(g), dotEncodingGraph{dst})
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("%+v\n", dst)

	for _, n := range graph.NodesOf(dst.Nodes()) {
		fmt.Printf("%+v\n", n)
	}
	for _, e := range graph.EdgesOf(dst.Edges()) {
		fmt.Printf("%+v\n", e)
	}
}

&{nodes:map[0:0xc000088570 1:0xc000088630] from:map[0:map[1:0xc000090300] 1:map[]] to:map[0:map[] 1:map[0:0xc000090300]] nodeIDs:{maxID:1 used:map[0:{} 1:{}] free:map[]}}
&{Node:0 dotID:A attrs:map[label:foo 2]}
&{Node:1 dotID:B attrs:map[label:bar 2]}
&{Edge:0xc0000902e0 attrs:map[label:baz 2]}

The new types, dotNode and dotEdge provide the hooks for the graph building code to annotate them with attributes, and the dotEncodingGraph ensures that these types are returned by the graph when the unmarshaling code is being run to add to the graph.

The reason we do it this way is to allow flexibility in behaviour of the encoding/decoding and to minimise the complexity of the graph types we provide.

[umarcor]

Thank you for the report. Yes, the encoding/dot documentation could be improved here, and some examples added.

Thank you for the very useful reply and example.

There are many example in the test code that show how this works

I assumed, while looking at the tests, that there are many more features which are actually supported than it might seem at first sight. However, from my little to no knowledge about graph theory, it is hard to grasp the relevant pieces.

The new types, dotNode and dotEdge provide the hooks for the graph building code to annotate them with attributes, and the dotEncodingGraph ensures that these types are returned by the graph when the unmarshaling code is being run to add to the graph.

This was precisely what I was missing. I had found https://godoc.org/gonum.org/v1/gonum/graph/encoding, but I did not know how to mix those Attribute and AttributeSetter types with simple example I had. Thanks, once again.

The reason we do it this way is to allow flexibility in behaviour of the encoding/decoding and to minimise the complexity of the graph types we provide.

I understand it, and I find it to be very elegant. However, this style of having lots of very small and simple types/funcs is a nightmare for the newcomer. This is because some good understanding of how all the pieces are combined is required in order to compose a rather minimal working example. Anyway, I am aware that I am not exactly the target audience, and the style fits for users targeting heavier workloads.

I understand that it is not easy to oversimplify things when you are focused on very low-level implementation details. So, in case it might be useful, I'd suggest adding a few short posts (or a notebook) about https://github.com/kortschak/graphprac (graph.go, analysis.go and net.go). I think that https://github.com/kortschak/graphprac/blob/master/graph-prac.ipynb is great for users that are ok with relying on kortschak/graphprac. But, from a wider point of view, graphprac is a great not-small not-large project for users that want to learn about gonum/graph.

I'm closing this because the issue is solved. I'm heading to extending the example 😄

[kortschak]

Reopening to improve docs.

[kortschak]

Note that graphprac is purely t class teaching notebook and not how I would do any of this in the real world.

I have been working through the Gonum User Survey responses and one of the main things to take from it is the need for more documentation, including examples and tutorials. This will be an are we will work on. (This is why I have re-opened this).

[umarcor]

Reopening to improve docs.

I'm sorry for closing it before. I did not realize that you had changed the title.

---

Note that graphprac is purely t class teaching notebook and not how I would do any of this in the real world.

My use case is quite simple, so I'm ok with traversing and processing the graph naively. For further insight, I have a dependency graph of some tasks: multiple sources need to be manipulated and mixed in order to generate targets. I want to retrieve a subgraph for each target (node with no output edges, only inputs). Hence, the relevant feature is to preserve labels (which define the names of the taks). I don't need any complex analysis.

For now, I could successfully:

// Read the graph
g := Unmarshal([]byte(src))

// Get a list of targets
tgts := getTargets(g)

// Induce a subgraph for each target
s := induce(g, tgts)

// Marshal and print each of the induced subgraphs:
for _, j := range s {
	fmt.Println("\nSUBGRAPH:")
	printGraph(j)
	b, e := dot.Marshal(j, "", "", "")
	if e == nil {
		fmt.Println(string(b))
	}
}

where

func getTargets(g *simple.DirectedGraph) []graph.Node {
	ns := make([]graph.Node, 0)
	for _, n := range graph.NodesOf(g.Nodes()) {
		if len(graph.NodesOf(g.From(n.ID()))) == 0 {
			ns = append(ns, n)
		}
	}
	return ns
}

func induce(g *simple.DirectedGraph, ns []graph.Node) []*simple.DirectedGraph {
	addNode := func(s *simple.DirectedGraph, n graph.Node) {
		if s.Node(n.ID()) == nil {
			s.AddNode(n)
		}
	}
	var walk func(g, s *simple.DirectedGraph, n graph.Node) []graph.Node
	walk = func(g, s *simple.DirectedGraph, n graph.Node) []graph.Node {
		addNode(s, n)
		if l := graph.NodesOf(g.From(n.ID())); len(l) > 0 {
			for _, x := range l {
				addNode(s, x)
				s.SetEdge(g.NewEdge(n, x))
				walk(g, s, x)
			}
		}
		return nil
	}
	ReverseEdges(g)
	o := make([]*simple.DirectedGraph, 0)
	for _, n := range ns {
		s := simple.NewDirectedGraph()
		walk(g, s, n)
		ReverseEdges(s)
		o = append(o, s)
	}
	ReverseEdges(g)
	return o
}

func ReverseEdges(g *simple.DirectedGraph) {
	for _, e := range graph.EdgesOf(g.Edges()) {
		// FIXME The attributes of the edge are not honored because the generic
		// implementations of ReversedEdge and/or SetEdge do not include them.
		g.SetEdge(e.ReversedEdge())
		g.RemoveEdge(e.From().ID(), e.To().ID())
	}
}

func printGraph(g *simple.DirectedGraph) {
	for _, n := range graph.NodesOf(g.Nodes()) {
		fmt.Printf("%+v\n", n)
	}
	for _, e := range graph.EdgesOf(g.Edges()) {
		fmt.Printf("%+v\n", e)
	}
}

The 'induction' works, subgraphs are properly generated and the labels are retained in the nodes. However, on the one hand, labels on the edges are lost, as commented in the code above. On the other hand, labels on the nodes are lost when data is marshaled. For example:

	src := `strict digraph {
		// Node definitions.
		A [label="foo 2"];
		B [label="bar 2"];
		// Edge definitions.
		A -> B [label="baz 2"];
		A -> C -> E -> F;
		C -> D;
		B -> F;
	}`

SUBGRAPH:
&{Node:4 dotID:F attrs:map[]}
&{Node:1 dotID:B attrs:map[label:bar 2]}
&{Node:0 dotID:A attrs:map[label:foo 2]}
&{Node:3 dotID:E attrs:map[]}
&{Node:2 dotID:C attrs:map[]}
{F:0xc0001307b0 T:0xc000130870}
{F:0xc0001306f0 T:0xc0001307b0}
{F:0xc000130600 T:0xc000130870}
{F:0xc000130540 T:0xc000130600}
{F:0xc000130540 T:0xc0001306f0}
strict digraph {
// Node definitions.
0;
1;
2;
3;
4;

// Edge definitions.
0 -> 1;
0 -> 2;
1 -> 4;
2 -> 3;
3 -> 4;
}

SUBGRAPH:
&{Node:5 dotID:D attrs:map[]}
&{Node:2 dotID:C attrs:map[]}
&{Node:0 dotID:A attrs:map[label:foo 2]}
{F:0xc000130540 T:0xc0001306f0}
{F:0xc0001306f0 T:0xc0001309c0}
strict digraph {
// Node definitions.
0;
2;
5;

// Edge definitions.
0 -> 2;
2 -> 5;
}

I'd like to ask three questions:

• Is there any built-in algorithm to replace the 'induce' function (my version, not the one in graphprac)? I tried with Dominators from graph/flow and DijkstraAllPaths from graph/path, but none of them seem to fit this use case.
• Although I don't need it, would defining From(), To() and ReversedEdge() for dotEdge similarly to how it is done in https://github.com/gonum/gonum/blob/master/graph/community/louvain_common.go#L254-L263 fix the issue with attributes on the edges being lost? I saw that that's what you did in graph: make edges and lines reversible #867.
• I believe that the fix for Marshal is similar to the one for the edges, i.e., that I need to define some additional functions. But I'm lost.

[kortschak]

Answering your questions here, but if there are more, please take them to gonum-dev.

1. No. Though TBH, I don't entirely understand what that is trying to do. There are generic graph traversal functions in traverse that might be helpful.

2. Yes, adding ReversedEdge to dotEdge will fix that. However, there is an easier way to reverse the edges of a graph; wrap your graph in a struct that swaps the order of nodes in Edge and HasEdgeFromTo and make From call the embedded graph's To and vice versa.

3. If you take this, with more detail, to gonum-dev, I can find some time to help you out with this. ISTM that a combination of topo.Sort to get the topological sort and then traverse.DepthFirst.Walk for each node in order from the topological sort not already visited would be a good way of doing it. This requires a graph inversion wrapper struct.