// Number Theory Applications in Algorithms

class NumberTheoryAlgorithms {
    
    // Greatest Common Divisor using Euclidean Algorithm
    gcd(a, b, depth = 0) {
        const indent = '  '.repeat(depth);
        console.log(`${indent}🔢 gcd(${a}, ${b}) called at depth ${depth}`);
        
        // Base case: gcd(a, 0) = a
        if (b === 0) {
            console.log(`${indent}✅ Base case: gcd(${a}, 0) = ${a}`);
            return a;
        }
        
        // Euclidean algorithm: gcd(a, b) = gcd(b, a mod b)
        const remainder = a % b;
        console.log(`${indent}🔄 Computing: gcd(${a}, ${b}) = gcd(${b}, ${a} mod ${b}) = gcd(${b}, ${remainder})`);
        
        return this.gcd(b, remainder, depth + 1);
    }
    
    // Extended Euclidean Algorithm (finds coefficients)
    extendedGCD(a, b) {
        console.log(`🔢 Extended GCD for ${a} and ${b}`);
        
        if (b === 0) {
            console.log(`Base case: ${a} = 1 × ${a} + 0 × 0`);
            return { gcd: a, x: 1, y: 0 };
        }
        
        const result = this.extendedGCD(b, a % b);
        const x = result.y;
        const y = result.x - Math.floor(a / b) * result.y;
        
        console.log(`${a} = ${x} × ${a} + ${y} × ${b} (gcd = ${result.gcd})`);
        return { gcd: result.gcd, x: x, y: y };
    }
    
    // Modular Exponentiation (efficient power calculation)
    modularExponentiation(base, exponent, modulus) {
        console.log(`⚡ Computing ${base}^${exponent} mod ${modulus} efficiently`);
        
        let result = 1;
        base = base % modulus;
        let currentExp = exponent;
        let currentBase = base;
        let step = 0;
        
        while (currentExp > 0) {
            step++;
            console.log(`Step ${step}: base=${currentBase}, exp=${currentExp}, result=${result}`);
            
            // If exponent is odd, multiply base with result
            if (currentExp % 2 === 1) {
                result = (result * currentBase) % modulus;
                console.log(`  Odd exponent: result = (${result / currentBase} × ${currentBase}) mod ${modulus} = ${result}`);
            }
            
            // Square the base and halve the exponent
            currentBase = (currentBase * currentBase) % modulus;
            currentExp = Math.floor(currentExp / 2);
            console.log(`  Next iteration: base=${currentBase}, exp=${currentExp}`);
        }
        
        console.log(`✅ Final result: ${base}^${exponent} mod ${modulus} = ${result}`);
        return result;
    }
    
    // Prime Number Testing
    isPrime(n) {
        console.log(`🔍 Testing if ${n} is prime`);
        
        if (n < 2) {
            console.log(`${n} < 2, not prime`);
            return false;
        }
        
        if (n === 2) {
            console.log(`${n} = 2, prime`);
            return true;
        }
        
        if (n % 2 === 0) {
            console.log(`${n} is even, not prime`);
            return false;
        }
        
        // Check odd divisors up to √n
        const limit = Math.sqrt(n);
        console.log(`Checking divisors up to √${n} ≈ ${limit.toFixed(2)}`);
        
        for (let i = 3; i <= limit; i += 2) {
            if (n % i === 0) {
                console.log(`${n} ÷ ${i} = ${n/i}, not prime`);
                return false;
            }
        }
        
        console.log(`✅ ${n} is prime!`);
        return true;
    }
    
    // Hash Function using Modular Arithmetic
    polynomialHash(string, base = 31, modulus = 1000000007) {
        console.log(`🔐 Computing polynomial hash for "${string}"`);
        console.log(`Using base=${base}, modulus=${modulus}`);
        
        let hash = 0;
        let currentPower = 1;
        
        for (let i = 0; i < string.length; i++) {
            const charCode = string.charCodeAt(i);
            const contribution = (charCode * currentPower) % modulus;
            hash = (hash + contribution) % modulus;
            
            console.log(`  Char '${string[i]}' (${charCode}): ${charCode} × ${currentPower} = ${contribution}, hash = ${hash}`);
            
            currentPower = (currentPower * base) % modulus;
        }
        
        console.log(`✅ Hash("${string}") = ${hash}`);
        return hash;
    }
    
