@buggyorg/graphtools - npm Package Compare versions

Comparing version 0.2.12 to 0.2.13

lib/backtrack.js

@@ -1,62 +0,19 @@
-'use strict';
 
-Object.defineProperty(exports, "__esModule", {
-  value: true
-});
-exports.backtrackPortGraph = backtrackPortGraph;
-exports.backtrackNetworkGraph = backtrackNetworkGraph;
+import _ from 'lodash';
 
-var _lodash = require('lodash');
-
-var _lodash2 = _interopRequireDefault(_lodash);
-
-function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; }
-
-function backtrackPortGraph(graph, node, fn) {
-  var getPredecessors = function getPredecessors() {
-    return (0, _lodash2.default)([]).map(function (e) {
-      return e.v;
-    });
-  };
-  return backtrack(graph, node, fn, getPredecessors);
-}
-
-function backtrackNetworkGraph(graph, node, fn) {
-  var getPredecessors = function getPredecessors(cur) {
-    return (0, _lodash2.default)([]).filter(function (e) {
-      return e.v === cur.node + '_PORT_' + cur.port;
-    }).map(function (e) {
-      return graph.predecessors(e.v);
-    }).flatten().map(function (e) {
-      return graph.predecessors(e);
-    }).flatten();
-  };
-  return backtrack(graph, node, fn, getPredecessors);
-}
-
-function backtrack(graph, node, fn, predecessor) {
+export default function backtrack(graph, node, fn) {
   // inPorts [ {port: name, payload: ?}]
-  var inPorts = fn(node, graph.node(node), undefined);
-  var callStack = _lodash2.default.map(inPorts, function (portData) {
-    return { node: node, port: portData.port, payload: portData.payload, path: [node] };
-  });
-  var endPoints = [];
+  var inPorts = fn(graph.node(node), undefined);
+  var callStack = _.map(inPorts, portData => ({ node: node, port: portData.port, payload: portData.payload }));
   while (callStack.length !== 0) {
     var cur = callStack.pop();
-    console.log(cur);
     var inEdges = graph.inEdges(cur.node);
-    var inNodes = predecessor(cur).plant(inEdges).value();
-    var newCallStackElements = (0, _lodash2.default)(inNodes).map(function (n) {
-      var result = fn(n, graph.node(n), cur.payload);
-      console.log(result);
-      return _lodash2.default.map(result, function (res) {
-        return { node: n, port: res.port, payload: res.payload, path: _lodash2.default.concat(cur.path, n) };
-      });
-    }).flatten().value();
-    if (newCallStackElements.length === 0) {
-      endPoints.push(cur);
-    }
-    callStack = _lodash2.default.concat(callStack, newCallStackElements);
+    var portEdges = _.filter(inEdges, e => e.v === cur.node + '_PORT_' + cur.port);
+    var inNodes = _(portEdges).map(e => graph.predecessors(e.v)).flatten().map(e => graph.predecessors(e)).flatten().value();
+    var newCallStackElements = _.map(inNodes, n => {
+      var result = fn(graph.node(n), cur.payload);
+      return _.map(result, port => ({ node: n, port: port }));
+    });
+    callStack = _.concat(callStack, _.flatten(newCallStackElements));
   }
-  return endPoints;
 }

lib/compoundify.js

@@ -17,2 +17,6 @@ 'use strict';
 
+var _objectHash = require('object-hash');
+
+var _objectHash2 = _interopRequireDefault(_objectHash);
+
 function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; }
@@ -67,3 +71,3 @@
 // checks if the element is blocked forward
