// Copyright ©2015 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 (
	"bytes"
	"os/exec"
	"testing"

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

// intset is an integer set.
type intset map[int64]struct{}

func linksTo(i ...int64) intset {
	if len(i) == 0 {
		return nil
	}
	s := make(intset)
	for _, v := range i {
		s[v] = struct{}{}
	}
	return s
}

var (
	// Example graph from http://en.wikipedia.org/wiki/File:PageRanks-Example.svg 16:17, 8 July 2009
	// Node identities are rewritten here to use integers from 0 to match with the DOT output.
	pageRankGraph = []intset{
		0:  nil,
		1:  linksTo(2),
		2:  linksTo(1),
		3:  linksTo(0, 1),
		4:  linksTo(3, 1, 5),
		5:  linksTo(1, 4),
		6:  linksTo(1, 4),
		7:  linksTo(1, 4),
		8:  linksTo(1, 4),
		9:  linksTo(4),
		10: linksTo(4),
	}

	// Example graph from http://en.wikipedia.org/w/index.php?title=PageRank&oldid=659286279#Power_Method
	powerMethodGraph = []intset{
		0: linksTo(1, 2),
		1: linksTo(3),
		2: linksTo(3, 4),
		3: linksTo(4),
		4: linksTo(0),
	}
)

func directedGraphFrom(g []intset) graph.Directed {
	dg := simple.NewDirectedGraph()
	for u, e := range g {
		for v := range e {
			dg.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
		}
	}
	return dg
}

func undirectedGraphFrom(g []intset) graph.Graph {
	dg := simple.NewUndirectedGraph()
	for u, e := range g {
		for v := range e {
			dg.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
		}
	}
	return dg
}

const alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

type namedNode struct {
	id   int64
	name string
}

func (n namedNode) ID() int64     { return n.id }
func (n namedNode) DOTID() string { return n.name }

func directedNamedIDGraphFrom(g []intset) graph.Directed {
	dg := simple.NewDirectedGraph()
	for u, e := range g {
		u := int64(u)
		nu := namedNode{id: u, name: alpha[u : u+1]}
		for v := range e {
			nv := namedNode{id: v, name: alpha[v : v+1]}
			dg.SetEdge(simple.Edge{F: nu, T: nv})
		}
	}
	return dg
}

func undirectedNamedIDGraphFrom(g []intset) graph.Graph {
	dg := simple.NewUndirectedGraph()
	for u, e := range g {
		u := int64(u)
		nu := namedNode{id: u, name: alpha[u : u+1]}
		for v := range e {
			nv := namedNode{id: v, name: alpha[v : v+1]}
			dg.SetEdge(simple.Edge{F: nu, T: nv})
		}
	}
	return dg
}

type attrNode struct {
	id   int64
	attr []encoding.Attribute
}

func (n attrNode) ID() int64                        { return n.id }
func (n attrNode) Attributes() []encoding.Attribute { return n.attr }

func directedNodeAttrGraphFrom(g []intset, attr [][]encoding.Attribute) graph.Directed {
	dg := simple.NewDirectedGraph()
	for u, e := range g {
		u := int64(u)
		var at []encoding.Attribute
		if u < int64(len(attr)) {
			at = attr[u]
		}
		nu := attrNode{id: u, attr: at}
		for v := range e {
			if v < int64(len(attr)) {
				at = attr[v]
			}
			nv := attrNode{id: v, attr: at}
			dg.SetEdge(simple.Edge{F: nu, T: nv})
		}
	}
	return dg
}

func undirectedNodeAttrGraphFrom(g []intset, attr [][]encoding.Attribute) graph.Graph {
	dg := simple.NewUndirectedGraph()
	for u, e := range g {
		u := int64(u)
		var at []encoding.Attribute
		if u < int64(len(attr)) {
			at = attr[u]
		}
		nu := attrNode{id: u, attr: at}
		for v := range e {
			if v < int64(len(attr)) {
				at = attr[v]
			}
			nv := attrNode{id: v, attr: at}
			dg.SetEdge(simple.Edge{F: nu, T: nv})
		}
	}
	return dg
}

type namedAttrNode struct {
	id   int64
	name string
	attr []encoding.Attribute
}

func (n namedAttrNode) ID() int64                        { return n.id }
func (n namedAttrNode) DOTID() string                    { return n.name }
func (n namedAttrNode) Attributes() []encoding.Attribute { return n.attr }

func directedNamedIDNodeAttrGraphFrom(g []intset, attr [][]encoding.Attribute) graph.Directed {
	dg := simple.NewDirectedGraph()
	for u, e := range g {
		u := int64(u)
		var at []encoding.Attribute
		if u < int64(len(attr)) {
			at = attr[u]
		}
		nu := namedAttrNode{id: u, name: alpha[u : u+1], attr: at}
		for v := range e {
			if v < int64(len(attr)) {
				at = attr[v]
			}
			nv := namedAttrNode{id: v, name: alpha[v : v+1], attr: at}
			dg.SetEdge(simple.Edge{F: nu, T: nv})
		}
	}
	return dg
}

