topology.js
function connectedComponents_sparse(cells) {
  var vertices  = unique(normalize(skeleton(cells, 0)))
    , labels    = new UnionFind(vertices.length)
  for(var i=0; i<cells.length; ++i) {
    var c = cells[i]
    for(var j=0; j<c.length; ++j) {
      var vj = findCell(vertices, [c[j]])
      for(var k=j+1; k<c.length; ++k) {
        labels.link(vj, findCell(vertices, [c[k]]))
      }
    }
  }
  var components        = []
    , component_labels  = labels.ranks
  for(var i=0; i<component_labels.length; ++i) {
    component_labels[i] = -1
  }
  for(var i=0; i<cells.length; ++i) {
    var l = labels.find(findCell(vertices, [cells[i][0]]));
    if(component_labels[l] < 0) {
      component_labels[l] = components.length
      components.push([cells[i].slice(0)])
    } else {
      components[component_labels[l]].push(cells[i].slice(0))
    }
  }
  return components
}
function connectedComponents_sparse(cells) {
  var vertices  = unique(normalize(skeleton(cells, 0)))
    , labels    = new UnionFind(vertices.length)
  for(var i=0; i<cells.length; ++i) {
    var c = cells[i]
    for(var j=0; j<c.length; ++j) {
      var vj = findCell(vertices, [c[j]])
      for(var k=j+1; k<c.length; ++k) {
        labels.link(vj, findCell(vertices, [c[k]]))
      }
    }
  }
  var components        = []
    , component_labels  = labels.ranks
  for(var i=0; i<component_labels.length; ++i) {
    component_labels[i] = -1
  }
  for(var i=0; i<cells.length; ++i) {
    var l = labels.find(findCell(vertices, [cells[i][0]]));
    if(component_labels[l] < 0) {
      component_labels[l] = components.length
      components.push([cells[i].slice(0)])
    } else {
      components[component_labels[l]].push(cells[i].slice(0))
    }
  }
  return components
}
function connectedComponents_sparse ( cells ) { var vertices = unique ( normalize ( skeleton ( cells , 0 ) ) ) , labels = new UnionFind ( vertices . length ) for ( var i = 0 ; i < cells . length ; ++ i ) { var c = cells [ i ] for ( var j = 0 ; j < c . length ; ++ j ) { var vj = findCell ( vertices , [ c [ j ] ] ) for ( var k = j + 1 ; k < c . length ; ++ k ) { labels . link ( vj , findCell ( vertices , [ c [ k ] ] ) ) } } } var components = [ ] , component_labels = labels . ranks for ( var i = 0 ; i < component_labels . length ; ++ i ) { component_labels [ i ] = - 1 } for ( var i = 0 ; i < cells . length ; ++ i ) { var l = labels . find ( findCell ( vertices , [ cells [ i ] [ 0 ] ] ) ) ; if ( component_labels [ l ] < 0 ) { component_labels [ l ] = components . length components . push ( [ cells [ i ] . slice ( 0 ) ] ) } else { components [ component_labels [ l ] ] . push ( cells [ i ] . slice ( 0 ) ) } } return components }
Computes connected components for a sparse graph
Computes connected components for a sparse graph