| // 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 |
| } |