Skip to content
Snippets Groups Projects
Select Git revision
  • bbb3479511c47b4999c12ae6b491dbc5947d4252
  • master default protected
  • rednatco-v2
  • rednatco
  • test
  • ntc-tube-uniform-color
  • ntc-tube-missing-atoms
  • restore-vertex-array-per-program
  • watlas2
  • dnatco_new
  • cleanup-old-nodejs
  • webmmb
  • fix_auth_seq_id
  • update_deps
  • ext_dev
  • ntc_balls
  • nci-2
  • plugin
  • bugfix-0.4.5
  • nci
  • servers
  • v0.5.0-dev.1
  • v0.4.5
  • v0.4.4
  • v0.4.3
  • v0.4.2
  • v0.4.1
  • v0.4.0
  • v0.3.12
  • v0.3.11
  • v0.3.10
  • v0.3.9
  • v0.3.8
  • v0.3.7
  • v0.3.6
  • v0.3.5
  • v0.3.4
  • v0.3.3
  • v0.3.2
  • v0.3.1
  • v0.3.0
41 results

encoding.ts

Blame
  • int-adjacency-graph.ts 11.46 KiB
    /**
     * Copyright (c) 2018 mol* contributors, licensed under MIT, See LICENSE file for more info.
     *
     * @author David Sehnal <david.sehnal@gmail.com>
     * @author Alexander Rose <alexander.rose@weirdbyte.de>
     */
    
    import { arrayPickIndices, cantorPairing } from 'mol-data/util';
    import { LinkedIndex, SortedArray } from 'mol-data/int';
    
    /**
     * Represent a graph using vertex adjacency list.
     *
     * Edges of the i-th vertex are stored in the arrays a and b
     * for indices in the range [offset[i], offset[i+1]).
     *
     * Edge properties are indexed same as in the arrays a and b.
     */
    export interface IntAdjacencyGraph<EdgeProps extends IntAdjacencyGraph.EdgePropsBase = {}> {
        readonly offset: ArrayLike<number>,
        readonly a: ArrayLike<number>,
        readonly b: ArrayLike<number>,
        readonly vertexCount: number,
        readonly edgeCount: number,
        readonly edgeProps: Readonly<EdgeProps>
    
        /**
         * Get the edge index between i-th and j-th vertex.
         * -1 if the edge does not exist.
         *
         * Because the a and b arrays contains each edge twice,
         * this always returns the smaller of the indices.
         *
         * `getEdgeIndex(i, j) === getEdgeIndex(j, i)`
         */
        getEdgeIndex(i: number, j: number): number,
        /**
         * Get the edge index between i-th and j-th vertex.
         * -1 if the edge does not exist.
         *
         * `getEdgeIndex(i, j) !== getEdgeIndex(j, i)`
         */
        getDirectedEdgeIndex(i: number, j: number): number,
        getVertexEdgeCount(i: number): number
    }
    
    export namespace IntAdjacencyGraph {
        export type EdgePropsBase = { [name: string]: ArrayLike<any> }
    
        class IntGraphImpl implements IntAdjacencyGraph<any> {
            readonly vertexCount: number;
            readonly edgeProps: object;
    
            getEdgeIndex(i: number, j: number): number {
                let a, b;
                if (i < j) { a = i; b = j; }
                else { a = j; b = i; }
                for (let t = this.offset[a], _t = this.offset[a + 1]; t < _t; t++) {
                    if (this.b[t] === b) return t;
                }
                return -1;
            }
    
            getDirectedEdgeIndex(i: number, j: number): number {
                for (let t = this.offset[i], _t = this.offset[i + 1]; t < _t; t++) {
                    if (this.b[t] === j) return t;
                }
                return -1;
            }
    
            getVertexEdgeCount(i: number): number {
                return this.offset[i + 1] - this.offset[i];
            }
    
            constructor(public offset: ArrayLike<number>, public a: ArrayLike<number>, public b: ArrayLike<number>, public edgeCount: number, edgeProps?: any) {
                this.vertexCount = offset.length - 1;
                this.edgeProps = edgeProps || {};
            }
        }
    
        export function create<EdgeProps extends IntAdjacencyGraph.EdgePropsBase = {}>(offset: ArrayLike<number>, a: ArrayLike<number>, b: ArrayLike<number>, edgeCount: number, edgeProps?: EdgeProps): IntAdjacencyGraph<EdgeProps> {
            return new IntGraphImpl(offset, a, b, edgeCount, edgeProps) as IntAdjacencyGraph<EdgeProps>;
        }
    
        export class EdgeBuilder {
            private bucketFill: Int32Array;
            private current = 0;
            private curA: number = 0;
            private curB: number = 0;
    
            offsets: Int32Array;
            edgeCount: number;
            /** the size of the A and B arrays */
            slotCount: number;
            a: Int32Array;
            b: Int32Array;
    
            createGraph<EdgeProps extends IntAdjacencyGraph.EdgePropsBase = {}>(edgeProps?: EdgeProps) {
                return create(this.offsets, this.a, this.b, this.edgeCount, edgeProps);
            }
    
            /**
             * @example
             *   const property = new Int32Array(builder.slotCount);
             *   for (let i = 0; i < builder.edgeCount; i++) {
             *     builder.addNextEdge();
             *     builder.assignProperty(property, srcProp[i]);
             *   }
             *   return builder.createGraph({ property });
             */
            addNextEdge() {
                const a = this.xs[this.current], b = this.ys[this.current];
    
                const oa = this.offsets[a] + this.bucketFill[a];
                const ob = this.offsets[b] + this.bucketFill[b];
    
                this.a[oa] = a;
                this.b[oa] = b;
                this.bucketFill[a]++;
    
                this.a[ob] = b;
                this.b[ob] = a;
                this.bucketFill[b]++;
    
                this.current++;
                this.curA = oa;
                this.curB = ob;
            }
    
            /** Builds property-less graph */
            addAllEdges() {
                for (let i = 0; i < this.edgeCount; i++) {
                    this.addNextEdge();
                }
            }
    
            assignProperty<T>(prop: { [i: number]: T }, value: T) {
                prop[this.curA] = value;
                prop[this.curB] = value;
            }
    
            constructor(public vertexCount: number, public xs: ArrayLike<number>, public ys: ArrayLike<number>) {
                this.edgeCount = xs.length;
                this.offsets = new Int32Array(this.vertexCount + 1);
                this.bucketFill = new Int32Array(this.vertexCount);
    
                const bucketSizes = new Int32Array(this.vertexCount);
                for (let i = 0, _i = this.xs.length; i < _i; i++) bucketSizes[this.xs[i]]++;
                for (let i = 0, _i = this.ys.length; i < _i; i++) bucketSizes[this.ys[i]]++;
    
                let offset = 0;
                for (let i = 0; i < this.vertexCount; i++) {
                    this.offsets[i] = offset;
                    offset += bucketSizes[i];
                }
                this.offsets[this.vertexCount] = offset;
                this.slotCount = offset;
                this.a = new Int32Array(offset);
                this.b = new Int32Array(offset);
            }
        }
    
        export class UniqueEdgeBuilder {
            private xs: number[] = [];
            private ys: number[] = [];
            private included = new Set<number>();
    
            addEdge(i: number, j: number) {
                let u = i, v = j;
                if (i > j) { u = j; v = i; }
                const id = cantorPairing(u, v);
                if (this.included.has(id)) return false;
                this.included.add(id);
                this.xs[this.xs.length] = u;
                this.ys[this.ys.length] = v;
                return true;
            }
    
            getGraph(): IntAdjacencyGraph {
                return fromVertexPairs(this.vertexCount, this.xs, this.ys);
            }
    
            // if we cant to add custom props as well
            getEdgeBuiler() {
                return new EdgeBuilder(this.vertexCount, this.xs, this.ys);
            }
    
            constructor(public vertexCount: number) {
            }
        }
    
        export function fromVertexPairs(vertexCount: number, xs: number[], ys: number[]) {
            const graphBuilder = new IntAdjacencyGraph.EdgeBuilder(vertexCount, xs, ys);
            graphBuilder.addAllEdges();
            return graphBuilder.createGraph();
        }
    
        export function induceByVertices<P extends IntAdjacencyGraph.EdgePropsBase>(graph: IntAdjacencyGraph<P>, vertexIndices: ArrayLike<number>): IntAdjacencyGraph<P> {
            const { b, offset, vertexCount, edgeProps } = graph;
            const vertexMap = new Int32Array(vertexCount);
            for (let i = 0, _i = vertexIndices.length; i < _i; i++) vertexMap[vertexIndices[i]] = i + 1;
    
            let newEdgeCount = 0;
            for (let i = 0; i < vertexCount; i++) {
                if (vertexMap[i] === 0) continue;
                for (let j = offset[i], _j = offset[i + 1]; j < _j; j++) {
                    if (b[j] > i && vertexMap[b[j]] !== 0) newEdgeCount++;
                }
            }
    
            const newOffsets = new Int32Array(vertexIndices.length + 1);
            const edgeIndices = new Int32Array(2 * newEdgeCount);
            const newA = new Int32Array(2 * newEdgeCount);
            const newB = new Int32Array(2 * newEdgeCount);
            let eo = 0, vo = 0;
            for (let i = 0; i < vertexCount; i++) {
                if (vertexMap[i] === 0) continue;
                const aa = vertexMap[i] - 1;
                for (let j = offset[i], _j = offset[i + 1]; j < _j; j++) {
                    const bb = vertexMap[b[j]];
                    if (bb === 0) continue;
    
                    newA[eo] = aa;
                    newB[eo] = bb - 1;
                    edgeIndices[eo] = j;
                    eo++;
                }
                newOffsets[++vo] = eo;
            }
    
            const newEdgeProps: P = {} as any;
            for (const key of Object.keys(edgeProps)) {
                newEdgeProps[key] = arrayPickIndices(edgeProps[key], edgeIndices);
            }
    
            return create(newOffsets, newA, newB, newEdgeCount, newEdgeProps);
        }
    
        export function connectedComponents(graph: IntAdjacencyGraph): { componentCount: number, componentIndex: Int32Array } {
            const vCount = graph.vertexCount;
    
            if (vCount === 0) return { componentCount: 0, componentIndex: new Int32Array(0) };
            if (graph.edgeCount === 0) {
                const componentIndex = new Int32Array(vCount);
                for (let i = 0, _i = vCount; i < _i; i++) {
                    componentIndex[i] = i;
                }
                return { componentCount: vCount, componentIndex };
            }
    
            const componentIndex = new Int32Array(vCount);
            for (let i = 0, _i = vCount; i < _i; i++) componentIndex[i] = -1;
            let currentComponent = 0;
            componentIndex[0] = currentComponent;
    
            const { offset, b: neighbor } = graph;
            const stack = [0];
            const list = LinkedIndex(vCount);
            list.remove(0);
    
            while (stack.length > 0) {
                const v = stack.pop()!;
                const cIdx = componentIndex[v];
    
                for (let eI = offset[v], _eI = offset[v + 1]; eI < _eI; eI++) {
                    const n = neighbor[eI];
                    if (!list.has(n)) continue;
                    list.remove(n);
                    stack.push(n);
                    componentIndex[n] = cIdx;
                }
    
                // check if we visited all vertices.
                // If not, create a new component and continue.
                if (stack.length === 0 && list.head >= 0) {
                    stack.push(list.head);
                    componentIndex[list.head] = ++currentComponent;
                    list.remove(list.head);
                }
            }
    
            return { componentCount: vCount, componentIndex };
        }
    
        /**
         * Check if any vertex in `verticesA` is connected to any vertex in `verticesB`
         * via at most `maxDistance` edges.
         *
         * Returns true if verticesA and verticesB are intersecting.
         */
        export function areVertexSetsConnected(graph: IntAdjacencyGraph, verticesA: SortedArray<number>, verticesB: SortedArray<number>, maxDistance: number): boolean {
            // check if A and B are intersecting, this handles maxDistance = 0
            if (SortedArray.areIntersecting(verticesA, verticesB)) return true;
            if (maxDistance < 1) return false;
    
            const visited = new Set<number>();
            for (let i = 0, il = verticesA.length; i < il; ++i) {
                visited.add(verticesA[i]);
            }
    
            return areVertexSetsConnectedImpl(graph, verticesA, verticesB, maxDistance, visited);
        }
    }
    
    function areVertexSetsConnectedImpl(graph: IntAdjacencyGraph, frontier: ArrayLike<number>, target: SortedArray<number>, distance: number, visited: Set<number>): boolean {
        const { b: neighbor, offset } = graph;
        const newFrontier: number[] = [];
    
        for (let i = 0, il = frontier.length; i < il; ++i) {
            const src = frontier[i];
    
            for (let j = offset[src], jl = offset[src + 1]; j < jl; ++j) {
                const other = neighbor[j];
                if (visited.has(other)) continue;
                if (SortedArray.has(target, other)) return true;
    
                visited.add(other);
                newFrontier[newFrontier.length] = other;
            }
        }
    
        return distance > 1 ? areVertexSetsConnectedImpl(graph, newFrontier, target, distance - 1, visited) : false;
    }