func TestTarjanSCC(t *testing.T) {
	for i, test := range tarjanTests {
		g := simple.NewDirectedGraph(0, math.Inf(1))
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(simple.Node(u)) {
				g.AddNode(simple.Node(u))
			}
			for v := range e {
				g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
			}
		}
		gotSCCs := TarjanSCC(g)
		// tarjan.strongconnect does range iteration over maps,
		// so sort SCC members to ensure consistent ordering.
		gotIDs := make([][]int, len(gotSCCs))
		for i, scc := range gotSCCs {
			gotIDs[i] = make([]int, len(scc))
			for j, id := range scc {
				gotIDs[i][j] = id.ID()
			}
			sort.Ints(gotIDs[i])
		}
		for _, iv := range test.ambiguousOrder {
			sort.Sort(internal.BySliceValues(test.want[iv.start:iv.end]))
			sort.Sort(internal.BySliceValues(gotIDs[iv.start:iv.end]))
		}
		if !reflect.DeepEqual(gotIDs, test.want) {
			t.Errorf("unexpected Tarjan scc result for %d:\n\tgot:%v\n\twant:%v", i, gotIDs, test.want)
		}
	}
}

func TestNavigableSmallWorldDirected(t *testing.T) {
	for p := 1; p < 5; p++ {
		for q := 0; q < 10; q++ {
			for r := 0.5; r < 10; r++ {
				for _, dims := range smallWorldDimensionParameters {
					g := &gnDirected{DirectedBuilder: simple.NewDirectedGraph(0, math.Inf(1))}
					err := NavigableSmallWorld(g, dims, p, q, r, nil)
					n := 1
					for _, d := range dims {
						n *= d
					}
					if err != nil {
						t.Fatalf("unexpected error: dims=%v n=%d, p=%d, q=%d, r=%v, r=%v: %v", dims, n, p, q, r, err)
					}
					if g.addSelfLoop {
						t.Errorf("unexpected self edge: dims=%v n=%d, p=%d, q=%d, r=%v", dims, n, p, q, r)
					}
					if g.addMultipleEdge {
						t.Errorf("unexpected multiple edge: dims=%v n=%d, p=%d, q=%d, r=%v", dims, n, p, q, r)
					}
				}
			}
		}
	}
}

func TestCyclesIn(t *testing.T) {
	for i, test := range cyclesInTests {
		g := simple.NewDirectedGraph(0, math.Inf(1))
		g.AddNode(simple.Node(-10)) // Make sure we test graphs with sparse IDs.
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(simple.Node(u)) {
				g.AddNode(simple.Node(u))
			}
			for v := range e {
				g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
			}
		}
		cycles := CyclesIn(g)
		var got [][]int
		if cycles != nil {
			got = make([][]int, len(cycles))
		}
		// johnson.circuit does range iteration over maps,
		// so sort to ensure consistent ordering.
		for j, c := range cycles {
			ids := make([]int, len(c))
			for k, n := range c {
				ids[k] = n.ID()
			}
			got[j] = ids
		}
		sort.Sort(ordered.BySliceValues(got))
		if !reflect.DeepEqual(got, test.want) {
			t.Errorf("unexpected johnson result for %d:\n\tgot:%#v\n\twant:%#v", i, got, test.want)
		}
	}
}

func TestHITS(t *testing.T) {
	for i, test := range hitsTests {
		g := simple.NewDirectedGraph(0, math.Inf(1))
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(simple.Node(u)) {
				g.AddNode(simple.Node(u))
			}
			for v := range e {
				g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
			}
		}
		got := HITS(g, test.tol)
		prec := 1 - int(math.Log10(test.wantTol))
		for n := range test.g {
			if !floats.EqualWithinAbsOrRel(got[n].Hub, test.want[n].Hub, test.wantTol, test.wantTol) {
				t.Errorf("unexpected HITS result for test %d:\ngot: %v\nwant:%v",
					i, orderedHubAuth(got, prec), orderedHubAuth(test.want, prec))
				break
			}
			if !floats.EqualWithinAbsOrRel(got[n].Authority, test.want[n].Authority, test.wantTol, test.wantTol) {
				t.Errorf("unexpected HITS result for test %d:\ngot: %v\nwant:%v",
					i, orderedHubAuth(got, prec), orderedHubAuth(test.want, prec))
				break
			}
		}
	}
}

