Annealing.py

import networkx as nx
import matplotlib.pyplot as plt
import random
from itertools import combinations
import numpy as np  
import math
from Optimal import OptimalNetworkMonitor

class AnnealingNetworkMonitor:
    def __init__(self, G, max_hops=5):
        if not isinstance(G, nx.DiGraph):
            raise ValueError("Graph must be a directed graph (DiGraph)")
        
        self.G = G
        self.max_hops = max_hops
        self.coverage_map = self._generate_coverage_map()
        
    def _generate_coverage_map(self):
        coverage_map = {}
        for node in self.G.nodes():
            coverage = self.get_neighbors_within_hops(node, self.max_hops)
            coverage_map[node] = coverage
        return coverage_map
    
    def get_neighbors_within_hops(self, node, max_hops):
        neighbors = set()
        current_level = {node}
        visited = {node}
        
        for _ in range(max_hops):
            next_level = set()
            for n in current_level:
                out_neighbors = set(self.G.successors(n)) - visited
                next_level.update(out_neighbors)
                visited.update(out_neighbors)
            
            neighbors.update(next_level)
            current_level = next_level
            if not current_level:
                break
                
        neighbors.add(node)
        return neighbors
    
    def solve_greedy(self):
        """classic greedy algorithm"""
        all_nodes = set(self.G.nodes())
        uncovered_nodes = all_nodes.copy()
        selected_monitors = set()
        
        while uncovered_nodes:
            # find the node that covers the most uncovered nodes
            best_node = None
            max_coverage = 0
            
            for node in all_nodes - selected_monitors:
                coverage = len(self.coverage_map[node] & uncovered_nodes)
                if coverage > max_coverage:
                    max_coverage = coverage
                    best_node = node
            
            if best_node is None or max_coverage == 0:
                # no more nodes to add
                selected_monitors.update(uncovered_nodes)
                break
            
            # add the best node to the set of monitors
            selected_monitors.add(best_node)
            # update the set of uncovered nodes
            uncovered_nodes -= self.coverage_map[best_node]
        
        return selected_monitors
    
    def print_solution_details(self, selected_monitors):
        """print the details of the selected monitors and coverage"""
        print("\nSelected monitor nodes:", selected_monitors)
        print("\nCoverage details:")
        covered_nodes = set()
        for monitor in selected_monitors:
            coverage = self.coverage_map[monitor]
            covered_nodes.update(coverage)
            print(f"Monitor {monitor} covers: {coverage}")
        print("\nTotal nodes covered:", len(covered_nodes))
        print("Total monitors used:", len(selected_monitors))
    
    def visualize(self, selected_monitors=None):
        plt.figure(figsize=(12, 8))
        pos = nx.spring_layout(self.G, k=1, iterations=50)
        
        nx.draw_networkx_edges(self.G, pos, edge_color='gray',
                             width=1, arrows=True,
                             arrowsize=20, arrowstyle='->')
        
        nx.draw_networkx_labels(self.G, pos)
        
        if selected_monitors:
            non_monitor_nodes = set(self.G.nodes()) - selected_monitors
            
            # draw non-monitor nodes (light blue)
            if non_monitor_nodes:
                nx.draw_networkx_nodes(self.G, pos,
                                     nodelist=list(non_monitor_nodes),
                                     node_color='lightblue',
                                     node_size=500)
            
            # draw monitor nodes (red)
            nx.draw_networkx_nodes(self.G, pos,
                                 nodelist=list(selected_monitors),
                                 node_color='red',
                                 node_size=700)
            
            # draw coverage range for each monitor
            for monitor in selected_monitors:
                covered_nodes = self.coverage_map[monitor]
                for covered in covered_nodes:
                    if covered != monitor:
                        plt.plot([pos[monitor][0], pos[covered][0]],
                               [pos[monitor][1], pos[covered][1]],
                               'r--', alpha=0.2)
        else:
            nx.draw_networkx_nodes(self.G, pos,
                                 node_color='lightblue',
                                 node_size=500)
        
        plt.title('Network Topology')
        plt.axis('off')
        plt.tight_layout()
        
        if selected_monitors:
            plt.plot([], [], 'r--', alpha=0.2, label='Coverage range')
            plt.plot([], [], 'ro', markersize=10, label='Monitor')
            plt.plot([], [], 'o', color='lightblue', markersize=10, label='Normal node')
            plt.legend()
        
        plt.show()

    def visualize_coverage_for_node(self, node):
        """visualize the coverage range for a specific node"""
        plt.figure(figsize=(12, 8))
        pos = nx.spring_layout(self.G, k=1, iterations=50)
        
        covered_nodes = self.coverage_map[node]
        non_covered = set(self.G.nodes()) - covered_nodes
        
        nx.draw_networkx_edges(self.G, pos, edge_color='gray',
                             width=1, arrows=True,
                             arrowsize=20, arrowstyle='->')
        
        if non_covered:
            nx.draw_networkx_nodes(self.G, pos,
                                 nodelist=list(non_covered),
                                 node_color='lightgray',
                                 node_size=500)
        
        covered_without_source = covered_nodes - {node}
        if covered_without_source:
            nx.draw_networkx_nodes(self.G, pos,
                                 nodelist=list(covered_without_source),
                                 node_color='lightblue',
                                 node_size=500)
        
        nx.draw_networkx_nodes(self.G, pos,
                             nodelist=[node],
                             node_color='red',
                             node_size=700)
        
        for covered in covered_nodes:
            if covered != node:
                plt.plot([pos[node][0], pos[covered][0]],
                        [pos[node][1], pos[covered][1]],
                        'r--', alpha=0.2)
        
        nx.draw_networkx_labels(self.G, pos)
        
        plt.title(f'Coverage range for node {node} (within {self.max_hops} hops)')
        plt.axis('off')
        plt.tight_layout()
        
        plt.plot([], [], 'r--', alpha=0.2, label='Coverage range')
        plt.plot([], [], 'ro', markersize=10, label='Source node')
        plt.plot([], [], 'o', color='lightblue', markersize=10, label='Covered node')
        plt.plot([], [], 'o', color='lightgray', markersize=10, label='Non-covered node')
        plt.legend()
        
        plt.show()
    
    def solve_greedy_with_exchange(self):
        """greedy algorithm with exchange"""
        # find the initial greedy solution
        monitors = self.solve_greedy()
        improved = True
        
        while improved:
            improved = False
            # try to exchange each monitor with another node
            for monitor in monitors.copy():
                for node in set(self.G.nodes()) - monitors:
                    # create a new solution with the exchange
                    temp_monitors = monitors - {monitor} | {node}
                    
                    # check if the new solution is valid and better
                    if self.is_valid_solution(temp_monitors) and len(temp_monitors) < len(monitors):
                        monitors = temp_monitors
                        improved = True
                        break
                if improved:
                    break
                    
        return monitors

    def solve_genetic(self, population_size=50, generations=100):
        """genetic algorithm"""
        def create_random_solution():
            """create a random solution"""
            solution = set()
            nodes = list(self.G.nodes())
            while not self.is_valid_solution(solution):
                solution.add(random.choice(nodes))
            return solution

        def crossover(sol1, sol2):
            """crossover operation"""
            # combine the two solutions
            combined = list(sol1 | sol2)
            new_size = random.randint(len(sol1), len(sol1) + len(sol2))
            new_sol = set(random.sample(combined, min(new_size, len(combined))))
            
            # ensure the solution is valid
            nodes = list(self.G.nodes())
            while not self.is_valid_solution(new_sol):
                new_sol.add(random.choice(nodes))
            return new_sol

        def mutate(solution):
            """mutation operation"""
            nodes = list(self.G.nodes())
            if random.random() < 0.1:  # mutation rate
                if random.random() < 0.5 and len(solution) > 1:
                    # remove a random node
                    solution.remove(random.choice(list(solution)))
                else:
                    # add a random non-monitor node
                    solution.add(random.choice(nodes))
                
                # ensure the solution is valid
                while not self.is_valid_solution(solution):
                    solution.add(random.choice(nodes))
            return solution

        # initialize the population
        population = [create_random_solution() for _ in range(population_size)]
        best_solution = min(population, key=len)
        
        # run the genetic algorithm
        for _ in range(generations):
            # select the best solutions
            population.sort(key=len)
            population = population[:population_size//2]
            
            # create new solutions
            new_population = population.copy()
            while len(new_population) < population_size:
                parent1, parent2 = random.sample(population, 2)
                child = crossover(parent1, parent2)
                child = mutate(child)
                new_population.append(child)
            
            population = new_population
            
            # update the best solution
            current_best = min(population, key=len)
            if len(current_best) < len(best_solution):
                best_solution = current_best
                
        return best_solution

    def solve_simulated_annealing(self, initial_temp=100, cooling_rate=0.95, iterations=1000):
        """simulated annealing algorithm"""
        def random_neighbor(solution):
            """generate a random neighbor solution"""
            new_solution = solution.copy()
            if random.random() < 0.5 and len(new_solution) > 1:
                # remove a random node
                new_solution.remove(random.choice(list(new_solution)))
            else:
                # add a random non-monitor node
                candidates = set(self.G.nodes()) - new_solution
                if candidates:
                    new_solution.add(random.choice(list(candidates)))
            return new_solution

        # start with a greedy solution
        current_solution = self.solve_greedy()
        best_solution = current_solution
        temperature = initial_temp
        
        while temperature > 1:
            for _ in range(iterations):
                new_solution = random_neighbor(current_solution)
                
                # check if the new solution is valid and better
                if self.is_valid_solution(new_solution):
                    delta = len(new_solution) - len(current_solution)
                    if delta < 0 or random.random() < math.exp(-delta / temperature):
                        current_solution = new_solution
                        if len(new_solution) < len(best_solution):
                            best_solution = new_solution
            
            temperature *= cooling_rate
            
        return best_solution

    def solve_hybrid(self):
        """compare different solutions and return the best one"""
        solutions = []
        
        greedy_sol = self.solve_greedy()
        solutions.append(greedy_sol)
        
        exchange_sol = self.solve_greedy_with_exchange()
        solutions.append(exchange_sol)
        
        genetic_sol = self.solve_genetic(population_size=30, generations=50)
        solutions.append(genetic_sol)
        
        sa_sol = self.solve_simulated_annealing()
        solutions.append(sa_sol)
        
        return min(solutions, key=len)

    def is_valid_solution(self, monitors):
        """check if the solution is valid(i.e., all nodes are covered)"""
        if not monitors:
            return False
            
        covered = set()
        for monitor in monitors:
            covered.update(self.coverage_map[monitor])
        
        return covered == set(self.G.nodes())
    
if __name__ == "__main__":
    # only for testing
    def create_large_random_digraph(n_nodes=100, p=0.05, ensure_connectivity=True, seed=None):
        """
        create a large random directed graph
        """
        if seed is not None:
            random.seed(seed)
            np.random.seed(seed)
        
        G = nx.DiGraph()
        
        G.add_nodes_from(range(n_nodes))
        
        for i in range(n_nodes):
            for j in range(n_nodes):
                if i != j and random.random() < p:
                    G.add_edge(i, j)
        
        if ensure_connectivity:
            # ensure the graph is strongly connected
            while not nx.is_strongly_connected(G):
                # find strongly connected components
                components = list(nx.strongly_connected_components(G))
                if len(components) > 1:
                    # randomly select two components
                    comp1, comp2 = random.sample(components, 2)
                    # from the first component, randomly select a node
                    node1 = random.choice(list(comp1))
                    # from the second component, randomly select a node
                    node2 = random.choice(list(comp2))
                    # add an edge between the two nodes
                    G.add_edge(node1, node2)
                    G.add_edge(node2, node1)
        
        return G

    # create a large random graph for testing
    G = create_large_random_digraph(n_nodes=300,p=0.02)
    monitor = AnnealingNetworkMonitor(G, max_hops=2)

    # test the optimal solution
    optimal_monitor = OptimalNetworkMonitor(G, max_hops=2)
    optimal_solution = optimal_monitor.solve()
    print(f"Optimal solution size: {len(optimal_solution)}")


    print("Testing different solutions:")

    greedy_solution = monitor.solve_greedy()
    print(f"Greedy solution size: {len(greedy_solution)}")

    exchange_solution = monitor.solve_greedy_with_exchange()
    print(f"Greedy with exchange solution size: {len(exchange_solution)}")

    genetic_solution = monitor.solve_genetic()
    print(f"Genetic solution size: {len(genetic_solution)}")

    sa_solution = monitor.solve_simulated_annealing()
    print(f"Simulated annealing solution size: {len(sa_solution)}")

    hybrid_solution = monitor.solve_hybrid()
    print(f"Hybrid solution size: {len(hybrid_solution)}")

    best_solution = min([greedy_solution, exchange_solution, genetic_solution, 
                        sa_solution, hybrid_solution], key=len)
    print(f"\nBest solution size: {len(best_solution)}")

    monitor.print_solution_details(best_solution)
    monitor.visualize(best_solution)