import networkx as nx
import matplotlib.pyplot as plt
from itertools import combinations
from typing import List, Set, Tuple, Dict

class Graph:
    def __init__(self):
        self.vertices = set()
        self.edges = set()
        self.adjacency_list = {}
    
    def add_vertex(self, vertex):
        """Add a vertex to the graph"""
        self.vertices.add(vertex)
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = set()
    
    def add_edge(self, u, v):
        """Add an undirected edge between vertices u and v"""
        self.add_vertex(u)
        self.add_vertex(v)
        self.edges.add((min(u, v), max(u, v)))
        self.adjacency_list[u].add(v)
        self.adjacency_list[v].add(u)
    
    def is_clique(self, vertices_subset: Set) -> bool:
        """Check if a subset of vertices forms a clique"""
        vertices_list = list(vertices_subset)
        n = len(vertices_list)
        
        # A clique of size n should have n(n-1)/2 edges
        expected_edges = n * (n - 1) // 2
        actual_edges = 0
        
        for i in range(n):
            for j in range(i + 1, n):
                u, v = vertices_list[i], vertices_list[j]
                if v in self.adjacency_list[u]:
                    actual_edges += 1
        
        return actual_edges == expected_edges
    
    def find_all_cliques_naive(self) -> List[Set]:
        """Find all maximal cliques using naive approach (exponential time)"""
        all_cliques = []
        
        # Check all possible subsets of vertices
        vertices_list = list(self.vertices)
        n = len(vertices_list)
        
        for size in range(1, n + 1):
            for subset in combinations(vertices_list, size):
                subset_set = set(subset)
                if self.is_clique(subset_set):
                    # Check if it's maximal (can't be extended)
                    is_maximal = True
                    for v in self.vertices - subset_set:
                        extended_set = subset_set | {v}
                        if self.is_clique(extended_set):
                            is_maximal = False
                            break
                    
                    if is_maximal:
                        all_cliques.append(subset_set)
        
        return all_cliques

# Example: Social network analysis
def create_social_network_example():
    """Create a sample social network for clique analysis"""
    graph = Graph()
    
    # Add friendships (edges)
    friendships = [
        ("Alice", "Bob"), ("Alice", "Carol"), ("Bob", "Carol"),  # Triangle clique
        ("David", "Eve"), ("David", "Frank"), ("Eve", "Frank"),  # Another triangle
        ("Carol", "David"),  # Bridge between groups
        ("Grace", "Henry"), ("Grace", "Ivy"), ("Henry", "Ivy"), ("Henry", "Jack")  # Mixed group
    ]
    
    for u, v in friendships:
        graph.add_edge(u, v)
    
    return graph

# Demonstrate clique detection
social_graph = create_social_network_example()
print("Social Network Analysis:")
print(f"Vertices: {social_graph.vertices}")
print(f"Edges: {social_graph.edges}")

# Check specific subsets
test_sets = [
    {"Alice", "Bob", "Carol"},
    {"David", "Eve", "Frank"},
    {"Grace", "Henry", "Ivy"},
    {"Alice", "David"}
]

for test_set in test_sets:
    is_clique = social_graph.is_clique(test_set)
    print(f"{test_set} is a clique: {is_clique}")

class CliqueAnalyzer:
    def __init__(self, graph: Graph):
        self.graph = graph
    
    def find_maximal_cliques_bron_kerbosch(self) -> List[Set]:
        """
        Bron-Kerbosch algorithm for finding all maximal cliques
        More efficient than naive approach
        """
        def bron_kerbosch(R, P, X, cliques):
            if not P and not X:
                # R is a maximal clique
                cliques.append(R.copy())
                return
            
            # Choose pivot to minimize branching
            pivot = max(P | X, key=lambda v: len(P & self.graph.adjacency_list[v]), default=None)
            
            for v in P - (self.graph.adjacency_list[pivot] if pivot else set()):
                neighbors_v = self.graph.adjacency_list[v]
                bron_kerbosch(
                    R | {v},
                    P & neighbors_v,
                    X & neighbors_v,
                    cliques
                )
                P.remove(v)
                X.add(v)
        
        cliques = []
        bron_kerbosch(set(), self.graph.vertices.copy(), set(), cliques)
        return cliques
    
    def find_maximum_clique(self) -> Set:
        """Find the maximum clique (largest by size)"""
        maximal_cliques = self.find_maximal_cliques_bron_kerbosch()
        if not maximal_cliques:
            return set()
        
        return max(maximal_cliques, key=len)
    
    def clique_number(self) -> int:
        """Return the clique number (size of maximum clique)"""
        maximum_clique = self.find_maximum_clique()
        return len(maximum_clique)

# Analyze our social network
analyzer = CliqueAnalyzer(social_graph)
maximal_cliques = analyzer.find_maximal_cliques_bron_kerbosch()
maximum_clique = analyzer.find_maximum_clique()

print(f"\nClique Analysis Results:")
print(f"Number of maximal cliques: {len(maximal_cliques)}")
print(f"Maximal cliques: {maximal_cliques}")
print(f"Maximum clique: {maximum_clique}")
print(f"Clique number: {analyzer.clique_number()}")

