Skip to content

Commit

Permalink
Add graphviz writer
Browse files Browse the repository at this point in the history
  • Loading branch information
cpettitt committed Sep 24, 2014
1 parent eaf1036 commit 74b7620
Show file tree
Hide file tree
Showing 8 changed files with 292 additions and 20 deletions.
8 changes: 4 additions & 4 deletions Makefile
Original file line number Diff line number Diff line change
Expand Up @@ -16,7 +16,7 @@ MOCHA_OPTS = -R dot
BUILD_DIR = build
COVERAGE_DIR = $(BUILD_DIR)/cov

SRC_FILES = index.js lib/dot-grammar.js lib/version.js $(shell find lib -type f -name '*.js')
SRC_FILES = index.js lib/dot/grammar.js lib/version.js $(shell find lib -type f -name '*.js')
TEST_FILES = $(shell find test -type f -name '*.js')
BUILD_FILES = $(addprefix $(BUILD_DIR)/, $(MOD).js $(MOD).min.js)

Expand All @@ -29,7 +29,7 @@ all: $(BUILD_FILES)
bench: all
@src/bench.js

lib/dot-grammar.js: src/dot-grammar.pegjs
lib/dot/grammar.js: src/dot-grammar.pegjs
$(PEGJS) --allowed-start-rules "start,graphStmt" -e 'module.exports' $< $@

lib/version.js: package.json
Expand All @@ -41,8 +41,8 @@ $(DIRS):
$(BUILD_DIR)/$(MOD).js: browser.js $(SRC_FILES) $(TEST_FILES) node_modules | $(BUILD_DIR)
@echo Building...
@$(ISTANBUL) cover $(ISTANBUL_OPTS) $(MOCHA) --dir $(COVERAGE_DIR) -- $(MOCHA_OPTS) $(TEST_FILES) || $(MOCHA) $(MOCHA_OPTS) $(TEST_FILES)
@$(JSHINT) $(JSHINT_OPTS) $(filter-out node_modules lib/dot-grammar.js, $?)
@$(JSCS) $(filter-out node_modules lib/dot-grammar.js, $?)
@$(JSHINT) $(JSHINT_OPTS) $(filter-out node_modules lib/dot/grammar.js, $?)
@$(JSCS) $(filter-out node_modules lib/dot/grammar.js, $?)
@$(BROWSERIFY) -x lodash $< > $@

$(BUILD_DIR)/$(MOD).min.js: $(BUILD_DIR)/$(MOD).js
Expand Down
19 changes: 4 additions & 15 deletions lib/dot.js → lib/dot/build-graph.js
Original file line number Diff line number Diff line change
@@ -1,20 +1,8 @@
var _ = require("lodash"),
dotGrammar = require("./dot-grammar"),
CGraph = require("./compound-graph"),
CDigraph = require("./compound-digraph");
CGraph = require("../compound-graph"),
CDigraph = require("../compound-digraph");

exports.readMany = readMany;
exports.read = readOne;

function readMany(str) {
var parseTree = dotGrammar.parse(str);
return _.map(parseTree, buildGraph);
}

function readOne(str) {
var parseTree = dotGrammar.parse(str, { startRule: "graphStmt" });
return buildGraph(parseTree);
}
module.exports = buildGraph;