    // Demonstrate number theory applications
    demonstrateNumberTheory() {
        console.log('=== NUMBER THEORY IN ALGORITHMS ===\n');
        
        console.log('1. GREATEST COMMON DIVISOR:');
        const gcdResult = this.gcd(48, 18);
        console.log(`GCD(48, 18) = ${gcdResult}\n`);
        
        console.log('2. EXTENDED GCD (for cryptography):');
        const extGcd = this.extendedGCD(35, 15);
        console.log(`Extended GCD result: gcd=${extGcd.gcd}, x=${extGcd.x}, y=${extGcd.y}\n`);
        
        console.log('3. MODULAR EXPONENTIATION (for encryption):');
        const modExp = this.modularExponentiation(3, 7, 5);
        console.log(`Modular exponentiation result: ${modExp}\n`);
        
        console.log('4. PRIME TESTING:');
        const primeTests = [17, 25, 29];
        primeTests.forEach(num => {
            const isPrime = this.isPrime(num);
            console.log(`${num} is ${isPrime ? 'prime' : 'not prime'}`);
        });
        console.log('');
        
        console.log('5. POLYNOMIAL HASHING:');
        const strings = ['hello', 'world', 'algorithm'];
        strings.forEach(str => {
            this.polynomialHash(str);
        });
        
        return {
            gcd: gcdResult,
            extendedGcd: extGcd,
            modularExp: modExp,
            hashing: 'Demonstrated'
        };
    }
}

// Test number theory algorithms
const numberTheory = new NumberTheoryAlgorithms();
numberTheory.demonstrateNumberTheory();

// Combinatorics Applications in Algorithms

class CombinatoricsAlgorithms {
    
    constructor() {
        this.factorialCache = new Map();
    }
    
    // Factorial with memoization
    factorial(n) {
        if (this.factorialCache.has(n)) {
            return this.factorialCache.get(n);
        }
        
        if (n <= 1) {
            this.factorialCache.set(n, 1);
            return 1;
        }
        
        const result = n * this.factorial(n - 1);
        this.factorialCache.set(n, result);
        return result;
    }
    
    // Permutations: P(n,r) = n! / (n-r)!
    permutations(n, r) {
        console.log(`🔄 Calculating P(${n}, ${r}) = ${n}! / (${n}-${r})!`);
        
        if (r > n) {
            console.log(`r > n, result = 0`);
            return 0;
        }
        
        const numerator = this.factorial(n);
        const denominator = this.factorial(n - r);
        const result = numerator / denominator;
        
        console.log(`P(${n}, ${r}) = ${numerator} / ${denominator} = ${result}`);
        console.log(`💡 Meaning: ${result} ways to arrange ${r} items from ${n} items where order matters`);
        
        return result;
    }
    
    // Combinations: C(n,r) = n! / (r! * (n-r)!)
    combinations(n, r) {
        console.log(`🔢 Calculating C(${n}, ${r}) = ${n}! / (${r}! × (${n}-${r})!)`);
        
        if (r > n) {
            console.log(`r > n, result = 0`);
            return 0;
        }
        
        const numerator = this.factorial(n);
        const denominator = this.factorial(r) * this.factorial(n - r);
        const result = numerator / denominator;
        
        console.log(`C(${n}, ${r}) = ${numerator} / (${this.factorial(r)} × ${this.factorial(n - r)}) = ${result}`);
        console.log(`💡 Meaning: ${result} ways to choose ${r} items from ${n} items where order doesn't matter`);
        
        return result;
    }
    
