<jupyter_start><jupyter_text>GA with random edge start population<jupyter_code>import sys; sys.path.append('..')
import math
from os import path
import random
import networkx as nx
from matplotlib import pyplot as plt
from graph import Graph
from graph.disjointsets import DisjointSets
from graph.reader import read_problem
from graph.steiner import prunning_mst
from graph.util import has_cycle, how_many_components
from base.binary.combiner import crossover_1point, crossover_2points, crossover_uniform
from base.chromosome import random_binary
from base.condition import BestKnownReached, BestSolutionKnowReached, Stagnation
from base.customevol import SteinerEvolution as Evolution
from base.customevol import SteinerPopulation as Population
from base.mutate import flip_onebit
from base.normalization import normalize
from base.pickers import random_picker
from base.selector import roullete
from base.tracker import DataTracker
from base.util import display, update_best, update_generation

from treetools import Eval, Converter
from pxsimpliest import SimpliestPX
from draw import hierarchy_pos<jupyter_output><empty_output><jupyter_text>---<jupyter_code># problema = path.join('..', 'datasets', 'ORLibrary', 'steinc1.txt')
problema = path.join('..', 'datasets', 'ORLibrary', 'steinb16.txt')

STPG = read_problem(problema)
STPG.nro_nodes
STPG.nro_edges
STPG.nro_terminals
print(STPG.terminals)
tamanho_populacao = 50
funcao_avaliacao = Eval(STPG)
terminals = set(STPG.terminals)

def is_terminal(vertice):
    return vertice in terminals
def prunning(treegraph):
    
    to_eliminate = set()
    
    for v in treegraph.vertices:
        degree = treegraph.degree(v)
        if (not is_terminal(v)) and (degree == 1):
            to_eliminate.add(v)
        elif (degree == 0) and (not is_terminal(v)) :
            treegraph.remove_node(v)
    
    checkbefore = set()
    
    while to_eliminate:
        while to_eliminate:
            v = to_eliminate.pop()
            for adj in treegraph.adjacent_to(v):
                checkbefore.add(adj)
            treegraph.remove_node(v)

        while checkbefore:
            u = checkbefore.pop()
            if (not is_terminal(u)) and (treegraph.degree(u) == 1):
                to_eliminate.add(u)
                
    return treegraph   
def random_treegraph_chromosome(STPG):
    
    graph = STPG.graph
    terminals = set(STPG.terminals)
    
    alledges = [(v, u, graph.weight(v,u)) for v, u in graph.gen_undirect_edges()]
    random.shuffle(alledges) # random component

    DS = DisjointSets()
    subgraph = Graph()
    total_cost = 0
    
    for v in graph.vertices:
        DS.make_set(v)

    while alledges :
        v, u, weight = alledges.pop()

        if DS.find(v) != DS.find(u):
            DS.union(v, u)
            total_cost += weight
            subgraph.add_edge(v, u, weight=weight)
            terminals.discard(v)
            terminals.discard(u)

    return prunning(subgraph)
gg = random_treegraph_chromosome(STPG)
funcao_avaliacao(gg)
gg = prunning(gg)
funcao_avaliacao(gg)
STPG.terminals - set(gg.vertices)
gg.edges<jupyter_output><empty_output><jupyter_text>---<jupyter_code>populacao = (Population(chromosomes=[ random_treegraph_chromosome(STPG) for _ in range(tamanho_populacao) ],
                        eval_function=funcao_avaliacao,
                        maximize=True)
                        .evaluate()
                        .callback(normalize)
                        .callback(update_best))
len(populacao)
populacao.documented_best.cost
evolution =  (Evolution()
                .evaluate()
                .callback(normalize)
                .callback(update_best)
                .select(selection_func=roullete)
                .crossover(combiner= SimpliestPX(STPG), parent_picker=random_picker)
                .callback(update_generation)
                .callback(display, every=100))
# %%time 

# resultado = populacao.evolve(evolution, n=500)
# resultado.runtime
# resultado.documented_best.cost
from itertools import product
def partitioning(individuo_a, individuo_b):
    
    subtree_a = individuo_a.chromosome
    subtree_b = individuo_b.chromosome

    partition = Graph()
    offspring = Graph()
    
    for v, w in subtree_a.gen_undirect_edges():
        weight = subtree_a.weight(v,w)

        if subtree_b.has_edge(v, w):
            offspring.add_edge(v, w, weight=weight)
        else:
            partition.add_edge(v, w, weight=weight)
            
    for v, w in subtree_b.gen_undirect_edges():
        weight = subtree_b.weight(v,w)

        if not subtree_a.has_edge(v, w):
            partition.add_edge(v, w, weight=weight)
            
    return partition, offspring 
individuos = [ x for x in populacao ]
for individuo in individuos:
    custo = individuo.cost
    print(custo, end='\t')
prod = product(individuos, repeat=2)

counter = 0
counter_cycle = 0 
not_cycle = 0

for a, b in prod:
    p, _ = partitioning(a, b)
    counter += 1
    if has_cycle(p):
        counter_cycle += 1
    else:
        not_cycle += 1
counter
counter_cycle
counter_cycle / counter<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09147528221097703, 'fraction_numerical': 0.004671078240560529, 'mean_word_length': 2.8961334344200154, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '120456', 'license': 'MIT', 'n_tokens_mistral': 1747, 'n_tokens_neox': 1642, 'n_words': 374, 'path': 'notebooks/GA_random_edge_population.ipynb', 'repo_name': 'rspozza/ppgi-stpg-gpx', 'size': '5138'}