aab12

import numpy as np
import copy
import sys
import time
import stopit
import psutil
import os
from datetime import datetime

class StatusCautator:  #clasa cu informatii
    def __init__(self, nume, status, prieteni):
        self.nume = nume
        self.status = status
        self.prieteni = prieteni
        self.initiale = [l[0] for l in nume]

class NodParcurgere:
    def __init__(self, index, info, parinte):
        self.index = index  # e indicele din vect de noduri
        self.info = info
        self.parinte = parinte # parintele din arborele de parcurgere

    def obtineDrum(self): #obtine drumul pana la nodul curent
        l = [self.info]
        nod = self
        while nod.parinte is not None:
            l.insert(0, nod.parinte.info)
            nod = nod.parinte
        return l

    def afisDrum(self):  # returneaza si lungimea drumului  pana la nodul curent
        l = self.obtineDrum()
        print("->".join(l))
        return len(l)

    def contineInDrum(self, infoNodNou):
        nodDrum = self
        while nodDrum is not None:
            if infoNodNou == nodDrum.info:
                return True
            nodDrum = nodDrum.parinte

        return False

    def __repr__(self):
        sir = ""
        sir += self.info + "("
        sir += "index = {}, ".format(self.index)
        sir += "drum="
        drum = self.obtineDrum()
        sir += "->".join(drum)
        sir += ")"
        return sir

class Node:
    def __init__(self, nume, status, prieteni, index):
        self.informatie = StatusCautator(nume, status, prieteni)
        self.index = index

    def to_string(self):
        my_str = str(self.index) + ") " + "".join(self.informatie.initiale) + ' - '
        my_str += " ".join(self.informatie.nume) + " (%s): " %self.informatie.status
        my_str += ", ".join([" ".join(fr) for fr in self.informatie.prieteni])
        return my_str

    # def __repr__(self):
    #     return self.to_string()

    def __str__(self):
        return self.to_string()

    def __eq__(self, other):
        return self.informatie.nume == other.informatie.nume


class Graph: #graful problemei din lab
    def __init__(self, noduri, matrice, vecini, v_e, start, scopuri):
        self.noduri = noduri
        self.matrice = matrice
        self.vecini = vecini
        self.v_e = v_e
        self.nrNoduri = len(matrice)
        self.start = start
        self.scopuri = scopuri

    def indiceNod(self, n):
        return self.noduri.index(n)

    def genereazaSuccesori(self, nodCurent):
        listaSuccesori = []
        for i in range(self.nrNoduri):
            if self.matrice[nodCurent.index][i] == 1 and not nodCurent.contineInDrum(self.noduri[i]):
                nodNou = NodParcurgere(i, self.noduri[i], nodCurent)
                listaSuccesori.append(nodNou)
        return listaSuccesori


    def __repr__(self):
        sir = ""
        for (k, v) in self.__dict__.items():
            sir+= "{} = {}\n".format(k, v)
        return sir


def obtineContacte(fisier):
    with open(fisier, 'r') as f:
        temp = f.readline().replace("'", '').split()
        initiale, numele = temp[0:2], temp[2:]
        print("\nIntialele cautate: ", initiale)
        linii = [l.replace("'", '').split() for l in f.readlines() ]
        contacte = list()
        noduri = list()
        for index, line in enumerate(linii):
            nume,status = line[:2], line[2]   #primele 2 elemente din vectorul format sunt mereu numele , al 3 lea mereu statusul
            prieteni = [(line[i], line[i+1]) for i in range(3, len(line), 2)] #toate elementele de la al 3 lea in fata sunt prietenii (mereu cu nume si prenume)
            contacte.append(Node(nume, status, prieteni, index))
            noduri.append(" ".join(nume))

    print("\nContinut folder:")
    print('\t' + "\n\t".join([str(fr) for fr in contacte]))

    return contacte, noduri, initiale


def initialeIdentice(nume, initiale):
    temp1 = [i[0] for i in nume.split()]
    return temp1 == initiale

