isomorphism - npm Package Compare versions

Comparing version 0.1.0 to 0.2.0

lib/index.js

@@ -6,4 +6,8 @@ 'use strict';
 });
-exports.allIsomorphisms = exports.extractAtMostOneIsomorphism = exports.flatmap = undefined;
+exports.allIsomorphismsForDigraphs = exports.allIsomorphismsForWeightedDigraphs = exports.extractAtMostOneIsomorphism = exports.flatmap = undefined;
 
+var _typeof = typeof Symbol === "function" && typeof Symbol.iterator === "symbol" ? function (obj) { return typeof obj; } : function (obj) { return obj && typeof Symbol === "function" && obj.constructor === Symbol && obj !== Symbol.prototype ? "symbol" : typeof obj; };
+
+var _slicedToArray = function () { function sliceIterator(arr, i) { var _arr = []; var _n = true; var _d = false; var _e = undefined; try { for (var _i = arr[Symbol.iterator](), _s; !(_n = (_s = _i.next()).done); _n = true) { _arr.push(_s.value); if (i && _arr.length === i) break; } } catch (err) { _d = true; _e = err; } finally { try { if (!_n && _i["return"]) _i["return"](); } finally { if (_d) throw _e; } } return _arr; } return function (arr, i) { if (Array.isArray(arr)) { return arr; } else if (Symbol.iterator in Object(arr)) { return sliceIterator(arr, i); } else { throw new TypeError("Invalid attempt to destructure non-iterable instance"); } }; }();
+
 var _ramda = require('ramda');
@@ -21,9 +25,32 @@
 