    // Generate all permutations of an array
    generatePermutations(array, currentPermutation = [], result = [], depth = 0) {
        const indent = '  '.repeat(depth);
        console.log(`${indent}🔄 Generating permutations: current=[${currentPermutation.join(',')}], remaining=[${array.join(',')}]`);
        
        // Base case: no more elements to permute
        if (array.length === 0) {
            console.log(`${indent}✅ Complete permutation: [${currentPermutation.join(', ')}]`);
            result.push([...currentPermutation]);
            return result;
        }
        
        // Recursive case: try each element as the next choice
        for (let i = 0; i < array.length; i++) {
            const chosen = array[i];
            const remaining = array.filter((_, index) => index !== i);
            
            console.log(`${indent}➡️ Choosing ${chosen}, remaining: [${remaining.join(',')}]`);
            
            currentPermutation.push(chosen);
            this.generatePermutations(remaining, currentPermutation, result, depth + 1);
            currentPermutation.pop(); // Backtrack
            
            console.log(`${indent}⬅️ Backtracking from ${chosen}`);
        }
        
        return result;
    }
    
    // Generate all combinations of size r from array
    generateCombinations(array, r, start = 0, currentCombination = [], result = [], depth = 0) {
        const indent = '  '.repeat(depth);
        console.log(`${indent}🔢 Generating combinations of size ${r}: current=[${currentCombination.join(',')}], start=${start}`);
        
        // Base case: combination is complete
        if (currentCombination.length === r) {
            console.log(`${indent}✅ Complete combination: [${currentCombination.join(', ')}]`);
            result.push([...currentCombination]);
            return result;
        }
        
        // Recursive case: try each remaining element
        for (let i = start; i < array.length; i++) {
            const chosen = array[i];
            console.log(`${indent}➡️ Adding ${chosen} to combination`);
            
            currentCombination.push(chosen);
            this.generateCombinations(array, r, i + 1, currentCombination, result, depth + 1);
            currentCombination.pop(); // Backtrack
            
            console.log(`${indent}⬅️ Removing ${chosen} from combination`);
        }
        
        return result;
    }
    
    // Count paths in a grid (dynamic programming application)
    countGridPaths(m, n) {
        console.log(`🗺️ Counting paths in ${m}×${n} grid (right and down moves only)`);
        
        // Mathematical insight: need (m-1) rights + (n-1) downs = total (m+n-2) moves
        // Choose (m-1) positions for right moves from (m+n-2) total positions
        const totalMoves = m + n - 2;
        const rightMoves = m - 1;
        
        console.log(`Total moves needed: ${totalMoves}`);
        console.log(`Right moves needed: ${rightMoves}`);
        console.log(`Down moves needed: ${n - 1}`);
        
        const paths = this.combinations(totalMoves, rightMoves);
        console.log(`✅ Total unique paths: C(${totalMoves}, ${rightMoves}) = ${paths}`);
        
        return paths;
    }
    
    // Demonstrate combinatorics applications
    demonstrateCombinatorics() {
        console.log('\n=== COMBINATORICS IN ALGORITHMS ===\n');
        
        console.log('1. PERMUTATIONS AND COMBINATIONS:');
        console.log('Team selection from 8 players:');
        const teamPerms = this.permutations(8, 3);
        console.log(`Ways to select and arrange 3 players: ${teamPerms}`);
        
        const teamCombs = this.combinations(8, 3);
        console.log(`Ways to select 3 players (order doesn't matter): ${teamCombs}\n`);
        
        console.log('2. GENERATING ALL PERMUTATIONS:');
        const smallArray = ['A', 'B', 'C'];
        console.log(`Generating all permutations of [${smallArray.join(', ')}]:`);
        const allPerms = this.generatePermutations(smallArray);
        console.log(`Total permutations found: ${allPerms.length}`);
        allPerms.forEach((perm, index) => {
            console.log(`  ${index + 1}: [${perm.join(', ')}]`);
        });
        console.log('');
        
        console.log('3. GENERATING ALL COMBINATIONS:');
        const numbers = [1, 2, 3, 4];
        console.log(`Generating all combinations of size 2 from [${numbers.join(', ')}]:`);
        const allCombs = this.generateCombinations(numbers, 2);
        console.log(`Total combinations found: ${allCombs.length}`);
        allCombs.forEach((comb, index) => {
            console.log(`  ${index + 1}: [${comb.join(', ')}]`);
        });
        console.log('');
        
        console.log('4. GRID PATH COUNTING:');
        const gridPaths = this.countGridPaths(3, 3);
        console.log(`Paths in 3×3 grid: ${gridPaths}\n`);
        
        console.log('5. REAL-WORLD APPLICATIONS:');
        console.log('- Password combinations: C(62, 8) for 8-char alphanumeric');
        console.log('- DNA sequences: 4^n possible sequences of length n');
        console.log('- Algorithm analysis: counting operations and complexity');
        console.log('- Graph theory: counting paths and cycles');
        
        return {
            permutations: teamPerms,
            combinations: teamCombs,
            allPermutations: allPerms.length,
            allCombinations: allCombs.length,
            gridPaths: gridPaths
        };
    }
}