def graf(contacte, noduri, initiale):
    matrice = np.zeros((len(contacte), len(contacte)), 'int8')
    vecini = dict()
    noade = list()
    margini = list()
    print("\nAscoiere nume cu numere: ")
    for contact in contacte:
        print('\t' + str(contact.index), end=": ") #pentru fiecare om din lista de prieteni: afisez id ul si fac append la contacte
        noade.append(contact.index)
        temp1List = list()
        for prieten in contact.informatie.prieteni:
            index = noduri.index(" ".join(prieten)) #asociez id urile prietenilor cu fiecare om in parte
            print(index, end= ' ')
            matrice[contact.index][index] = 1
            temp1List.append(index)
            margini.append((contact.index, index))
        vecini[contact.index] = temp1List
        print()

    v_e = dict()
    v_e["noade"] = noade
    v_e["margini"] = margini
    simetric = np.sum([(a == b) for (a, b) in zip(matrice, np.transpose (matrice))]) == len(contacte)**2

    print("\nMatrice: \n", matrice)
    print("\nVecini: \n", vecini)
    print("\nNoade\Margini: \n", v_e)
    print("\nGraf neorientat: \n") if simetric else print("\n Graf orientat")

    scopuri = [k for k in noduri if initialeIdentice(k, initiale)]
    print("\nScopuri", scopuri)

    return Graph(noduri, matrice, vecini, v_e, noduri[0], scopuri)



@stopit.threading_timeoutable(default="Depasit timp de timeout ")
######### Algoritm BF
def breadth_first(gr):
    nrSolutiiCautate = 4
    # in coada vom avea doar noduri de tip NodParcuregere (nodurile din arborele de parcurgere)
    c = [NodParcurgere(gr.noduri.index(gr.start), gr.start, None)]

    continua = True #Variabila pe care o setam false cand consideram ca s-au afisat suficiente solutii
    scopuri = gr.scopuri.copy()

    while len(c) > 0 and continua:
        nodCurent = c.pop(0)

        if nodCurent.info in scopuri:
            nodCurent.afisDrum()
            nrSolutiiCautate -= 1
            scopuri.remove(nodCurent.info)

            if nrSolutiiCautate == 0:
                continua = False

        listaSuccesori  = gr.genereazaSuccesori(nodCurent)
        c.extend(listaSuccesori)

continua1 = True

@stopit.threading_timeoutable(default="Depasit timp de timeout ")
####### Algoritm depth_first
def depth_first(gr):
    # vom simula o stiva prin relatia de parinte a nodului curent
    df(NodParcurgere(gr.noduri.index(gr.start), gr.start, None), gr)

nrSolutiiCautate = 4


def df(nodCurent, gr):
    global continua1, nrSolutiiCautate
    if not continua1:
        return

    if nodCurent.info in gr.scopuri:
        print("Solutie: ", end="")
        nodCurent.afisDrum()
        nrSolutiiCautate -= 1
        if nrSolutiiCautate == 0:
            continua1 = False

    listaSuccesori = gr.genereazaSuccesori(nodCurent)
    for sc in listaSuccesori:
        df(sc, gr)

# @stopit.threading_timeoutable(default="Depasit timp de timeout ")
# ###### Algoritmul Depth First Iretartiv
# def depth_first_iterative_deepening(gr, adancimeMaxima):
#     # vom simula o stiva prin relatia de parinte a nodului curent
#     for i in range(1, adancimeMaxima):
#         dfi(i, NodParcurgere(gr.noduri.index(gr.start), gr.start, None), gr)
#
# # e exact ca functia df din laborator doar ca impunem si o lungime maxima a drumului
# nrSolutii = 5
# continua2 = True
#
#
# def dfi(adMaxCurenta, nodCurent, gr):
#     global nrSolutii, continua2
#     # descrestem adMaxCurenta pana la 0
#     if adMaxCurenta <= 0 or not continua2:  # ar trebui adMaxCurenta sa nu ajunga niciodata < 0
#         return
#     adMaxCurenta -= 1
#
#     if nodCurent.info in gr.scopuri:
#         print("Solutie: ", end=" ")
#         nodCurent.afisDrum()
#         input()
#         nrSolutii -= 1
#         if nrSolutii == 0:
#             continua2 = False
#     listaSuccesori = gr.genereazaSuccesori(nodCurent)
#     for sc in listaSuccesori:
#         dfi(adMaxCurenta, sc, gr)

def test(file1):
    contacte, noduri, initiale = obtineContacte(file1)
    my_graph = graf(contacte, noduri, initiale)

    print("\nBF:")
    start_time = datetime.now()
    breadth_first(my_graph)
    end_time = datetime.now()
    print('\nDurata BF: {}'.format(end_time - start_time))
    memorieOcupata = psutil.Process(os.getpid())
    print("Memorie ocupata de BF: {}".format(memorieOcupata.memory_info()[0]) + " bytes")


    print("\nDF: ")
    depth_first(my_graph)

    print("\nDFI: ")
    # depth_first_iterative_deepening(my_graph, 5)


test("file1.txt")