/**
 * Forbidden Subgraph Detection
 *
 * Efficient detection of induced subgraphs in graphs.
 * Core infrastructure for 120+ forbidden subgraph graph classes.
 *
 * Key operations:
 * - `hasInducedSubgraph()` - Check if graph contains specific induced subgraph
 * - `detectMultipleSubgraphs()` - Batch detection of multiple patterns
 * - `SUBGRAPH_PATTERNS` - Predefined pattern library
 */
/**
 * Subgraph pattern template
 *
 * Patterns define vertex count and edge connections.
 * Vertices are numbered 0 to size-1.
 */
export interface SubgraphPattern {
    /** Pattern name (e.g., "P5", "C5", "bull") */
    name: string;
    /** Number of vertices in pattern */
    size: number;
    /** Edge connections as vertex pairs */
    edges: Array<[number, number]>;
}
/**
 * Adjacency list representation
 *
 * Maps vertex ID to set of adjacent vertices.
 */
export type AdjacencyList = ReadonlyMap<number, ReadonlySet<number>>;
/**
 * Build adjacency list from edge list
 *
 * @param vertices - Set of vertex IDs
 * @param edges - Array of edge pairs
 * @returns Adjacency list map
 */
export declare const buildAdjacencyList: (vertices: ReadonlySet<number>, edges: ReadonlyArray<readonly [number, number]>) => AdjacencyList;
/**
 * Check if graph contains induced subgraph matching pattern
 *
 * @param adjacency - Graph adjacency list
 * @param pattern - Pattern to search for
 * @returns true if induced subgraph exists
 */
export declare const hasInducedSubgraph: (adjacency: AdjacencyList, pattern: SubgraphPattern) => boolean;
/**
 * Detect multiple subgraph patterns in one pass
 *
 * Optimized batch detection that avoids redundant combination generation.
 *
 * @param adjacency - Graph adjacency list
 * @param patterns - Array of patterns to detect
 * @returns Map of pattern name to detection result
 */
export declare const detectMultipleSubgraphs: (adjacency: AdjacencyList, patterns: readonly SubgraphPattern[]) => ReadonlyMap<string, boolean>;
/**
 * Library of common forbidden subgraph patterns
 */
export declare const SUBGRAPH_PATTERNS: {
    /** Path P3 (3 vertices) */
    readonly P3: SubgraphPattern;
    /** Path P4 (4 vertices) */
    readonly P4: SubgraphPattern;
    /** Path P5 (5 vertices) */
    readonly P5: SubgraphPattern;
    /** Path P6 (6 vertices) */
    readonly P6: SubgraphPattern;
    /** Path P7 (7 vertices) */
    readonly P7: SubgraphPattern;
    /** Cycle C3 (triangle) */
    readonly C3: SubgraphPattern;
    /** Cycle C4 (square) */
    readonly C4: SubgraphPattern;
    /** Cycle C5 (pentagon) */
    readonly C5: SubgraphPattern;
    /** Cycle C6 (hexagon) */
    readonly C6: SubgraphPattern;
    /** Cycle C7 (heptagon) */
    readonly C7: SubgraphPattern;
    /** Complete K2 (edge) */
    readonly K2: SubgraphPattern;
    /** Complete K3 (triangle) */
    readonly K3: SubgraphPattern;
    /** Complete K4 */
    readonly K4: SubgraphPattern;
    /** Complete K5 */
    readonly K5: SubgraphPattern;
    /**
     * Bull graph
     * Triangle with two pendant vertices
     *
     *     2
     *     |
     * 0 - 1 - 3
     *     |
     *     4
     */
    readonly bull: SubgraphPattern;
    /**
     * Gem graph
     * P4 with a universal vertex
     *
     *     2
     *     |
     * 0 - 1 - 3
     *     |
     *     4
     * plus all edges from vertex 1
     */
    readonly gem: SubgraphPattern;
    /**
     * Net graph
     * Triangle with three pendant vertices
     *
     *       2
     *      /|\
     *     3 0 4
     *      \|/
     *       1
     */
    readonly net: SubgraphPattern;
    /**
     * House graph
     * P5 with a chord forming a "roof"
     *
     *   2 - 3
     *   |   |
     * 0 - 1 - 4
     */
    readonly house: SubgraphPattern;
    /**
     * Diamond graph
     * K4 minus one edge
     *
     *   2
     *  /|\
     * 3-0-1
     *  \|/
     *   4
     */
    readonly diamond: SubgraphPattern;
    /**
     * Claw graph K1,3
     * Star with 3 leaves
     *
     *     2
     *     |
     * 0 - 1 - 3
     *     |
     *     4
     */
    readonly claw: SubgraphPattern;
    /**
     * Fork graph
     * P4 with an extra pendant attached to second vertex
     *
     *     2
     *     |
     * 0 - 1 - 3 - 4
     */
    readonly fork: SubgraphPattern;
    /**
     * Chair graph
     * P4 plus a pendant attached to center
     *
     *   2
     *   |
     *   1
     *   |
     * 0-1-3-4  (vertex 1 has pendant 2)
     */
    readonly chair: SubgraphPattern;
    /**
     * Dart graph
     * Triangle with a path attached
     *
     *   1---2
     *   |\ /
     *   | 0
     *   |/
     *   3
     */
    readonly dart: SubgraphPattern;
    /**
     * Kite graph
     * Diamond with a pendant
     */
    readonly kite: SubgraphPattern;
    /**
     * Banner graph
     * Triangle with a path of length 2 attached
     */
    readonly banner: SubgraphPattern;
    /**
     * 4-cycle with chord
     * C4 plus one diagonal
     */
    readonly C4_chord: SubgraphPattern;
};
/**
 * Get all pattern names from library
 */
export declare const ALL_PATTERN_NAMES: readonly (keyof typeof SUBGRAPH_PATTERNS)[];
/**
 * Get pattern by name
 * @param name
 */
export declare const getPattern: (name: keyof typeof SUBGRAPH_PATTERNS) => SubgraphPattern;
//# sourceMappingURL=forbidden-subgraphs.d.ts.map