Welp, it took me a couple of days to wrap my head around what @foobar_lv2 's code was doing – bitwise operations is not something I’ve ever messed with. Still the example was self-contained enough that I think I know how it works, and I took a stab at some code that uses it. Since there’s discussion of making a graph type based on it, I thought someone might benefit from seeing the code (even if it’s just to state how bad it is!)
I didn’t try do do all the interfaces right now, just some that I use in my code. I make no claim that it’s as performant or correct as it could be:
# I don't use/modify all these in this section of code, but I'm to lazy to clean it up...
import LightGraphs: AbstractGraph, SimpleGraph, SimpleDiGraph, AbstractEdge, SimpleEdge, has_edge, is_directed, edgetype, src, dst, ne, nv, vertices, has_vertex, outneighbors, inneighbors, edges, add_edge!, rem_edge!, indegree, outdegree
# Code from foobar_lv2 in Julia discourse thread -- construct bitarray from bool
function mk_chunks(m::Matrix{Bool})
n = size(m, 1)
n == size(m,2) || error("matrix wants to be square")
nchunks = Base.num_bit_chunks(n)
bm_M = falses(nchunks<<6, n+1)
bm_MT = falses(nchunks<<6, n+1)
bm_M[1:n, end] .= true
bm_MT[1:n, end] .= true
bm_M[1:n, 1:n] .= m
bm_MT[1:n, 1:n] .= m'
M = reshape(bm_M.chunks, (nchunks, n+1))
MT = reshape(bm_MT.chunks, (nchunks, n+1))
return M, MT
end
# BitArray-style graphs - focus on digraph for now
# I often require the degree distribution in my code, so I find it useful
# to pre-calculate and update as needed, rather than
# do it on the fly.
struct lightbitdigraph{G<:Array{UInt64}}
graph::G
graphT::G
indegree::Vector{Int64}
outdegree::Vector{Int64}
end
# Basic outer contructor when we just have a boolean graph to start
# takes a digraph, stores the bitgraph and transpose, and the
# degree distribution.
function lightbitdigraph(g::G) where {G<:AbstractArray{Bool}}
lightbitdigraph(mk_chunks(g)..., vec(sum(g, dims=1)), vec(sum(g, dims=2)))
end
# Define some needed helper functions
# I don't define all the needed interfaces here, just a few I use
# (plus a couple extra I found useful)
nchunks(g::T) where {T<:lightbitdigraph} = size(g.graph, 1)
nv(g::T) where {T<:lightbitdigraph} = size(g.graph, 2) - 1
vertices(g::T) where {T<:lightbitdigraph} = 1:nv(g)
chunks(g::T) where {T<:lightbitdigraph} = 1:nchunks(g)
# Get number of edges
# Note that self-loops are valid in some of the code here - careful.
function ne(g::T) where {T<:lightbitdigraph}
x = 0
@inbounds for v in vertices(g)
for c in chunks(g)
x += count_ones(g.graph[c, v])
end
end
return x
end
# Check whether a given edge exists
function has_edge(g::T, i, j) where {T<:lightbitdigraph}
i1, i2 = Base.get_chunks_id(i)
@inbounds return !iszero(g.graph[i1, j] & (1<<i2))
end
# Assert a given edge is "on"
function add_edge!(g::T, i, j) where {T<:lightbitdigraph}
i1, i2 = Base.get_chunks_id(i)
j1, j2 = Base.get_chunks_id(j)
@inbounds g.graph[i1, j] |= 1<<i2
@inbounds g.graphT[j1, i] |= 1<<j2
return nothing
end
# Assert a given edge is off
function rem_edge!(g::T, i, j) where {T<:lightbitdigraph}
i1, i2 = Base.get_chunks_id(i)
j1, j2 = Base.get_chunks_id(j)
@inbounds g.graph[i1, j] &= ~1<<i2
@inbounds g.graphT[i1, j] &= ~1<<j2
return nothing
end
# Toggle a given edge on/off
function toggle_edge!(g::T, i, j) where {T<:lightbitdigraph}
i1, i2 = Base.get_chunks_id(i)
j1, j2 = Base.get_chunks_id(j)
@inbounds g.graph[i1, j] ⊻= 1<<i2
@inbounds g.graphT[j1, i] ⊻= 1<<j2
return nothing
end
# Calculate indegrees for a given node
# I use pre-calculated degrees for this type,
# but testing showed that doing it on the fly was only a bit slower than
# standard lightgraph type on a 500 node graph
function indegree(g::T, v::V) where {T<:lightbitdigraph, V<:Int}
@inbounds return g.indegree[v]
end
# Calculate outdegrees for a given node
function outdegree(g::T, v::V) where {T<:lightbitdigraph, V<:Int}
@inbounds return g.outdegree[v]
end
A few notes:
In benchmarking, the speed of calculating just change statistics for existing edges (used to get total subgraph statistric counts) is actually a bit slower than the previous matrix{Bool} graph I was using. However, as that particular calculation seems to be an odd edge case I still can’t explain, the larger algorithm (that loops over the graph many times, toggling edges) is much, much faster.
The basic transitive triple calculation is 100x faster. The algorithm I have that loops over the graph multiple times takes <75ms, compared to ~ 650 ms in my original code (single Matrix{Bool}.
I made a version that uses two Matrix{Bool}s (the graph and it’s transpose) for comparison (out of curiosity), and this is still 7x faster than that.
I still have a bit of testing to confirm I’m getting identical output, so I’m not yet posting my full code… but I thought this might be useful to someone (or to me, if someone sees something I’m doing badly wrong in defining or using the types.)