Architecture Graph Tree Evaluation

architecture_graph_evaluation.js

/**
  @name constructTree
  @description Creates vertex and in-edge hashmaps given a topology

  @example 
  assert.deepStrictEqual(
    constructTree([ { breadth: 2 }, { breadth: 1 } ]),
    {
      vertices: { 
        '0': { id: '0', depth: 1 }, 
        '0_0': { id: '0_0', depth: 2 }, 
        '0_1': { id: '0_1', depth: 2 }, 
        '0_0_0': { id: '0_0_0', depth: 3 }, 
        '0_1_0': { id: '0_1_0', depth: 3 }
      }, 
      edges: {
        '0_0': '0',
        '0_1': '0',
        '0_0_0': '0_0',
        '0_1_0': '0_1'
      }
    }
)
*/
 

const constructTree = (topology=[{breadth:3},{breadth:3}])=>{
  const root={id:'0',depth:1}
  const vertices={'0':root};
  const edges={}; //{id1:node,id2:node}
  const queue=[root];
  let next,node,b,breadth;
  while((next=queue.shift())){
    for (b=-1,breadth=topology[next.depth-1].breadth;++b<breadth;){
      node={id:`${next.id}_${b}`}
      vertices[node.id]=node
      edges[node.id]=next.id
      node.depth=next.depth+1
      if (node.depth<=topology.length)queue.push(node)
    }
  }
  return {vertices, edges}
}

/**
  @name enumerateTreeTopologies
  @description Simple function to create topologies for giventrees of given depth and breadths

  @example 
  assert.deepStrictEqual(
    enumerateTreeTopologies(3,2),
    [
      [ { breadth: 1 } ], 
      [ { breadth: 2 } ], 
      [ { breadth: 1 }, { breadth: 1 } ], 
      [ { breadth: 2 }, { breadth: 2 } ], 
      [ { breadth: 1 }, { breadth: 1 }, { breadth: 1 } ], 
      [ { breadth: 2 }, { breadth: 2 }, { breadth: 2 } ]
    ] 
  )
*/

const enumerateTreeTopologies=(max_depth=4,max_breadth=2)=>{
  const topologyList=[];
  for (let d=0,b=0,current_depth=0,topology=[];++d<=max_depth;){
    for (b=0;++b<=max_breadth;){
      for (topology=[],current_depth=0;++current_depth<=d;){
        topology.push({breadth:b});
      }
      topologyList.push(topology)
    }
  }
  return topologyList
}


/**
  @name countEdges
  @description given a tree, returns edge counts
  
  @example
  assert.deepStrictEqual(
    countEdges({
      vertices: {
        '0':{ id: '0', depth: 1 }, 
        '0_0': { id: '0_0', depth: 2 }, 
        '0_1': { id: '0_1', depth: 2 }, 
        '0_0_0': { id: '0_0_0', depth: 3 }, 
        '0_0_1': { id: '0_0_1', depth: 3 }, 
        '0_1_0': { id: '0_1_0', depth: 3 }, 
        '0_1_1': { id: '0_1_1', depth: 3 }
      }, 
      edges: {
        '0_0': '0', 
        '0_1': '0', 
        '0_0_0': '0_0', 
        '0_0_1': '0_0', 
        '0_1_0': '0_1', 
        '0_1_1': '0_1'
      }
    }),
    {
      forward: 4,
      tree: 6,
      cross: 22,
      vertices: 7,
      edges: 32
    }
  )
*/
const countEdges = ({vertices,edges})=>{
  let counts={forward:0,tree:0,cross:0,vertices:0,edges:0};
  for (id in vertices){
    ++counts.vertices

    for (relatedId in vertices){
      if(relatedId.startsWith(id)) continue;// omit equal ids, and prevent double-counting since tree is directed
      
      ++counts.edges
      !id.startsWith(relatedId)         ? ++counts.cross : // not ancestor
      edges[id]===vertices[relatedId].id   ? ++counts.tree : // parent
                                          ++counts.forward; // ancestor
    }
  }
  return counts;
}