class CliquePartitionSolver:
    def __init__(self, graph: Graph):
        self.graph = graph
        self.complement_graph = self._compute_complement()
    
    def _compute_complement(self) -> Graph:
        """Compute the complement graph"""
        complement = Graph()
        
        # Add all vertices
        for v in self.graph.vertices:
            complement.add_vertex(v)
        
        # Add edges that are NOT in the original graph
        vertices_list = list(self.graph.vertices)
        for i in range(len(vertices_list)):
            for j in range(i + 1, len(vertices_list)):
                u, v = vertices_list[i], vertices_list[j]
                edge = (min(u, v), max(u, v))
                
                if edge not in self.graph.edges:
                    complement.add_edge(u, v)
        
        return complement
    
    def greedy_clique_partition(self) -> Tuple[List[Set], int]:
        """
        Greedy algorithm for clique partition
        Not optimal but gives reasonable approximation
        """
        remaining_vertices = self.graph.vertices.copy()
        partition = []
        
        while remaining_vertices:
            # Find a maximal clique in the remaining subgraph
            current_clique = self._find_greedy_clique(remaining_vertices)
            partition.append(current_clique)
            remaining_vertices -= current_clique
        
        return partition, len(partition)
    
    def _find_greedy_clique(self, vertices: Set) -> Set:
        """Find a maximal clique greedily from given vertices"""
        if not vertices:
            return set()
        
        # Start with highest degree vertex
        degrees = {v: len(self.graph.adjacency_list[v] & vertices) for v in vertices}
        start_vertex = max(degrees, key=degrees.get)
        
        clique = {start_vertex}
        candidates = self.graph.adjacency_list[start_vertex] & vertices
        
        # Greedily add vertices that are connected to all vertices in current clique
        while candidates:
            # Choose vertex with highest degree among candidates
            next_vertex = max(candidates, 
                            key=lambda v: len(self.graph.adjacency_list[v] & candidates))
            
            clique.add(next_vertex)
            # Update candidates to only those connected to all vertices in clique
            candidates &= self.graph.adjacency_list[next_vertex]
        
        return clique
    
    def brute_force_partition(self) -> Tuple[List[Set], int]:
        """
        Brute force approach for small graphs
        Tries all possible partitions (exponential time)
        """
        n = len(self.graph.vertices)
        vertices_list = list(self.graph.vertices)
        
        min_partitions = float('inf')
        best_partition = None
        
        # Generate all possible partitions using Bell numbers approach
        for k in range(1, n + 1):
            partitions = self._generate_partitions(vertices_list, k)
            
            for partition in partitions:
                # Check if all parts are cliques
                if all(self.graph.is_clique(part) for part in partition):
                    if len(partition) < min_partitions:
                        min_partitions = len(partition)
                        best_partition = partition
                        break  # Found optimal for this k
            
            if best_partition:
                break  # Found optimal solution
        
        return best_partition if best_partition else [set(vertices_list)], min_partitions
    
    def _generate_partitions(self, vertices: List, k: int):
        """Generate all possible k-partitions of vertices (simplified)"""
        # This is a simplified version - full implementation would use
        # Stirling numbers or Bell numbers for complete enumeration
        if k == 1:
            yield [set(vertices)]
        elif k == len(vertices):
            yield [{v} for v in vertices]
        # For brevity, we'll skip the full recursive implementation

# Example analysis
print("\nClique Partition Analysis:")
solver = CliquePartitionSolver(social_graph)

# Greedy solution
greedy_partition, greedy_size = solver.greedy_clique_partition()
print(f"Greedy partition ({greedy_size} cliques): {greedy_partition}")

# Verify partition validity
total_vertices = set()
for clique in greedy_partition:
    total_vertices |= clique
    print(f"  Clique {clique}: is_clique = {social_graph.is_clique(clique)}")

print(f"Covers all vertices: {total_vertices == social_graph.vertices}")

class NPCompletenessDemo:
    """Demonstration of NP-completeness concepts"""
    
    @staticmethod
    def graph_coloring_to_clique_partition(graph: Graph, coloring: Dict) -> List[Set]:
        """
        Convert a graph coloring to a clique partition of the complement graph
        This demonstrates the reduction between the two problems
        """
        # Group vertices by color
        color_classes = {}
        for vertex, color in coloring.items():
            if color not in color_classes:
                color_classes[color] = set()
            color_classes[color].add(vertex)
        
        return list(color_classes.values())
    
    @staticmethod
    def clique_partition_to_graph_coloring(partition: List[Set]) -> Dict:
        """
        Convert a clique partition to a graph coloring
        """
        coloring = {}
        for color, clique in enumerate(partition):
            for vertex in clique:
                coloring[vertex] = color
        
        return coloring
    
    @staticmethod
    def verify_reduction(original_graph: Graph, complement_graph: Graph, 
                        partition: List[Set]) -> bool:
        """
        Verify that a clique partition of the original graph
        corresponds to a valid coloring of the complement graph
        """
        # Check that partition consists of cliques in original graph
        for clique in partition:
            if not original_graph.is_clique(clique):
                return False
        
        # Check that coloring is valid in complement graph
        coloring = NPCompletenessDemo.clique_partition_to_graph_coloring(partition)
        
        for u, v in complement_graph.edges:
            if coloring[u] == coloring[v]:
                return False  # Adjacent vertices have same color - invalid
        
        return True

# Demonstrate the reduction
print("\nNP-Completeness Demonstration:")
demo = NPCompletenessDemo()

# Use our previous partition
if 'greedy_partition' in locals():
    is_valid_reduction = demo.verify_reduction(social_graph, solver.complement_graph, greedy_partition)
    print(f"Reduction verification: {is_valid_reduction}")
    
    # Show corresponding coloring
    coloring = demo.clique_partition_to_graph_coloring(greedy_partition)
    print(f"Corresponding coloring: {coloring}")

class TsengAlgorithm:
    """
    Implementation of Tseng's algorithm for maximal clique construction
    """
    
    def __init__(self, graph: Graph):
        self.graph = graph
        self.visited = set()
    
    def find_maximal_clique_from_vertex(self, start_vertex) -> Set:
        """
        Find a maximal clique starting from a given vertex using Tseng's approach
        """
        if start_vertex not in self.graph.vertices:
            return set()
        
        # Initialize clique with start vertex
        clique = {start_vertex}
        
        # Candidates are neighbors of the start vertex
        candidates = self.graph.adjacency_list[start_vertex].copy()
        
        # Iteratively add vertices to the clique
        while candidates:
            # Select vertex using Tseng's selection criteria
            next_vertex = self._select_next_vertex(clique, candidates)
            
            if next_vertex is None:
                break
            
            # Add vertex to clique
            clique.add(next_vertex)
            
            # Update candidates to maintain clique property
            # Only keep vertices that are adjacent to ALL vertices in current clique
            candidates = self._update_candidates(clique, candidates)
        
        return clique
    
    def _select_next_vertex(self, current_clique: Set, candidates: Set):
        """
        Tseng's vertex selection strategy:
        Choose vertex with maximum number of connections to current candidates
        """
        if not candidates:
            return None
        
        best_vertex = None
        max_connections = -1
        
        for candidate in candidates:
            # Count connections to other candidates
            connections = len(self.graph.adjacency_list[candidate] & candidates)
            
            if connections > max_connections:
                max_connections = connections
                best_vertex = candidate
        
        return best_vertex
    
    def _update_candidates(self, clique: Set, old_candidates: Set) -> Set:
        """
        Update candidate set to maintain clique property
        """
        new_candidates = set()
        
        for candidate in old_candidates:
            # Check if candidate is adjacent to ALL vertices in current clique
            is_adjacent_to_all = True
            for clique_vertex in clique:
                if candidate not in self.graph.adjacency_list[clique_vertex]:
                    is_adjacent_to_all = False
                    break
            
            if is_adjacent_to_all:
                new_candidates.add(candidate)
        
        return new_candidates
    
    def tseng_clique_partition(self) -> Tuple[List[Set], int]:
        """
        Use Tseng's algorithm to construct a clique partition
        """
        partition = []
        remaining_vertices = self.graph.vertices.copy()
        
        while remaining_vertices:
            # Choose starting vertex (highest degree in remaining subgraph)
            degrees = {v: len(self.graph.adjacency_list[v] & remaining_vertices) 
                      for v in remaining_vertices}
            start_vertex = max(degrees, key=degrees.get)
            
            # Find maximal clique starting from this vertex
            clique = self.find_maximal_clique_from_vertex_in_subgraph(
                start_vertex, remaining_vertices)
            
            partition.append(clique)
            remaining_vertices -= clique
        
        return partition, len(partition)
    
    def find_maximal_clique_from_vertex_in_subgraph(self, start_vertex, subgraph_vertices):
        """
        Modified version that works within a subgraph
        """
        clique = {start_vertex}
        candidates = self.graph.adjacency_list[start_vertex] & subgraph_vertices
        
        while candidates:
            # Use Tseng's selection within the subgraph
            next_vertex = None
            max_connections = -1
            
            for candidate in candidates:
                connections = len(self.graph.adjacency_list[candidate] & candidates)
                if connections > max_connections:
                    max_connections = connections
                    next_vertex = candidate
            
            if next_vertex is None:
                break
            
            clique.add(next_vertex)
            
            # Update candidates
            new_candidates = set()
            for candidate in candidates:
                if candidate != next_vertex:
                    # Check adjacency to all clique vertices
                    if all(candidate in self.graph.adjacency_list[cv] for cv in clique):
                        new_candidates.add(candidate)
            
            candidates = new_candidates
        
        return clique

