algorithm_engineering_project.py

# -*- coding: utf-8 -*-
"""Algorithm Engineering Project.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1SrIBvpGkFKG9gCF_G-xH13TqyTsOeSHR
"""

# -*- coding: utf-8 -*-
"""
Doubly Linked List Implementation (https://www.geeksforgeeks.org/doubly-linked-list/)
"""
import random

# A linked list node
class Node:

    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None
        self.id = data
        self.weight = 1

# Creating a node class
class Node:
  def __init__(self, data):
    self.data = data #adding an element to the node
    self.next = None # Initally this node will not be linked with any other node
    self.prev = None # It will not be linked in either direction


# Creating a doubly linked list class
class DoublyLinkedList:
  def __init__(self):
    self.head = None # Initally there are no elements in the list
    self.tail = None
    self.num_items = 0

  def exists(self, element):
      if type(element) == Node:
          element = element.data

      node = self.head
      while node is not None:
          if node.data == element:
              return True
          node = node.next
      return False
  def push_front(self, new_data): # Adding an element before the first element
    new_node = Node(new_data) # creating a new node with the desired value
    new_node.next = self.head # newly created node's next pointer will refer to the old head
    self.num_items += 1
    if self.head != None: # Checks whether list is empty or not
        self.head.prev = new_node # old head's previous pointer will refer to newly created node
        self.head = new_node # new node becomes the new head
        new_node.prev = None

    else: # If the list is empty, make new node both head and tail
      self.head = new_node
      self.tail = new_node
      new_node.prev = None # There's only one element so both pointers refer to null


  def append(self, new_data): # Adding an element after the last element
      if type(new_data) == Node:
          new_data = new_data.data
      self.num_items += 1
      # print("Appending", new_data, "now there are", self.num_items, "items.", end=" | ")
      new_node = Node(new_data)
      new_node.prev = self.tail

      if self.tail == None: # checks whether the list is empty, if so make both head and tail as new node
        # print("Self tail is NONE")
        self.head = new_node
        self.tail = new_node
        new_node.next = None # the first element's previous pointer has to refer to null

      else: # If list is not empty, change pointers accordingly
        self.tail.next = new_node
        new_node.next = None
        self.tail = new_node # Make new node the new tail

  def peek_front(self): # returns first element
    if self.head == None: # checks whether list is empty or not
      print("List is empty")
    else:
      return self.head.data


  def peek_back(self): # returns last element
    if self.tail == None: # checks whether list is empty or not
      print("List is empty")
    else:
      return self.tail.data


  def pop_front(self): # removes and returns the first element

    if self.head == None:
      return

    else:
      self.num_items -= 1

      temp = self.head
      if temp.next is not None:
          temp.next.prev = None # remove previous pointer referring to old head

      self.head = temp.next # make second element the new head
      temp.next = None # remove next pointer referring to new head

      if self.head is None:
          self.tail = None

      return temp.data


  def pop_back(self): # removes and returns the last element
    if self.tail == None:
      print("List is empty")

    else:
      self.num_items -= 1
      temp = self.tail
      temp.prev.next = None # removes next pointer referring to old tail
      self.tail = temp.prev # make second to last element the new tail
      temp.prev = None # remove previous pointer referring to new tail
      return temp.data

  def deleteNode(self, dele):
      # Base Case
      if self.head is None or dele is None:
          return

      # If node to be deleted is head node
      if self.head == dele:
          self.head = dele.next

      if self.tail == dele:
          self.tail = dele.prev

      # Change next only if node to be deleted is NOT
      # the last node
      if dele.next is not None:
          dele.next.prev = dele.prev

      # Change prev only if node to be deleted is NOT
      # the first node
      if dele.prev is not None:
          dele.prev.next = dele.next

      self.num_items -= 1

  def insert_after(self, temp_node, new_data): # Inserting a new node after a given node
    self.num_items += 1
    if temp_node == None:
      print("Given node is empty")

    if temp_node != None:
      new_node = Node(new_data)
      new_node.next = temp_node.next
      temp_node.next = new_node
      new_node.prev = temp_node
      if new_node.next != None:
        new_node.next.prev = new_node

      if temp_node == self.tail: # checks whether new node is being added to the last element
        self.tail = new_node # makes new node the new tail

  def printList(self, node=None):
        if node is None:
            node = self.head

        if self.num_items == 0:
            print("Empty")
            return
        while node:
            print(node.data,'-> ',end='')
            last = node
            node = node.next
        print()



  def insert_before(self, temp_node, new_data): # Inserting a new node before a given node
    self.num_items += 1
    if temp_node == None:
      print("Given node is empty")

    if temp_node != None:
      new_node.prev = temp_node.prev
      temp_node.prev = new_node
      new_node.next = temp_node
      if new_node.prev != None:
        new_node.prev.next = new_node

      if temp_node == self.head: # checks whether new node is being added before the first element
        self.head = new_node # makes new node the new head

  def getData(self):
      node = self.head
      data = Array()
      while node:
        data.insert(node.data)
        last = node
        node = node.next
      return data


import sys
max = sys.maxsize
"""Custom Array Implementation <br>
Used part of https://codezup.com/create-own-custom-array-implementation-python/

"""

from random import randrange