-// In the directed graph `graph`, does `vertex` have an edge to `neighbor`?
+var getIndex = function getIndex(_ref) {
+  var _ref2 = _slicedToArray(_ref, 2),
+      index = _ref2[0],
+      weight = _ref2[1];
 
+  return index;
+};
+var getWeight = function getWeight(_ref3) {
+  var _ref4 = _slicedToArray(_ref3, 2),
+      index = _ref4[0],
+      weight = _ref4[1];
 
-var isAdjacent = function isAdjacent(graph, vertex, neighbor) {
-  for (var i = 0; i <= graph[vertex].length; i++) {
-    if (graph[vertex][i] > neighbor) return false; // NOTE: adjacency list must be sorted ascending
-    if (graph[vertex][i] === neighbor) return true;
+  return weight;
+};
+var weightOneEdge = function weightOneEdge(index) {
+  return [index, 1];
+};
+var digraphToWeighted = function digraphToWeighted(graph) {
+  return (0, _ramda.map)(function (neighbors) {
+    return (0, _ramda.map)(function (neighborIndex) {
+      return weightOneEdge(neighborIndex);
+    }, neighbors);
+  }, graph);
+};
+
+// In the directed graph `graph`, does `vertex` have an edge to `neighbor`?
+var isAdjacent = function isAdjacent(graph, accessIndex, adjacencyPred, vertex, neighbor) {
+  for (var i = 0; i < graph[vertex].length; i++) {
+    if (accessIndex(graph[vertex][i]) > neighbor) return false; // NOTE: adjacency list must be sorted ascending
+    if (adjacencyPred(graph[vertex][i], neighbor)) return true;
   }
@@ -33,7 +60,2 @@ return false;
 
-// What is the degree of `vertex` in `graph`?
-var deg = function deg(graph, vertex) {
-  return graph[vertex].length;
-};
-
 /* Ullman */
@@ -48,14 +70,28 @@
 
-  for (var patternVertex = 0; patternVertex < pattern.length; patternVertex++) {
-    var targetVertexForPatternVertex = mappedTargetVertex(patternVertex);
-    if (targetVertexForPatternVertex === null) return [];
-    var patternVector = pattern[patternVertex];
+  for (var _patternVertex = 0; _patternVertex < pattern.length; _patternVertex++) {
+    var correspondingTargetVertex = mappedTargetVertex(_patternVertex);
+    if (correspondingTargetVertex === null) return [];
+    var patternVector = pattern[_patternVertex];
+
+    var _loop = function _loop(j) {
+      var _patternVector$j = _slicedToArray(patternVector[j], 2),
+          patternNeighbor = _patternVector$j[0],
+          patternNeighborEdgeWeight = _patternVector$j[1];
+
+      var maybeTargetNeighbor = mappedTargetVertex(patternNeighbor);
+      if (maybeTargetNeighbor === null || !isAdjacent(target, getIndex, function (edge, neighborIndex) {
+        return getIndex(edge) === neighborIndex && getWeight(edge) >= patternNeighborEdgeWeight;
+      }, correspondingTargetVertex, maybeTargetNeighbor)) {
+        return {
+          v: []
+        };
+      }
+    };
+
     for (var j = 0; j < patternVector.length; j++) {
-      var patternNeighbor = patternVector[j];
-      var maybeTarget = mappedTargetVertex(patternNeighbor);
-      if (maybeTarget === null || !isAdjacent(target, targetVertexForPatternVertex, maybeTarget)) {
-        return [];
-      }
+      var _ret = _loop(j);
+
+      if ((typeof _ret === 'undefined' ? 'undefined' : _typeof(_ret)) === "object") return _ret.v;
     }
-    iso.push(targetVertexForPatternVertex);
+    iso.push(correspondingTargetVertex);
   }
@@ -77,5 +113,5 @@ return [iso];
   var refinedMapping = [];
-  for (var patternVertex = 0; patternVertex < mapping.length; patternVertex++) {
+  for (var _patternVertex2 = 0; _patternVertex2 < mapping.length; _patternVertex2++) {
     refinedMapping.push([]);
-    var mappingVector = mapping[patternVertex];
+    var mappingVector = mapping[_patternVertex2];
 
@@ -85,5 +121,5 @@ if (mappingVector.length === 0) return null; // No possible mapping!
     for (var i = 0; i < mappingVector.length; i++) {
-      var _possibleTarget = mappingVector[i];
-      if (predicate(patternVertex, _possibleTarget)) {
-        refinedMapping[patternVertex].push(_possibleTarget);
+      var possibleTarget = mappingVector[i];
+      if (predicate(_patternVertex2, possibleTarget)) {
+        refinedMapping[_patternVertex2].push(possibleTarget);
       }
@@ -97,2 +133,7 @@ }
 var degreeRefine = function degreeRefine(pattern, target, mapping) {
+  // What is the degree of `vertex` in `graph`?
+  var deg = function deg(graph, vertex) {
+    return graph[vertex].length;
+  };
+
   return refine(mapping, function (patternVertex, targetVertex) {
@@ -105,5 +146,17 @@ return deg(pattern, patternVertex) <= deg(target, targetVertex);
   return refine(mapping, function (patternVertex, targetVertex) {
-    return (0, _ramda.all)(function (patternVertexNeighbor) {
-      return (0, _ramda.any)(function (targetVertexNeighbor) {
-        return isAdjacent(mapping, patternVertexNeighbor, targetVertexNeighbor);
+    return (0, _ramda.all)(function (_ref5) {
+      var _ref6 = _slicedToArray(_ref5, 2),
+          patternVertexNeighbor = _ref6[0],
+          patternNeighborEdgeWeight = _ref6[1];
+
+      return (0, _ramda.any)(function (_ref7) {
+        var _ref8 = _slicedToArray(_ref7, 2),
+            targetVertexNeighbor = _ref8[0],
+            targetNeighborEdgeWeight = _ref8[1];
+
+        return isAdjacent(mapping, function (x) {
+          return x;
+        }, function (edge, neighborIndex) {
+          return edge === neighborIndex;
+        }, patternVertexNeighbor, targetVertexNeighbor) && patternNeighborEdgeWeight <= targetNeighborEdgeWeight;
       }, target[targetVertex]);
@@ -132,5 +185,13 @@ }, pattern[patternVertex]);
 
-var allIsomorphisms = exports.allIsomorphisms = function allIsomorphisms(pattern, target, initialpossibleMappings) {
+var allIsomorphismsForWeightedDigraphs = exports.allIsomorphismsForWeightedDigraphs = function allIsomorphismsForWeightedDigraphs(pattern, target, initialpossibleMappings) {
+
   var maybeRefined = degreeRefine(pattern, target, initialpossibleMappings || allMappings(pattern.length, target.length));
   return !maybeRefined ? [] : pattern.length > target.length ? [] : search(pattern, target, maybeRefined, 0);
+};
+
+var allIsomorphismsForDigraphs = exports.allIsomorphismsForDigraphs = function allIsomorphismsForDigraphs(pattern, target, initialpossibleMappings) {
+  var weightedPattern = digraphToWeighted(pattern);
+  var weightedTarget = digraphToWeighted(target);
+
+  return allIsomorphismsForWeightedDigraphs(weightedPattern, weightedTarget, initialpossibleMappings);
 };

package.json

 {
   "name": "isomorphism",
-  "version": "0.1.0",
+  "version": "0.2.0",
   "description": "Find subgraph isomorphisms with Ullman's 1976 algorithm.",
@@ -5,0 +5,0 @@ "main": "lib/index.js",

test/test.js

@@ -6,3 +6,3 @@ /* @flow */
 import assert from 'assert'
-import { allIsomorphisms } from '../lib/index'
+import { allIsomorphismsForDigraphs, allIsomorphismsForWeightedDigraphs } from '../lib/index'
 
@@ -19,7 +19,35 @@ declare class describe {
 
-describe('Isomorphism', function () {
+describe('Weighted', function () {
 
+  it('Three-cycle with one two-weighted edge has one isomorpism to a certain directed Hajos graph', function () {
+    assert.deepEqual(
+      allIsomorphismsForWeightedDigraphs(
+        [
+          [[1,200]],
+          [[2,1]],
+          [[0,1]]
+        ],
+        [
+          [[1,800]],
+          [[2,1],[3,1]],
+          [[0,1],[4,1]],
+          [[4,1]],
+          [[1,1],[5,1]],
+          [[2,1]]
+        ],
+        null
+      ),
+      [
+        [0,1,2]
+      ]
+    )
+  })
+
+})
+
+describe('Unweighted', function () {
+
   it('a -> b has only one isomorphism to a -> b', function () {
     assert.deepEqual(
-      allIsomorphisms(
+      allIsomorphismsForDigraphs(
         [
@@ -43,3 +71,3 @@ [1],
     assert.deepEqual(
-      allIsomorphisms(
+      allIsomorphismsForDigraphs(
         [
@@ -67,3 +95,3 @@ [1],
     assert.deepEqual(
-      allIsomorphisms(
+      allIsomorphismsForDigraphs(
         [
@@ -103,3 +131,3 @@ [1],
     assert.deepEqual(
-      allIsomorphisms(
+      allIsomorphismsForDigraphs(
         [
@@ -143,3 +171,3 @@ [1],
     assert.deepEqual(
-      allIsomorphisms(
+      allIsomorphismsForDigraphs(
         [
@@ -171,3 +199,3 @@ [1],
     assert.deepEqual(
-      allIsomorphisms(
+      allIsomorphismsForDigraphs(
         [
@@ -174,0 +202,0 @@ [1],

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

20545

increased by34.51%

Lines of code

363

increased by26.48%

Number of medium supply chain risk alerts

0

decreased by-100%

No dependency changes