# Apply Tseng's algorithm
print("\nTseng's Algorithm Analysis:")
tseng_solver = TsengAlgorithm(social_graph)

# Find partition using Tseng's approach
tseng_partition, tseng_size = tseng_solver.tseng_clique_partition()
print(f"Tseng partition ({tseng_size} cliques): {tseng_partition}")

# Verify validity
for i, clique in enumerate(tseng_partition):
    is_valid_clique = social_graph.is_clique(clique)
    print(f"  Clique {i+1} {clique}: valid = {is_valid_clique}")

# Compare with greedy approach
print(f"\nComparison:")
print(f"Greedy approach: {greedy_size} cliques")
print(f"Tseng's approach: {tseng_size} cliques")

class BranchAndBoundCliquePartition:
    """
    Branch and bound algorithm for exact clique partition
    """
    
    def __init__(self, graph: Graph):
        self.graph = graph
        self.best_partition_size = float('inf')
        self.best_partition = None
    
    def solve(self) -> Tuple[List[Set], int]:
        """
        Find optimal clique partition using branch and bound
        """
        vertices_list = list(self.graph.vertices)
        initial_partition = []
        remaining_vertices = set(vertices_list)
        
        self._branch_and_bound(initial_partition, remaining_vertices, 0)
        
        return self.best_partition, self.best_partition_size
    
    def _branch_and_bound(self, current_partition: List[Set], 
                         remaining_vertices: Set, current_size: int):
        """
        Recursive branch and bound procedure
        """
        # Pruning: if current size already exceeds best known, stop
        if current_size >= self.best_partition_size:
            return
        
        # Base case: no vertices remaining
        if not remaining_vertices:
            if current_size < self.best_partition_size:
                self.best_partition_size = current_size
                self.best_partition = [clique.copy() for clique in current_partition]
            return
        
        # Lower bound estimation
        lower_bound = current_size + self._estimate_lower_bound(remaining_vertices)
        if lower_bound >= self.best_partition_size:
            return  # Prune this branch
        
        # Try different maximal cliques starting from remaining vertices
        cliques_to_try = self._generate_maximal_cliques(remaining_vertices)
        
        for clique in cliques_to_try:
            # Create new partition with this clique
            new_partition = current_partition + [clique]
            new_remaining = remaining_vertices - clique
            
            # Recurse
            self._branch_and_bound(new_partition, new_remaining, current_size + 1)
    
    def _estimate_lower_bound(self, vertices: Set) -> int:
        """
        Estimate lower bound on number of cliques needed for remaining vertices
        """
        if not vertices:
            return 0
        
        # Simple bound: use independence number of complement subgraph
        # For now, use a greedy approximation
        remaining = vertices.copy()
        cliques_needed = 0
        
        while remaining:
            # Find a maximal clique greedily
            clique = self._greedy_clique_in_subgraph(remaining)
            remaining -= clique
            cliques_needed += 1
        
        return cliques_needed
    
    def _generate_maximal_cliques(self, vertices: Set) -> List[Set]:
        """
        Generate all maximal cliques in the subgraph induced by vertices
        (Simplified version for demonstration)
        """
        if len(vertices) > 10:  # Limit for efficiency
            # Return only one greedy clique for large sets
            return [self._greedy_clique_in_subgraph(vertices)]
        
        # For small sets, try multiple starting points
        cliques = []
        for v in vertices:
            clique = self._maximal_clique_from_vertex_in_subgraph(v, vertices)
            if clique not in cliques:
                cliques.append(clique)
        
        return cliques
    
    def _greedy_clique_in_subgraph(self, vertices: Set) -> Set:
        """Find a greedy maximal clique in subgraph"""
        if not vertices:
            return set()
        
        # Start with highest degree vertex in subgraph
        degrees = {v: len(self.graph.adjacency_list[v] & vertices) for v in vertices}
        start = max(degrees, key=degrees.get)
        
        clique = {start}
        candidates = self.graph.adjacency_list[start] & vertices
        
        while candidates:
            # Add vertex with most connections to current candidates
            next_v = max(candidates, 
                        key=lambda v: len(self.graph.adjacency_list[v] & candidates))
            clique.add(next_v)
            candidates &= self.graph.adjacency_list[next_v]
        
        return clique
    
    def _maximal_clique_from_vertex_in_subgraph(self, start_vertex: str, vertices: Set) -> Set:
        """Find maximal clique starting from specific vertex in subgraph"""
        clique = {start_vertex}
        candidates = self.graph.adjacency_list[start_vertex] & vertices
        
        for candidate in list(candidates):
            if all(candidate in self.graph.adjacency_list[cv] for cv in clique):
                clique.add(candidate)
                candidates &= self.graph.adjacency_list[candidate]
        
        return clique

# For small graphs, we can try exact solution
print("\nBranch and Bound (for small graphs):")
if len(social_graph.vertices) <= 8:  # Only for small examples
    bb_solver = BranchAndBoundCliquePartition(social_graph)
    bb_partition, bb_size = bb_solver.solve()
    print(f"Optimal partition ({bb_size} cliques): {bb_partition}")
else:
    print("Graph too large for demonstration - would use approximation in practice")