# and my own function definitions
class Array(object):
    def __init__(self, size=max, fill=False, defaultValue = None):
        self.size = size
        self.len = 0
        self.items = list()

        if fill is True:
          count = 0
          while count < size:
            self.items[count] = -1

        if defaultValue is not None:
            self.len = len(self.items)
            if(len(defaultValue) == size or len(defaultValue) < size):
                for j in range(len(defaultValue)):
                    if(defaultValue[j]):
                        self.items.append(defaultValue[j])
                for i in range(len(defaultValue), size):
                    self.items.append(None)
            else:
                print('Elements are more than the size specified')

    def grow(self, until, insertArray=False, insertDLL=False):
      while self.myLen()-1 < until:
        if insertArray:
          self.insert(Array())
        elif insertDLL:
          self.insert(DoublyLinkedList())
        else:
          self.insert(-1)
    def exists(self, element):
      for i in range(self.myLen()):
        if self.items[i] == element:
          return True

      return False

    def myLen(self):
        return self.len

    def insert(self, element):
        # if self.myLen() < self.size:
        idx = self.myLen() - 1
        self.insertAfterIndex(idx, element)
        return

    def insertFirst(self, element):
        if (self.myLen() < self.size):
            for i in range(self.myLen(), 0, -1):
                self.items[i] = self.items[i - 1]
            self.items[0] = element
            self.len += 1
        else:
            print('Element index out of range')

    def insertAtIndex(self, index, element):
        if (self.myLen() < self.size):
            for i in range(self.myLen(), index, -1):
                self.items[i] = self.items[i - 1]
            self.items[index] = element
            self.len += 1
        else:
            print('Element index out of range')

    def insertAfterIndex(self, index, element):
        if index == self.myLen()-1:
            self.items.append(element)
            self.len += 1

        elif (self.myLen() < self.size):
            for i in range(self.myLen(), index + 1, -1):
                self.items[i] = self.items[i - 1]
            self.items[index + 1] = element
            self.len += 1
        else:
            print(self.myLen(), self.size)
            print('Element index out of range')

    def insertBeforeIndex(self, index, element):
        if (self.myLen() < self.size):
            for i in range(self.myLen(), index - 1, -1):
                self.items[i] = self.items[i - 1]
            self.items[index - 1] = element
            self.len += 1
        else:
            print('Element index out of range')

    def delete(self, element):
        if element in self.items:
            Index = self.items.index(element)
            self.items[Index] = None
            self -= 1
        else:
            print('This element is not in the Array!')

    def remove(self, element):
      self.items = [i for i in self.items if i != element]
      self.len = len(self.items)

    def search(self, element):
        if element in self.items:
            position = 0
            for i in range(self.myLen()):
                if(self.items[i] == element):
                    break
                else:
                    position += 1

            print('Element {} found at position {}'.format(element, position))
        else:
            print('This element is not in the Array!')

    # allow indexing
    def __getitem__(self, key):
        return self.items[key]

    def __setitem__(self, key, value):
        self.items[key] = value

    def set(self, index, ele):
      self.items[index] = ele
      return

    def at(self, index):
      return self.items[index]

    def extend(self, new_array):
      for item in new_array.items:
        self.insert(item)


import time
import matplotlib.pyplot as plt

def get_graph_name(graph_type):
    name = ''
    if graph_type == 0:
        name = 'cycle'
    elif graph_type ==1:
        name = 'complete'
    elif graph_type == 2:
        name = 'uniform'
    elif graph_type ==3:
        name = 'skew_low'
    elif graph_type == 4:
        name = 'skew_high'
    return name

def plot(x, y, graph_type, folder='', make_table=True, order='SLVO', multiplier="1"):
    name = get_graph_name(graph_type)
    plt.plot(x.items, y.items)
    plt.xlabel("Vertex Amount")
    if folder == 'terminal':
        plt.title(name)
        plt.ylabel("Terminal Clique Size")
    elif folder == 'degree':
        plt.title(name)
        plt.ylabel("Max Degree when Deleted")
    elif folder == 'colors_needed':
        plt.title("Number of colors needed")
        plt.ylabel("Colors Used")
    else:
        plt.title(name)
        plt.ylabel("Execution Time (s)")

    if folder == 'color':
        plt.title('Time Needed to Color '+ name + ' with ' + order + ' ordering')

    elif folder == 'order':
        txt = 'Time Needed to Order ' + name + ' Using '+order
        plt.title(txt)

    if folder != '':
        folder = folder+'/'


    plt.savefig('./plots/'+folder+name+'_'+order+'_'+str(multiplier))
    plt.clf()
    if make_table:
        table(x, y, graph_type, folder, order, multiplier)

def table(x, y, graph_type, folder='', order='SLVO', multiplier='1'):
    fig, ax =plt.subplots(1,1)
    # Have to make it a 2D list
    data = Array()
    for i in range(x.myLen()):
        data.insert([x[i], y[i]])
    column_labels=["Number of Vertices", "Time Taken(s)"]
    ax.axis('tight')
    ax.axis('off')
    ax.table(cellText=data.items,colLabels=column_labels,loc="center")

    name = get_graph_name(graph_type)
    plt.savefig('./tables/'+folder+name+'_'+order+'_'+str(multiplier))
    plt.clf()

def histograph(adj_list, graph_type):
    edge_count = Array()
    for i in range(adj_list.myLen()):
        edge_count.insert(adj_list[i].num_items)

    name = get_graph_name(graph_type)
    num_bins = 10
    n, bins, patches = plt.hist(edge_count.items, num_bins, facecolor='blue', alpha=0.5,
                                rwidth=0.3)
    plt.xlabel("Number of edges")
    plt.ylabel("Number of vertices")
    plt.savefig('./histogram/'+name)