func undirectedNamedIDNodeAttrGraphFrom(g []intset, attr [][]encoding.Attribute) graph.Graph {
	dg := simple.NewUndirectedGraph()
	for u, e := range g {
		u := int64(u)
		var at []encoding.Attribute
		if u < int64(len(attr)) {
			at = attr[u]
		}
		nu := namedAttrNode{id: u, name: alpha[u : u+1], attr: at}
		for v := range e {
			if v < int64(len(attr)) {
				at = attr[v]
			}
			nv := namedAttrNode{id: v, name: alpha[v : v+1], attr: at}
			dg.SetEdge(simple.Edge{F: nu, T: nv})
		}
	}
	return dg
}

type attrEdge struct {
	from, to graph.Node

	attr []encoding.Attribute
}

func (e attrEdge) From() graph.Node                 { return e.from }
func (e attrEdge) To() graph.Node                   { return e.to }
func (e attrEdge) ReversedEdge() graph.Edge         { e.from, e.to = e.to, e.from; return e }
func (e attrEdge) Weight() float64                  { return 0 }
func (e attrEdge) Attributes() []encoding.Attribute { return e.attr }

func directedEdgeAttrGraphFrom(g []intset, attr map[edge][]encoding.Attribute) graph.Directed {
	dg := simple.NewDirectedGraph()
	for u, e := range g {
		u := int64(u)
		for v := range e {
			dg.SetEdge(attrEdge{from: simple.Node(u), to: simple.Node(v), attr: attr[edge{from: u, to: v}]})
		}
	}
	return dg
}

func undirectedEdgeAttrGraphFrom(g []intset, attr map[edge][]encoding.Attribute) graph.Graph {
	dg := simple.NewUndirectedGraph()
	for u, e := range g {
		u := int64(u)
		for v := range e {
			dg.SetEdge(attrEdge{from: simple.Node(u), to: simple.Node(v), attr: attr[edge{from: u, to: v}]})
		}
	}
	return dg
}

type portedEdge struct {
	from, to graph.Node

	fromPort    string
	fromCompass string
	toPort      string
	toCompass   string
}

func (e portedEdge) From() graph.Node { return e.from }
func (e portedEdge) To() graph.Node   { return e.to }
func (e portedEdge) ReversedEdge() graph.Edge {
	e.from, e.to = e.to, e.from
	e.fromPort, e.toPort = e.toPort, e.fromPort
	e.fromCompass, e.toCompass = e.toCompass, e.fromCompass
	return e
}
func (e portedEdge) Weight() float64 { return 0 }

func (e portedEdge) FromPort() (port, compass string) {
	return e.fromPort, e.fromCompass
}
func (e portedEdge) ToPort() (port, compass string) {
	return e.toPort, e.toCompass
}

func directedPortedAttrGraphFrom(g []intset, attr [][]encoding.Attribute, ports map[edge]portedEdge) graph.Directed {
	dg := simple.NewDirectedGraph()
	for u, e := range g {
		u := int64(u)
		var at []encoding.Attribute
		if u < int64(len(attr)) {
			at = attr[u]
		}
		nu := attrNode{id: u, attr: at}
		for v := range e {
			if v < int64(len(attr)) {
				at = attr[v]
			}
			pe := ports[edge{from: u, to: v}]
			pe.from = nu
			pe.to = attrNode{id: v, attr: at}
			dg.SetEdge(pe)
		}
	}
	return dg
}

func undirectedPortedAttrGraphFrom(g []intset, attr [][]encoding.Attribute, ports map[edge]portedEdge) graph.Graph {
	dg := simple.NewUndirectedGraph()
	for u, e := range g {
		u := int64(u)
		var at []encoding.Attribute
		if u < int64(len(attr)) {
			at = attr[u]
		}
		nu := attrNode{id: u, attr: at}
		for v := range e {
			if v < int64(len(attr)) {
				at = attr[v]
			}
			pe := ports[edge{from: u, to: v}]
			pe.from = nu
			pe.to = attrNode{id: v, attr: at}
			dg.SetEdge(pe)
		}
	}
	return dg
}

type graphAttributer struct {
	graph.Graph
	graph encoding.Attributer
	node  encoding.Attributer
	edge  encoding.Attributer
}

func (g graphAttributer) DOTAttributers() (graph, node, edge encoding.Attributer) {
	return g.graph, g.node, g.edge
}

type structuredGraph struct {
	*simple.UndirectedGraph
	sub []Graph
}