class ApproximationAlgorithms:
    """
    Collection of approximation algorithms for clique partition
    """
    
    def __init__(self, graph: Graph):
        self.graph = graph
    
    def sequential_greedy_approximation(self) -> Tuple[List[Set], int]:
        """
        Sequential greedy approximation
        Approximation ratio: O(log n)
        """
        remaining_vertices = self.graph.vertices.copy()
        partition = []
        
        while remaining_vertices:
            # Find the largest clique in the current subgraph
            best_clique = self._find_largest_clique_approximation(remaining_vertices)
            partition.append(best_clique)
            remaining_vertices -= best_clique
        
        return partition, len(partition)
    
    def _find_largest_clique_approximation(self, vertices: Set) -> Set:
        """
        Approximation for finding largest clique in subgraph
        """
        if not vertices:
            return set()
        
        # Use greedy approach: start with highest degree vertex
        degrees = {v: len(self.graph.adjacency_list[v] & vertices) for v in vertices}
        current_vertex = max(degrees, key=degrees.get)
        
        clique = {current_vertex}
        candidates = self.graph.adjacency_list[current_vertex] & vertices
        
        # Greedy extension
        while candidates:
            # Choose vertex with maximum degree in current candidate set
            degrees_in_candidates = {v: len(self.graph.adjacency_list[v] & candidates) 
                                   for v in candidates}
            next_vertex = max(degrees_in_candidates, key=degrees_in_candidates.get)
            
            clique.add(next_vertex)
            candidates &= self.graph.adjacency_list[next_vertex]
        
        return clique
    
    def randomized_approximation(self, iterations: int = 100) -> Tuple[List[Set], int]:
        """
        Randomized approximation algorithm
        Runs multiple random trials and returns best result
        """
        best_partition = None
        best_size = float('inf')
        
        for _ in range(iterations):
            partition = self._randomized_single_trial()
            if len(partition) < best_size:
                best_size = len(partition)
                best_partition = partition
        
        return best_partition, best_size
    
    def _randomized_single_trial(self) -> List[Set]:
        """Single trial of randomized algorithm"""
        import random
        
        remaining_vertices = list(self.graph.vertices)
        random.shuffle(remaining_vertices)  # Randomize order
        remaining_set = set(remaining_vertices)
        partition = []
        
        while remaining_set:
            # Random starting vertex from remaining
            start_vertex = random.choice(list(remaining_set))
            clique = self._build_clique_randomly(start_vertex, remaining_set)
            partition.append(clique)
            remaining_set -= clique
        
        return partition
    
    def _build_clique_randomly(self, start_vertex: str, available_vertices: Set) -> Set:
        """Build clique randomly starting from given vertex"""
        import random
        
        clique = {start_vertex}
        candidates = list(self.graph.adjacency_list[start_vertex] & available_vertices)
        
        while candidates:
            # Randomly choose next vertex with some bias toward higher degree
            weights = [len(self.graph.adjacency_list[v] & set(candidates)) + 1 
                      for v in candidates]
            next_vertex = random.choices(candidates, weights=weights)[0]
            
            clique.add(next_vertex)
            candidates = [v for v in candidates 
                         if v in self.graph.adjacency_list[next_vertex]]
        
        return clique

# Compare approximation algorithms
print("\nApproximation Algorithms Comparison:")
approx_solver = ApproximationAlgorithms(social_graph)

# Sequential greedy
seq_partition, seq_size = approx_solver.sequential_greedy_approximation()
print(f"Sequential greedy: {seq_size} cliques")

# Randomized approach
rand_partition, rand_size = approx_solver.randomized_approximation(iterations=50)
print(f"Randomized (50 trials): {rand_size} cliques")

print(f"\nAlgorithm Performance Summary:")
print(f"Greedy:           {greedy_size} cliques")
print(f"Tseng's:          {tseng_size} cliques")
print(f"Sequential Greedy: {seq_size} cliques")
print(f"Randomized:       {rand_size} cliques")

class SocialNetworkAnalysis:
    """
    Application of clique partition to social network analysis
    """
    
    def __init__(self):
        self.network = Graph()
        self.user_metadata = {}
    
    def add_user(self, user_id: str, metadata: Dict):
        """Add user with metadata"""
        self.network.add_vertex(user_id)
        self.user_metadata[user_id] = metadata
    
    def add_friendship(self, user1: str, user2: str):
        """Add friendship between users"""
        self.network.add_edge(user1, user2)
    
    def detect_communities(self) -> Dict:
        """
        Detect tight communities using clique partition
        """
        # Use Tseng's algorithm for community detection
        tseng_solver = TsengAlgorithm(self.network)
        communities, num_communities = tseng_solver.tseng_clique_partition()
        
        # Analyze communities
        community_analysis = {}
        for i, community in enumerate(communities):
            analysis = {
                'members': list(community),
                'size': len(community),
                'density': self._compute_community_density(community),
                'common_interests': self._find_common_interests(community)
            }
            community_analysis[f'Community_{i+1}'] = analysis
        
        return community_analysis
    
    def _compute_community_density(self, community: Set) -> float:
        """Compute density of connections within community"""
        if len(community) < 2:
            return 1.0
        
        possible_edges = len(community) * (len(community) - 1) // 2
        actual_edges = 0
        
        community_list = list(community)
        for i in range(len(community_list)):
            for j in range(i + 1, len(community_list)):
                u, v = community_list[i], community_list[j]
                if (min(u, v), max(u, v)) in self.network.edges:
                    actual_edges += 1
        
        return actual_edges / possible_edges if possible_edges > 0 else 0
    
    def _find_common_interests(self, community: Set) -> List[str]:
        """Find common interests among community members"""
        if not community:
            return []
        
        # Find intersection of interests
        common_interests = None
        for user in community:
            user_interests = set(self.user_metadata.get(user, {}).get('interests', []))
            if common_interests is None:
                common_interests = user_interests
            else:
                common_interests &= user_interests
        
        return list(common_interests) if common_interests else []

# Create a more complex social network
print("\nSocial Network Community Detection:")
social_analyzer = SocialNetworkAnalysis()

# Add users with interests
users_data = [
    ("Alice", {"interests": ["sports", "music", "travel"]}),
    ("Bob", {"interests": ["sports", "gaming", "music"]}),
    ("Carol", {"interests": ["sports", "travel", "food"]}),
    ("David", {"interests": ["tech", "gaming", "programming"]}),
    ("Eve", {"interests": ["tech", "programming", "AI"]}),
    ("Frank", {"interests": ["tech", "AI", "research"]}),
    ("Grace", {"interests": ["art", "music", "photography"]}),
    ("Henry", {"interests": ["art", "photography", "design"]}),
    ("Ivy", {"interests": ["music", "photography", "travel"]})
]

for user_id, metadata in users_data:
    social_analyzer.add_user(user_id, metadata)