// Test combinatorics algorithms
const combinatorics = new CombinatoricsAlgorithms();
combinatorics.demonstrateCombinatorics();

// Set Theory and Boolean Logic in Algorithms

class SetTheoryAlgorithms {
    
    // Set operations with detailed explanations
    setUnion(setA, setB) {
        console.log(`🔗 Computing A ∪ B (Union)`);
        console.log(`A = {${Array.from(setA).join(', ')}}`);
        console.log(`B = {${Array.from(setB).join(', ')}}`);
        
        const union = new Set([...setA, ...setB]);
        console.log(`A ∪ B = {${Array.from(union).join(', ')}}`);
        console.log(`💡 Union contains all elements from both sets (no duplicates)`);
        
        return union;
    }
    
    setIntersection(setA, setB) {
        console.log(`🔗 Computing A ∩ B (Intersection)`);
        console.log(`A = {${Array.from(setA).join(', ')}}`);
        console.log(`B = {${Array.from(setB).join(', ')}}`);
        
        const intersection = new Set();
        for (const element of setA) {
            if (setB.has(element)) {
                intersection.add(element);
                console.log(`  ${element} ∈ A and ${element} ∈ B → add to intersection`);
            }
        }
        
        console.log(`A ∩ B = {${Array.from(intersection).join(', ')}}`);
        console.log(`💡 Intersection contains only elements in both sets`);
        
        return intersection;
    }
    
    setDifference(setA, setB) {
        console.log(`🔗 Computing A - B (Difference)`);
        console.log(`A = {${Array.from(setA).join(', ')}}`);
        console.log(`B = {${Array.from(setB).join(', ')}}`);
        
        const difference = new Set();
        for (const element of setA) {
            if (!setB.has(element)) {
                difference.add(element);
                console.log(`  ${element} ∈ A but ${element} ∉ B → add to difference`);
            }
        }
        
        console.log(`A - B = {${Array.from(difference).join(', ')}}`);
        console.log(`💡 Difference contains elements in A but not in B`);
        
        return difference;
    }
    
    // Boolean logic operations
    evaluateBooleanExpression(expression, variables) {
        console.log(`🔍 Evaluating Boolean expression: ${expression}`);
        console.log(`Variables: ${JSON.stringify(variables)}`);
        
        // Simple parser for basic boolean expressions
        let result = expression;
        
        // Replace variables with their values
        for (const [variable, value] of Object.entries(variables)) {
            result = result.replaceAll(variable, value.toString());
        }
        
        console.log(`After substitution: ${result}`);
        
        // Evaluate the expression (simplified evaluation)
        try {
            const finalResult = eval(result.replaceAll('AND', '&&').replaceAll('OR', '||').replaceAll('NOT', '!'));
            console.log(`✅ Result: ${finalResult}`);
            return finalResult;
        } catch (error) {
            console.log(`❌ Error evaluating expression: ${error.message}`);
            return null;
        }
    }
    
