Convert "Algorithms on Graphs" graph format to dot format

Readme.md

todot.js

Convert Algorithms on Graphs graph format into dot format

Usage

cat input.txt | node todot.js

Display image in terminal

cat input.txt | node todot.js | dot -Tpng | imgcat

Requires graphviz & beta version of iTerm2.

Example

Input

First line contains number of vertices and number of edges. Subsequent lines define edges between vertices.

5 6
1 2
2 3
3 4
1 4
1 5
5 4

Output

digraph {
  1 -> 2
  2 -> 3
  3 -> 4
  1 -> 4
  1 -> 5
  5 -> 4
}

License

OSC

todot.js

var type = process.argv[2] || 'digraph'
readInput(function (err, data) {
  if (err) throw err
  var meta = parseGraphMeta(data)

  console.log(toDot(type, meta))
})

function toDot (type, meta) {
  var explicitVertices = meta.edges.reduce(function (v, e) {
    if (v.indexOf(e[0]) === -1) v.push(e[0])
    if (v.indexOf(e[1]) === -1) v.push(e[1])
    return v
  }, [])

  var soloVertices = []
  for (var i = 1; i <= meta.totalVertices; i++) {
    if (explicitVertices.indexOf(String(i)) === -1) soloVertices.push(String(i))
  }
  const arrow = type === 'digraph' ? '->' : '--'
  return [
    type + ' {',
    soloVertices.map(function (v) { return '  ' + v }).join('\n'),
    meta.edges.map(function (e) {
      let edge = '  ' + e[0] + ` ${arrow} ` + e[1]
      if (e.length === 3) edge += `[label=" ${e[2]} "];`
      return edge
    }).join('\n'),
    '}'
  ].filter(Boolean).join('\n')
}

function parseGraphMeta (data) {
  var pairs = data.trim()
  .split(/[\r\n]+/)
  .map(function (line) { return line.trim() })
  .map(function (line) {
    return line.split(/\s+/)
  })

  var totalVertices = parseInt(pairs[0][0])
  var totalEdges = parseInt(pairs[0][1])
  var edges = pairs.slice(1, totalEdges + 1)

  return {
    totalEdges: totalEdges,
    totalVertices: totalVertices,
    edges: edges
  }
}

function readInput (fn) {
  var buffer = []
  process.stdin
  .on('data', function (data) {
    buffer.push(data)
  })
  .on('end', function () {
    fn(null, buffer.join(' '))
  })
  .on('error', fn)
}