# Add friendships
friendships = [
    ("Alice", "Bob"), ("Alice", "Carol"), ("Bob", "Carol"),  # Sports group
    ("David", "Eve"), ("David", "Frank"), ("Eve", "Frank"),  # Tech group
    ("Grace", "Henry"), ("Grace", "Ivy"), ("Henry", "Ivy"),  # Art group
    ("Carol", "David"), ("Bob", "Grace"), ("Ivy", "Alice")   # Bridge connections
]

for u, v in friendships:
    social_analyzer.add_friendship(u, v)

# Detect communities
communities = social_analyzer.detect_communities()
for community_name, analysis in communities.items():
    print(f"\n{community_name}:")
    print(f"  Members: {analysis['members']}")
    print(f"  Size: {analysis['size']}")
    print(f"  Density: {analysis['density']:.2f}")
    print(f"  Common interests: {analysis['common_interests']}")

import numpy as np
from typing import Tuple

class ImageSegmentationCliquePartition:
    """
    Image segmentation using clique partition on pixel similarity graph
    """
    
    def __init__(self, image_array: np.ndarray, similarity_threshold: float = 0.8):
        self.image = image_array
        self.height, self.width = image_array.shape[:2]
        self.similarity_threshold = similarity_threshold
        self.pixel_graph = self._build_pixel_graph()
    
    def _build_pixel_graph(self) -> Graph:
        """
        Build graph where pixels are vertices and edges represent similarity
        """
        graph = Graph()
        
        # Add all pixels as vertices
        for i in range(self.height):
            for j in range(self.width):
                pixel_id = f"({i},{j})"
                graph.add_vertex(pixel_id)
        
        # Add edges based on pixel similarity
        for i in range(self.height):
            for j in range(self.width):
                current_pixel = f"({i},{j})"
                
                # Check 8-connected neighbors
                for di in [-1, 0, 1]:
                    for dj in [-1, 0, 1]:
                        if di == 0 and dj == 0:
                            continue
                        
                        ni, nj = i + di, j + dj
                        if 0 <= ni < self.height and 0 <= nj < self.width:
                            neighbor_pixel = f"({ni},{nj})"
                            
                            # Calculate similarity
                            if self._pixel_similarity(i, j, ni, nj) > self.similarity_threshold:
                                graph.add_edge(current_pixel, neighbor_pixel)
        
        return graph
    
    def _pixel_similarity(self, i1: int, j1: int, i2: int, j2: int) -> float:
        """
        Calculate similarity between two pixels
        """
        if len(self.image.shape) == 2:  # Grayscale
            val1, val2 = self.image[i1, j1], self.image[i2, j2]
            return 1.0 - abs(val1 - val2) / 255.0
        else:  # Color
            val1, val2 = self.image[i1, j1], self.image[i2, j2]
            diff = np.linalg.norm(val1 - val2)
            max_diff = np.sqrt(3 * 255**2)  # Maximum possible difference
            return 1.0 - diff / max_diff
    
    def segment_image(self) -> Tuple[List[Set], np.ndarray]:
        """
        Segment image using clique partition
        """
        # Use greedy clique partition for efficiency
        solver = CliquePartitionSolver(self.pixel_graph)
        segments, num_segments = solver.greedy_clique_partition()
        
        # Create segmentation mask
        segment_mask = np.zeros((self.height, self.width), dtype=int)
        
        for segment_id, segment in enumerate(segments):
            for pixel_id in segment:
                # Parse pixel coordinates
                coords = pixel_id.strip('()').split(',')
                i, j = int(coords[0]), int(coords[1])
                segment_mask[i, j] = segment_id
        
        return segments, segment_mask
    
    def analyze_segments(self, segments: List[Set]) -> Dict:
        """
        Analyze properties of image segments
        """
        analysis = {}
        
        for i, segment in enumerate(segments):
            # Calculate segment properties
            pixels = []
            for pixel_id in segment:
                coords = pixel_id.strip('()').split(',')
                pi, pj = int(coords[0]), int(coords[1])
                pixels.append((pi, pj))
            
            # Calculate average color/intensity
            if len(self.image.shape) == 2:  # Grayscale
                avg_intensity = np.mean([self.image[pi, pj] for pi, pj in pixels])
                properties = {'avg_intensity': avg_intensity}
            else:  # Color
                avg_color = np.mean([self.image[pi, pj] for pi, pj in pixels], axis=0)
                properties = {'avg_color': avg_color.tolist()}
            
            properties.update({
                'size': len(segment),
                'bounding_box': self._get_bounding_box(pixels)
            })
            
            analysis[f'Segment_{i}'] = properties
        
        return analysis
    
    def _get_bounding_box(self, pixels: List[Tuple[int, int]]) -> Dict:
        """Calculate bounding box of pixel set"""
        if not pixels:
            return {}
        
        min_i = min(p[0] for p in pixels)
        max_i = max(p[0] for p in pixels)
        min_j = min(p[1] for p in pixels)
        max_j = max(p[1] for p in pixels)
        
        return {
            'top_left': (min_i, min_j),
            'bottom_right': (max_i, max_j),
            'width': max_j - min_j + 1,
            'height': max_i - min_i + 1
        }

# Demonstrate with synthetic image
print("\nImage Segmentation Application:")

# Create simple synthetic image for demonstration
synthetic_image = np.zeros((6, 6), dtype=np.uint8)
synthetic_image[0:2, 0:2] = 100  # Top-left region
synthetic_image[0:2, 4:6] = 200  # Top-right region
synthetic_image[4:6, 0:2] = 150  # Bottom-left region
synthetic_image[4:6, 4:6] = 250  # Bottom-right region

print("Synthetic image (6x6):")
print(synthetic_image)

# Apply clique partition segmentation
segmenter = ImageSegmentationCliquePartition(synthetic_image, similarity_threshold=0.9)
segments, segment_mask = segmenter.segment_image()

print(f"\nFound {len(segments)} segments")
print("Segment mask:")
print(segment_mask)

# Analyze segments
segment_analysis = segmenter.analyze_segments(segments)
for segment_name, properties in segment_analysis.items():
    print(f"\n{segment_name}:")
    for prop, value in properties.items():
        print(f"  {prop}: {value}")

