from graph.graph.Graph_AdjacencyList import GraphAdjacencyList
from priorityQueue.PQbinomialHeap import PQbinomialHeap
from priorityQueue.PQ_Dheap import PQ_DHeap
from priorityQueue.PQbinaryHeap import PQbinaryHeap
import random


def priorityVisit(graph):
    verticeMax = graph.getNodeMaxWeight()
    priorityQueue = PQbinomialHeap()
    priorityQueue.insert(verticeMax.getId(), verticeMax.getWeight())
    markedNodes = [verticeMax.getId()]
    list = []

    while not priorityQueue.isEmpty():
        idNode = priorityQueue.findMax()
        list.append(idNode)
    #   print("id: ", idNode)
    #   print("peso: ", graph.getNode(idNode).getWeight(), "\n\n")
        priorityQueue.deleteMax()
        adjacentNodes = graph.getAdj(idNode)
        for nodeIndex in adjacentNodes:
            if nodeIndex not in markedNodes:
                node = graph.getNode(nodeIndex)
                priorityQueue.insert(node.getId(), node.getWeight())
                markedNodes.append(nodeIndex)
    print(len(list))
    return list

def graphGenerator(numberOfNodes):
    graph = GraphAdjacencyList()

    for i in range(numberOfNodes):
        weight = random.randint(0, 100)
        graph.addNode(i, weight)

    nodes = graph.getNodes().copy()

    n = numberOfNodes
    startNode = random.randint(0, n - 1)
    startNode = nodes.pop(startNode).getId()
    n -= 1
    for i in range(n):
        node = random.randint(0, n - 1 - i)
        node = nodes.pop(node).getId()
        graph.insertEdge(startNode, node)
        startNode = node

    k = random.randint(1, int(numberOfNodes / 2) + 1)

    for i in range(k):
        n = numberOfNodes
        nodes = graph.getNodes().copy()

        node1 = nodes.pop(random.randint(0, n - 1)).getId()
        while(len(graph.getAdj(node1)) == numberOfNodes - 1):
            nodes.append(node1)
            node1 = nodes.pop(random.randint(0, n - 1)).getId()
        n -= 1

        node2 = nodes.pop(random.randint(0, n - 1)).getId()
        n -= 1
        while(graph.isAdj(node1, node2)):
            node2 = nodes.pop(random.randint(0, n - 1)).getId()
            n -= 1

        graph.insertEdge(node1, node2)
    #print("Numero Archi:", len(graph.getEdges()))
    graph.print()
    return graph


if __name__ == "__main__":

    graphGenerator(90000)