func undirectedStructuredGraphFrom(c []edge, g ...[]intset) graph.Graph {
	s := &structuredGraph{UndirectedGraph: simple.NewUndirectedGraph()}
	var base int64
	for i, sg := range g {
		sub := simple.NewUndirectedGraph()
		for u, e := range sg {
			u := int64(u)
			for v := range e {
				ce := simple.Edge{F: simple.Node(u + base), T: simple.Node(v + base)}
				sub.SetEdge(ce)
			}
		}
		s.sub = append(s.sub, namedGraph{id: int64(i), Graph: sub})
		base += int64(len(sg))
	}
	for _, e := range c {
		s.SetEdge(simple.Edge{F: simple.Node(e.from), T: simple.Node(e.to)})
	}
	return s
}

func (g structuredGraph) Structure() []Graph {
	return g.sub
}

type namedGraph struct {
	id int64
	graph.Graph
}

func (g namedGraph) DOTID() string { return alpha[g.id : g.id+1] }

type subGraph struct {
	id int64
	graph.Graph
}

func (g subGraph) ID() int64 { return g.id }
func (g subGraph) Subgraph() graph.Graph {
	return namedGraph(g)
}

func undirectedSubGraphFrom(g []intset, s map[int64][]intset) graph.Graph {
	var base int64
	subs := make(map[int64]subGraph)
	for i, sg := range s {
		sub := simple.NewUndirectedGraph()
		for u, e := range sg {
			u := int64(u)
			for v := range e {
				ce := simple.Edge{F: simple.Node(u + base), T: simple.Node(v + base)}
				sub.SetEdge(ce)
			}
		}
		subs[i] = subGraph{id: i, Graph: sub}
		base += int64(len(sg))
	}

	dg := simple.NewUndirectedGraph()
	for u, e := range g {
		u := int64(u)
		var nu graph.Node
		if sg, ok := subs[u]; ok {
			sg.id += base
			nu = sg
		} else {
			nu = simple.Node(u + base)
		}
		for v := range e {
			var nv graph.Node
			if sg, ok := subs[v]; ok {
				sg.id += base
				nv = sg
			} else {
				nv = simple.Node(v + base)
			}
			dg.SetEdge(simple.Edge{F: nu, T: nv})
		}
	}
	return dg
}