class DataClusteringCliquePartition:
    """
    Data clustering using clique partition on similarity graph
    """
    
    def __init__(self, data_points: List[List[float]], similarity_threshold: float = 0.7):
        self.data_points = data_points
        self.similarity_threshold = similarity_threshold
        self.similarity_graph = self._build_similarity_graph()
    
    def _build_similarity_graph(self) -> Graph:
        """
        Build similarity graph from data points
        """
        graph = Graph()
        n = len(self.data_points)
        
        # Add vertices for each data point
        for i in range(n):
            graph.add_vertex(f"point_{i}")
        
        # Add edges based on similarity
        for i in range(n):
            for j in range(i + 1, n):
                similarity = self._compute_similarity(i, j)
                if similarity > self.similarity_threshold:
                    graph.add_edge(f"point_{i}", f"point_{j}")
        
        return graph
    
    def _compute_similarity(self, i: int, j: int) -> float:
        """
        Compute similarity between two data points using cosine similarity
        """
        point1 = np.array(self.data_points[i])
        point2 = np.array(self.data_points[j])
        
        # Cosine similarity
        dot_product = np.dot(point1, point2)
        norm1 = np.linalg.norm(point1)
        norm2 = np.linalg.norm(point2)
        
        if norm1 == 0 or norm2 == 0:
            return 0
        
        return dot_product / (norm1 * norm2)
    
    def cluster_data(self) -> Tuple[List[List[int]], Dict]:
        """
        Cluster data using clique partition
        """
        # Apply clique partition
        solver = CliquePartitionSolver(self.similarity_graph)
        clique_partition, num_clusters = solver.greedy_clique_partition()
        
        # Convert to data point indices
        clusters = []
        for clique in clique_partition:
            cluster_indices = [int(vertex.split('_')[1]) for vertex in clique]
            clusters.append(cluster_indices)
        
        # Analyze clusters
        cluster_analysis = self._analyze_clusters(clusters)
        
        return clusters, cluster_analysis
    
    def _analyze_clusters(self, clusters: List[List[int]]) -> Dict:
        """
        Analyze properties of discovered clusters
        """
        analysis = {}
        
        for i, cluster in enumerate(clusters):
            cluster_points = [self.data_points[idx] for idx in cluster]
            cluster_array = np.array(cluster_points)
            
            properties = {
                'size': len(cluster),
                'centroid': np.mean(cluster_array, axis=0).tolist(),
                'variance': np.var(cluster_array, axis=0).tolist(),
                'intra_cluster_similarity': self._compute_intra_cluster_similarity(cluster)
            }
            
            analysis[f'Cluster_{i}'] = properties
        
        return analysis
    
    def _compute_intra_cluster_similarity(self, cluster: List[int]) -> float:
        """
        Compute average similarity within cluster
        """
        if len(cluster) < 2:
            return 1.0
        
        similarities = []
        for i in range(len(cluster)):
            for j in range(i + 1, len(cluster)):
                sim = self._compute_similarity(cluster[i], cluster[j])
                similarities.append(sim)
        
        return np.mean(similarities)

# Demonstrate data clustering
print("\nData Clustering Application:")

# Generate synthetic data clusters
np.random.seed(42)
cluster1 = np.random.multivariate_normal([1, 1], [[0.1, 0], [0, 0.1]], 4)
cluster2 = np.random.multivariate_normal([3, 3], [[0.1, 0], [0, 0.1]], 3)
cluster3 = np.random.multivariate_normal([1, 3], [[0.1, 0], [0, 0.1]], 3)

synthetic_data = np.vstack([cluster1, cluster2, cluster3]).tolist()

print(f"Synthetic data points ({len(synthetic_data)} points):")
for i, point in enumerate(synthetic_data):
    print(f"  Point {i}: {[round(x, 2) for x in point]}")

# Apply clique partition clustering
clustering = DataClusteringCliquePartition(synthetic_data, similarity_threshold=0.8)
clusters, cluster_analysis = clustering.cluster_data()

print(f"\nDiscovered {len(clusters)} clusters:")
for i, cluster in enumerate(clusters):
    print(f"Cluster {i}: points {cluster}")

print(f"\nCluster Analysis:")
for cluster_name, properties in cluster_analysis.items():
    print(f"\n{cluster_name}:")
    for prop, value in properties.items():
        if isinstance(value, list):
            print(f"  {prop}: {[round(x, 3) for x in value]}")
        else:
            print(f"  {prop}: {round(value, 3) if isinstance(value, float) else value}")

class ParameterizedComplexityAnalysis:
    """
    Analysis of clique partition from parameterized complexity perspective
    """
    
    @staticmethod
    def analyze_by_clique_width(graph: Graph, max_clique_size: int) -> Dict:
        """
        Analyze complexity when parameterized by maximum clique size
        """
        analyzer = CliqueAnalyzer(graph)
        clique_number = analyzer.clique_number()
        
        analysis = {
            'clique_number': clique_number,
            'parameter_value': max_clique_size,
            'is_fpt': clique_number <= max_clique_size,
            'complexity_note': f"FPT when clique size ≤ {max_clique_size}"
        }
        
        return analysis
    
    @staticmethod
    def analyze_by_treewidth(graph: Graph, treewidth: int) -> Dict:
        """
        Analyze complexity when parameterized by treewidth
        """
        # Simplified analysis - real treewidth computation is complex
        n = len(graph.vertices)
        
        analysis = {
            'graph_size': n,
            'treewidth_parameter': treewidth,
            'is_polynomial': treewidth < np.log(n),
            'complexity_note': f"Polynomial when treewidth = O(log n)"
        }
        
        return analysis

# Parameterized analysis
print("\nParameterized Complexity Analysis:")
param_analysis = ParameterizedComplexityAnalysis()

clique_analysis = param_analysis.analyze_by_clique_width(social_graph, max_clique_size=3)
print("Analysis by clique size:")
for key, value in clique_analysis.items():
    print(f"  {key}: {value}")

treewidth_analysis = param_analysis.analyze_by_treewidth(social_graph, treewidth=2)
print("\nAnalysis by treewidth:")
for key, value in treewidth_analysis.items():
    print(f"  {key}: {value}")

class OnlineCliquePartition:
    """
    Online algorithm for clique partition where vertices arrive sequentially
    """
    
    def __init__(self):
        self.current_partition = []
        self.graph = Graph()
        self.vertices_processed = 0
    
    def process_vertex(self, new_vertex: str, neighbors: Set[str]):
        """
        Process a new vertex with its connections to previously seen vertices
        """
        self.vertices_processed += 1
        
        # Add vertex and edges to graph
        self.graph.add_vertex(new_vertex)
        for neighbor in neighbors:
            if neighbor in self.graph.vertices:
                self.graph.add_edge(new_vertex, neighbor)
        
        # Find best clique to add this vertex to
        best_clique_idx = self._find_best_clique_for_vertex(new_vertex)
        
        if best_clique_idx is not None:
            # Add to existing clique
            self.current_partition[best_clique_idx].add(new_vertex)
        else:
            # Create new clique
            self.current_partition.append({new_vertex})
        
        return len(self.current_partition)
    
    def _find_best_clique_for_vertex(self, vertex: str) -> int:
        """
        Find best existing clique to add the vertex to
        """
        for i, clique in enumerate(self.current_partition):
            # Check if vertex is connected to all vertices in clique
            if all(neighbor in self.graph.adjacency_list[vertex] for neighbor in clique):
                return i
        
        return None  # No suitable clique found
    
    def get_current_partition(self) -> List[Set]:
        """Get current partition"""
        return self.current_partition.copy()
    
    def competitive_ratio_analysis(self, offline_optimal: int) -> float:
        """
        Analyze competitive ratio compared to offline optimal
        """
        online_size = len(self.current_partition)
        return online_size / offline_optimal if offline_optimal > 0 else float('inf')