    // Truth table generation
    generateTruthTable(variables, expression) {
        console.log(`📊 Generating truth table for: ${expression}`);
        console.log(`Variables: [${variables.join(', ')}]`);
        
        const numVariables = variables.length;
        const numRows = Math.pow(2, numVariables);
        const table = [];
        
        console.log('\nTruth Table:');
        const header = variables.join(' | ') + ' | ' + expression;
        console.log(header);
        console.log('-'.repeat(header.length));
        
        for (let i = 0; i < numRows; i++) {
            const row = {};
            let binaryString = i.toString(2).padStart(numVariables, '0');
            
            // Set variable values based on binary representation
            for (let j = 0; j < numVariables; j++) {
                const value = binaryString[j] === '1';
                row[variables[j]] = value;
            }
            
            // Evaluate expression with current variable assignment
            const result = this.evaluateBooleanExpression(expression, row);
            row.result = result;
            
            // Format row for display
            const rowDisplay = variables.map(v => row[v] ? 'T' : 'F').join(' | ') + ' | ' + (result ? 'T' : 'F');
            console.log(rowDisplay);
            
            table.push(row);
        }
        
        return table;
    }
    
    // Practical application: Database query optimization
    optimizeQuery(tables, conditions) {
        console.log(`🗃️ Query Optimization using Set Theory`);
        console.log(`Tables: ${tables.map(t => t.name).join(', ')}`);
        console.log(`Conditions: ${JSON.stringify(conditions)}`);
        
        // Simulate finding optimal join order using set theory
        const tableSizes = new Map(tables.map(t => [t.name, t.size]));
        console.log(`Table sizes: ${JSON.stringify(Object.fromEntries(tableSizes))}`);
        
        // Use set intersection to estimate result sizes
        let currentResultSize = Math.min(...Array.from(tableSizes.values()));
        console.log(`Starting with smallest table size: ${currentResultSize}`);
        
        for (const condition of conditions) {
            // Simulate selectivity based on condition type
            const selectivity = condition.includes('=') ? 0.1 : 0.5;
            currentResultSize = Math.floor(currentResultSize * selectivity);
            console.log(`After condition "${condition}": estimated ${currentResultSize} rows`);
        }
        
        console.log(`✅ Optimized query estimated result: ${currentResultSize} rows`);
        return currentResultSize;
    }
    
    // Demonstrate set theory applications
    demonstrateSetTheory() {
        console.log('\n=== SET THEORY & BOOLEAN LOGIC ===\n');
        
        console.log('1. SET OPERATIONS:');
        const setA = new Set([1, 2, 3, 4, 5]);
        const setB = new Set([4, 5, 6, 7, 8]);
        
        const union = this.setUnion(setA, setB);
        console.log('');
        
        const intersection = this.setIntersection(setA, setB);
        console.log('');
        
        const difference = this.setDifference(setA, setB);
        console.log('');
        
        console.log('2. BOOLEAN LOGIC:');
        const expression = 'A AND (B OR NOT C)';
        const variables = { A: true, B: false, C: true };
        const result = this.evaluateBooleanExpression(expression, variables);
        console.log('');
        
        console.log('3. TRUTH TABLE:');
        const truthTable = this.generateTruthTable(['A', 'B'], 'A AND B');
        console.log('');
        
        console.log('4. PRACTICAL APPLICATION - Query Optimization:');
        const tables = [
            { name: 'users', size: 1000000 },
            { name: 'orders', size: 5000000 },
            { name: 'products', size: 100000 }
        ];
        const conditions = ['user_id = 12345', 'order_date > 2023-01-01'];
        const optimizedSize = this.optimizeQuery(tables, conditions);
        console.log('');
        
        console.log('5. REAL-WORLD APPLICATIONS:');
        console.log('- Database indexing and query optimization');
        console.log('- Logic circuit design and verification');
        console.log('- Data deduplication and merging');
        console.log('- Access control and permission systems');
        console.log('- Graph algorithms (vertex and edge sets)');
        
        return {
            setOperations: { union: union.size, intersection: intersection.size, difference: difference.size },
            booleanLogic: result,
            truthTable: truthTable.length,
            queryOptimization: optimizedSize
        };
    }
}