/**
  @name countedEdgesToCsv
  @description given counted edges, returns them in csv format

  
  @example
  assert.deepStrictEqual(
    countedEdgesToCsv([
      {
        forward: 1,
        tree: 2,
        cross: 0,
        vertices: 3,
        edges: 3,
        topology: [ { breadth: 1 }, { breadth: 1 } ]
      },
      {
        forward: 2, 
        tree: 4, 
        cross: 8,
        vertices: 5,
        edges: 14,
        topology: [ { breadth: 2 }, { breadth: 1 } ]
      }
    ]),
    [
      'depth,breadth,tree,forward,cross,vertices,edges',
      '2,1_1,2,1,0,3,3',
      '2,2_1,4,2,8,5,14'
    ].join('\n')
  )
*/
const countedEdgesToCsv = (countedEdgesWithTopology=[{tree:0,forward:0,cross:0,topology:[{breadth:2}]}])=>{
  return ['depth','breadth','tree','forward','cross','vertices','edges'].join(',')+
  '\n'+
  countedEdgesWithTopology
  .map(({tree,forward,cross,vertices,edges,topology:t})=>[t.length,t.map(lvl=>lvl.breadth).join('_'),tree,forward,cross,vertices,edges])
  .map(vals=>vals.join(','))
  .join('\n');
}


// console.log(
//   countedEdgesToCsv(
//     enumerateTreeTopologies(4,10)
//     .map(topology=>({topology,...countEdges(constructTree(topology))}))
//   )
// )

// `
// depth,breadth,tree,forward,cross,vertices,edges
// 1,1,1,0,0,2,1
// 1,2,2,0,2,3,4
// 1,3,3,0,6,4,9
// 1,4,4,0,12,5,16
// 1,5,5,0,20,6,25
// 1,6,6,0,30,7,36
// 1,7,7,0,42,8,49
// 1,8,8,0,56,9,64
// 1,9,9,0,72,10,81
// 1,10,10,0,90,11,100
// 2,1_1,2,1,0,3,3
// 2,2_2,6,4,22,7,32
// 2,3_3,12,9,114,13,135
// 2,4_4,20,16,348,21,384
// 2,5_5,30,25,820,31,875
// 2,6_6,42,36,1650,43,1728
// 2,7_7,56,49,2982,57,3087
// 2,8_8,72,64,4984,73,5120
// 2,9_9,90,81,7848,91,8019
// 2,10_10,110,100,11790,111,12000
// 3,1_1_1,3,3,0,4,6
// 3,2_2_2,14,20,142,15,176
// 3,3_3_3,39,63,1356,40,1458
// 3,4_4_4,84,144,6684,85,6912
// 3,5_5_5,155,275,23320,156,23750
// 3,6_6_6,258,468,65370,259,66096
// 3,7_7_7,399,735,157332,400,158466
// 3,8_8_8,584,1088,338296,585,339968
// 3,9_9_9,819,1539,666864,820,669222
// 3,10_10_10,1110,2100,1226790,1111,1230000
// 4,1_1_1_1,4,6,0,5,10
// 4,2_2_2_2,30,68,734,31,832
// 4,3_3_3_3,120,306,13668,121,14094
// 4,4_4_4_4,340,912,113436,341,114688
// 4,5_5_5_5,780,2150,603320,781,606250
// 4,6_6_6_6,1554,4356,2404650,1555,2410560
// 4,7_7_7_7,2800,7938,7821324,2801,7832062
// 4,8_8_8_8,4680,13376,21870968,4681,21889024
// 4,9_9_9_9,7380,21222,54414576,7381,54443178
// 4,10_10_10_10,11110,32100,123356790,11111,123400000
// `

various related calcs

function Fact(num){
  let rval=1;
  for (let i = 2; i <= num; i++)
      rval = rval * i;
  return rval;
}

var perms = (n,k) => Fact(n) / Fact(n-k);
var choose = (n,k) => Fact(n) / (Fact(k)*Fact(n-k));
var pathEdges = d => d*(d+1)/2; // number of edges in a path of length d
var allPaths = (d,b)=>pathEdges(d) * b**d;
var duplicatePaths = (d,b)=> d<=0 ? 0 : allPaths(d,b) + duplicatePaths(d-1,b);
var treePaths = (d,b)=> d<=1 ? 0 : allPaths(d-1,b) - duplicatePaths(d-2,b);
var uniquePathsWithOnlyTreeEdges = (d,b)=>( (d*(b*(d**(b+1))-((b+1)*(d**b))+1)) / ((d-1)**2) );
// subtract # of leaves from root.
var uniquePathsWithForwardEdges = (d,b)=>{};
var uniquePathsWithCrossEdges = (d,b)=>{};
var uniquePathsWithTreeAndForwardEdges = (d,b)=>{};
var uniquePathsWithTreeAndCrossEdges = (d,b)=>{};
var uniquePathsWithTreeAndForwardAndCrossEdges = (d,b)=>{};


var D=4
var B=2
var siblings = B-1
var V=(D**B)-1
var E=V-1
var Leaves = B**(D-1);
var Branches = V-Leaves-1;