# Re: Implementing and optimizing a simple graph metric

```Joseph Rushton Wakeling:
```
```http://braingam.es/2013/09/betweenness-centrality-in-dgraph/
```
```
Some small improvements:

```
T[] betweenness(Graph, T = double)(ref Graph g, bool[] ignore = null)
```    if (isGraph!Graph && isFloatingPoint!T)
{
enum T T0 = 0;
enum T T1 = 1;
```
auto centrality = minimallyInitializedArray!(typeof(return))(g.vertexCount);
```    centrality[] = T0;
auto stack = new size_t[g.vertexCount];
auto sigma = minimallyInitializedArray!T(g.vertexCount);
sigma[] = T0;
auto delta = minimallyInitializedArray!T(g.vertexCount);
delta[] = T0;
auto d = minimallyInitializedArray!long(g.vertexCount);
d[] = -1;
auto q = VertexQueue(g.vertexCount);
auto p = new Appender!(size_t[])[g.vertexCount];

foreach (immutable s; 0 .. g.vertexCount)
{
if (ignore && ignore[s])
{
continue;
}

size_t stackLength = 0;
assert(q.empty);
sigma[s] = T1;
d[s] = 0;
q.push(s);

while (!q.empty)
{
immutable size_t v = q.front;
q.pop;
stack[stackLength] = v;
++stackLength;
foreach (immutable w; g.neighboursOut(v))
{
if (ignore && ignore[w])
{
continue;
}

if (d[w] < 0)
{
q.push(w);
d[w] = d[v] + 1;
assert(sigma[w] == T0);
sigma[w] = sigma[v];
p[w].clear;
p[w].put(v);
}
else if (d[w] > (d[v] + 1))
{
/* w has already been encountered, but we've
found a shorter path to the source.  This
is probably only relevant to the weighted
case, but let's keep it here in order to
be ready for that update. */
d[w] = d[v] + 1L;
sigma[w] = sigma[v];
p[w].clear;
p[w].put(v);
}
else if (d[w] == (d[v] + 1))
{
sigma[w] += sigma[v];
p[w].put(v);
}
}
}

while (stackLength > 0)
{
--stackLength;
immutable w = stack[stackLength];
foreach (immutable v; p[w].data)
{
```
delta[v] += ((sigma[v] / sigma[w]) * (T1 + delta[w]));
```            }
if (w != s)
{
centrality[w] += delta[w];
}
sigma[w] = T0;
delta[w] = T0;
d[w] = -1;
}
}

static if (!g.directed)
{
centrality[] /= 2;
}

return centrality;
}

```
Just for a test, try to allocate all those arrays in a different way:
```- First try a std.array.Array using the LDC2 compiler;
```
- Another thing to try is to allocate them on the stack using core.stdc.stdlib.alloca:
```auto p = cast(T*)alloca(T.sizeof * g.vertexCount);
if (!p) throw new MemoryError...
auto centrality = p[0 .. g.vertexCount];
```
This probably can't be used for very large graphs, so you have to add even more logic to allocate the arrays on the C heap if they are too much large. This could be useful if you call betweenness() many many times.
```- Try to optionally accept the buffers from outside.

Bye,
bearophile
```