basant307/AI_Governance_Project

1import * as util from '../../util/index.mjs';2import * as math from '../../math.mjs';3import * as is from '../../is.mjs';4 5/* eslint-disable no-unused-vars */6const defaults = {7  fit: true, // whether to fit the viewport to the graph8  directed: false, // whether the tree is directed downwards (or edges can point in any direction if false)9  direction: 'downward', // determines the direction in which the tree structure is drawn.  The possible values are 'downward', 'upward', 'rightward', or 'leftward'.10  padding: 30, // padding on fit11  circle: false, // put depths in concentric circles if true, put depths top down if false12  grid: false, // whether to create an even grid into which the DAG is placed (circle:false only)13  spacingFactor: 1.75, // positive spacing factor, larger => more space between nodes (N.B. n/a if causes overlap)14  boundingBox: undefined, // constrain layout bounds; { x1, y1, x2, y2 } or { x1, y1, w, h }15  avoidOverlap: true, // prevents node overlap, may overflow boundingBox if not enough space16  nodeDimensionsIncludeLabels: false, // Excludes the label when calculating node bounding boxes for the layout algorithm17  roots: undefined, // the roots of the trees18  depthSort: undefined, // a sorting function to order nodes at equal depth. e.g. function(a, b){ return a.data('weight') - b.data('weight') }19  animate: false, // whether to transition the node positions20  animationDuration: 500, // duration of animation in ms if enabled21  animationEasing: undefined, // easing of animation if enabled,22  animateFilter: function ( node, i ){ return true; }, // a function that determines whether the node should be animated.  All nodes animated by default on animate enabled.  Non-animated nodes are positioned immediately when the layout starts23  ready: undefined, // callback on layoutready24  stop: undefined, // callback on layoutstop25  transform: function (node, position ){ return position; } // transform a given node position. Useful for changing flow direction in discrete layouts26};27 28const deprecatedOptionDefaults = {29  maximal: false, // whether to shift nodes down their natural BFS depths in order to avoid upwards edges (DAGS only); setting acyclic to true sets maximal to true also30  acyclic: false, // whether the tree is acyclic and thus a node could be shifted (due to the maximal option) multiple times without causing an infinite loop; setting to true sets maximal to true also; if you are uncertain whether a tree is acyclic, set to false to avoid potential infinite loops31};32 33/* eslint-enable */34 35const getInfo = ele => ele.scratch('breadthfirst');36const setInfo = (ele, obj) => ele.scratch('breadthfirst', obj);37 38function BreadthFirstLayout( options ){39  this.options = util.extend( {}, defaults, deprecatedOptionDefaults, options );40}41 42BreadthFirstLayout.prototype.run = function(){43  const options = this.options;44  const cy = options.cy;45  const eles = options.eles;46  const nodes = eles.nodes().filter( n => n.isChildless() );47  const graph = eles;48  const directed = options.directed;49  const maximal = options.acyclic || options.maximal || options.maximalAdjustments > 0; // maximalAdjustments for compat. w/ old code; also, setting acyclic to true sets maximal to true50 51  const hasBoundingBox = !!options.boundingBox;52  const bb = math.makeBoundingBox( hasBoundingBox ? options.boundingBox :53    structuredClone(cy.extent()));54 55  let roots;56  if( is.elementOrCollection( options.roots ) ){57    roots = options.roots;58  } else if( is.array( options.roots ) ){59    const rootsArray = [];60 61    for( let i = 0; i < options.roots.length; i++ ){62      const id = options.roots[ i ];63      const ele = cy.getElementById( id );64      rootsArray.push( ele );65    }66 67    roots = cy.collection( rootsArray );68  } else if( is.string( options.roots ) ){69    roots = cy.$( options.roots );70 71  } else {72    if( directed ){73      roots = nodes.roots();74    } else {75      const components = eles.components();76 77      roots = cy.collection();78      for( let i = 0; i < components.length; i++ ){79        const comp = components[i];80        const maxDegree = comp.maxDegree( false );81        const compRoots = comp.filter( function( ele ){82          return ele.degree( false ) === maxDegree;83        } );84 85        roots = roots.add( compRoots );86      }87    }88  }89 90  const depths = [];91  const foundByBfs = {};92 93  const addToDepth = ( ele, d ) => {94    if( depths[d] == null ){95      depths[d] = [];96    }97 98    const i = depths[d].length;99 100    depths[d].push( ele );101 102    setInfo( ele, {103      index: i,104      depth: d105    } );106  };107 108  const changeDepth = ( ele, newDepth ) => {109    const { depth, index } = getInfo( ele );110 111    depths[ depth ][ index ] = null;112 113    // add only childless nodes114    if (ele.isChildless()) addToDepth( ele, newDepth );115  };116 117  // find the depths of the nodes118  graph.bfs( {119    roots: roots,120    directed: options.directed,121    visit: function( node, edge, pNode, i, depth ){122      const ele = node[0];123      const id = ele.id();124      125      // add only childless nodes126      if (ele.isChildless()) addToDepth( ele, depth );127      foundByBfs[ id ] = true;128    }129  } );130 131  // check for nodes not found by bfs132  const orphanNodes = [];133  for( let i = 0; i < nodes.length; i++ ){134    const ele = nodes[ i ];135 136    if( foundByBfs[ ele.id() ] ){137      continue;138    } else {139      orphanNodes.push( ele );140    }141  }142 143  // assign the nodes a depth and index144  const assignDepthsAt = function( i ){145    const eles = depths[ i ];146 147    for( let j = 0; j < eles.length; j++ ){148      const ele = eles[ j ];149 150      if( ele == null ){151        eles.splice( j, 1 );152        j--;153        continue;154      }155 156      setInfo(ele, {157        depth: i,158        index: j159      });160    }161  };162 163  const adjustMaximally = function( ele, shifted ){164    const eInfo = getInfo( ele );165    const incomers = ele.incomers().filter( el => el.isNode() && eles.has(el) );166    let maxDepth = -1;167    const id = ele.id();168 169    for( let k = 0; k < incomers.length; k++ ){170      const incmr = incomers[k];171      const iInfo = getInfo( incmr );172 173      maxDepth = Math.max( maxDepth, iInfo.depth );174    }175 176    if( eInfo.depth <= maxDepth ){177      if( !options.acyclic && shifted[id] ){178        return null;179      }180 181      const newDepth = maxDepth + 1;182      changeDepth( ele, newDepth );183      shifted[id] = newDepth;184 185      return true;186    }187 188    return false;189  };190 191  // for the directed case, try to make the edges all go down (i.e. depth i => depth i + 1)192  if( directed && maximal ){193    const Q = [];194    const shifted = {};195 196    const enqueue = n => Q.push(n);197    const dequeue = () => Q.shift();198 199    nodes.forEach( n => Q.push(n) );200 201    while( Q.length > 0 ){202      const ele = dequeue();203      const didShift = adjustMaximally( ele, shifted );204 205      if( didShift ){206        ele.outgoers().filter( el => el.isNode() && eles.has(el) ).forEach( enqueue );207      } else if( didShift === null ){208        util.warn('Detected double maximal shift for node `' + ele.id() + '`.  Bailing maximal adjustment due to cycle.  Use `options.maximal: true` only on DAGs.');209 210        break; // exit on failure211      }212    }213  }214 215  // find min distance we need to leave between nodes216  let minDistance = 0;217  if( options.avoidOverlap ){218    for( let i = 0; i < nodes.length; i++ ){219      const n = nodes[ i ];220      const nbb = n.layoutDimensions( options );221      const w = nbb.w;222      const h = nbb.h;223 224      minDistance = Math.max( minDistance, w, h );225    }226  }227 228  // get the weighted percent for an element based on its connectivity to other levels229  const cachedWeightedPercent = {};230  const getWeightedPercent = function( ele ){231    if( cachedWeightedPercent[ ele.id() ] ){232      return cachedWeightedPercent[ ele.id() ];233    }234 235    const eleDepth = getInfo( ele ).depth;236    const neighbors = ele.neighborhood();237    let percent = 0;238    let samples = 0;239 240    for( let i = 0; i < neighbors.length; i++ ){241      const neighbor = neighbors[ i ];242 243      if( neighbor.isEdge() || neighbor.isParent() || !nodes.has( neighbor ) ){244        continue;245      }246 247      const bf = getInfo( neighbor );248 249      if (bf == null){ continue; }250 251      const index = bf.index;252      const depth = bf.depth;253 254      // unassigned neighbours shouldn't affect the ordering255      if( index == null || depth == null ){256        continue;257      }258 259      const nDepth = depths[ depth ].length;260 261      if( depth < eleDepth ){ // only get influenced by elements above262        percent += index / nDepth;263        samples++;264      }265    }266 267    samples = Math.max( 1, samples );268    percent = percent / samples;269 270    if( samples === 0 ){ // put lone nodes at the start271      percent = 0;272    }273 274    cachedWeightedPercent[ ele.id() ] = percent;275    return percent;276  };277 278 279  // rearrange the indices in each depth level based on connectivity280  let sortFn = function( a, b ){281    const apct = getWeightedPercent( a );282    const bpct = getWeightedPercent( b );283 284    const diff = apct - bpct;285 286    if( diff === 0 ){287      return util.sort.ascending( a.id(), b.id() ); // make sure sort doesn't have don't-care comparisons288    } else {289      return diff;290    }291  };292 293  if (options.depthSort !== undefined) {294    sortFn = options.depthSort;295  }296 297  let depthsLen = depths.length;298 299  // sort each level to make connected nodes closer300  for( let i = 0; i < depthsLen; i++ ){301    depths[ i ].sort( sortFn );302    assignDepthsAt( i );303  }304 305  // assign orphan nodes to a new top-level depth306  const orphanDepth = [];307  for( let i = 0; i < orphanNodes.length; i++ ){308    orphanDepth.push( orphanNodes[i] );309  }310 311  const assignDepths = function(){312    for( let i = 0; i < depthsLen; i++ ){313      assignDepthsAt( i );314    }315  };316  317  // add a new top-level depth only when there are orphan nodes318  if (orphanDepth.length) {319    depths.unshift( orphanDepth );320    depthsLen = depths.length;321    assignDepths();322  }323 324  let biggestDepthSize = 0;325  for( let i = 0; i < depthsLen; i++ ){326    biggestDepthSize = Math.max( depths[ i ].length, biggestDepthSize );327  }328 329  const center = {330    x: bb.x1 + bb.w / 2,331    y: bb.y1 + bb.h / 2332  };333 334  // average node size335  const aveNodeSize = nodes.reduce((acc, node) => ((box) => ({336    w: acc.w === -1 ? box.w : (acc.w + box.w) / 2,337    h: acc.h === -1 ? box.h : (acc.h + box.h) / 2,338  }))(node.boundingBox({339    includeLabels: options.nodeDimensionsIncludeLabels340  })), { w: -1, h: -1 });341 342  const distanceY = Math.max(343    // only one depth344    depthsLen === 1 ? 0 :345      // inside a bounding box, no need for top & bottom padding346      hasBoundingBox ? ((bb.h - options.padding * 2 - aveNodeSize.h) / (depthsLen - 1)) :347        (bb.h - options.padding * 2 - aveNodeSize.h) / (depthsLen + 1),348    minDistance );349 350  const maxDepthSize = depths.reduce( (max, eles) => Math.max(max, eles.length), 0 );351 352  const getPositionTopBottom = function( ele ){353    const { depth, index } = getInfo( ele );354 355    if ( options.circle ){356      let radiusStepSize = Math.min( bb.w / 2 / depthsLen, bb.h / 2 / depthsLen );357      radiusStepSize = Math.max( radiusStepSize, minDistance );358 359      let radius = radiusStepSize * depth + radiusStepSize - (depthsLen > 0 && depths[0].length <= 3 ? radiusStepSize / 2 : 0);360      const theta = 2 * Math.PI / depths[ depth ].length * index;361 362      if( depth === 0 && depths[0].length === 1 ){363        radius = 1;364      }365 366      return {367        x: center.x + radius * Math.cos( theta ),368        y: center.y + radius * Math.sin( theta )369      };370 371    } else {372      const depthSize = depths[ depth ].length;373      const distanceX = Math.max(374        // only one depth375        depthSize === 1 ? 0 :376          // inside a bounding box, no need for left & right padding377          hasBoundingBox ? ((bb.w - options.padding * 2 - aveNodeSize.w) / ((options.grid ? maxDepthSize : depthSize) - 1)):378            (bb.w - options.padding * 2 - aveNodeSize.w) / ((options.grid ? maxDepthSize : depthSize) + 1),379        minDistance );380 381      const epos = {382        x: center.x + (index + 1 - (depthSize + 1) / 2) * distanceX,383        y: center.y + (depth + 1 - (depthsLen + 1) / 2) * distanceY384      };385 386      return epos;387    }388  };389 390  const rotateDegrees = {391    'downward': 0,392    'leftward': 90,393    'upward': 180,394    'rightward': -90,395  }396 397  if (Object.keys(rotateDegrees).indexOf(options.direction) === -1) {398    util.error(`Invalid direction '${options.direction}' specified for breadthfirst layout. Valid values are: ${Object.keys(rotateDegrees).join(', ')}`);399  }400 401  const getPosition = (ele) => util.rotatePosAndSkewByBox(getPositionTopBottom(ele), bb, rotateDegrees[options.direction]);402 403  eles.nodes().layoutPositions( this, options, getPosition);404 405  return this; // chaining406};407 408export default BreadthFirstLayout;