simplicial-complex - npm Package Compare versions

Comparing version 0.2.0 to 0.3.0

package.json

 {
   "name": "simplicial-complex",
-  "version": "0.2.0",
+  "version": "0.3.0",
   "description": "Topological indexing for simplicial complexes",
@@ -5,0 +5,0 @@ "main": "topology.js",

README.md

@@ -69,4 +69,4 @@ simplicial-complex
 
-Generic
--------
+Structural
+----------
 
@@ -102,4 +102,2 @@ ### `dimension(cells)`
 
-Indexing and Incidence
-----------------------
 
@@ -125,6 +123,15 @@ ### `compareCells(a, b)`
 
-**Returns** `cells`
+**Returns:** `cells`
 
 **Time complexity:** `O(d * log(cells.length) * cells.length )`
 
+### `unique(cells)`
+Removes all duplicate cells from the complex.  Note that this is done **in place**.  `cells` will be mutated.  If this is not acceptable, make a copy of `cells` first.
+
+* `cells` is a `normalize`d complex
+
+**Returns:** `cells`
+
+**Time complexity:** `O(cells.length)`
+
 ### `findCell(cells, c)`
@@ -140,5 +147,27 @@ Finds a lower bound on the first index of cell `c` in a `normalize`d array of cells.
 
-### `buildIndex(from_cells, to_cells)`
-Builds an index for [neighborhood queries](http://en.wikipedia.org/wiki/Polygon_mesh#Summary_of_mesh_representation).  This allows you to quickly find cells the in `to_cells` which are incident to cells in `from_cells`.
+Topological
+-----------
 
+### `explode(cells)`
+Enumerates all cells in the complex, with duplicates
+
+* `cells` is an array of cells
+
+**Returns:** A list of all cells in the complex
+
+**Time complexity:** `O(2^d * cells.length)`
+
+### `skeleton(cells, n)`
+Enumerates all n cells in the complex, with duplicates
+
+* `cells` is an array of cells
+* `n` is the dimension of the cycles to compute
+
+**Returns:**  A list of all n-cells
+
+**Time complexity:** `O(d^n * cells.length)`
+
+### `incidence(from_cells, to_cells)`
+Builds an index for [neighborhood queries](http://en.wikipedia.org/wiki/Polygon_mesh#Summary_of_mesh_representation) (aka a sparse incidence matrix).  This allows you to quickly find the cells in `to_cells` which are incident to cells in `from_cells`.
+
 * `from_cells` a `normalize`d array of cells
@@ -151,5 +180,2 @@ * `to_cells` a list of cells which we are going to query against
 
-Basic Topology
---------------
-
 ### `dual(cells[, vertex_count])`
@@ -162,3 +188,3 @@ Computes the [dual](http://en.wikipedia.org/wiki/Hypergraph#Incidence_matrix) of the complex.  An important application of this is that it gives a more optimized way to build an index for vertices for cell complexes with sequentially enumerated vertices.  For example,
 
-    top.buildIndex(cells, top.skeleton(cells, 0), 0)
+    top.buildIndex(cells, top.unique(top.normalize(top.skeleton(cells, 0))), 0)
     
@@ -172,37 +198,2 @@ * `cells` is a cell complex
 
-### `subcells(cells, n)`
-Enumerates all n cells in the complex.
-
-* `cells` is an array of cells
-* `n` is the dimension of the cycles to compute
-
-**Returns:**  A list of all cycles
-
-**Time complexity:** `O(d^n * cells.length)`
-
-### `skeleton(cells, n)`
-Computes the [n-skeleton](http://en.wikipedia.org/wiki/N-skeleton) of an unoriented simplicial complex.  This is the set of all unique n-cells up to permutation.
-
-* `cells` is a cell complex
-* `n` is the dimension of the skeleton to compute.
-
-**Returns:** A `normalize` array of all n-cells which are unique up to permutation.
-
-**Example:**
-
-* `skeleton(tris, 1)` returns all the edge in a triangular mesh
-* `skeleton(tets, 2)` returns all the faces of a tetrahedral mesh
-* `skeleton(cells, 0)` returns all the vertices of a mesh
-
-**Time complexity:**  `O( n^d * cells.length )`, where d is the `dimension` of the cell complex
-
-### `boundary(cells)`
-Computes the <a href="http://en.wikipedia.org/wiki/Boundary_(topology)">d-dimensional boundary</a> of all cells, including duplicates.
-
-* `cells` is a cell complex.
-
-**Returns:** An array of cells representing the boundary of the cell complex.
-
-**Time complexity:** `O((d^n + log(cells.length)) * cells.length)`
-
 ### `connectedComponents(cells[, vertex_count])`
@@ -209,0 +200,0 @@ Splits a simplicial complex into its <a href="http://en.wikipedia.org/wiki/Connected_component_(topology)">connected components</a>.  If `vertex_count` is specified, we assume that the cell complex is dense -- or in other words the vertices of the cell complex is the set of integers [0, vertex_count).  This allows for a slightly more efficient implementation.  If unspecified, a more general but less efficient sparse algorithm is used.

test/test.js

@@ -88,3 +88,3 @@ var test = require("tap").test
   var r = [[1,2,3]];
-  arr_equals(t, top.skeleton(r,1), [
+  arr_equals(t, top.unique(top.normalize(top.skeleton(r,1))), [
     [1,2],
@@ -96,3 +96,3 @@ [1,3],
   var h = [[1,2,3],[2,3,4]];
-  arr_equals(t, top.skeleton(h, 1), [
+  arr_equals(t, top.unique(top.normalize(top.skeleton(h, 1))), [
     [1,2],
@@ -106,3 +106,3 @@ [1,3],
   var k = [[1,2,3,4,5,6,7,8]];
-  arr_equals(t, top.skeleton(k, 0), [
+  arr_equals(t, top.normalize(top.skeleton(k, 0)), [
     [1],
@@ -178,3 +178,3 @@ [2],
   
-  var index = top.buildIndex(from_cells, to_cells);
+  var index = top.incidence(from_cells, to_cells);
   t.equals(index.length, from_cells.length);
@@ -181,0 +181,0 @@

topology.js

@@ -114,2 +114,20 @@ "use strict"; "use restrict";
 
+//Removes all duplicate cells in the complex
+function unique(cells) {
+  var ptr = 1;
+  for(var i=1; i<cells.length; ++i) {
+    var a = cells[i];
+    if(compareCells(a, cells[i-1])) {
+      if(i === ptr) {
+        ptr++;
+        continue;
+      }
+      cells[ptr++] = a;
+    }
+  }
+  cells.length = ptr;
+  return cells;
+}
+exports.unique = unique;
+
 //Finds a cell in a normalized cell complex
@@ -137,3 +155,3 @@ function findCell(cells, c) {
 //Builds an index for an n-cell.  This is more general than dual, but less efficient
-function buildIndex(from_cells, to_cells) {
+function incidence(from_cells, to_cells) {
   var index = new Array(from_cells.length);
@@ -168,3 +186,3 @@ for(var i=0; i<index.length; ++i) {
 }
-exports.buildIndex = buildIndex;
+exports.incidence = incidence;
 
@@ -174,3 +192,3 @@ //Computes the dual of the mesh.  This is basically an optimized version of buildIndex for the situation where from_cells is just the list of vertices
   if(!vertex_count) {
-    return buildIndex(skeleton(cells, 0), cells, 0);
+    return incidence(unique(normalize(skeleton(cells, 0))), cells, 0);
   }
@@ -191,4 +209,22 @@ var res = new Array(vertex_count);
 
-//Enumerates all of the n-cells of a cell complex (in more technical terms, the boundary operator with free coefficients)
-function fullSkeleton(cells, n) {
+//Enumerates all cells in the complex
+function explode(cells) {
+  var result = [];
+  for(var i=0; i<cells.length; ++i) {
+    var c = cells[i];
+    for(var j=1; j<1<<c.length; ++j) {
+      var b = [];
+      for(var k=0; k<c.length; ++k) {
+        if(j & (1<<k)) {
+          b.push(c[k]);
+        }
+      }
+    }
+  }
+  return result;
+}
+exports.explode = explode;
+
+//Enumerates all of the n-cells of a cell complex
+function skeleton(cells, n) {
   if(n < 0) {
@@ -214,29 +250,2 @@ return [];
 }
-exports.fullSkeleton = fullSkeleton;
-
-//Computes the n-skeleton of a cell complex (in other words, the n-boundary operator in the homology over the Boolean semiring)
-function skeleton(cells, n) {
-  if(n < 0) {
-    return [];
-  }
-  var res = fullSkeleton(cells, n);
-  normalize(res);
-  var ptr = 1;
-  for(var i=1; i<res.length; ++i) {
-    var a = res[i];
-    if(compareCells(a, res[i-1])) {
-      if(i === ptr) {
-        ptr++;
-        continue;
-      }
-      var b = res[ptr++];
-      b.length = a.length;
-      for(var j=0; j<a.length; ++j) {
-        b[j] = a[j];
-      }
-    }
-  }
-  res.length = ptr;
-  return res;
-}
 exports.skeleton = skeleton;
@@ -293,3 +302,3 @@
 function connectedComponents_sparse(cells) {
-  var vertices  = skeleton(cells, 0)
+  var vertices  = unique(normalize(skeleton(cells, 0)))
     , labels    = new UnionFind(vertices.length);
@@ -296,0 +305,0 @@ for(var i=0; i<cells.length; ++i) {

No alert changes

Improved metrics

Lines of code

502

increased by1.62%

Worsened metrics

Total package byte prevSize

22099

decreased by-1.57%

Number of lines in readme file

209

decreased by-4.13%

No dependency changes