# Program 1
# Create program accepts number vertices
# Create undirected complete graph with V vertices
# Output graph in format below
# All edges should have weight of 1
# Create chart showing run times for various values
# Create graph of running times vs. various values (USE LINEAR SCALE ON AXIS)
# Describe how the running times support your analysis of the asymptotic running times
def undirected_complete_graph(v):

  # Create adjacency list
  aj_list = Array(v)

  # Create list of numbers 1->V
  vertices = Array(v)

  P = Array(v)

  # Calculate number of edges for a complete graph with V vertices
  edges = int((v * (v-1)) / 2)

  E = Array(edges * 2)
  for i in range(v):
    aj_list.insert(DoublyLinkedList())
    vertices.insert(i)

  # Connect the vertices
  count = 1

  for i in range(v):
    P.insert(count)
    for j in range(v):
      if j != i:
        aj_list[i].append(vertices[j])
        E.insert(j)
        count += 1

  return P, E, aj_list

# Program 2
# Create a cycle with V vertices using an adjacency list
def cycle(v):
  if v == 1 or v == 2:
    return 'Error - Invalid Input'

  # Create adjacency list
  aj_list = Array(v)

  # Create list of numbers 1->V
  vertices = Array(v)

  P = Array(v)
  E = Array(v*2)
  for i in range(v):
    aj_list.insert(DoublyLinkedList())
    vertices.insert(i)

  # Connect the vertices in a cyclic manner
  count = 1
  for i in range(v):
    P.insert(count)
    if i == (v-1):
      aj_list[i].append(0) # Connect back to beginning
      E.insert(0)
      count += 1
    else:
      aj_list[i].append(vertices[i+1])
      E.insert(vertices[i+1])
      count += 1

  return P, E, aj_list


# Accepts the nmuber of conflicts between pairs of vertices for "random" graphs
def uniform_distribution(E, V):
  vertices = Array()
  adj_list = Array()
  for i in range(V):
      adj_list.insert(DoublyLinkedList())

  while vertices.myLen() < 2*E:
    # Uniformly select a new vertex
    new_pair = False
    while new_pair == False:
        v1 = random.randint(0, V-1)
        v2 = random.randint(0, V-1)

        if v1 == v2:
            continue
        elif adj_list[v1].exists(v2) or adj_list[v2].exists(v1):
            continue
        else:
            new_pair = True
            # print("Found new pair: ", v1, v2)
            vertices.insert(v1)
            vertices.insert(v2)
            adj_list[v1].append(v2)
            adj_list[v2].append(v1)

  return vertices, adj_list

# Lower numbered vertices are linearly more likely than higher numbered vertices
def skewed_distribution(E, V):
  # Create new list
  # Each lower number will have some X entries
  # if we have 5 vertices
  # 0,0,0,0,0 1,1,1,1 2,2,2 3,3 4

  # Creating the new array
  entries = V
  skewed_list = Array()
  for i in range(V):
    j = 0
    while j < entries:
      skewed_list.insert(i)
      j+=1

    entries -= 1

  # Select 2*E Indices and get the value at that index
  vertices = Array()

  adj_list = Array()
  for i in range(V):
      adj_list.insert(DoublyLinkedList())

  while vertices.myLen() < 2*E:
    # Uniformly select a new vertex
    new_pair = False
    while new_pair == False:
        v1 = skewed_list[random.randint(0,skewed_list.myLen()-1)]
        v2 = skewed_list[random.randint(0,skewed_list.myLen()-1)]
        if v1 == v2:
            continue
        elif adj_list[v1].exists(v2) or adj_list[v2].exists(v1):
            continue
        else:
            new_pair = True
            # print("Found new pair: ", v1, v2)
            vertices.insert(v1)
            vertices.insert(v2)

            adj_list[v1].append(v2)
            adj_list[v2].append(v1)

  return vertices, adj_list

# My custom distribution will be the opposite of the skewed distribution
# Where larger numbers have a higher chance of being chosen for conflict

def custom_distribution(E, V):
  # Create new list
  # Each higheer number will have some X entries
  # if we have 5 vertices
  # 0,1,1,2,2,2,3,3,3,3,4,4,4,4,4
  # Creating the new array
  entries = V
  skewed_list = Array()
  for i in reversed(range(V)):
    j = 0
    while j < entries:
      skewed_list.insert(i)
      j += 1

    entries -= 1

  # Select 2*E Indices and get the value at that index
  vertices = Array()
  adj_list = Array()
  for i in range(V):
      adj_list.insert(DoublyLinkedList())

  while vertices.myLen() < 2*E:
    # Uniformly select a new vertex
    new_pair = False
    while new_pair == False:
        v1 = skewed_list[random.randint(0,skewed_list.myLen()-1)]
        v2 = skewed_list[random.randint(0,skewed_list.myLen()-1)]
        if v1 == v2:
            continue
        elif adj_list[v1].exists(v2) or adj_list[v2].exists(v1):
            continue
        else:
            new_pair = True
            # print("Found new pair: ", v1, v2)
            vertices.insert(v1)
            vertices.insert(v2)

            adj_list[v1].append(v2)
            adj_list[v2].append(v1)

  return vertices, adj_list

def write_to_file(v, P,E, ftype):
  # Accepts the P and E arrays
  # Outputs to file
  fname = "./files/"+ftype+".txt"
  f = open(fname, "w")

  # Number of vertices
  f.write( str(v) )
  f.write('\n')
  # Starting location for vertices
  for i in range(v):
      f.write( str( P[i] + v + 1))
      f.write('\n')


  for i in range(E.myLen()):
      f.write( str(E[i]) )
      f.write(" ")
      f.write(str(1))
      f.write('\n')

  f.close()

# Create graph from vertices generated from distribution
def create_graph_from_adjacency_list(v, adj_list):
  # Create adjacency list
  P = Array()
  E = Array()

  # Create E and P
  count=1
  # don't go thru vertex, do the indices lol dummy
  for vertex in range(v):
    P.insert(count)
    connected_vertices = adj_list[vertex].getData()
    E.extend(connected_vertices)
    count += connected_vertices.myLen()

  return P, E, adj_list