var encodeTests = []struct {
	name string
	g    graph.Graph

	prefix string

	want string
}{
	// Empty graph.
	{
		name: "Empty Undirected",
		g:    simple.NewUndirectedGraph(),
		want: `strict graph "Empty Undirected" {
}`,
	},
	{
		name: "Empty Directed",
		g:    simple.NewDirectedGraph(),
		want: `strict digraph "Empty Directed" {
}`,
	},

	// Basic graph.Graph handling.
	{
		name: "PageRank",
		g:    directedGraphFrom(pageRankGraph),

		want: `strict digraph PageRank {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;
	5;
	6;
	7;
	8;
	9;
	10;

	// Edge definitions.
	1 -> 2;
	2 -> 1;
	3 -> 0;
	3 -> 1;
	4 -> 1;
	4 -> 3;
	4 -> 5;
	5 -> 1;
	5 -> 4;
	6 -> 1;
	6 -> 4;
	7 -> 1;
	7 -> 4;
	8 -> 1;
	8 -> 4;
	9 -> 4;
	10 -> 4;
}`,
	},
	{
		g: undirectedGraphFrom(pageRankGraph),

		want: `strict graph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;
	5;
	6;
	7;
	8;
	9;
	10;

	// Edge definitions.
	0 -- 3;
	1 -- 2;
	1 -- 3;
	1 -- 4;
	1 -- 5;
	1 -- 6;
	1 -- 7;
	1 -- 8;
	3 -- 4;
	4 -- 5;
	4 -- 6;
	4 -- 7;
	4 -- 8;
	4 -- 9;
	4 -- 10;
}`,
	},
	{
		g: directedGraphFrom(powerMethodGraph),

		want: `strict digraph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -> 1;
	0 -> 2;
	1 -> 3;
	2 -> 3;
	2 -> 4;
	3 -> 4;
	4 -> 0;
}`,
	},
	{
		g: undirectedGraphFrom(powerMethodGraph),

		want: `strict graph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -- 1;
	0 -- 2;
	0 -- 4;
	1 -- 3;
	2 -- 3;
	2 -- 4;
	3 -- 4;
}`,
	},
	{
		g:      undirectedGraphFrom(powerMethodGraph),
		prefix: "# ",

		want: `# strict graph {
# 	// Node definitions.
# 	0;
# 	1;
# 	2;
# 	3;
# 	4;
#
# 	// Edge definitions.
# 	0 -- 1;
# 	0 -- 2;
# 	0 -- 4;
# 	1 -- 3;
# 	2 -- 3;
# 	2 -- 4;
# 	3 -- 4;
# }`,
	},

	// Names named nodes.
	{
		name: "PageRank",
		g:    directedNamedIDGraphFrom(pageRankGraph),

		want: `strict digraph PageRank {
	// Node definitions.
	A;
	B;
	C;
	D;
	E;
	F;
	G;
	H;
	I;
	J;
	K;

	// Edge definitions.
	B -> C;
	C -> B;
	D -> A;
	D -> B;
	E -> B;
	E -> D;
	E -> F;
	F -> B;
	F -> E;
	G -> B;
	G -> E;
	H -> B;
	H -> E;
	I -> B;
	I -> E;
	J -> E;
	K -> E;
}`,
	},
	{
		g: undirectedNamedIDGraphFrom(pageRankGraph),

		want: `strict graph {
	// Node definitions.
	A;
	B;
	C;
	D;
	E;
	F;
	G;
	H;
	I;
	J;
	K;

	// Edge definitions.
	A -- D;
	B -- C;
	B -- D;
	B -- E;
	B -- F;
	B -- G;
	B -- H;
	B -- I;
	D -- E;
	E -- F;
	E -- G;
	E -- H;
	E -- I;
	E -- J;
	E -- K;
}`,
	},
	{
		g: directedNamedIDGraphFrom(powerMethodGraph),

		want: `strict digraph {
	// Node definitions.
	A;
	B;
	C;
	D;
	E;

	// Edge definitions.
	A -> B;
	A -> C;
	B -> D;
	C -> D;
	C -> E;
	D -> E;
	E -> A;
}`,
	},
	{
		g: undirectedNamedIDGraphFrom(powerMethodGraph),

		want: `strict graph {
	// Node definitions.
	A;
	B;
	C;
	D;
	E;

	// Edge definitions.
	A -- B;
	A -- C;
	A -- E;
	B -- D;
	C -- D;
	C -- E;
	D -- E;
}`,
	},
	{
		g:      undirectedNamedIDGraphFrom(powerMethodGraph),
		prefix: "# ",

		want: `# strict graph {
# 	// Node definitions.
# 	A;
# 	B;
# 	C;
# 	D;
# 	E;
#
# 	// Edge definitions.
# 	A -- B;
# 	A -- C;
# 	A -- E;
# 	B -- D;
# 	C -- D;
# 	C -- E;
# 	D -- E;
# }`,
	},

	// Handling nodes with attributes.
	{
		g: directedNodeAttrGraphFrom(powerMethodGraph, nil),

		want: `strict digraph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -> 1;
	0 -> 2;
	1 -> 3;
	2 -> 3;
	2 -> 4;
	3 -> 4;
	4 -> 0;
}`,
	},
	{
		g: undirectedNodeAttrGraphFrom(powerMethodGraph, nil),

		want: `strict graph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -- 1;
	0 -- 2;
	0 -- 4;
	1 -- 3;
	2 -- 3;
	2 -- 4;
	3 -- 4;
}`,
	},
	{
		g: directedNodeAttrGraphFrom(powerMethodGraph, [][]encoding.Attribute{
			2: {{Key: "fontsize", Value: "16"}, {Key: "shape", Value: "ellipse"}},
			4: {},
		}),

		want: `strict digraph {
	// Node definitions.
	0;
	1;
	2 [
		fontsize=16
		shape=ellipse
	];
	3;
	4;

	// Edge definitions.
	0 -> 1;
	0 -> 2;
	1 -> 3;
	2 -> 3;
	2 -> 4;
	3 -> 4;
	4 -> 0;
}`,
	},
	{
		g: undirectedNodeAttrGraphFrom(powerMethodGraph, [][]encoding.Attribute{
			2: {{Key: "fontsize", Value: "16"}, {Key: "shape", Value: "ellipse"}},
			4: {},
		}),

		want: `strict graph {
	// Node definitions.
	0;
	1;
	2 [
		fontsize=16
		shape=ellipse
	];
	3;
	4;

	// Edge definitions.
	0 -- 1;
	0 -- 2;
	0 -- 4;
	1 -- 3;
	2 -- 3;
	2 -- 4;
	3 -- 4;
}`,
	},
	{
		g: directedNamedIDNodeAttrGraphFrom(powerMethodGraph, [][]encoding.Attribute{
			2: {{Key: "fontsize", Value: "16"}, {Key: "shape", Value: "ellipse"}},
			4: {},
		}),

		want: `strict digraph {
	// Node definitions.
	A;
	B;
	C [
		fontsize=16
		shape=ellipse
	];
	D;
	E;

	// Edge definitions.
	A -> B;
	A -> C;
	B -> D;
	C -> D;
	C -> E;
	D -> E;
	E -> A;
}`,
	},
	{
		g: undirectedNamedIDNodeAttrGraphFrom(powerMethodGraph, [][]encoding.Attribute{
			0: nil,
			1: nil,
			2: {{Key: "fontsize", Value: "16"}, {Key: "shape", Value: "ellipse"}},
			3: nil,
			4: {},
		}),

		want: `strict graph {
	// Node definitions.
	A;
	B;
	C [
		fontsize=16
		shape=ellipse
	];
	D;
	E;

	// Edge definitions.
	A -- B;
	A -- C;
	A -- E;
	B -- D;
	C -- D;
	C -- E;
	D -- E;
}`,
	},

	// Handling edge with attributes.
	{
		g: directedEdgeAttrGraphFrom(powerMethodGraph, nil),

		want: `strict digraph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -> 1;
	0 -> 2;
	1 -> 3;
	2 -> 3;
	2 -> 4;
	3 -> 4;
	4 -> 0;
}`,
	},
	{
		g: undirectedEdgeAttrGraphFrom(powerMethodGraph, nil),

		want: `strict graph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -- 1;
	0 -- 2;
	0 -- 4;
	1 -- 3;
	2 -- 3;
	2 -- 4;
	3 -- 4;
}`,
	},
	{
		g: directedEdgeAttrGraphFrom(powerMethodGraph, map[edge][]encoding.Attribute{
			{from: 0, to: 2}: {{Key: "label", Value: `"???"`}, {Key: "style", Value: "dashed"}},
			{from: 2, to: 4}: {},
			{from: 3, to: 4}: {{Key: "color", Value: "red"}},
		}),

		want: `strict digraph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -> 1;
	0 -> 2 [
		label="???"
		style=dashed
	];
	1 -> 3;
	2 -> 3;
	2 -> 4;
	3 -> 4 [color=red];
	4 -> 0;
}`,
	},
	{
		g: undirectedEdgeAttrGraphFrom(powerMethodGraph, map[edge][]encoding.Attribute{
			{from: 0, to: 2}: {{Key: "label", Value: `"???"`}, {Key: "style", Value: "dashed"}},
			{from: 2, to: 4}: {},
			{from: 3, to: 4}: {{Key: "color", Value: "red"}},
		}),

		want: `strict graph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -- 1;
	0 -- 2 [
		label="???"
		style=dashed
	];
	0 -- 4;
	1 -- 3;
	2 -- 3;
	2 -- 4;
	3 -- 4 [color=red];
}`,
	},
	{
		g: undirectedEdgeAttrGraphFrom(powerMethodGraph, map[edge][]encoding.Attribute{
			// label attribute not quoted and containing spaces.
			{from: 0, to: 2}: {{Key: "label", Value: `hello world`}, {Key: "style", Value: "dashed"}},
			{from: 2, to: 4}: {},
			{from: 3, to: 4}: {{Key: "label", Value: `foo bar`}},
		}),

		want: `strict graph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -- 1;
	0 -- 2 [
		label="hello world"
		style=dashed
	];
	0 -- 4;
	1 -- 3;
	2 -- 3;
	2 -- 4;
	3 -- 4 [label="foo bar"];
}`,
	},
	{
		g: undirectedEdgeAttrGraphFrom(powerMethodGraph, map[edge][]encoding.Attribute{
			// keywords must be quoted if used as attributes.
			{from: 0, to: 2}: {{Key: "label", Value: `NODE`}, {Key: "style", Value: "dashed"}},
			{from: 2, to: 4}: {},
			{from: 3, to: 4}: {{Key: "label", Value: `subgraph`}},
		}),

		want: `strict graph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -- 1;
	0 -- 2 [
		label="NODE"
		style=dashed
	];
	0 -- 4;
	1 -- 3;
	2 -- 3;
	2 -- 4;
	3 -- 4 [label="subgraph"];
}`,
	},

	// Handling nodes with ports.
	{
		g: directedPortedAttrGraphFrom(powerMethodGraph, nil, nil),

		want: `strict digraph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -> 1;
	0 -> 2;
	1 -> 3;
	2 -> 3;
	2 -> 4;
	3 -> 4;
	4 -> 0;
}`,
	},
	{
		g: undirectedPortedAttrGraphFrom(powerMethodGraph, nil, nil),

		want: `strict graph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -- 1;
	0 -- 2;
	0 -- 4;
	1 -- 3;
	2 -- 3;
	2 -- 4;
	3 -- 4;
}`,
	},
	{
		g: directedPortedAttrGraphFrom(powerMethodGraph,
			[][]encoding.Attribute{
				2: {{Key: "shape", Value: "record"}, {Key: "label", Value: `"<Two>English|<Zwei>German"`}},
				4: {{Key: "shape", Value: "record"}, {Key: "label", Value: `"<Four>English|<Vier>German"`}},
			},
			map[edge]portedEdge{
				{from: 0, to: 1}: {fromCompass: "s"},
				{from: 0, to: 2}: {fromCompass: "s", toPort: "Zwei", toCompass: "e"},
				{from: 2, to: 3}: {fromPort: "Zwei", fromCompass: "e"},
				{from: 2, to: 4}: {fromPort: "Two", fromCompass: "w", toPort: "Four", toCompass: "w"},
				{from: 3, to: 4}: {toPort: "Four", toCompass: "w"},
				{from: 4, to: 0}: {fromPort: "Four", fromCompass: "_", toCompass: "s"},
			},
		),

		want: `strict digraph {
	// Node definitions.
	0;
	1;
	2 [
		shape=record
		label="<Two>English|<Zwei>German"
	];
	3;
	4 [
		shape=record
		label="<Four>English|<Vier>German"
	];

	// Edge definitions.
	0:s -> 1;
	0:s -> 2:Zwei:e;
	1 -> 3;
	2:Zwei:e -> 3;
	2:Two:w -> 4:Four:w;
	3 -> 4:Four:w;
	4:Four:_ -> 0:s;
}`,
	},
	{
		g: undirectedPortedAttrGraphFrom(powerMethodGraph,
			[][]encoding.Attribute{
				2: {{Key: "shape", Value: "record"}, {Key: "label", Value: `"<Two>English|<Zwei>German"`}},
				4: {{Key: "shape", Value: "record"}, {Key: "label", Value: `"<Four>English|<Vier>German"`}},
			},
			map[edge]portedEdge{
				{from: 0, to: 1}: {fromCompass: "s"},
				{from: 0, to: 2}: {fromCompass: "s", toPort: "Zwei", toCompass: "e"},
				{from: 2, to: 3}: {fromPort: "Zwei", fromCompass: "e"},
				{from: 2, to: 4}: {fromPort: "Two", fromCompass: "w", toPort: "Four", toCompass: "w"},
				{from: 3, to: 4}: {toPort: "Four", toCompass: "w"},
				{from: 4, to: 0}: {fromPort: "Four", fromCompass: "_", toCompass: "s"},
			},
		),

		want: `strict graph {
	// Node definitions.
	0;
	1;
	2 [
		shape=record
		label="<Two>English|<Zwei>German"
	];
	3;
	4 [
		shape=record
		label="<Four>English|<Vier>German"
	];

	// Edge definitions.
	0:s -- 1;
	0:s -- 2:Zwei:e;
	0:s -- 4:Four:_;
	1 -- 3;
	2:Zwei:e -- 3;
	2:Two:w -- 4:Four:w;
	3 -- 4:Four:w;
}`,
	},

	// Handling graph attributes.
	{
		g: graphAttributer{
			Graph: undirectedEdgeAttrGraphFrom(powerMethodGraph, map[edge][]encoding.Attribute{
				{from: 0, to: 2}: {{Key: "label", Value: `"???"`}, {Key: "style", Value: "dashed"}},
				{from: 2, to: 4}: {},
				{from: 3, to: 4}: {{Key: "color", Value: "red"}},
			}),
			graph: nil, node: nil, edge: nil,
		},

		want: `strict graph {
	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -- 1;
	0 -- 2 [
		label="???"
		style=dashed
	];
	0 -- 4;
	1 -- 3;
	2 -- 3;
	2 -- 4;
	3 -- 4 [color=red];
}`,
	},
	{
		g: graphAttributer{
			Graph: undirectedEdgeAttrGraphFrom(powerMethodGraph, map[edge][]encoding.Attribute{
				{from: 0, to: 2}: {{Key: "label", Value: `"???"`}, {Key: "style", Value: "dashed"}},
				{from: 2, to: 4}: {},
				{from: 3, to: 4}: {{Key: "color", Value: "red"}},
			}),
			graph: &encoding.Attributes{{Key: "rankdir", Value: `"LR"`}},
			node:  &encoding.Attributes{{Key: "fontsize", Value: "16"}, {Key: "shape", Value: "ellipse"}},
			edge:  nil,
		},

		want: `strict graph {
	graph [
		rankdir="LR"
	];
	node [
		fontsize=16
		shape=ellipse
	];

	// Node definitions.
	0;
	1;
	2;
	3;
	4;

	// Edge definitions.
	0 -- 1;
	0 -- 2 [
		label="???"
		style=dashed
	];
	0 -- 4;
	1 -- 3;
	2 -- 3;
	2 -- 4;
	3 -- 4 [color=red];
}`,
	},

	// Handling structured graphs.
	{
		g: undirectedStructuredGraphFrom(nil, powerMethodGraph, pageRankGraph),

		want: `strict graph {
	subgraph A {
		// Node definitions.
		0;
		1;
		2;
		3;
		4;

		// Edge definitions.
		0 -- 1;
		0 -- 2;
		0 -- 4;
		1 -- 3;
		2 -- 3;
		2 -- 4;
		3 -- 4;
	}
	subgraph B {
		// Node definitions.
		5;
		6;
		7;
		8;
		9;
		10;
		11;
		12;
		13;
		14;
		15;

		// Edge definitions.
		5 -- 8;
		6 -- 7;
		6 -- 8;
		6 -- 9;
		6 -- 10;
		6 -- 11;
		6 -- 12;
		6 -- 13;
		8 -- 9;
		9 -- 10;
		9 -- 11;
		9 -- 12;
		9 -- 13;
		9 -- 14;
		9 -- 15;
	}
}`,
	},
	{
		g: undirectedStructuredGraphFrom([]edge{{from: 0, to: 9}}, powerMethodGraph, pageRankGraph),

		want: `strict graph {
	subgraph A {
		// Node definitions.
		0;
		1;
		2;
		3;
		4;

		// Edge definitions.
		0 -- 1;
		0 -- 2;
		0 -- 4;
		1 -- 3;
		2 -- 3;
		2 -- 4;
		3 -- 4;
	}
	subgraph B {
		// Node definitions.
		5;
		6;
		7;
		8;
		9;
		10;
		11;
		12;
		13;
		14;
		15;

		// Edge definitions.
		5 -- 8;
		6 -- 7;
		6 -- 8;
		6 -- 9;
		6 -- 10;
		6 -- 11;
		6 -- 12;
		6 -- 13;
		8 -- 9;
		9 -- 10;
		9 -- 11;
		9 -- 12;
		9 -- 13;
		9 -- 14;
		9 -- 15;
	}
	// Node definitions.
	0;
	9;

	// Edge definitions.
	0 -- 9;
}`,
	},

	// Handling subgraphs.
	{
		g: undirectedSubGraphFrom(pageRankGraph, map[int64][]intset{2: powerMethodGraph}),

		want: `strict graph {
	// Node definitions.
	5;
	6;
	8;
	9;
	10;
	11;
	12;
	13;
	14;
	15;

	// Edge definitions.
	5 -- 8;
	6 -- subgraph H {
		// Node definitions.
		0;
		1;
		2;
		3;
		4;

		// Edge definitions.
		0 -- 1;
		0 -- 2;
		0 -- 4;
		1 -- 3;
		2 -- 3;
		2 -- 4;
		3 -- 4;
	};
	6 -- 8;
	6 -- 9;
	6 -- 10;
	6 -- 11;
	6 -- 12;
	6 -- 13;
	8 -- 9;
	9 -- 10;
	9 -- 11;
	9 -- 12;
	9 -- 13;
	9 -- 14;
	9 -- 15;
}`,
	},
	{
		name: "H",
		g:    undirectedSubGraphFrom(pageRankGraph, map[int64][]intset{1: powerMethodGraph}),

		want: `strict graph H {
	// Node definitions.
	5;
	7;
	8;
	9;
	10;
	11;
	12;
	13;
	14;
	15;

	// Edge definitions.
	5 -- 8;
	subgraph G {
		// Node definitions.
		0;
		1;
		2;
		3;
		4;

		// Edge definitions.
		0 -- 1;
		0 -- 2;
		0 -- 4;
		1 -- 3;
		2 -- 3;
		2 -- 4;
		3 -- 4;
	} -- 7;
	subgraph G {
		// Node definitions.
		0;
		1;
		2;
		3;
		4;
	} -- 8;
	subgraph G {
		// Node definitions.
		0;
		1;
		2;
		3;
		4;
	} -- 9;
	subgraph G {
		// Node definitions.
		0;
		1;
		2;
		3;
		4;
	} -- 10;
	subgraph G {
		// Node definitions.
		0;
		1;
		2;
		3;
		4;
	} -- 11;
	subgraph G {
		// Node definitions.
		0;
		1;
		2;
		3;
		4;
	} -- 12;
	subgraph G {
		// Node definitions.
		0;
		1;
		2;
		3;
		4;
	} -- 13;
	8 -- 9;
	9 -- 10;
	9 -- 11;
	9 -- 12;
	9 -- 13;
	9 -- 14;
	9 -- 15;
}`,
	},
}

