graph/encoding/dot/decode_test.go

// Copyright ©2017 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package dot

import (
	"fmt"
	"testing"

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

func TestRoundTrip(t *testing.T) {
	golden := []struct {
		want     string
		directed bool
	}{
		{
			want:     directed,
			directed: true,
		},
		{
			want:     undirected,
			directed: false,
		},
		{
			want:     directedID,
			directed: true,
		},
		{
			want:     undirectedID,
			directed: false,
		},
		{
			want:     directedWithPorts,
			directed: true,
		},
		{
			want:     undirectedWithPorts,
			directed: false,
		},
		{
			want:     directedAttrs,
			directed: true,
		},
		{
			want:     undirectedAttrs,
			directed: false,
		},
	}
	for i, g := range golden {
		var dst encoding.Builder
		if g.directed {
			dst = newDotDirectedGraph()
		} else {
			dst = newDotUndirectedGraph()
		}
		data := []byte(g.want)
		if err := Unmarshal(data, dst); err != nil {
			t.Errorf("i=%d: unable to unmarshal DOT graph; %v", i, err)
			continue
		}
		buf, err := Marshal(dst, "", "", "\t")
		if err != nil {
			t.Errorf("i=%d: unable to marshal graph; %v", i, dst)
			continue
		}
		got := string(buf)
		if got != g.want {
			t.Errorf("i=%d: graph content mismatch; want:\n%s\n\ngot:\n%s", i, g.want, got)
			continue
		}
	}
}

const directed = `strict digraph {
	graph [
		outputorder=edgesfirst
	];
	node [
		shape=circle
		style=filled
	];
	edge [
		penwidth=5
		color=gray
	];

	// Node definitions.
	A [label="foo 2"];
	B [label="bar 2"];

	// Edge definitions.
	A -> B [label="baz 2"];
}`

const undirected = `strict graph {
	graph [
		outputorder=edgesfirst
	];
	node [
		shape=circle
		style=filled
	];
	edge [
		penwidth=5
		color=gray
	];

	// Node definitions.
	A [label="foo 2"];
	B [label="bar 2"];

	// Edge definitions.
	A -- B [label="baz 2"];
}`

const directedID = `strict digraph G {
	// Node definitions.
	A;
	B;

	// Edge definitions.
	A -> B;
}`

const undirectedID = `strict graph H {
	// Node definitions.
	A;
	B;

	// Edge definitions.
	A -- B;
}`

const directedWithPorts = `strict digraph {
	// Node definitions.
	A;
	B;
	C;
	D;
	E;
	F;

	// Edge definitions.
	A:foo -> B:bar;
	A -> C:bar;
	B:foo -> C;
	D:foo:n -> E:bar:s;
	D:e -> F:bar:w;
	E:_ -> F:c;
}`

const undirectedWithPorts = `strict graph {
	// Node definitions.
	A;
	B;
	C;
	D;
	E;
	F;

	// Edge definitions.
	A:foo -- B:bar;
	A -- C:bar;
	B:foo -- C;
	D:foo:n -- E:bar:s;
	D:e -- F:bar:w;
	E:_ -- F:c;
}`

const directedAttrs = `strict digraph {
	node [
		shape=circle
		style=filled
		label="NODE"
	];
	edge [
		penwidth=5
		color=gray
		label=3.14
	];

	// Node definitions.
	A [label=<br>];
	B [label=-14];

	// Edge definitions.
	A -> B [label="hello world"];
}`

const undirectedAttrs = `strict graph {
	node [
		shape=circle
		style=filled
		label="NODE"
	];
	edge [
		penwidth=5
		color=gray
		label=3.14
	];

	// Node definitions.
	A [label=<br>];
	B [label=-14];

	// Edge definitions.
	A -- B [label="hello world"];
}`

func TestChainedEdgeAttributes(t *testing.T) {
	golden := []struct {
		in, want string
		directed bool
	}{
		{
			in:       directedChained,
			want:     directedNonchained,
			directed: true,
		},
		{
			in:       undirectedChained,
			want:     undirectedNonchained,
			directed: false,
		},
	}
	for i, g := range golden {
		var dst encoding.Builder
		if g.directed {
			dst = newDotDirectedGraph()
		} else {
			dst = newDotUndirectedGraph()
		}
		data := []byte(g.in)
		if err := Unmarshal(data, dst); err != nil {
			t.Errorf("i=%d: unable to unmarshal DOT graph; %v", i, err)
			continue
		}
		buf, err := Marshal(dst, "", "", "\t")
		if err != nil {
			t.Errorf("i=%d: unable to marshal graph; %v", i, dst)
			continue
		}
		got := string(buf)
		if got != g.want {
			t.Errorf("i=%d: graph content mismatch; want:\n%s\n\ngot:\n%s", i, g.want, got)
			continue
		}
	}
}

const directedChained = `strict digraph {
	graph [
		outputorder=edgesfirst
	];
	node [
		shape=circle
		style=filled
	];
	edge [
		penwidth=5
		color=gray
	];

	// Node definitions.
	A [label="foo 2"];
	B [label="bar 2"];

	// Edge definitions.
	A -> B -> A [label="baz 2"];
}`

const directedNonchained = `strict digraph {
	graph [
		outputorder=edgesfirst
	];
	node [
		shape=circle
		style=filled
	];
	edge [
		penwidth=5
		color=gray
	];

	// Node definitions.
	A [label="foo 2"];
	B [label="bar 2"];

	// Edge definitions.
	A -> B [label="baz 2"];
	B -> A [label="baz 2"];
}`

const undirectedChained = `graph {
	graph [
		outputorder=edgesfirst
	];
	node [
		shape=circle
		style=filled
	];
	edge [
		penwidth=5
		color=gray
	];

	// Node definitions.
	A [label="foo 2"];
	B [label="bar 2"];
	C [label="bif 2"];

	// Edge definitions.
	A -- B -- C [label="baz 2"];
}`

const undirectedNonchained = `strict graph {
	graph [
		outputorder=edgesfirst
	];
	node [
		shape=circle
		style=filled
	];
	edge [
		penwidth=5
		color=gray
	];

	// Node definitions.
	A [label="foo 2"];
	B [label="bar 2"];
	C [label="bif 2"];

	// Edge definitions.
	A -- B [label="baz 2"];
	B -- C [label="baz 2"];
}`

func TestMultigraphDecoding(t *testing.T) {
	for i, test := range []struct {
		directed bool
		input    string
		expected string
	}{
		{
			directed: true,
			input:    directedMultigraph,
			expected: directedMultigraph,
		},
		{
			directed: false,
			input:    undirectedMultigraph,
			expected: undirectedMultigraph,
		},
		{
			directed: true,
			input:    directedSelfLoopMultigraph,
			expected: directedSelfLoopMultigraph,
		},
		{
			directed: false,
			input:    undirectedSelfLoopMultigraph,
			expected: undirectedSelfLoopMultigraph,
		},
	} {
		var dst encoding.MultiBuilder
		if test.directed {
			dst = multi.NewDirectedGraph()
		} else {
			dst = multi.NewUndirectedGraph()
		}

		if err := UnmarshalMulti([]byte(test.input), dst); err != nil {
			t.Errorf("i=%d: unable to unmarshal DOT graph; %v", i, err)
			continue
		}
		buf, err := MarshalMulti(dst, "", "", "\t")
		if err != nil {
			t.Errorf("i=%d: unable to marshal graph; %v", i, dst)
			continue
		}
		actual := string(buf)
		if actual != test.expected {
			t.Errorf("i=%d: graph content mismatch; want:\n%s\n\nactual:\n%s", i, test.expected, actual)
			continue
		}
	}
}

func TestMultigraphLineIDsharing(t *testing.T) {
	for i, test := range []struct {
		directed bool
		lines    []multi.Line
		expected string
	}{
		{
			directed: true,
			lines: []multi.Line{
				{F: multi.Node(0), T: multi.Node(1), UID: 0},
				{F: multi.Node(0), T: multi.Node(1), UID: 1},
				{F: multi.Node(0), T: multi.Node(2), UID: 0},
				{F: multi.Node(2), T: multi.Node(0), UID: 0},
			},
			expected: directedMultigraph,
		},
		{
			directed: false,
			lines: []multi.Line{
				{F: multi.Node(0), T: multi.Node(1), UID: 0},
				{F: multi.Node(0), T: multi.Node(1), UID: 1},
				{F: multi.Node(0), T: multi.Node(2), UID: 0},
				{F: multi.Node(0), T: multi.Node(2), UID: 1},
			},
			expected: undirectedMultigraph,
		},
		{
			directed: true,
			lines: []multi.Line{
				{F: multi.Node(0), T: multi.Node(0), UID: 0},
				{F: multi.Node(0), T: multi.Node(0), UID: 1},
				{F: multi.Node(1), T: multi.Node(1), UID: 0},
				{F: multi.Node(1), T: multi.Node(1), UID: 1},
			},
			expected: directedSelfLoopMultigraph,
		},
		{
			directed: false,
			lines: []multi.Line{
				{F: multi.Node(0), T: multi.Node(0), UID: 0},
				{F: multi.Node(0), T: multi.Node(0), UID: 1},
				{F: multi.Node(1), T: multi.Node(1), UID: 0},
				{F: multi.Node(1), T: multi.Node(1), UID: 1},
			},
			expected: undirectedSelfLoopMultigraph,
		},
	} {
		var dst encoding.MultiBuilder
		if test.directed {
			dst = multi.NewDirectedGraph()
		} else {
			dst = multi.NewUndirectedGraph()
		}

		for _, l := range test.lines {
			dst.SetLine(l)
		}

		buf, err := MarshalMulti(dst, "", "", "\t")
		if err != nil {
			t.Errorf("i=%d: unable to marshal graph; %v", i, dst)
			continue
		}
		actual := string(buf)
		if actual != test.expected {
			t.Errorf("i=%d: graph content mismatch; want:\n%s\n\nactual:\n%s", i, test.expected, actual)
			continue
		}
	}
}

const directedMultigraph = `digraph {
	// Node definitions.
	0;
	1;
	2;

	// Edge definitions.
	0 -> 1;
	0 -> 1;
	0 -> 2;
	2 -> 0;
}`

const undirectedMultigraph = `graph {
	// Node definitions.
	0;
	1;
	2;

	// Edge definitions.
	0 -- 1;
	0 -- 1;
	0 -- 2;
	0 -- 2;
}`

const directedSelfLoopMultigraph = `digraph {
	// Node definitions.
	0;
	1;

	// Edge definitions.
	0 -> 0;
	0 -> 0;
	1 -> 1;
	1 -> 1;
}`

const undirectedSelfLoopMultigraph = `graph {
	// Node definitions.
	0;
	1;

	// Edge definitions.
	0 -- 0;
	0 -- 0;
	1 -- 1;
	1 -- 1;
}`

// Below follows a minimal implementation of a graph capable of validating the
// round-trip encoding and decoding of DOT graphs with nodes and edges
// containing DOT attributes.

// dotDirectedGraph extends simple.DirectedGraph to add NewNode and NewEdge
// methods for creating user-defined nodes and edges.
//
// dotDirectedGraph implements the encoding.Builder and the dot.Graph
// interfaces.
type dotDirectedGraph struct {
	*simple.DirectedGraph
	id                string
	graph, node, edge attributes
}

// newDotDirectedGraph returns a new directed capable of creating user-defined
// nodes and edges.
func newDotDirectedGraph() *dotDirectedGraph {
	return &dotDirectedGraph{DirectedGraph: simple.NewDirectedGraph()}
}

// NewNode returns a new node with a unique node ID for the graph.
func (g *dotDirectedGraph) NewNode() graph.Node {
	return &dotNode{Node: g.DirectedGraph.NewNode()}
}

// NewEdge returns a new Edge from the source to the destination node.
func (g *dotDirectedGraph) NewEdge(from, to graph.Node) graph.Edge {
	return &dotEdge{Edge: g.DirectedGraph.NewEdge(from, to)}
}

// DOTAttributers implements the dot.Attributers interface.
func (g *dotDirectedGraph) DOTAttributers() (graph, node, edge encoding.Attributer) {
	return g.graph, g.node, g.edge
}

// DOTAttributeSetters implements the dot.AttributeSetters interface.
func (g *dotDirectedGraph) DOTAttributeSetters() (graph, node, edge encoding.AttributeSetter) {
	return &g.graph, &g.node, &g.edge
}

// SetDOTID sets the DOT ID of the graph.
func (g *dotDirectedGraph) SetDOTID(id string) {
	g.id = id
}

// DOTID returns the DOT ID of the graph.
func (g *dotDirectedGraph) DOTID() string {
	return g.id
}

// dotUndirectedGraph extends simple.UndirectedGraph to add NewNode and NewEdge
// methods for creating user-defined nodes and edges.
//
// dotUndirectedGraph implements the encoding.Builder and the dot.Graph
// interfaces.
type dotUndirectedGraph struct {
	*simple.UndirectedGraph
	id                string
	graph, node, edge attributes
}

// newDotUndirectedGraph returns a new undirected capable of creating user-
// defined nodes and edges.
func newDotUndirectedGraph() *dotUndirectedGraph {
	return &dotUndirectedGraph{UndirectedGraph: simple.NewUndirectedGraph()}
}

// NewNode adds a new node with a unique node ID to the graph.
func (g *dotUndirectedGraph) NewNode() graph.Node {
	return &dotNode{Node: g.UndirectedGraph.NewNode()}
}

// NewEdge returns a new Edge from the source to the destination node.
func (g *dotUndirectedGraph) NewEdge(from, to graph.Node) graph.Edge {
	return &dotEdge{Edge: g.UndirectedGraph.NewEdge(from, to)}
}

// DOTAttributers implements the dot.Attributers interface.
func (g *dotUndirectedGraph) DOTAttributers() (graph, node, edge encoding.Attributer) {
	return g.graph, g.node, g.edge
}

// DOTUnmarshalerAttrs implements the dot.UnmarshalerAttrs interface.
func (g *dotUndirectedGraph) DOTAttributeSetters() (graph, node, edge encoding.AttributeSetter) {
	return &g.graph, &g.node, &g.edge
}

// SetDOTID sets the DOT ID of the graph.
func (g *dotUndirectedGraph) SetDOTID(id string) {
	g.id = id
}

// DOTID returns the DOT ID of the graph.
func (g *dotUndirectedGraph) DOTID() string {
	return g.id
}

// dotNode extends simple.Node with a label field to test round-trip encoding
// and decoding of node DOT label attributes.
type dotNode struct {
	graph.Node
	dotID string
	// Node label.
	Label string
}

// DOTID returns the node's DOT ID.
func (n *dotNode) DOTID() string {
	return n.dotID
}

// 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 {
	if attr.Key != "label" {
		return fmt.Errorf("unable to unmarshal node DOT attribute with key %q", attr.Key)
	}
	n.Label = attr.Value
	return nil
}