def generate_graph(graph_type, v, e, write, histogram):
    # Create graph
    name = ''
    if graph_type == 0:
        P, E, adj_list = cycle(v)
        name = "cycle_"+str(v)
    elif graph_type ==1:
        P, E, adj_list = undirected_complete_graph(v)
        name = "complete_"+str(v)
    elif graph_type ==2:
        vertices, adj_list = uniform_distribution(e, v)
        name = "uniform_"+str(v)+"_"+str(e)
        P, E, adj_list = create_graph_from_adjacency_list(v, adj_list)
    elif graph_type ==3:
        vertices, adj_list = skewed_distribution(e,v)
        name = "skew_low_"+str(v)+"_"+str(e)
        P, E, adj_list = create_graph_from_adjacency_list(v, adj_list)
    elif graph_type ==4:
        vertices, adj_list = custom_distribution(e,v)
        name = "skew_high_"+str(v)+"_"+str(e)
        P, E, adj_list = create_graph_from_adjacency_list(v, adj_list)

    if write:
        write_to_file(v, P, E, name)
    if histogram:
        histograph(adj_list, graph_type)

    return name

###############################################################################
###############################################################################
###############################################################################

# Part 2

class Vertex():
  def __init__(self, id):
    # Field 1
    self.id = id
    # Field 2
    self.edge_list_ptr = id # Pointer to edge list will be the index NOTE
    # Field 3
    self.color = -1
    self.degree = 0
    # Field 4
    self.same_degree_ptr = -1 # Index
    self.order_deleted_list_ptr = -1

def create_graph_from_file_input(fname, cycle=False):
    line_number = 1
    num_vertices = 0

    # Create file reader
    f = open(fname, "r")
    num_vertices = int(f.readline())
    line_number += 1

    P = Array()
    E = Array()

    # Init adjacency list
    adj_list = Array()

    created_vertices = Array()

    for i in range(num_vertices):
      adj_list.insert(DoublyLinkedList()) # Edge list
      created_vertices.insert(Vertex(i)) # Creating vertex


    curr_vertex = 0
    # Read where the connections begin
    while curr_vertex < num_vertices:
      line = f.readline()
      P.insert(int(line[:-1]))
      line_number += 1
      curr_vertex += 1

    # print(P.items)
    curr_vertex = 0
    # Create list of DLL of vertices of same current degree
    degree_list = Array()

    # Read in edges for current vertex
    while True:
      skip = False
      # print("Line number", line_number)
      # print("Curr vertex", curr_vertex)
      curr_degree = created_vertices[curr_vertex].degree
      # print("CURRENT DEGREE IS", curr_degree)
      if curr_vertex == P.myLen()-1:
          skip = True

      if skip is False:
          # Check for empty
          # print(line_number)
          while line_number == P[curr_vertex +1]:

            created_vertices[curr_vertex].edge_list_ptr = curr_vertex # storing idx location in
            # Add this vertex to corresponding DLL of same degree
            curr_degree = created_vertices[curr_vertex].degree
            if degree_list.myLen()-1 < curr_degree:
              # Grow
              # print("(1) Grow to", curr_degree, "for vertex", curr_vertex)
              degree_list.grow(curr_degree, insertDLL=True)

            # print("Appending current vertex", curr_vertex, "in file input to degree ", curr_degree, created_vertices[curr_vertex].degree)
            degree_list[curr_degree].append(curr_vertex)
            curr_vertex += 1
            if curr_vertex == P.myLen()-1:
                # print("Curr vertex", curr_vertex)
                break

      # NOTE ON WHITESPACE WHAT IF NO EDGES
      line = f.readline() # string
      if line == '':
          curr_degree = created_vertices[curr_vertex].degree
          if degree_list.myLen()-1 < curr_degree:
            # Grow
            # print("Grow to ", curr_degree)
            degree_list.grow(curr_degree, insertDLL=True)

          degree_list[curr_degree].append(curr_vertex)
          if cycle == True:
              adj_list[adjacent_vertex].append(curr_vertex)
          # print("Current degree is", curr_degree, "adding", curr_vertex)
          break

      # Break up the line by space
      line_list = []
      buffer = ""
      for idx in range(len(line)):
          char = line[idx]
          if char == " ":
              line_list.append(buffer)
              buffer = ""
          elif idx == len(line)-1:
              buffer += char
              line_list.append(buffer)
          else:
              buffer += char

      adjacent_vertex = int(line_list[0])
      weight = int(line_list[1])
      # print("Adjacent vertex is", adjacent_vertex)
      # print("Current vertex is", curr_vertex)
      # print("Appending adjacent vertex file input")
      adj_list[curr_vertex].append(adjacent_vertex)
      if cycle == True:
          adj_list[adjacent_vertex].append(curr_vertex)
          created_vertices[adjacent_vertex].degree += 1

      created_vertices[curr_vertex].degree += 1
      line_number += 1

    return created_vertices, degree_list, adj_list