// Test set theory algorithms
const setTheory = new SetTheoryAlgorithms();
setTheory.demonstrateSetTheory();

// Graph Theory Foundations for Algorithms

class GraphTheoryFoundations {
    
    constructor() {
        this.createSampleGraph();
    }
    
    createSampleGraph() {
        // Create a sample graph: Social network representation
        this.graph = {
            vertices: ['Alice', 'Bob', 'Charlie', 'Diana', 'Eve'],
            edges: [
                ['Alice', 'Bob'],
                ['Alice', 'Charlie'],
                ['Bob', 'Diana'],
                ['Charlie', 'Diana'],
                ['Diana', 'Eve']
            ],
            // Adjacency list representation
            adjacencyList: {
                'Alice': ['Bob', 'Charlie'],
                'Bob': ['Alice', 'Diana'],
                'Charlie': ['Alice', 'Diana'],
                'Diana': ['Bob', 'Charlie', 'Eve'],
                'Eve': ['Diana']
            }
        };
    }
    
    // Graph properties analysis
    analyzeGraphProperties() {
        console.log(`📊 Analyzing Graph Properties`);
        console.log(`Vertices: [${this.graph.vertices.join(', ')}]`);
        console.log(`Edges: ${this.graph.edges.map(e => `(${e[0]}, ${e[1]})`).join(', ')}`);
        
        const numVertices = this.graph.vertices.length;
        const numEdges = this.graph.edges.length;
        
        console.log(`\n📈 Basic Properties:`);
        console.log(`|V| = ${numVertices} vertices`);
        console.log(`|E| = ${numEdges} edges`);
        
        // Calculate degree of each vertex
        const degrees = {};
        for (const vertex of this.graph.vertices) {
            degrees[vertex] = this.graph.adjacencyList[vertex].length;
            console.log(`degree(${vertex}) = ${degrees[vertex]}`);
        }
        
        // Graph density
        const maxPossibleEdges = (numVertices * (numVertices - 1)) / 2;
        const density = numEdges / maxPossibleEdges;
        console.log(`\n🔍 Graph Density: ${numEdges}/${maxPossibleEdges} = ${density.toFixed(3)}`);
        console.log(`💡 Density close to 0 = sparse, close to 1 = dense`);
        
        return { vertices: numVertices, edges: numEdges, density: density, degrees: degrees };
    }
    
    // Matrix representations
    createAdjacencyMatrix() {
        console.log(`\n🗃️ Creating Adjacency Matrix`);
        
        const n = this.graph.vertices.length;
        const matrix = Array(n).fill().map(() => Array(n).fill(0));
        
        // Create vertex index mapping
        const vertexIndex = {};
        this.graph.vertices.forEach((vertex, index) => {
            vertexIndex[vertex] = index;
        });
        
        console.log(`Vertex indices: ${JSON.stringify(vertexIndex)}`);
        
        // Fill matrix based on edges
        for (const [u, v] of this.graph.edges) {
            const i = vertexIndex[u];
            const j = vertexIndex[v];
            matrix[i][j] = 1;
            matrix[j][i] = 1; // Undirected graph
            console.log(`Edge (${u}, ${v}): matrix[${i}][${j}] = matrix[${j}][${i}] = 1`);
        }
        
        console.log(`\n📋 Adjacency Matrix:`);
        console.log('     ' + this.graph.vertices.join('  '));
        for (let i = 0; i < n; i++) {
            const row = this.graph.vertices[i].padEnd(4) + matrix[i].join('  ');
            console.log(row);
        }
        
        return matrix;
    }
    
