completeTree method
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();
}