function buildGraph(parseTree) {
var g = parseTree.type === "graph" ? new CGraph() : new CDigraph(),
Expand Down Expand Up @@ -143,3 +131,4 @@ function collectNodeIds(stmt) {

return _.keys(ids);
}

File renamed without changes.
9 changes: 9 additions & 0 deletions lib/dot/index.js
Original file line number Diff line number Diff line change
@@ -0,0 +1,9 @@
var read = require("./read-one"),
readMany = require("./read-many"),
write = require("./write-one");

module.exports = {
read: read,
readMany: readMany,
write: write
};
8 changes: 8 additions & 0 deletions lib/dot/read-many.js
Original file line number Diff line number Diff line change
@@ -0,0 +1,8 @@
var _ = require("lodash"),
grammar = require("./grammar"),
buildGraph = require("./build-graph");

module.exports = function readMany(str) {
var parseTree = grammar.parse(str);
return _.map(parseTree, buildGraph);
};
8 changes: 8 additions & 0 deletions lib/dot/read-one.js
Original file line number Diff line number Diff line change
@@ -0,0 +1,8 @@
var grammar = require("./grammar"),
buildGraph = require("./build-graph");

module.exports = function readOne(str) {
var parseTree = grammar.parse(str, { startRule: "graphStmt" });
return buildGraph(parseTree);
};

135 changes: 135 additions & 0 deletions lib/dot/write-one.js
Original file line number Diff line number Diff line change
@@ -0,0 +1,135 @@
var _ = require("lodash");

module.exports = writeOne;

var UNESCAPED_ID_PATTERN = /^[a-zA-Z\200-\377_][a-zA-Z\200-\377_0-9]*$/;

function writeOne(g, options) {
var ec = g.isDirected() ? "->" : "--",
writer = new Writer();

options = options || {};

if (options.strict) {
writer.write("strict ");
}

writer.writeLine((g.isDirected() ? "digraph" : "graph") + " {");
writer.indent();

var graphAttrs = g.getGraph();
if (_.isObject(graphAttrs)) {
_.each(graphAttrs, function(v, k) {
writer.writeLine(id(k) + "=" + id(v) + ";");
});
}

writeSubgraph(g, undefined, writer);

g.edges().forEach(function(edge) {
writeEdge(edge, ec, writer);
});

writer.unindent();
writer.writeLine("}");

return writer.toString();
}

function writeSubgraph(g, v, writer) {
var children = g.getChildren ? g.getChildren(v) : g.nodeIds();
_.each(children, function(w) {
if (!g.getChildren || !g.getChildren(w).length) {
writeNode(g, w, writer);
} else {
writer.writeLine("subgraph " + id(w) + " {");
writer.indent();

_.map(g.getNode(w), function(val, key) {
writer.writeLine(id(key) + "=" + id(val) + ";");
});

writeSubgraph(g, w, writer);
writer.unindent();
writer.writeLine("}");
}
});
}

function writeNode(g, v, writer) {
writer.write(id(v));
writeAttrs(g.getNode(v), writer);
writer.writeLine();
}

function writeEdge(edge, ec, writer) {
var edges = edge.label,
v = edge.v,
w = edge.w;

if (_.isPlainObject(edges)) {
edges = [edges];
} else if (!_.isArray(edges)) {
edges = [{}];
}

_.each(edges, function(attrs) {
writer.write(id(v) + " " + ec + " " + id(w));
writeAttrs(attrs, writer);
writer.writeLine();
});
}

function writeAttrs(attrs, writer) {
if (_.isObject(attrs)) {
var attrStrs = _.map(attrs, function(val, key) {
return id(key) + "=" + id(val);
});
if (attrStrs.length) {
writer.write(" [" + attrStrs.join(",") + "]");
}
}
}

function id(obj) {
if (typeof obj === "number" || obj.toString().match(UNESCAPED_ID_PATTERN)) {
return obj;
}

return "\"" + obj.toString().replace(/"/g, "\\\"") + "\"";
}

// Helper object for making a pretty printer
function Writer() {
this._indent = "";
this._content = "";
this._shouldIndent = true;
}

Writer.prototype.INDENT = " ";

Writer.prototype.indent = function() {
this._indent += this.INDENT;
};

Writer.prototype.unindent = function() {
this._indent = this._indent.slice(this.INDENT.length);
};

Writer.prototype.writeLine = function(line) {
this.write((line || "") + "\n");
this._shouldIndent = true;
};

Writer.prototype.write = function(str) {
if (this._shouldIndent) {
this._shouldIndent = false;
this._content += this._indent;
}
this._content += str;
};

Writer.prototype.toString = function() {
return this._content;
};

125 changes: 124 additions & 1 deletion test/dot-test.js
Original file line number Diff line number Diff line change
@@ -1,6 +1,9 @@
var _ = require("lodash"),
expect = require("./chai").expect,
dot = require("..").dot;
dot = require("..").dot,
Digraph = require("..").Digraph,
CDigraph = require("..").CDigraph,
Graph = require("..").Graph;

describe("dot", function() {
describe("read", function() {
Expand Down Expand Up @@ -373,4 +376,124 @@ describe("dot", function() {
expect(gs[1].isDirected()).to.be.false;
});
});

describe("write", function() {
it("can write an empty digraph", function() {
var str = dot.write(new Digraph());
var g = dot.read(str);
expect(g.nodeCount()).to.equal(0);
expect(g.edgeCount()).to.equal(0);
expect(g.getGraph()).to.eql({});
expect(g.isDirected()).to.be.true;
});

it("can write an empty graph", function() {
var str = dot.write(new Graph());
var g = dot.read(str);
expect(g.nodeCount()).to.equal(0);
expect(g.edgeCount()).to.equal(0);
expect(g.getGraph()).to.eql({});
expect(g.isDirected()).to.be.false;
});

it("can write a graph label with an object", function() {
var g = new Digraph();
g.setGraph({ foo: "bar" });
var str = dot.write(g);
var g2 = dot.read(str);
expect(g2.getGraph()).to.eql({ foo: "bar" });
});

it("can write a node", function() {
var g = new Digraph();
g.setNode("n1");
var str = dot.write(g);
var g2 = dot.read(str);
expect(g2.hasNode("n1")).to.be.true;
expect(g2.getNode("n1")).to.eql({});
expect(g2.nodeCount()).to.equal(1);
expect(g2.edgeCount()).to.equal(0);
});

it("can write a node with attributes", function() {
var g = new Digraph();
g.setNode("n1", { foo: "bar" });
var str = dot.write(g);
var g2 = dot.read(str);
expect(g2.getNode("n1")).to.eql({ foo: "bar" });
expect(g2.nodeCount()).to.equal(1);
expect(g2.edgeCount()).to.equal(0);
});

it("can write an edge", function() {
var g = new Digraph();
g.setEdge("n1", "n2");
var str = dot.write(g, { strict: true });
var g2 = dot.read(str);
expect(g2.hasEdge("n1", "n2")).to.be.true;
expect(g2.getEdge("n1", "n2")).to.eql({});
expect(g2.nodeCount()).to.equal(2);
expect(g2.edgeCount()).to.equal(1);
});

it("can write an edge with attributes", function() {
var g = new Digraph();
g.setEdge("n1", "n2", { foo: "bar" });
var str = dot.write(g, { strict: true });
var g2 = dot.read(str);
expect(g2.getEdge("n1", "n2")).to.eql({ foo: "bar" });
expect(g2.nodeCount()).to.equal(2);
expect(g2.edgeCount()).to.equal(1);
});

it("can write multi-edges", function() {
var g = new Digraph();
g.setEdge("n1", "n2", [{ foo: "bar" }, { foo: "baz" }]);
var str = dot.write(g);
var g2 = dot.read(str);
expect(_.sortBy(g2.getEdge("n1", "n2"), "foo")).to.eql([
{ foo: "bar" },
{ foo: "baz" }
]);
expect(g2.nodeCount()).to.equal(2);
expect(g2.edgeCount()).to.equal(1);
});

it("can write ids that must be escaped", function() {
var g = new Digraph();
g.setNode("\"n1\"");
var str = dot.write(g);
var g2 = dot.read(str);
expect(g2.hasNode("\"n1\"")).to.be.true;
expect(g2.getNode("\"n1\"")).to.eql({});
expect(g2.nodeCount()).to.equal(1);
expect(g2.edgeCount()).to.equal(0);
});

it("can write subgraphs", function() {
var g = new CDigraph();
g.setParent("n1", "root");
var str = dot.write(g);
var g2 = dot.read(str);
expect(g2.hasNode("n1")).to.be.true;
expect(g2.hasNode("root")).to.be.true;
expect(g2.getParent("n1")).to.equal("root");
expect(g2.nodeCount()).to.equal(2);
expect(g2.edgeCount()).to.equal(0);
});

it("can write subgraphs with attributes", function() {
var g = new CDigraph();
g.setParent("n1", "root");
g.setNode("root", { foo: "bar" });
var str = dot.write(g);
var g2 = dot.read(str);
expect(g2.hasNode("n1")).to.be.true;
expect(g2.hasNode("root")).to.be.true;
expect(g2.getNode("root")).to.eql({ foo: "bar" });
expect(g2.getParent("n1")).to.equal("root");
expect(g2.nodeCount()).to.equal(2);
expect(g2.edgeCount()).to.equal(0);
});
});
});

0 comments on commit 74b7620

Please sign in to comment.