    // Path finding using graph theory
    findAllPaths(start, end, currentPath = [], allPaths = [], depth = 0) {
        const indent = '  '.repeat(depth);
        console.log(`${indent}🔍 Finding paths from ${start} to ${end}`);
        console.log(`${indent}Current path: [${currentPath.join(' → ')}]`);
        
        // Add current vertex to path
        currentPath.push(start);
        
        // Base case: reached destination
        if (start === end) {
            console.log(`${indent}✅ Found complete path: [${currentPath.join(' → ')}]`);
            allPaths.push([...currentPath]);
        } else {
            // Recursive case: explore neighbors
            const neighbors = this.graph.adjacencyList[start] || [];
            console.log(`${indent}Neighbors of ${start}: [${neighbors.join(', ')}]`);
            
            for (const neighbor of neighbors) {
                // Avoid cycles (don't revisit vertices in current path)
                if (!currentPath.includes(neighbor)) {
                    console.log(`${indent}➡️ Exploring neighbor ${neighbor}`);
                    this.findAllPaths(neighbor, end, currentPath, allPaths, depth + 1);
                } else {
                    console.log(`${indent}⚠️ Skipping ${neighbor} (already in path - would create cycle)`);
                }
            }
        }
        
        // Backtrack: remove current vertex from path
        currentPath.pop();
        console.log(`${indent}⬅️ Backtracking from ${start}`);
        
        return allPaths;
    }
    
    // Graph connectivity analysis
    analyzeConnectivity() {
        console.log(`\n🔗 Analyzing Graph Connectivity`);
        
        // Check if graph is connected using DFS
        const visited = new Set();
        const startVertex = this.graph.vertices[0];
        
        console.log(`Starting DFS from ${startVertex}:`);
        this.dfsConnectivity(startVertex, visited, 0);
        
        const isConnected = visited.size === this.graph.vertices.length;
        console.log(`\n📊 Connectivity Analysis:`);
        console.log(`Visited ${visited.size} out of ${this.graph.vertices.length} vertices`);
        console.log(`Graph is ${isConnected ? 'CONNECTED' : 'NOT CONNECTED'}`);
        
        if (!isConnected) {
            const unvisited = this.graph.vertices.filter(v => !visited.has(v));
            console.log(`Unreachable vertices: [${unvisited.join(', ')}]`);
        }
        
        return { isConnected: isConnected, visitedCount: visited.size };
    }
    
    dfsConnectivity(vertex, visited, depth) {
        const indent = '  '.repeat(depth);
        console.log(`${indent}🔍 DFS visiting ${vertex}`);
        
        visited.add(vertex);
        
        const neighbors = this.graph.adjacencyList[vertex] || [];
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                console.log(`${indent}➡️ Exploring unvisited neighbor ${neighbor}`);
                this.dfsConnectivity(neighbor, visited, depth + 1);
            } else {
                console.log(`${indent}⚪ ${neighbor} already visited`);
            }
        }
    }
    
    // Demonstrate graph theory applications
    demonstrateGraphTheory() {
        console.log('\n=== GRAPH THEORY FOUNDATIONS ===\n');
        
        console.log('SAMPLE GRAPH: Social Network');
        console.log('Vertices = People, Edges = Friendships\n');
        
        const properties = this.analyzeGraphProperties();
        
        const matrix = this.createAdjacencyMatrix();
        
        console.log('\n🛤️ PATH FINDING:');
        console.log('Finding all paths from Alice to Eve:');
        const paths = this.findAllPaths('Alice', 'Eve');
        console.log(`\nAll paths found:`);
        paths.forEach((path, index) => {
            console.log(`  Path ${index + 1}: ${path.join(' → ')}`);
        });
        
        const connectivity = this.analyzeConnectivity();
        
        console.log('\n🌍 REAL-WORLD APPLICATIONS:');
        console.log('- Social Networks: Friend recommendations, influence analysis');
        console.log('- Transportation: Route planning, traffic optimization');
        console.log('- Computer Networks: Data routing, network topology');
        console.log('- Web Graphs: PageRank, link analysis');
        console.log('- Dependency Graphs: Build systems, task scheduling');
        console.log('- Biological Networks: Protein interactions, gene regulation');
        
        return {
            properties: properties,
            paths: paths.length,
            connectivity: connectivity.isConnected
        };
    }
}

// Test graph theory foundations
const graphTheory = new GraphTheoryFoundations();
graphTheory.demonstrateGraphTheory();