func TestEncode(t *testing.T) {
	for i, test := range encodeTests {
		got, err := Marshal(test.g, test.name, test.prefix, "\t")
		if err != nil {
			t.Errorf("unexpected error: %v", err)
			continue
		}
		if string(got) != test.want {
			t.Errorf("unexpected DOT result for test %d:\ngot: %s\nwant:%s", i, got, test.want)
		}
		checkDOT(t, got)
	}
}

type intlist []int64

func createMultigraph(g []intlist) graph.Multigraph {
	dg := multi.NewUndirectedGraph()
	for u, e := range g {
		u := int64(u)
		nu := multi.Node(u)
		for _, v := range e {
			nv := multi.Node(v)
			dg.SetLine(dg.NewLine(nu, nv))
		}
	}
	return dg
}

func createNamedMultigraph(g []intlist) graph.Multigraph {
	dg := multi.NewUndirectedGraph()
	for u, e := range g {
		u := int64(u)
		nu := namedNode{id: u, name: alpha[u : u+1]}
		for _, v := range e {
			nv := namedNode{id: v, name: alpha[v : v+1]}
			dg.SetLine(dg.NewLine(nu, nv))
		}
	}
	return dg
}

func createDirectedMultigraph(g []intlist) graph.Multigraph {
	dg := multi.NewDirectedGraph()
	for u, e := range g {
		u := int64(u)
		nu := multi.Node(u)
		for _, v := range e {
			nv := multi.Node(v)
			dg.SetLine(dg.NewLine(nu, nv))
		}
	}
	return dg
}