# Demonstrate online algorithm
print("\nOnline Clique Partition:")
online_solver = OnlineCliquePartition()

# Simulate online arrival of vertices
online_sequence = [
    ("Alice", set()),
    ("Bob", {"Alice"}),
    ("Carol", {"Alice", "Bob"}),
    ("David", set()),
    ("Eve", {"David"}),
    ("Frank", {"David", "Eve"}),
    ("Grace", set())
]

for vertex, neighbors in online_sequence:
    num_cliques = online_solver.process_vertex(vertex, neighbors)
    print(f"Added {vertex} (neighbors: {neighbors}): {num_cliques} cliques")

final_online_partition = online_solver.get_current_partition()
print(f"\nFinal online partition: {final_online_partition}")

# Compare with offline optimal
offline_graph = online_solver.graph
offline_solver = CliquePartitionSolver(offline_graph)
offline_partition, offline_size = offline_solver.greedy_clique_partition()

print(f"Offline partition: {offline_partition}")
print(f"Competitive ratio: {len(final_online_partition) / offline_size:.2f}")

class MLEnhancedCliquePartition:
    """
    Machine learning enhanced clique partition algorithm
    """
    
    def __init__(self, graph: Graph):
        self.graph = graph
        self.vertex_features = self._extract_vertex_features()
    
    def _extract_vertex_features(self) -> Dict[str, List[float]]:
        """
        Extract features for each vertex for ML prediction
        """
        features = {}
        
        for vertex in self.graph.vertices:
            # Graph-based features
            degree = len(self.graph.adjacency_list[vertex])
            clustering_coeff = self._local_clustering_coefficient(vertex)
            
            # Structural features
            num_triangles = self._count_triangles(vertex)
            
            features[vertex] = [degree, clustering_coeff, num_triangles]
        
        return features
    
    def _local_clustering_coefficient(self, vertex: str) -> float:
        """
        Compute local clustering coefficient
        """
        neighbors = self.graph.adjacency_list[vertex]
        if len(neighbors) < 2:
            return 0.0
        
        # Count edges between neighbors
        edges_between_neighbors = 0
        neighbors_list = list(neighbors)
        
        for i in range(len(neighbors_list)):
            for j in range(i + 1, len(neighbors_list)):
                u, v = neighbors_list[i], neighbors_list[j]
                if (min(u, v), max(u, v)) in self.graph.edges:
                    edges_between_neighbors += 1
        
        possible_edges = len(neighbors) * (len(neighbors) - 1) // 2
        return edges_between_neighbors / possible_edges
    
    def _count_triangles(self, vertex: str) -> int:
        """
        Count number of triangles containing the vertex
        """
        neighbors = self.graph.adjacency_list[vertex]
        triangles = 0
        
        neighbors_list = list(neighbors)
        for i in range(len(neighbors_list)):
            for j in range(i + 1, len(neighbors_list)):
                u, v = neighbors_list[i], neighbors_list[j]
                if (min(u, v), max(u, v)) in self.graph.edges:
                    triangles += 1
        
        return triangles
    
    def ml_guided_partition(self) -> Tuple[List[Set], int]:
        """
        Use ML to guide clique partition decisions
        """
        # Simplified ML approach: use features to predict vertex ordering
        vertex_scores = {}
        
        for vertex, features in self.vertex_features.items():
            # Simple scoring function (in practice, would use trained model)
            score = features[0] * 0.4 + features[1] * 0.4 + features[2] * 0.2
            vertex_scores[vertex] = score
        
        # Order vertices by predicted importance
        ordered_vertices = sorted(vertex_scores.keys(), 
                                key=lambda v: vertex_scores[v], reverse=True)
        
        # Build partition using this ordering
        partition = []
        remaining_vertices = set(ordered_vertices)
        
        while remaining_vertices:
            # Start with highest-scored remaining vertex
            start_vertex = next(v for v in ordered_vertices if v in remaining_vertices)
            
            # Build clique greedily, prioritizing high-scored vertices
            clique = self._build_ml_guided_clique(start_vertex, remaining_vertices, vertex_scores)
            partition.append(clique)
            remaining_vertices -= clique
        
        return partition, len(partition)
    
    def _build_ml_guided_clique(self, start_vertex: str, available: Set[str], 
                               scores: Dict[str, float]) -> Set:
        """
        Build clique guided by ML scores
        """
        clique = {start_vertex}
        candidates = self.graph.adjacency_list[start_vertex] & available
        
        while candidates:
            # Choose candidate with highest ML score
            best_candidate = max(candidates, key=lambda v: scores[v])
            
            clique.add(best_candidate)
            candidates &= self.graph.adjacency_list[best_candidate]
        
        return clique

# Demonstrate ML-enhanced approach
print("\nML-Enhanced Clique Partition:")
ml_solver = MLEnhancedCliquePartition(social_graph)

print("Vertex features:")
for vertex, features in ml_solver.vertex_features.items():
    print(f"  {vertex}: degree={features[0]}, clustering={features[1]:.3f}, triangles={features[2]}")

ml_partition, ml_size = ml_solver.ml_guided_partition()
print(f"\nML-guided partition ({ml_size} cliques): {ml_partition}")

# Compare all approaches
print(f"\nFinal Algorithm Comparison:")
print(f"Greedy:           {greedy_size} cliques")
print(f"Tseng's:          {tseng_size} cliques")
print(f"Sequential Greedy: {seq_size} cliques") 
print(f"Randomized:       {rand_size} cliques")
print(f"ML-guided:        {ml_size} cliques")