def smallest_last_vertex_ordering(vertices, degree_list, adj_list):
  # Vertices is a list of Vertex objects
  # Degree list is a list of DLL with integers
  # Essentially takes the create_graph_from_file_input output and performs
  # smallest last vertex ordering on it
  # print("Performing SLVO")
  # print("===============")
  # print("Checking degree list")

  removed_vertices = 0
  deleted_list = Array()
  deleted_degree_list = Array() # Consisting of the degrees when removed
  max_degree_when_deleted = -1
  # Iteratively delete a vertex of smallest degree
  while removed_vertices != vertices.myLen():
    checking_degree = 0
    # print('--------------------------------')
    # for id, vertex in enumerate(vertices.items):
        # print("vertex", id, "has degree", vertex.degree, end=' | ')
    while degree_list[checking_degree].head is None:
        checking_degree += 1
        # print("Checking degree", checking_degree)
        # print("Removed", removed_vertices, "vertices")
        # print("Degree list length:", degree_list.myLen())

        # print("Number of Vertices removed", removed_vertices)
        # print("num items in degree list of ", checking_degree, degree_list[checking_degree].num_items)
    # print("Degree", checking_degree)
    # print()
    # print("Using degree", checking_degree)
    # Remove head

    vertex_removed = degree_list[checking_degree].pop_front()

    # Update the position in degree_list
    vertex_removed_degree = vertices[vertex_removed].degree
    # print("REMOVING VERTEX", vertex_removed, "with degree", vertex_removed_degree)

    # Update the deleted degree list so I can find terminal clique later
    deleted_degree_list.insert(vertex_removed_degree)

    # Update the current degree
    if vertex_removed_degree > max_degree_when_deleted:
      max_degree_when_deleted = vertex_removed_degree

    # Update deleted list
    # print("Deleting ", vertex_removed.id, vertex_removed.data)
    # print("Type of vertex removed is ", type(vertex_removed))
    deleted_list.insert(vertex_removed)
    # Update vertex
    vertices[vertex_removed].degree = -1
    # Update number of removed vertices
    removed_vertices += 1

    # Update every connected vertex
    # print("ID", vertex_removed.data,"has edge list:")
    idx = vertices[vertex_removed].edge_list_ptr
    dll = adj_list[idx]
    # print("Edge list")
    connected_node = dll.head
    while connected_node is not None: # node is connected vertex
      connected_node_degree = vertices[connected_node.data].degree
      # print(node.data, "has degree", node_degree)
    #  Update this vertex's position in the degree list

      if connected_node_degree != -1:
          # print("Searching for vertex", node.data, "with degree", vertices[node.data].degree)
          # if degree_list[connected_node_degree].exists(connected_node.data) == False:
              # print("Vertex", connected_node.data, "does not exist in degree list of", connected_node_degree)
              # degree_list[connected_node_degree].printList()

          search_node = degree_list[connected_node_degree].head


          # Find which node is representing this vertex
          # print("Searching for", connected_node.data)
          while search_node.data != connected_node.data:
              search_node = search_node.next

          # if search_node is not None:
          # Delete it from current degree in dg list
          # print("Node degree is ", connected_node_degree)
          # print("Connected node is", connected_node.data, "search node is", search_node.data)
          degree_list[vertices[connected_node.data].degree].deleteNode(search_node)
          # print("Removed ", search_node.data)
          # Place it in new DLL
          # print("Moving ", search_node.data, " with degree ", connected_node_degree, "into", vertices[connected_node.data].degree-1)

          degree_list[vertices[connected_node.data].degree-1].append(connected_node)
          # degree_list[vertices[connected_node.data].degree-1].printList()
          # Decrease its degree
          vertices[connected_node.data].degree -= 1

      connected_node = connected_node.next
  # print("List of deleted vertices: ")
  # for node in deleted_list.items:
  #     print(node.data, end=', ')
  # print()
  # print(deleted_degree_list.items)
  return vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted

def smallest_original_degree_last_vertex_ordering(vertices, degree_list, adj_list):
  removed_vertices = 0
  deleted_list = Array()
  deleted_degree_list = Array() # Consisting of the degrees when removed
  max_degree_when_deleted = -1

  while removed_vertices != vertices.myLen():
    checking_degree = 0
    # print('--------------------------------')
    # for id, vertex in enumerate(vertices.items):
        # print("vertex", id, "has degree", vertex.degree, end=' | ')
    while degree_list[checking_degree].num_items == 0:
        checking_degree += 1

    vertex_removed = degree_list[checking_degree].pop_front()

    # Update the deleted degree list so I can find terminal clique later
    deleted_degree_list.insert(checking_degree)

    # Update the current degree
    if checking_degree > max_degree_when_deleted:
      max_degree_when_deleted = checking_degree

    # Update deleted list
    deleted_list.insert(vertex_removed)
    # Update vertex
    vertices[vertex_removed].degree = -1
    # Update number of removed vertices
    removed_vertices += 1

    # Update every connected vertex
    # print("ID", vertex_removed.data,"has edge list:")
    idx = vertices[vertex_removed].edge_list_ptr
    dll = adj_list[idx]
    # print("Edge list")
    node = dll.head
    while node is not None: # node is connected vertex
      node_degree = vertices[node.data].degree
      vertices[node.data].degree -= 1
    #  Update this vertex's position in the degree list
      node = node.next
  # print("Vertices removed in the following order:")
  # for v in deleted_list.items:
  #     print(v.data, end=', ')
  # print()
  return vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted

def largest_last_vertex_ordering(vertices, degree_list, adj_list):
  # Vertices is a list of Vertex objects
  # Degree list is a list of DLL with integers
  # Essentially takes the create_graph_from_file_input output and performs
  # smallest last vertex ordering on it
  # print("Performing SLVO")
  # print("===============")
  # print("Checking degree list")

  removed_vertices = 0
  deleted_list = Array()
  deleted_degree_list = Array() # Consisting of the degrees when removed
  max_degree_when_deleted = -1
  # Iteratively delete a vertex of smallest degree
  while removed_vertices != vertices.myLen():
    checking_degree = degree_list.myLen()-1
    # print('--------------------------------')
    # for id, vertex in enumerate(vertices.items):
        # print("vertex", id, "has degree", vertex.degree, end=' | ')
    while degree_list[checking_degree].head is None:
        checking_degree -= 1
        # print("Checking degree", checking_degree)
        # print("Removed", removed_vertices, "vertices")
        # print("Degree list length:", degree_list.myLen())

        # print("Number of Vertices removed", removed_vertices)
        # print("num items in degree list of ", checking_degree, degree_list[checking_degree].num_items)
    # print("Degree", checking_degree)
    # print()
    # print("Using degree", checking_degree)
    # Remove head

    vertex_removed = degree_list[checking_degree].pop_front()

    # Update the position in degree_list
    vertex_removed_degree = vertices[vertex_removed].degree
    # print("REMOVING VERTEX", vertex_removed, "with degree", vertex_removed_degree)

    # Update the deleted degree list so I can find terminal clique later
    deleted_degree_list.insert(vertex_removed_degree)

    # Update the current degree
    if vertex_removed_degree > max_degree_when_deleted:
      max_degree_when_deleted = vertex_removed_degree

    # Update deleted list
    # print("Deleting ", vertex_removed.id, vertex_removed.data)
    # print("Type of vertex removed is ", type(vertex_removed))
    deleted_list.insert(vertex_removed)
    # Update vertex
    vertices[vertex_removed].degree = -1
    # Update number of removed vertices
    removed_vertices += 1

    # Update every connected vertex
    # print("ID", vertex_removed.data,"has edge list:")
    idx = vertices[vertex_removed].edge_list_ptr
    dll = adj_list[idx]
    # print("Edge list")
    connected_node = dll.head
    while connected_node is not None: # node is connected vertex
      connected_node_degree = vertices[connected_node.data].degree
      # print(node.data, "has degree", node_degree)
    #  Update this vertex's position in the degree list

      if connected_node_degree != -1:
          # print("Searching for vertex", node.data, "with degree", vertices[node.data].degree)
          # if degree_list[connected_node_degree].exists(connected_node.data) == False:
              # print("Vertex", connected_node.data, "does not exist in degree list of", connected_node_degree)
              # degree_list[connected_node_degree].printList()

          search_node = degree_list[connected_node_degree].head


          # Find which node is representing this vertex
          # print("Searching for", connected_node.data)
          while search_node.data != connected_node.data:
              search_node = search_node.next

          # if search_node is not None:
          # Delete it from current degree in dg list
          # print("Node degree is ", connected_node_degree)
          # print("Connected node is", connected_node.data, "search node is", search_node.data)
          degree_list[vertices[connected_node.data].degree].deleteNode(search_node)
          # print("Removed ", search_node.data)
          # Place it in new DLL
          # print("Moving ", search_node.data, " with degree ", connected_node_degree, "into", vertices[connected_node.data].degree-1)

          degree_list[vertices[connected_node.data].degree-1].append(connected_node)
          # degree_list[vertices[connected_node.data].degree-1].printList()
          # Decrease its degree
          vertices[connected_node.data].degree -= 1

      connected_node = connected_node.next
  # print("List of deleted vertices: ")
  # for node in deleted_list.items:
  #     print(node.data, end=', ')
  # print()
  # print(deleted_degree_list.items)
  return vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted


def largest_original_degree_last_vertex_ordering(vertices, degree_list, adj_list):
  removed_vertices = 0
  deleted_list = Array()
  deleted_degree_list = Array() # Consisting of the degrees when removed
  max_degree_when_deleted = -1

  while removed_vertices != vertices.myLen():
    checking_degree = degree_list.myLen()-1
    # print('--------------------------------')
    # for id, vertex in enumerate(vertices.items):
        # print("vertex", id, "has degree", vertex.degree, end=' | ')
    while degree_list[checking_degree].num_items == 0:
        checking_degree += 1

    vertex_removed = degree_list[checking_degree].pop_front()

    # Update the deleted degree list so I can find terminal clique later
    deleted_degree_list.insert(checking_degree)

    # Update the current degree
    if checking_degree > max_degree_when_deleted:
      max_degree_when_deleted = checking_degree

    # Update deleted list
    deleted_list.insert(vertex_removed)
    # Update vertex
    vertices[vertex_removed].degree = -1
    # Update number of removed vertices
    removed_vertices += 1

    # Update every connected vertex
    # print("ID", vertex_removed.data,"has edge list:")
    idx = vertices[vertex_removed].edge_list_ptr
    dll = adj_list[idx]
    # print("Edge list")
    node = dll.head
    while node is not None: # node is connected vertex
      node_degree = vertices[node.data].degree
      vertices[node.data].degree -= 1
    #  Update this vertex's position in the degree list
      node = node.next
  # print("Vertices removed in the following order:")
  # for v in deleted_list.items:
  #     print(v.data, end=', ')
  # print()
  return vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted

def random_skewed_low_degree_vertex_ordering(vertices, degree_list, adj_list):
  # Get number of vertices
  num_vertices = vertices.myLen()

  # Create "skewed" list.  Lower ID will have more entries
  skewed_list = Array()
  entries = vertices.myLen()
  for i in range(num_vertices):
    j = 0
    while j < entries:
      skewed_list.insert(i)
      j+=1

    entries -= 1

  # Perform the removal of vertices until none left
  vertices_removed = 0
  max_degree = -1
  deleted_degree_list = Array()
  deleted_list = Array()
  while vertices_removed < num_vertices:
    # Random uniformly select from this list
    selected_id = skewed_list[random.randint(0, skewed_list.myLen()-1)]
    # Remove the selected ID occurences from the skewed list
    skewed_list.remove(selected_id)
    # Increase number of vertices removed
    vertices_removed += 1
    # Store degree when removed
    if vertices[selected_id].degree > max_degree:
      max_degree = vertices[selected_id].degree

    # Adjust the connected vertices' degrees, but don't move from current spot in degree list
    idx = vertices[selected_id].edge_list_ptr
    dll = adj_list[idx]

    # Append to deleted degree list
    deleted_degree_list.insert(vertices[selected_id].degree)
    # Append to deleted list
    deleted_list.insert(selected_id)
    # Set degree to removed
    vertices[selected_id].degree = -1

    # Check max degree
    if vertices[selected_id].degree > max_degree:
      max_degree = vertices[selected_id].degree

    node = dll.head
    while node:
      if vertices[node.data].degree >= 0:
        vertices[node.data].degree -= 1
      node = node.next

    vertices_removed += 1

  return vertices, degree_list, deleted_degree_list, deleted_list, max_degree