// Attributes returns the DOT attributes of the node.
func (n *dotNode) Attributes() []encoding.Attribute {
	if len(n.Label) == 0 {
		return nil
	}
	return []encoding.Attribute{{
		Key:   "label",
		Value: n.Label,
	}}
}

type dotPortLabels struct {
	Port, Compass string
}

// dotEdge extends simple.Edge with a label field to test round-trip encoding and
// decoding of edge DOT label attributes.
type dotEdge struct {
	graph.Edge
	// Edge label.
	Label          string
	FromPortLabels dotPortLabels
	ToPortLabels   dotPortLabels
}

// SetAttribute sets a DOT attribute.
func (e *dotEdge) SetAttribute(attr encoding.Attribute) error {
	if attr.Key != "label" {
		return fmt.Errorf("unable to unmarshal node DOT attribute with key %q", attr.Key)
	}
	e.Label = attr.Value
	return nil
}

// Attributes returns the DOT attributes of the edge.
func (e *dotEdge) Attributes() []encoding.Attribute {
	if len(e.Label) == 0 {
		return nil
	}
	return []encoding.Attribute{{
		Key:   "label",
		Value: e.Label,
	}}
}

func (e *dotEdge) SetFromPort(port, compass string) error {
	e.FromPortLabels.Port = port
	e.FromPortLabels.Compass = compass
	return nil
}