-var checkForward = function checkForward(elem, graph, topsort, last) {
+var blockedForward = function blockedForward(elem, graph, topsort, last) {
   if (_lodash2.default.indexOf(topsort, elem) > last) {
@@ -83,3 +87,3 @@ return false;
 
-      if (checkForward(succ, graph, topsort, last)) {
+      if (blockedForward(succ, graph, topsort, last)) {
         return true;
@@ -105,3 +109,3 @@ }
 // checks if the element is blocked backward
-var checkBackward = function checkBackward(elem, graph, topsort, first) {
+var blockedBackward = function blockedBackward(elem, graph, topsort, first) {
   if (_lodash2.default.indexOf(topsort, elem) > first) {
@@ -121,3 +125,3 @@ return false;
 
-      if (checkBackward(pred, graph, topsort, first)) {
+      if (blockedBackward(pred, graph, topsort, first)) {
         return true;
@@ -142,4 +146,42 @@ }
 
+var sameParents = function sameParents(graph, subset) {
+  if (subset.length < 1) {
+    return true;
+  }
+  var par = graph.parent(subset[0]);
+  var _iteratorNormalCompletion4 = true;
+  var _didIteratorError4 = false;
+  var _iteratorError4 = undefined;
+
+  try {
+    for (var _iterator4 = subset[Symbol.iterator](), _step4; !(_iteratorNormalCompletion4 = (_step4 = _iterator4.next()).done); _iteratorNormalCompletion4 = true) {
+      var n = _step4.value;
+
+      if (graph.parent(n) !== par) {
+        return false;
+      }
+    }
+  } catch (err) {
+    _didIteratorError4 = true;
+    _iteratorError4 = err;
+  } finally {
+    try {
+      if (!_iteratorNormalCompletion4 && _iterator4.return) {
+        _iterator4.return();
+      }
+    } finally {
+      if (_didIteratorError4) {
+        throw _iteratorError4;
+      }
+    }
+  }
+
+  return true;
+};
+
 function isCompoundable(g, subset) {
   var graph = _graphlib2.default.json.read(JSON.parse(JSON.stringify(_graphlib2.default.json.write(g))));
+  if (!sameParents(graph, subset) || !graph.isCompound()) {
+    return false;
+  }
   markNodes(graph, subset);
@@ -154,3 +196,3 @@ var topsort = _graphlib2.default.alg.topsort(graph);
       }
-      if (checkForward(topsort[i], graph, topsort, last) && checkBackward(topsort[i], graph, topsort)) {
+      if (blockedForward(topsort[i], graph, topsort, last) && blockedBackward(topsort[i], graph, topsort)) {
         return false;
@@ -168,6 +210,35 @@ }
   }
+  if (subset.length < 1) {
+    return g;
+  }
   var graph = _graphlib2.default.json.read(JSON.parse(JSON.stringify(_graphlib2.default.json.write(g))));
   markNodes(graph, subset);
-  console.log(JSON.stringify(_graphlib2.default.json.write(graph)));
+  var comp = 'comp' + (0, _objectHash2.default)(graph);
+  graph.setNode(comp);
+  var _iteratorNormalCompletion5 = true;
+  var _didIteratorError5 = false;
+  var _iteratorError5 = undefined;
+
+  try {
+    for (var _iterator5 = subset[Symbol.iterator](), _step5; !(_iteratorNormalCompletion5 = (_step5 = _iterator5.next()).done); _iteratorNormalCompletion5 = true) {
+      var n = _step5.value;
+
+      graph.setParent(n, comp);
+    }
+  } catch (err) {
+    _didIteratorError5 = true;
+    _iteratorError5 = err;
+  } finally {
+    try {
+      if (!_iteratorNormalCompletion5 && _iterator5.return) {
+        _iterator5.return();
+      }
+    } finally {
+      if (_didIteratorError5) {
+        throw _iteratorError5;
+      }
+    }
+  }
+
   return graph;
 }

lib/utils.js

@@ -45,3 +45,3 @@ 'use strict';
 function edit(graph) {
-  return _graphlib2.default.json.write(graph);
+  return JSON.parse(JSON.stringify(_graphlib2.default.json.write(graph)));
 }
@@ -48,0 +48,0 @@

lib/walkNetworkGraph.js

@@ -33,9 +33,9 @@ 'use strict';
 
-function neighbor(graph, node, port, neighborFn, multiCase, multiPortFn, jumpOver, jumpOverFn) {
+function neighbor(graph, node, port, neighborFn, nType, multiCase, multiPortFn, jumpOver, jumpOverFn) {
   var edges = graph.edges();
   var portNode = node + '_PORT_' + port;
   var nodes = _lodash2.default.filter(edges, function (e) {
-    return e.v === portNode;
+    return e[nType] === portNode;
   }).map(function (e) {
-    return e.v;
+    return e[nType];
   });
@@ -60,5 +60,5 @@ if (nodes.length > 1) {
     if (neigh.name.indexOf(multiCase) !== -1) {
-      return _lodash2.default.flatten([neighbor(graph, neigh.name, multiPortFn(graph, neigh.name, 0), neighborFn, multiCase, multiPortFn, jumpOver, jumpOverFn), neighbor(graph, neigh.name, multiPortFn(graph, neigh.name, 1), neighborFn, multiCase, multiPortFn, jumpOver, jumpOverFn)]);
+      return _lodash2.default.flatten([neighbor(graph, neigh.name, multiPortFn(graph, neigh.name, 0), neighborFn, nType, multiCase, multiPortFn, jumpOver, jumpOverFn), neighbor(graph, neigh.name, multiPortFn(graph, neigh.name, 1), neighborFn, nType, multiCase, multiPortFn, jumpOver, jumpOverFn)]);
     } else if (neigh.name.indexOf(jumpOver) !== -1) {
-      return neighbor(graph, neigh.name, multiPortFn(graph, neigh.name, 0), neighborFn, multiCase, multiPortFn, jumpOver, jumpOverFn);
+      return neighbor(graph, neigh.name, multiPortFn(graph, neigh.name, 0), neighborFn, nType, multiCase, multiPortFn, jumpOver, jumpOverFn);
     }
@@ -71,7 +71,7 @@ return { node: neigh.name, port: lastPort };
 function successor(graph, node, port) {
-  return neighbor(graph, node, port, _lodash2.default.partial(getSuccessorWithCheck, graph, _lodash2.default, node, port), '_DUPLICATE_', _utils.nthOutput, '_JOIN_', _utils.nthOutput);
+  return neighbor(graph, node, port, _lodash2.default.partial(getSuccessorWithCheck, graph, _lodash2.default, node, port), 'v', '_DUPLICATE_', _utils.nthOutput, '_JOIN_', _utils.nthOutput);
 }
 
 function predecessor(graph, node, port) {
-  return neighbor(graph, node, port, _lodash2.default.partial(getPredecessorWithCheck, graph, _lodash2.default, node, port), '_JOIN_', _utils.nthInput, '_DUPLICATE_', _utils.nthInput);
+  return neighbor(graph, node, port, _lodash2.default.partial(getPredecessorWithCheck, graph, _lodash2.default, node, port), 'w', '_JOIN_', _utils.nthInput, '_DUPLICATE_', _utils.nthInput);
 }

lib/walkPort.js

@@ -55,3 +55,3 @@ 'use strict';
 function predecessorPort(graph, node, port) {
-  var edges = graph.edges(node);
+  var edges = graph.nodeEdges(node);
   var nodes = _lodash2.default.filter(edges, function (e) {
@@ -64,6 +64,3 @@ return e.v === node + '_PORT_' + port;
     var predecessors = graph.predecessors(nodes[i]);
-    if (predecessors.length === 0) {
-      return [];
-    }
-    while (graph.predecessors(predecessors[0]).length > 0 && graph.node(predecessors[0]).hierarchyBorder) {
+    while (graph.node(predecessors[0]).hierarchyBorder) {
       predecessors = graph.predecessors(predecessors[0]);
@@ -74,3 +71,3 @@ }
   }
-  nodes = _lodash2.default.compact(nodes).map(function (n) {
+  nodes = nodes.map(function (n) {
     return n.split('_')[n.split('_').length - 1];
@@ -77,0 +74,0 @@ });

package.json

 {
   "name": "@buggyorg/graphtools",
-  "version": "0.2.12",
+  "version": "0.2.13",
   "description": "Tools for processing buggy graphs.",
@@ -18,6 +18,7 @@ "main": "lib/api.js",
     "graphlib": "^2.1.0",
-    "lodash": "^4.6.1"
+    "lodash": "^4.6.1",
+    "object-hash": "^1.1.2"
   },
   "devDependencies": {
-    "@buggyorg/dupjoin": "^0.1.4",
+    "@buggyorg/dupjoin": "^0.1.5",
     "@buggyorg/npg-port-remodeler": "^0.1.9",
@@ -24,0 +25,0 @@ "babel-cli": "^6.4.5",

src/compoundify.js

 import graphlib from 'graphlib'
 import _ from 'lodash'
+import hash from 'object-hash'
 
@@ -30,7 +31,7 @@ var markNodes = function (graph, subset) {
 // checks if the element is blocked forward
-var checkForward = function (elem, graph, topsort, last) {
+var blockedForward = function (elem, graph, topsort, last) {
   if (_.indexOf(topsort, elem) > last) { return false }
   if (graph.node(elem).mark) { return true }
   for (let succ of graph.successors(elem)) {
-    if (checkForward(succ, graph, topsort, last)) { return true }
+    if (blockedForward(succ, graph, topsort, last)) { return true }
   }
@@ -40,12 +41,22 @@ }
 // checks if the element is blocked backward
-var checkBackward = function (elem, graph, topsort, first) {
+var blockedBackward = function (elem, graph, topsort, first) {
   if (_.indexOf(topsort, elem) > first) { return false }
   if (graph.node(elem).mark) { return true }
   for (let pred of graph.predecessors(elem)) {
-    if (checkBackward(pred, graph, topsort, first)) { return true }
+    if (blockedBackward(pred, graph, topsort, first)) { return true }
   }
 }
 
+var sameParents = function (graph, subset) {
+  if (subset.length < 1) { return true }
+  var par = graph.parent(subset[0])
+  for (let n of subset) {
+    if (graph.parent(n) !== par) { return false }
+  }
+  return true
+}
+
 export function isCompoundable (g, subset) {
   var graph = graphlib.json.read(JSON.parse(JSON.stringify(graphlib.json.write(g))))
+  if (!sameParents(graph, subset) || !graph.isCompound()) { return false }
   markNodes(graph, subset)
@@ -60,3 +71,3 @@ var topsort = graphlib.alg.topsort(graph)
       }
-      if (checkForward(topsort[i], graph, topsort, last) && checkBackward(topsort[i], graph, topsort)) {
+      if (blockedForward(topsort[i], graph, topsort, last) && blockedBackward(topsort[i], graph, topsort)) {
         return false
@@ -72,6 +83,11 @@ }
   if (!isCompoundable(g, subset)) { throw new Error('This subset cannot be compoundified given this particular subset.') }
+  if (subset.length < 1) { return g }
   var graph = graphlib.json.read(JSON.parse(JSON.stringify(graphlib.json.write(g))))
   markNodes(graph, subset)
-  console.log(JSON.stringify(graphlib.json.write(graph)))
+  var comp = 'comp' + hash(graph)
+  graph.setNode(comp)
+  for (let n of subset) {
+    graph.setParent(n, comp)
+  }
   return graph
 }

src/utils.js

@@ -14,3 +14,3 @@
 export function edit (graph) {
-  return graphlib.json.write(graph)
+  return JSON.parse(JSON.stringify(graphlib.json.write(graph)))
 }
@@ -17,0 +17,0 @@

src/walkNetworkGraph.js

@@ -21,6 +21,6 @@
 
-function neighbor (graph, node, port, neighborFn, multiCase, multiPortFn, jumpOver, jumpOverFn) {
+function neighbor (graph, node, port, neighborFn, nType, multiCase, multiPortFn, jumpOver, jumpOverFn) {
   var edges = graph.edges()
   var portNode = node + '_PORT_' + port
-  var nodes = _.filter(edges, (e) => e.v === portNode).map((e) => e.v)
+  var nodes = _.filter(edges, (e) => e[nType] === portNode).map((e) => e[nType])
   if (nodes.length > 1) {
@@ -45,7 +45,7 @@ throw new Error('Invalid port graph, every port can only have one predecessor (violated for ' + node + '@' + port + ')')
       return _.flatten([
-        neighbor(graph, neigh.name, multiPortFn(graph, neigh.name, 0), neighborFn, multiCase, multiPortFn, jumpOver, jumpOverFn),
-        neighbor(graph, neigh.name, multiPortFn(graph, neigh.name, 1), neighborFn, multiCase, multiPortFn, jumpOver, jumpOverFn)
+        neighbor(graph, neigh.name, multiPortFn(graph, neigh.name, 0), neighborFn, nType, multiCase, multiPortFn, jumpOver, jumpOverFn),
+        neighbor(graph, neigh.name, multiPortFn(graph, neigh.name, 1), neighborFn, nType, multiCase, multiPortFn, jumpOver, jumpOverFn)
       ])
     } else if (neigh.name.indexOf(jumpOver) !== -1) {
-      return neighbor(graph, neigh.name, multiPortFn(graph, neigh.name, 0), neighborFn, multiCase, multiPortFn, jumpOver, jumpOverFn)
+      return neighbor(graph, neigh.name, multiPortFn(graph, neigh.name, 0), neighborFn, nType, multiCase, multiPortFn, jumpOver, jumpOverFn)
     }
@@ -58,7 +58,7 @@ return {node: neigh.name, port: lastPort}
 export function successor (graph, node, port) {
-  return neighbor(graph, node, port, _.partial(getSuccessorWithCheck, graph, _, node, port), '_DUPLICATE_', nthOutput, '_JOIN_', nthOutput)
+  return neighbor(graph, node, port, _.partial(getSuccessorWithCheck, graph, _, node, port), 'v', '_DUPLICATE_', nthOutput, '_JOIN_', nthOutput)
 }
 
 export function predecessor (graph, node, port) {
-  return neighbor(graph, node, port, _.partial(getPredecessorWithCheck, graph, _, node, port), '_JOIN_', nthInput, '_DUPLICATE_', nthInput)
+  return neighbor(graph, node, port, _.partial(getPredecessorWithCheck, graph, _, node, port), 'w', '_JOIN_', nthInput, '_DUPLICATE_', nthInput)
 }

test/compoundify.js

@@ -29,2 +29,9 @@ /* global describe, it */
 
+  var simpleDif = grlib.json.read(JSON.parse(fs.readFileSync('./test/fixtures/compoundify/simple.json')))
+  simpleDif.setNode('par')
+  simpleDif.setParent('a', 'par')
+  it('different parents in subset of simple graph', () => {
+    expect(cmpdfy.isCompoundable(simpleDif, ['a', 'b'])).to.be.false
+  })
+
   var diamond = grlib.json.read(JSON.parse(fs.readFileSync('./test/fixtures/compoundify/diamond.json')))
@@ -57,8 +64,26 @@ it('all nodes in subset in diamond graph', () => {
 
-// TODO: Unfinished
 describe('Compoundification of Subset of Nodes', () => {
   var simple = grlib.json.read(JSON.parse(fs.readFileSync('./test/fixtures/compoundify/simple.json')))
+  it('impossible subset of simple graph', () => {
+    expect(() => cmpdfy.compoundify(simple, ['a', 'c'])).to.throw(Error)
+  })
+
   it('empty subset of simple graph', () => {
-    cmpdfy.compoundify(simple, [])
+    expect(cmpdfy.compoundify(simple, [])).to.deep.equal(simple)
   })
+
+  it('unary subset of simple graph', () => {
+    var graph = cmpdfy.compoundify(simple, ['b'])
+    expect(graph.nodes().length).to.equal(4)
+    expect(graph.parent('b')).to.not.be.undefined
+    expect(graph.parent('a')).to.be.undefined
+  })
+
+  it('possible subset of simple graph', () => {
+    var graph = cmpdfy.compoundify(simple, ['b', 'a'])
+    expect(graph.nodes().length).to.equal(4)
+    expect(graph.parent('a')).to.not.be.undefined
+    expect(graph.parent('b')).to.not.be.undefined
+    expect(graph.parent('c')).to.be.undefined
+  })
 })

test/walk.js

@@ -182,2 +182,9 @@ /* global describe, it */
     })
+    
+    if(setting === 'network graphs') {
+      it('can walk through recursive map correctly', () => {
+        var mapG = grlib.json.read(JSON.parse(fs.readFileSync('./test/fixtures/map_recursive.json')))
+        var paths = walk.walkBack(mapG, 'mapInc', ['data'], {keepPorts: true})
+      })
+    }
   })
@@ -184,0 +191,0 @@ }

No alert changes

Improved metrics

Total package byte prevSize

209538

increased by73.9%

Number of package files

43

increased by2.38%

Lines of code

7076

increased by92.91%

Worsened metrics

Dependency count

3

increased by50%

Dependency changes

• + Addedobject-hash@^1.1.2

• + Addedobject-hash@1.3.1(transitive)