completeTree method

Graph<V, E> completeTree({
  1. required int vertexCount,
  2. int arity = 2,
})

Creates a complete tree with vertexCount nodes and a branching factor of arity. By definition it is completely filled on every level except for the last one; where all the nodes are as far left as possible.

Implementation

Graph<V, E> completeTree({required int vertexCount, int arity = 2}) {
  assert(arity >= 1, 'Branching factor must be positive');
  final builder = newBuilder();
  if (vertexCount <= 0) {
    return builder.build();
  }
  final parents = QueueList<int>.from([0]);
  builder.addVertexIndex(0);
  for (var child = 1; child < vertexCount;) {
    final parent = parents.removeFirst();
    for (var i = 0; i < arity && child < vertexCount; i++, child++) {
      parents.addLast(child);
      builder.addVertexIndex(child);
      builder.addEdgeIndex(parent, child);
    }
  }
  return builder.build();
}