func (e *dotEdge) SetToPort(port, compass string) error {
	e.ToPortLabels.Port = port
	e.ToPortLabels.Compass = compass
	return nil
}

func (e *dotEdge) FromPort() (port, compass string) {
	return e.FromPortLabels.Port, e.FromPortLabels.Compass
}

func (e *dotEdge) ToPort() (port, compass string) {
	return e.ToPortLabels.Port, e.ToPortLabels.Compass
}

// attributes is a helper for global attributes.
type attributes []encoding.Attribute

func (a attributes) Attributes() []encoding.Attribute {
	return []encoding.Attribute(a)
}
func (a *attributes) SetAttribute(attr encoding.Attribute) error {
	*a = append(*a, attr)
	return nil
}

const undirectedSelfLoopGraph = `graph {
	// Node definitions.
	0;
	1;

	// Edge definitions.
	0 -- 0;
	1 -- 1;
}`

const directedSelfLoopGraph = `digraph {
	// Node definitions.
	0;
	1;

	// Edge definitions.
	0 -> 0;
	1 -> 1;
}`

func TestSelfLoopSimple(t *testing.T) {
	for _, test := range []struct {
		dst func() encoding.Builder
		src string
	}{
		{
			dst: func() encoding.Builder { return simple.NewUndirectedGraph() },
			src: undirectedSelfLoopGraph,
		},
		{
			dst: func() encoding.Builder { return simple.NewDirectedGraph() },
			src: directedSelfLoopGraph,
		},
	} {
		dst := test.dst()
		message, panicked := panics(func() {
			err := Unmarshal([]byte(test.src), dst)
			if err == nil {
				t.Errorf("expected error for self loop addition to %T", dst)
			}
		})
		if panicked {
			t.Errorf("unexpected panic for self loop addition to %T: %s", dst, message)
		}
	}
}

func panics(fn func()) (message string, ok bool) {
	defer func() {
		r := recover()
		message = fmt.Sprint(r)
		ok = r != nil
	}()
	fn()
	return
}