You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
58 lines
1.6 KiB
58 lines
1.6 KiB
import { expect } from "chai"
|
|
|
|
import { colorGreedy, createGraph, neighbors, vertices } from "../../lib/data/graph"
|
|
|
|
const g = createGraph((v, e) => {
|
|
v("a", true)
|
|
v("b", true)
|
|
v("c", true)
|
|
v("d", true)
|
|
|
|
e("a", "b")
|
|
e("a", "c")
|
|
})
|
|
|
|
const empty = createGraph((v, e) => { })
|
|
|
|
describe("graph", () => {
|
|
describe("neighbors", () => {
|
|
it("returns neighbors of vertex", () => {
|
|
const ns = neighbors(g, "a")
|
|
expect(ns).to.deep.equal(new Set(["b", "c"]))
|
|
})
|
|
|
|
it("returns empty set when vertex has no neighbors", () => {
|
|
const ns = neighbors(g, "d")
|
|
expect(ns).to.deep.equal(new Set())
|
|
})
|
|
|
|
it("throw on invalid vertex", () => {
|
|
expect(() => neighbors(empty, "x")).to.throw()
|
|
})
|
|
})
|
|
|
|
describe("vertices", () => {
|
|
it("return all vertices for a graph", () => {
|
|
const vs = vertices(g)
|
|
expect(vs).to.deep.equal(new Set(["a", "b", "c", "d"]))
|
|
})
|
|
})
|
|
|
|
describe("colorGreedy", () => {
|
|
it("colors graph", () => {
|
|
const g = createGraph((v, e) => {
|
|
[0, 1, 2, 3, 4].forEach(i => v("x" + i, true))
|
|
|
|
e("x0", "x1")
|
|
e("x1", "x2")
|
|
e("x2", "x3")
|
|
})
|
|
|
|
const coloring1 = colorGreedy(g, ["x0", "x1", "x2", "x3", "x4"])
|
|
expect(coloring1.numColors).to.equal(2)
|
|
|
|
const coloring2 = colorGreedy(g, ["x0", "x3", "x1", "x2", "x4"])
|
|
expect(coloring2.numColors).to.equal(3)
|
|
})
|
|
})
|
|
})
|