func TestSort(t *testing.T) {
	for i, test := range tarjanTests {
		g := simple.NewDirectedGraph(0, math.Inf(1))
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(simple.Node(u)) {
				g.AddNode(simple.Node(u))
			}
			for v := range e {
				g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
			}
		}
		sorted, err := Sort(g)
		var gotSortedLen int
		for _, n := range sorted {
			if n != nil {
				gotSortedLen++
			}
		}
		if gotSortedLen != test.sortedLength {
			t.Errorf("unexpected number of sortable nodes for test %d: got:%d want:%d", i, gotSortedLen, test.sortedLength)
		}
		if err == nil != test.sortable {
			t.Errorf("unexpected sortability for test %d: got error: %v want: nil-error=%t", i, err, test.sortable)
		}
		if err != nil && len(err.(Unorderable)) != test.unorderableLength {
			t.Errorf("unexpected number of unorderable nodes for test %d: got:%d want:%d", i, len(err.(Unorderable)), test.unorderableLength)
		}
	}
}

// Builds a BFS tree (as a directed graph) from the given graph and start node.
func BFSTree(g graph.Graph, start graph.Node) *simple.DirectedGraph {
	if !g.Has(start) {
		panic(fmt.Sprintf("BFSTree: Start node %r not in graph %r", start, g))
	}

	ret := simple.NewDirectedGraph(0.0, math.Inf(1))
	seen := make(map[int]bool)
	q := queue.New()
	q.Add(start)
	ret.AddNode(simple.Node(start.ID()))

	for q.Length() > 0 {
		node := q.Peek().(graph.Node)
		q.Remove()
		for _, neighbor := range g.From(node) {
			if !seen[neighbor.ID()] {
				seen[neighbor.ID()] = true
				ret.AddNode(simple.Node(neighbor.ID()))
				ret.SetEdge(simple.Edge{F: simple.Node(node.ID()), T: simple.Node(neighbor.ID()), W: g.Edge(node, neighbor).Weight()})
				q.Add(neighbor)
			}
		}
	}

	return ret
}

func (g *DirectedGraph) Copy(src Graph) {
	g.DirectedGraph = *simple.NewDirectedGraph(0, math.Inf(1))
	graph.Copy(&g.DirectedGraph, src)
	g.paths = make(map[string]int)
	for k, v := range src.(*DirectedGraph).paths {
		g.paths[k] = v
	}
}