def random_skewed_high_degree_vertex_ordering(vertices, degree_list, adj_list):
  # Get number of vertices
  num_vertices = vertices.myLen()

  # Create "skewed" list.  Lower ID will have more entries
  skewed_list = Array()
  entries = vertices.myLen()
  for i in reversed(range(num_vertices)):
    j = 0
    while j < entries:
      skewed_list.insert(i)
      j+=1

    entries -= 1

  # Perform the removal of vertices until none left
  vertices_removed = 0
  max_degree = -1
  deleted_degree_list = Array()
  deleted_list = Array()
  while vertices_removed < num_vertices:
      # Random uniformly select from this list
    selected_id = skewed_list[random.randint(0, skewed_list.myLen()-1)]
    # Remove the selected ID occurences from the skewed list
    skewed_list.remove(selected_id)
    # Increase number of vertices removed
    vertices_removed += 1
    # Store degree when removed
    if vertices[selected_id].degree > max_degree:
      max_degree = vertices[selected_id].degree

    # Adjust the connected vertices' degrees, but don't move from current spot in degree list
    idx = vertices[selected_id].edge_list_ptr
    dll = adj_list[idx]

    # Append to deleted degree list
    deleted_degree_list.insert(vertices[selected_id].degree)
    # Append to deleted list
    deleted_list.insert(selected_id)
    # Set degree to removed
    vertices[selected_id].degree = -1

    # Check max degree
    if vertices[selected_id].degree > max_degree:
      max_degree = vertices[selected_id].degree

    node = dll.head
    while node:
      if vertices[node.data].degree >= 0:
        vertices[node.data].degree -= 1
      node = node.next

    vertices_removed += 1

  return vertices, degree_list, deleted_degree_list, deleted_list, max_degree


def scan_and_assign_colors(vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted, adj_list):
  # Go from end
  # print("============================")
  # for vertex in deleted_list:
  #     print(vertex.id, end=',')
  idx = deleted_degree_list.myLen() - 1

  # Find the terminal clique
  # Terminal clique begins where the degree value no longer increases when reversed
  # [ 0 1 2 1 3 2 1 0]
  # Reversed
  # [ 0 1 2 3 1 2 1 0]
  size_terminal_clique = 0
  clique_begins_idx = -1
  colors_needed = -1

  while idx > 0:
    if deleted_degree_list[idx] >= deleted_degree_list[idx - 1]:
      clique_begins_idx = idx
      break
    else:
      idx -=1
      size_terminal_clique += 1

  size_terminal_clique += 1
  # Color
  idx = deleted_degree_list.myLen() - 1
  # Degree when deleted + 1 is upper bound on the color
  # Check adjacent and use smallest that isn't in use

  while idx >= 0:
    id = deleted_list[idx] # ID of vertex
    max_color = deleted_degree_list[idx] + 1
    color_list = Array()
    for i in range(max_color+1):
      color_list.insert(i)
    # Compare to adjacent vertices
    dll = adj_list[id]
    node = dll.head
    connected_colors = Array()
    while node:
      connected_color = vertices[node.data].color
      if connected_colors.exists(connected_color) is False:
        connected_colors.insert(connected_color)

      node = node.next

    # Iterated through connected colors
    # Find minimum
    # Loop through the possible colors, and pick first one
    chosen_color = -1
    # print("Color list items: ", color_list.items)
    for color in color_list.items:
      if connected_colors.exists(color) is False:
        chosen_color = color
        if chosen_color > colors_needed-1:
            colors_needed = chosen_color+1
        break


    if chosen_color == -1:
      print("Can't color graph using this number of colors.")

    # print(id, "CHOSE COLOR ", chosen_color)
    vertices[id].color = chosen_color
    idx -= 1

  # print("Final coloring")
  colored_list = Array()
  for i in range(vertices.myLen()):
      v = vertices[i]
      # print(v.id, "has color", v.color)
      colored_list.insert(v.color)

  return vertices, max_degree_when_deleted, size_terminal_clique, colors_needed, colored_list

def part2(v, name):
    written_name = "./files/"+name+".txt"
    print("Creating graph from file created:", name)
    created_vertices, degree_list, adj_list = create_graph_from_file_input(written_name)

    P, E, a = create_graph_from_adjacency_list(v, adj_list)

    # Validate they are the same
    # write_to_file(v, P, E, name+"_recreated")
    print("0: SLVO")
    print("1: SODL")
    choice = int(input("Which ordering would you like to use? "))
    # Perform Ordering
    if choice == 0:
        vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted = smallest_last_vertex_ordering(created_vertices, degree_list, adj_list)
    elif choice ==1:
        vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted = smallest_original_degree_last_vertex_ordering(created_vertices, degree_list, adj_list)
    # Perform Coloring
    vertices, max_degree_when_deleted, size_terminal_clique, colors_needed, colored_list = scan_and_assign_colors(vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted, adj_list)