class CliquePartitionFramework:
    """
    Comprehensive framework for clique partition analysis and solving
    """
    
    def __init__(self, graph: Graph):
        self.graph = graph
        self.algorithms = {
            'greedy': CliquePartitionSolver(graph),
            'tseng': TsengAlgorithm(graph),
            'approximation': ApproximationAlgorithms(graph)
        }
        self.results = {}
    
    def run_all_algorithms(self) -> Dict:
        """
        Run all available algorithms and compare results
        """
        results = {}
        
        # Greedy approach
        greedy_partition, greedy_size = self.algorithms['greedy'].greedy_clique_partition()
        results['greedy'] = {
            'partition': greedy_partition,
            'size': greedy_size,
            'runtime': self._measure_runtime(lambda: self.algorithms['greedy'].greedy_clique_partition())
        }
        
        # Tseng's algorithm
        tseng_partition, tseng_size = self.algorithms['tseng'].tseng_clique_partition()
        results['tseng'] = {
            'partition': tseng_partition,
            'size': tseng_size,
            'runtime': self._measure_runtime(lambda: self.algorithms['tseng'].tseng_clique_partition())
        }
        
        # Approximation algorithms
        seq_partition, seq_size = self.algorithms['approximation'].sequential_greedy_approximation()
        results['sequential_greedy'] = {
            'partition': seq_partition,
            'size': seq_size,
            'runtime': self._measure_runtime(lambda: self.algorithms['approximation'].sequential_greedy_approximation())
        }
        
        rand_partition, rand_size = self.algorithms['approximation'].randomized_approximation(50)
        results['randomized'] = {
            'partition': rand_partition,
            'size': rand_size,
            'runtime': self._measure_runtime(lambda: self.algorithms['approximation'].randomized_approximation(50))
        }
        
        self.results = results
        return results
    
    def _measure_runtime(self, algorithm_func) -> float:
        """
        Measure algorithm runtime
        """
        import time
        start_time = time.time()
        algorithm_func()
        end_time = time.time()
        return end_time - start_time
    
    def generate_report(self) -> str:
        """
        Generate comprehensive analysis report
        """
        if not self.results:
            self.run_all_algorithms()
        
        report = ["Clique Partition Analysis Report", "=" * 40]
        
        # Graph statistics
        report.append(f"\nGraph Statistics:")
        report.append(f"  Vertices: {len(self.graph.vertices)}")
        report.append(f"  Edges: {len(self.graph.edges)}")
        report.append(f"  Density: {2 * len(self.graph.edges) / (len(self.graph.vertices) * (len(self.graph.vertices) - 1)):.3f}")
        
        # Algorithm comparison
        report.append(f"\nAlgorithm Comparison:")
        report.append(f"{'Algorithm':<20} {'Cliques':<10} {'Runtime (s)':<12}")
        report.append("-" * 45)
        
        for alg_name, result in self.results.items():
            report.append(f"{alg_name:<20} {result['size']:<10} {result['runtime']:<12.6f}")
        
        # Best result
        best_algorithm = min(self.results.keys(), key=lambda k: self.results[k]['size'])
        report.append(f"\nBest Result: {best_algorithm} with {self.results[best_algorithm]['size']} cliques")
        
        # Partition analysis
        best_partition = self.results[best_algorithm]['partition']
        report.append(f"\nBest Partition Analysis:")
        for i, clique in enumerate(best_partition):
            report.append(f"  Clique {i+1}: {clique} (size: {len(clique)})")
        
        return "\n".join(report)
    
    def visualize_partition(self, algorithm_name: str = None):
        """
        Create visualization of partition (simplified text-based)
        """
        if not self.results:
            self.run_all_algorithms()
        
        if algorithm_name is None:
            algorithm_name = min(self.results.keys(), key=lambda k: self.results[k]['size'])
        
        partition = self.results[algorithm_name]['partition']
        
        print(f"\nPartition Visualization ({algorithm_name}):")
        print("-" * 50)
        
        for i, clique in enumerate(partition):
            print(f"Clique {i+1}: {', '.join(sorted(clique))}")
            
            # Show internal connections
            clique_list = list(clique)
            connections = []
            for j in range(len(clique_list)):
                for k in range(j + 1, len(clique_list)):
                    u, v = clique_list[j], clique_list[k]
                    if (min(u, v), max(u, v)) in self.graph.edges:
                        connections.append(f"{u}-{v}")
            
            if connections:
                print(f"  Connections: {', '.join(connections)}")
            print()

# Create comprehensive analysis framework
print("\nComprehensive Clique Partition Framework:")
framework = CliquePartitionFramework(social_graph)

# Run analysis
all_results = framework.run_all_algorithms()

# Generate report
report = framework.generate_report()
print(report)

# Visualize best partition
framework.visualize_partition()

def create_research_toolkit():
    """
    Tools and libraries for clique partition research
    """
    
    toolkit = {
        "graph_libraries": {
            "NetworkX": "Python library for graph analysis and algorithms",
            "igraph": "R/Python library with efficient graph algorithms", 
            "SNAP": "Stanford Network Analysis Platform",
            "Boost Graph Library": "C++ graph algorithms library"
        },
        
        "optimization_solvers": {
            "Gurobi": "Commercial optimization solver for ILP formulations",
            "CPLEX": "IBM optimization solver",
            "OR-Tools": "Google's optimization tools",
            "SCIP": "Academic optimization solver"
        },
        
        "datasets": {
            "SNAP Datasets": "Stanford large network dataset collection",
            "KONECT": "Koblenz Network Collection",
            "Network Repository": "Interactive scientific network data repository",
            "Social Computing Data Repository": "ASU social network datasets"
        },
        
        "benchmarking": {
            "DIMACS Clique Benchmarks": "Standard benchmarks for clique problems",
            "BHOSLIB": "Benchmarks for optimization problems",
            "Graph Coloring Instances": "Complement graphs for clique partition"
        }
    }
    
    return toolkit

# Implementation tips for researchers
def implementation_best_practices():
    """
    Best practices for implementing clique partition algorithms
    """
    
    practices = {
        "data_structures": [
            "Use adjacency lists for sparse graphs",
            "Consider adjacency matrices for dense graphs", 
            "Implement efficient set operations for clique testing",
            "Use bit vectors for large graphs"
        ],
        
        "optimization_techniques": [
            "Implement early pruning in branch-and-bound",
            "Use upper and lower bounds effectively",
            "Consider parallel processing for independent subproblems",
            "Cache repeated computations"
        ],
        
        "testing_and_validation": [
            "Verify clique partition validity automatically",
            "Test on known benchmark instances",
            "Compare with optimal solutions on small graphs",
            "Measure runtime and memory usage systematically"
        ],
        
        "scalability": [
            "Profile code to identify bottlenecks",
            "Consider approximation algorithms for large instances",
            "Implement streaming algorithms for dynamic graphs",
            "Use graph preprocessing techniques"
        ]
    }
    
    return practices

print("\nResearch Tools and Resources:")
toolkit = create_research_toolkit()
for category, tools in toolkit.items():
    print(f"\n{category.replace('_', ' ').title()}:")
    for tool, description in tools.items():
        print(f"  • {tool}: {description}")

print("\nImplementation Best Practices:")
practices = implementation_best_practices()
for category, tips in practices.items():
    print(f"\n{category.replace('_', ' ').title()}:")
    for tip in tips:
        print(f"  • {tip}")