Simple GraphJet

AdjacencyList.java

package segments;

import java.util.*;

public class AdjacencyList {
    private static final int[] NODE_THRESHOLDS;

    static {
        NODE_THRESHOLDS = new int[32];
        NODE_THRESHOLDS[0] = 0;

        for (int i = 1; i < NODE_THRESHOLDS.length; i++) {
            NODE_THRESHOLDS[i] += Math.pow(2, i);
        }
    }

    private final int expectedNodes;
    private final IdEncoder encoder;
    private final List<EdgePool> edgePools = new ArrayList<>();
    private final Map<Integer, List<Integer>> adjacencyList;
    private final Map<Integer, Integer> cardinalities;


    public AdjacencyList(int expectedNodes) {
        this.expectedNodes = expectedNodes;
        this.encoder = new IdEncoder();
        adjacencyList = new HashMap<>();
        cardinalities = new HashMap<>();
    }

    public void addEdge(int sourceNode, int target, byte edgeType) {
        int encodedEdge = encoder.encode(target, edgeType);

        List<Integer> poolPositions = adjacencyList.getOrDefault(sourceNode, new ArrayList<>(4));
        int currentPool = poolPositions.size() - 1;

        // Load cardinality for node to calculate position in pool
        int cardinality = cardinalities.getOrDefault(sourceNode, 0);
        int poolIndex = getPoolForCardinality(cardinality) - 1;

        if (poolIndex > (edgePools.size() - 1)) {
            // We need a new pool
            addEdgePool(expectedNodes);
        }

        int slicePosition;

        if (poolIndex == currentPool && poolPositions.size() > 0) {
            // There is a current slice and there is still space in it
            slicePosition = poolPositions.get(currentPool);
        } else {
            // We need to create a new slice
            slicePosition = edgePools.get(poolIndex).getNewSlicePosition();
            poolPositions.add(slicePosition);
        }

        EdgePool pool = edgePools.get(poolIndex);

        // FIXME
        int positionInSlice = cardinality - NODE_THRESHOLDS[poolIndex];

        pool.addToSlice(slicePosition, positionInSlice, encodedEdge);
        adjacencyList.put(sourceNode, poolPositions);
        cardinalities.put(sourceNode, cardinality + 1);
    }

    public int[] getRightNodes(int sourceNode) {
        List<Integer> slices = adjacencyList.get(sourceNode);
        int cardinality = cardinalities.get(sourceNode);
        int[] nodes = new int[cardinality];
        int nodeCount = 0;

        for (int i = 0; i < slices.size(); i++) {
            EdgePool pool = edgePools.get(i);
            int[] slice = pool.getSlice(slices.get(i));

            // Convert bitpacked edges to vertex only
            int nodesLeft = cardinality - nodeCount;

            for (int s = 0; s < slice.length && s < nodesLeft; s++) {
                int decoded = encoder.decodeNode(slice[s]);
                nodes[(nodeCount + s)] = encoder.decodeNode(decoded);
            }

            nodeCount += slice.length;
        }
        return nodes;
    }

    void addEdgePool(int expectedNodes) {
        int currentPools = edgePools.size();
        // Slice sizes scale 2^(pools + 1): 2, 4, 8, 16, 32...
        int sliceSize = (int) Math.pow(2, 1 + currentPools);
        // Number of slices per pool scale n / 2^(pools - 1): n, n/2, n/4, n/8...
        int slices = (int) (expectedNodes / Math.pow(2, currentPools - 1));
        // Create a edge pool
        edgePools.add(new EdgePool(slices, sliceSize));
    }

    int getPoolForCardinality(int cardinality) {
        // Todo: Make faster with lookup table: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
        return (int) Math.floor(Math.log(cardinality + 2) / Math.log(2));
    }
}

EdgePool.java

package segments;

import java.util.Arrays;

/**
 * Holds all adjacency list slices for one size
 */
public class EdgePool {
    private final int sliceSize;
    private final int numberOfSlices;
    private final int[] slices;
    private int currentSlice;

    public EdgePool(int sliceCount, int sliceSize) {
        this.numberOfSlices = sliceCount;
        this.sliceSize = sliceSize;
        this.slices = new int[sliceCount * sliceSize];
    }

    public void addToSlice(int slice, int position, int encodedEdge) {
        if (slice > numberOfSlices) {
            throw new IndexOutOfBoundsException("No segment at position " + slice);
        }

        // We iterated into next slice.
        if (position - (slice * sliceSize) >= sliceSize) {
            throw new IndexOutOfBoundsException("Segment at position " + slice + "is full in this pool.");
        }

        slices[position] = encodedEdge;
    }

    public int[] getSlice(int position) {
        int i = position * sliceSize;
        return Arrays.copyOfRange(slices, i, i + sliceSize);
    }

    public int getNewSlicePosition() {
        currentSlice++;
        return currentSlice;
    }

    public int getSliceSize() {
        return sliceSize;
    }
}

IdEncoder.java

package segments;

public class IdEncoder {
    private static final int EDGE_TYPE_BITS = Byte.BYTES * 8;
    private static final int ALLOWED_NODE_BITS = (Integer.BYTES * 8) - EDGE_TYPE_BITS;

    public IdEncoder() {
    }

    public int encode(int node, byte edgeType) {
        if (node >>> ALLOWED_NODE_BITS > 0) {
            throw new IllegalArgumentException(
                    String.format("The node needs to be less than %d bits long.", ALLOWED_NODE_BITS));
        }
        return (edgeType << ALLOWED_NODE_BITS) | node;
    }

    public byte decodeEdgeType(int encodedEdge) {
        return (byte) (encodedEdge >>> ALLOWED_NODE_BITS);
    }

    public int decodeNode(int encodedEdge) {
        return ((encodedEdge << EDGE_TYPE_BITS) >> EDGE_TYPE_BITS);
    }
}

WriteableSegment

package segments;

/**
 * Left side of bipartite graph, contains references to outgoing edges.
 */
public class WriteableSegment {
    private final AdjacencyList adjacencyList;

    public WriteableSegment(int expectedNodes) {
        this.adjacencyList = new AdjacencyList(expectedNodes);
    }

    public void insert(int sourceNode, int targetEdge, byte edgeType) {
        adjacencyList.addEdge(sourceNode, targetEdge, edgeType);
    }

    public int[] getRightEdges(int sourceNode) {
        return adjacencyList.getRightNodes(sourceNode);
    }
}