func createNamedDirectedMultigraph(g []intlist) graph.Multigraph {
	dg := multi.NewDirectedGraph()
	for u, e := range g {
		u := int64(u)
		nu := namedNode{id: u, name: alpha[u : u+1]}
		for _, v := range e {
			nv := namedNode{id: v, name: alpha[v : v+1]}
			dg.SetLine(dg.NewLine(nu, nv))
		}
	}
	return dg
}

var encodeMultiTests = []struct {
	name string
	g    graph.Multigraph

	prefix string

	want string
}{
	{
		g: createMultigraph([]intlist{}),
		want: `graph {
}`,
	},
	{
		g: createMultigraph([]intlist{
			0: {1},
			1: {0, 2},
			2: {},
		}),
		want: `graph {
	// Node definitions.
	0;
	1;
	2;

	// Edge definitions.
	0 -- 1;
	0 -- 1;
	1 -- 2;
}`,
	},
	{
		g: createMultigraph([]intlist{
			0: {1},
			1: {2, 2},
			2: {0, 0, 0},
		}),
		want: `graph {
	// Node definitions.
	0;
	1;
	2;

	// Edge definitions.
	0 -- 1;
	0 -- 2;
	0 -- 2;
	0 -- 2;
	1 -- 2;
	1 -- 2;
}`,
	},
	{
		g: createNamedMultigraph([]intlist{
			0: {1},
			1: {2, 2},
			2: {0, 0, 0},
		}),
		want: `graph {
	// Node definitions.
	A;
	B;
	C;

	// Edge definitions.
	A -- B;
	A -- C;
	A -- C;
	A -- C;
	B -- C;
	B -- C;
}`,
	},
	{
		g: createMultigraph([]intlist{
			0: {2, 1, 0},
			1: {2, 1, 0},
			2: {2, 1, 0},
		}),
		want: `graph {
	// Node definitions.
	0;
	1;
	2;

	// Edge definitions.
	0 -- 0;
	0 -- 1;
	0 -- 1;
	0 -- 2;
	0 -- 2;
	1 -- 1;
	1 -- 2;
	1 -- 2;
	2 -- 2;
}`,
	},
	{
		g: createDirectedMultigraph([]intlist{}),
		want: `digraph {
}`,
	},
	{
		g: createDirectedMultigraph([]intlist{
			0: {1},
			1: {0, 2},
			2: {},
		}),
		want: `digraph {
	// Node definitions.
	0;
	1;
	2;

	// Edge definitions.
	0 -> 1;
	1 -> 0;
	1 -> 2;
}`,
	},
	{
		g: createDirectedMultigraph([]intlist{
			0: {1},
			1: {2, 2},
			2: {0, 0, 0},
		}),
		want: `digraph {
	// Node definitions.
	0;
	1;
	2;

	// Edge definitions.
	0 -> 1;
	1 -> 2;
	1 -> 2;
	2 -> 0;
	2 -> 0;
	2 -> 0;
}`,
	},
	{
		g: createNamedDirectedMultigraph([]intlist{
			0: {1},
			1: {2, 2},
			2: {0, 0, 0},
		}),
		want: `digraph {
	// Node definitions.
	A;
	B;
	C;

	// Edge definitions.
	A -> B;
	B -> C;
	B -> C;
	C -> A;
	C -> A;
	C -> A;
}`,
	},
	{
		g: createDirectedMultigraph([]intlist{
			0: {2, 1, 0},
			1: {2, 1, 0},
			2: {2, 1, 0},
		}),
		want: `digraph {
	// Node definitions.
	0;
	1;
	2;

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

func TestEncodeMulti(t *testing.T) {
	for i, test := range encodeMultiTests {
		got, err := MarshalMulti(test.g, test.name, test.prefix, "\t")
		if err != nil {
			t.Errorf("unexpected error: %v", err)
			continue
		}
		if string(got) != test.want {
			t.Errorf("unexpected DOT result for test %d:\ngot: %s\nwant:%s", i, got, test.want)
		}
		checkDOT(t, got)
	}
}

// checkDOT hands b to the dot executable if it exists and fails t if dot
// returns an error.
func checkDOT(t *testing.T, b []byte) {
	dot, err := exec.LookPath("dot")
	if err != nil {
		t.Logf("skipping DOT syntax check: %v", err)
		return
	}
	cmd := exec.Command(dot)
	cmd.Stdin = bytes.NewReader(b)
	stderr := &bytes.Buffer{}
	cmd.Stderr = stderr
	err = cmd.Run()
	if err != nil {
		t.Errorf("invalid DOT syntax: %v\n%s\ninput:\n%s", err, stderr.String(), b)
	}
}