def part1():
    # What type of graph

    print("0: Cycle")
    print("1: Complete")
    print("2: Uniform random graph")
    print("3: Skewed low random graph")
    print("4: Skewed high random graph")

    graph_type = int(input("Input which graph you would like: "))

    creating_graphs = input("Creating plots (y/n): ")
    creating_hist = input("Creating histogram (y/n): ")
    v = -1
    name = ""
    if creating_graphs == "y":
        max_vert = int(input("Enter # vertices to go up to (increment 1000): "))
        times = Array()
        vertex_amount = Array()
        i = 1000
        e = i
        while i <= max_vert:
            start_time = time.time()
            _ = generate_graph(graph_type, i, e, False, False)
            times.insert(time.time() - start_time)
            vertex_amount.insert(i)
            i += 1000
            plot(vertex_amount, times, graph_type)
    else:
        v = int(input("Number of vertices: "))
        e = -1
        if graph_type > 1:
            e = int(input("Enter number of edges: "))
        if creating_hist == "y":
            name = generate_graph(graph_type, v, e, False, True)
        else:
            name = generate_graph(graph_type, v, e, write=True, histogram=False)
    return v, name

def scatter_plot(x, y, graph_type, order='SLVO', multiplier="1"):
    plt.scatter(x,y)
    plt.ylabel("Degree when Deleted")
    plt.xlabel("Order Colored")
    name = get_graph_name(graph_type)
    plt.title(name)
    if multiplier == 1:
        m = "one"
    if multiplier == 2:
        m = "two"
    plt.savefig('./plots/scatter/'+name+'_'+order+'_'+str(multiplier))
    plt.clf()

def part2plots():
    print("0: Cycle")
    print("1: Complete")
    print("2: Uniform random graph")
    print("3: Skewed low random graph")
    print("4: Skewed high random graph")

    graph_type = int(input("Input which graph you would like: "))

    name = ""
    max_vert = int(input("Enter # vertices to go up to (increment 1000): "))
    ordering_times = Array()
    coloring_times = Array()
    max_degrees = Array()
    terminal_sizes = Array()
    vertex_amount = Array()
    cn_list = Array()

    i = 1000
    multiplier = int(input("Multiplier for edges: "))
    e = multiplier * i
    print("0: SLVO")
    print("1: SODL")
    print("2: LLVO")
    print("3: LODL")
    print("4: RSLO")
    print("5: RSHO")
    choices = ["SLVO", "SODL", "LLVO", "LODL", "RSLO", "RSHO"]

    choice = int(input("Which ordering would you like to use? "))
    cycle = False
    if graph_type == 0:
        cycle = True

    selected_ordering = choices[choice]
    while i <= max_vert:
        print("Using", i, "vertices.")
        name = generate_graph(graph_type, i, e, True, False)

        vertex_amount.insert(i)
        # Read from file
        written_name = "./files/"+name+".txt"

        created_vertices, degree_list, adj_list = create_graph_from_file_input(written_name, cycle)
        P, E, adj_list = create_graph_from_adjacency_list(i, adj_list)


        # Time the ordering
        start_time = time.time()
        # Perform Ordering
        # Perform Ordering
        if choice == 0:
            vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted = smallest_last_vertex_ordering(created_vertices, degree_list, adj_list)
        elif choice ==1:
            vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted = smallest_original_degree_last_vertex_ordering(created_vertices, degree_list, adj_list)
        elif choice == 2:
            vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted = largest_last_vertex_ordering(created_vertices, degree_list, adj_list)
        elif choice == 3:
            vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted = largest_original_degree_last_vertex_ordering(created_vertices, degree_list, adj_list)
        elif choice == 4:
            vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted = random_skewed_low_degree_vertex_ordering(created_vertices, degree_list, adj_list)
        elif choice == 5:
            vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted = random_skewed_high_degree_vertex_ordering(created_vertices, degree_list, adj_list)


        ordering_times.insert(time.time() - start_time)
        # Perform Coloring
        start_time = time.time()

        vertices, max_degree_when_deleted, size_terminal_clique, colors_needed, colored_list = scan_and_assign_colors(vertices, degree_list, deleted_degree_list, deleted_list, max_degree_when_deleted, adj_list)
        coloring_times.insert(time.time() - start_time)

        max_degrees.insert(max_degree_when_deleted)
        terminal_sizes.insert(size_terminal_clique)

        cn_list.insert(colors_needed)

        # print("term size:", size_terminal_clique)

        if i == max_vert:
            # Scatter plot
            degrees = reversed(deleted_degree_list.items)
            scatter_plot(x=list(range(1,len(deleted_degree_list.items)+1)), y=deleted_degree_list.items, graph_type=graph_type, order=selected_ordering, multiplier=multiplier)

        i += 1000

    # Plots with lines
    plot(vertex_amount, ordering_times, graph_type, folder='order', order=selected_ordering, multiplier=multiplier)
    plot(vertex_amount, cn_list, graph_type, folder='colors_needed', order=selected_ordering, multiplier=multiplier)
    plot(vertex_amount, coloring_times, graph_type, folder='color', order=selected_ordering, multiplier=multiplier)
    plot(vertex_amount, terminal_sizes, graph_type, folder='terminal', make_table=False, order=selected_ordering, multiplier=multiplier) # Need to do this on variety of graphs
    plot(vertex_amount, max_degrees, graph_type, folder='degree', make_table=False, order=selected_ordering, multiplier=multiplier)

def main():
    print("1 - Part 1")
    print("2 - Part 2")
    print("3 - Testing plots for 2")
    choice = int(input("Enter your choice: "))
    if choice == 1:
        v, name = part1()
    if choice == 2:
        name = input("Enter file name: ")
        v = int(input("Enter number of vertices: "))
        part2(v, name)
    else:
        part2plots()



main()