func directedEdgeAttrGraphFrom(g []set, attr map[edge][]Attribute) graph.Directed {
	dg := simple.NewDirectedGraph(0, math.Inf(1))
	for u, e := range g {
		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 directedGraphFrom(g []set) graph.Directed {
	dg := simple.NewDirectedGraph(0, math.Inf(1))
	for u, e := range g {
		for v := range e {
			dg.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
		}
	}
	return dg
}

func directedNamedIDGraphFrom(g []set) graph.Directed {
	dg := simple.NewDirectedGraph(0, math.Inf(1))
	for u, e := range g {
		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 TestGnpDirected(t *testing.T) {
	for n := 2; n <= 20; n++ {
		for p := 0.; p <= 1; p += 0.1 {
			g := &gnDirected{DirectedBuilder: simple.NewDirectedGraph(0, math.Inf(1))}
			err := Gnp(g, n, p, nil)
			if err != nil {
				t.Fatalf("unexpected error: n=%d, p=%v: %v", n, p, err)
			}
			if g.addSelfLoop {
				t.Errorf("unexpected self edge: n=%d, p=%v", n, p)
			}
			if g.addMultipleEdge {
				t.Errorf("unexpected multiple edge: n=%d, p=%v", n, p)
			}
		}
	}
}

func TestGnmDirected(t *testing.T) {
	for n := 2; n <= 20; n++ {
		nChoose2 := (n - 1) * n / 2
		for m := 0; m <= nChoose2*2; m++ {
			g := &gnDirected{DirectedBuilder: simple.NewDirectedGraph(0, math.Inf(1))}
			err := Gnm(g, n, m, nil)
			if err != nil {
				t.Fatalf("unexpected error: n=%d, m=%d: %v", n, m, err)
			}
			if g.addSelfLoop {
				t.Errorf("unexpected self edge: n=%d, m=%d", n, m)
			}
			if g.addMultipleEdge {
				t.Errorf("unexpected multiple edge: n=%d, m=%d", n, m)
			}
		}
	}
}

func directedNamedIDNodeAttrGraphFrom(g []set, attr [][]Attribute) graph.Directed {
	dg := simple.NewDirectedGraph(0, math.Inf(1))
	for u, e := range g {
		var at []Attribute
		if u < len(attr) {
			at = attr[u]
		}
		nu := namedAttrNode{id: u, name: alpha[u : u+1], attr: at}
		for v := range e {
			if v < 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 directedPortedAttrGraphFrom(g []set, attr [][]Attribute, ports map[edge]portedEdge) graph.Directed {
	dg := simple.NewDirectedGraph(0, math.Inf(1))
	for u, e := range g {
		var at []Attribute
		if u < len(attr) {
			at = attr[u]
		}
		nu := attrNode{id: u, attr: at}
		for v := range e {
			if v < 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 TestIsPath(t *testing.T) {
	dg := simple.NewDirectedGraph(0, math.Inf(1))
	if !IsPathIn(dg, nil) {
		t.Error("IsPath returns false on nil path")
	}
	p := []graph.Node{simple.Node(0)}
	if IsPathIn(dg, p) {
		t.Error("IsPath returns true on nonexistant node")
	}
	dg.AddNode(p[0])
	if !IsPathIn(dg, p) {
		t.Error("IsPath returns false on single-length path with existing node")
	}
	p = append(p, simple.Node(1))
	dg.AddNode(p[1])
	if IsPathIn(dg, p) {
		t.Error("IsPath returns true on bad path of length 2")
	}
	dg.SetEdge(simple.Edge{F: p[0], T: p[1], W: 1})
	if !IsPathIn(dg, p) {
		t.Error("IsPath returns false on correct path of length 2")
	}
	p[0], p[1] = p[1], p[0]
	if IsPathIn(dg, p) {
		t.Error("IsPath erroneously returns true for a reverse path")
	}
	p = []graph.Node{p[1], p[0], simple.Node(2)}
	dg.SetEdge(simple.Edge{F: p[1], T: p[2], W: 1})
	if !IsPathIn(dg, p) {
		t.Error("IsPath does not find a correct path for path > 2 nodes")
	}
	ug := simple.NewUndirectedGraph(0, math.Inf(1))
	ug.SetEdge(simple.Edge{F: p[1], T: p[0], W: 1})
	ug.SetEdge(simple.Edge{F: p[1], T: p[2], W: 1})
	if !IsPathIn(dg, p) {
		t.Error("IsPath does not correctly account for undirected behavior")
	}
}

func TestPageRankSparse(t *testing.T) {
	for i, test := range pageRankTests {
		g := simple.NewDirectedGraph(0, math.Inf(1))
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(simple.Node(u)) {
				g.AddNode(simple.Node(u))
			}
			for v := range e {
				g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
			}
		}
		got := PageRankSparse(g, test.damp, test.tol)
		prec := 1 - int(math.Log10(test.wantTol))
		for n := range test.g {
			if !floats.EqualWithinAbsOrRel(got[n], test.want[n], test.wantTol, test.wantTol) {
				t.Errorf("unexpected PageRank result for test %d:\ngot: %v\nwant:%v",
					i, orderedFloats(got, prec), orderedFloats(test.want, prec))
				break
			}
		}
	}
}

	"github.com/gonum/graph"
	"github.com/gonum/graph/simple"
	"github.com/gonum/matrix/mat64"
)

var directedGraphs = []struct {
	g      func() graph.DirectedBuilder
	edges  []simple.Edge
	absent float64
	merge  func(x, y float64, xe, ye graph.Edge) float64

	want mat64.Matrix
}{
	{
		g: func() graph.DirectedBuilder { return simple.NewDirectedGraph(0, 0) },
		edges: []simple.Edge{
			{F: simple.Node(0), T: simple.Node(1), W: 2},
			{F: simple.Node(1), T: simple.Node(0), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
		},
		want: mat64.NewSymDense(3, []float64{
			0, (1. + 2.) / 2., 0,
			(1. + 2.) / 2., 0, 1. / 2.,
			0, 1. / 2., 0,
		}),
	},
	{
		g: func() graph.DirectedBuilder { return simple.NewDirectedGraph(0, 0) },
		edges: []simple.Edge{
			{F: simple.Node(0), T: simple.Node(1), W: 2},

func construct_graph_directed(db *sql.DB, k int, min time.Time, max time.Time) (*simple.DirectedGraph, map[string]string) {

	// Make the query:
	rows, err := db.Query(
		"SELECT G.name, E.name, COUNT(*) "+
			"FROM EMPLOYEE E, EMPLOYEE G, EMAIL F, RECEIVERS R "+
			"WHERE R.emp_id=E.id AND R.id=F.id AND G.id=F.sender_id AND G.name<>E.name AND "+
			"DATE(F.time_sent) >= TO_DATE($2, 'yyyy-mm-dd') AND "+
			"DATE(F.time_sent) <= TO_DATE($3, 'yyyy-mm-dd') "+
			"GROUP BY G.name, E.name "+
			"HAVING COUNT(*) > $1",
		k,
		fmt.Sprintf("%d-%02d-%02d", min.Year(), min.Month(), min.Day()),
		fmt.Sprintf("%d-%02d-%02d", max.Year(), max.Month(), max.Day()))
	if err != nil {
		log.Fatal(err)
	}
	defer rows.Close()

	// Temporary variables:
	var (
		u         string
		v         string
		weight    float64
		tmpNodeId int
		uNode     simple.Node
		vNode     simple.Node
	)

	// Map Node UID to string names
	idMap := make(map[string]string)
	// Map string names to Node UIDs
	existsMap := make(map[string]int)
	g := simple.NewDirectedGraph(0, 0) // Self weight and default edge weight

	for rows.Next() {
		// Read each row
		err := rows.Scan(&u, &v, &weight)
		if err != nil {
			log.Fatal(err)
		}

		// Set variables for the existence of strings in the map, and by inference, the nodes
		_, uExists := existsMap[u]
		_, vExists := existsMap[v]

		if !uExists {
			// Get a new node id
			tmpNodeId = g.NewNodeID()
			// Create the left node and map the id to string
			uNode = simple.Node(tmpNodeId)
			g.AddNode(uNode)
			idMap[strconv.Itoa(tmpNodeId)] = u
			existsMap[u] = tmpNodeId
		}

		if !vExists {
			// Get a new node id
			tmpNodeId = g.NewNodeID()
			// Create the right node and map the id to string
			vNode = simple.Node(tmpNodeId)
			g.AddNode(vNode)
			idMap[strconv.Itoa(tmpNodeId)] = v
			existsMap[v] = tmpNodeId
		}

		uExistNode := g.Node(existsMap[u])
		vExistNode := g.Node(existsMap[v])

		// Create and add an edge between these two nodes:
		newEdge := simple.Edge{uExistNode, vExistNode, weight}
		g.SetEdge(newEdge)

	}
	rows.Close()
	return g, idMap
}

func NewGraph() Graph {
	return &DirectedGraph{
		DirectedGraph: *simple.NewDirectedGraph(0, math.Inf(1)),
		paths:         make(map[string]int),
	}
}

func TestDistanceCentralityDirected(t *testing.T) {
	const tol = 1e-12
	prec := 1 - int(math.Log10(tol))

	for i, test := range directedCentralityTests {
		g := simple.NewDirectedGraph(0, math.Inf(1))
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(simple.Node(u)) {
				g.AddNode(simple.Node(u))
			}
			for v := range e {
				g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v), W: 1})
			}
		}
		p, ok := path.FloydWarshall(g)
		if !ok {
			t.Errorf("unexpected negative cycle in test %d", i)
			continue
		}

		var got map[int]float64

		got = Closeness(g, p)
		for n := range test.g {
			if !floats.EqualWithinAbsOrRel(got[n], 1/test.farness[n], tol, tol) {
				want := make(map[int]float64)
				for n, v := range test.farness {
					want[n] = 1 / v
				}
				t.Errorf("unexpected closeness centrality for test %d:\ngot: %v\nwant:%v",
					i, orderedFloats(got, prec), orderedFloats(want, prec))
				break
			}
		}

		got = Farness(g, p)
		for n := range test.g {
			if !floats.EqualWithinAbsOrRel(got[n], test.farness[n], tol, tol) {
				t.Errorf("unexpected farness for test %d:\ngot: %v\nwant:%v",
					i, orderedFloats(got, prec), orderedFloats(test.farness, prec))
				break
			}
		}

		got = Harmonic(g, p)
		for n := range test.g {
			if !floats.EqualWithinAbsOrRel(got[n], test.harmonic[n], tol, tol) {
				t.Errorf("unexpected harmonic centrality for test %d:\ngot: %v\nwant:%v",
					i, orderedFloats(got, prec), orderedFloats(test.harmonic, prec))
				break
			}
		}

		got = Residual(g, p)
		for n := range test.g {
			if !floats.EqualWithinAbsOrRel(got[n], test.residual[n], tol, tol) {
				t.Errorf("unexpected residual closeness for test %d:\ngot: %v\nwant:%v",
					i, orderedFloats(got, prec), orderedFloats(test.residual, prec))
				break
			}
		}
	}
}