ProjectFinal_Vu.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "83f3690c",
   "metadata": {
    "scrolled": false
   },
   "source": [
    "## Name: Roland Vu\n",
    "\n",
    "## Title: Graph Analysis for Maximum Chromatic Vectors\n",
    "\n",
    "### Background\n",
    "\n",
    "In this project, I have been exploring graph coloring and the chromatic polynomial as part of my undergraduate mathematics research. I analyzed a given dataset of chromatic polynomial of all connected graphs up to order 9, provided by my research advisor, and studied their respective chromatic vectors. I also investigated various graph properties to gain insights into the characteristics of graphs that yield the largest chromatic vectors.\n",
    "\n",
    "### Python Packages and Methods\n",
    "\n",
    "For this research project, I used the following Python packages:\n",
    "\n",
    "- Pandas: for data manipulation and analysis.\n",
    "- NetworkX: for graph theory and graph operations.\n",
    "- NumPy: for data manipulation and matrix operations.\n",
    "- SciPy: for statistical computations.\n",
    "- Matplotlib: for graph visualization.\n",
    "\n",
    "### Code Outline\n",
    "\n",
    "The code for my research project will accomplish the following tasks:\n",
    "\n",
    "1. Load and preprocess the dataset of connected graphs up to order 9 using Pandas.\n",
    "2. Sort the dataset by the chromatic vector and group it by vertices and edges using Pandas.\n",
    "3. Utilize NetworkX in conjunction with Pandas to calculate and add the following graph properties to the dataset:\n",
    "   - Number of spanning tree\n",
    "   - Number of biconnected components\n",
    "   - Number of 3-cycles\n",
    "   - Number of 4-cycles\n",
    "   - Number of 5-cycles\n",
    "   - Number of 6-cycles\n",
    "   - Number of spanning trees\n",
    "   - Degree sequence\n",
    "   - Degree variance\n",
    "   - Degree deviation\n",
    "4. Utilize Pandas to analyze the dataset and identify the graphs that yield the largest chromatic vectors in their respective groups.\n",
    "5. Statistical analysis using Pandas and SciPy to calculate the percentile rank of maximum chromatic vector graph properties versus other non-max graphs within their group.\n",
    "6. Visualize graphs and results using NetworkX in conjunction with Matplotlib for data visualization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c1f57d75",
   "metadata": {
    "ExecuteTime": {
     "start_time": "2023-04-14T00:54:23.084217Z",
     "end_time": "2023-04-14T00:54:25.235535Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import pandas, networkx, and matplotlib and some helper functions\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import networkx as nx\n",
    "from scipy import stats\n",
    "import matplotlib.pyplot as plt\n",
    "from ast import literal_eval as make_tuple"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1e79df6d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read original dataset csv into DataFrame\n",
    "df = pd.read_csv('dataset/vector9.csv')\n",
    "\n",
    "# Remove first couple rows of graph data that is below 6 vertices because they are too small to be useful\n",
    "df = df.drop(df.index[0:29])\n",
    "\n",
    "# Coalesce all chromatic coefficients into a tuple and drop unused columns\n",
    "df['Vector'] = list(zip(df.Coef1, df.Coef2, df.Coef3, df.Coef4, df.Coef5, df.Coef6, df.Coef7, df.Coef8, df.Coef9))\n",
    "df = df.drop(['Coef1', 'Coef2', 'Coef3', 'Coef4', 'Coef5', 'Coef6', 'Coef7', 'Coef8', 'Coef9'], axis=1)\n",
    "\n",
    "# Display dataframe\n",
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "682258aa",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Stable sort means preserving order if elements are equal\n",
    "# Sorting by tuple representation of the chromatic vector as defined in Python standard library\n",
    "df_sorted = df.sort_values(['Vector'], kind='stable')\n",
    "\n",
    "# After that, stable sort DataFrame\n",
    "df_sorted = df_sorted.sort_values(['Vertices', 'Edges'], kind='stable')\n",
    "\n",
    "# Display dataframe\n",
    "df_sorted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "690de8eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# This cell compute the number of biconnection, 3-cycle, 4-cycle, 5-cycle, 6-cycle, and spanning tree for all graphs\n",
    "# It will also compute the degree sequence, degree variation, and degree deviation for all graphs\n",
    "# This will take at least 2-3 hours to complete on a powerful machine, so save your result after the first time\n",
    "\n",
    "# Instantiate list to hold results\n",
    "spanning_tree_list = list()\n",
    "biconnected_list   = list()\n",
    "three_cycle_list   = list()\n",
    "four_cycle_list    = list()\n",
    "five_cycle_list    = list()\n",
    "six_cycle_list     = list()\n",
    "degree_list        = list()\n",
    "variance_list      = list()\n",
    "deviation_list     = list()\n",
    "\n",
    "# For each graphs, do:\n",
    "for graph6id in df_sorted['G6id']:\n",
    "    \n",
    "    # Convert graph6id to instance of NetworkX graph\n",
    "    G = nx.from_graph6_bytes(graph6id.encode(\"ascii\"))\n",
    "\n",
    "    # Get the Laplacian matrix of G as a numpy array\n",
    "    matrix = nx.laplacian_matrix(G).toarray()\n",
    "\n",
    "    # Delete a row and a column from matrix\n",
    "    matrix = np.delete(matrix, 0, axis=0)\n",
    "    matrix = np.delete(matrix, 0, axis=1)\n",
    "\n",
    "    # Append the determinant of submatrix, aka number of spanning trees, to list\n",
    "    spanning_tree_list.append(int(round(np.linalg.det(matrix))))\n",
    "\n",
    "    # Get number of biconnection and append to list\n",
    "    biconnected_list.append(len(list(nx.biconnected_components(G))))\n",
    "    \n",
    "    # Generate all simple cycles for graph G\n",
    "    cycle_list = list(nx.simple_cycles(G.to_directed()))\n",
    "    \n",
    "    # Trim all '2-cycle' and sort list\n",
    "    cycle_list = [sorted(x) for x in cycle_list if len(x) >= 3]\n",
    "    \n",
    "    # Append number of n-cycle to n_list\n",
    "    three_cycle_list.append(len(set(map(tuple, [x for x in cycle_list if len(x) == 3]))))\n",
    "    four_cycle_list.append(len(set(map(tuple, [x for x in cycle_list if len(x) == 4]))))\n",
    "    five_cycle_list.append(len(set(map(tuple, [x for x in cycle_list if len(x) == 5]))))\n",
    "    six_cycle_list.append(len(set(map(tuple, [x for x in cycle_list if len(x) == 6]))))\n",
    "\n",
    "    # Get degree iterator from graph and map into a tuple\n",
    "    degree = tuple(map(lambda x: x[1], G.degree))\n",
    "\n",
    "    # Append degree tuple to list\n",
    "    degree_list.append(degree)\n",
    "\n",
    "    # Compute the degree mean\n",
    "    mean = sum(degree) / len(degree)\n",
    "\n",
    "    # Compute the variance\n",
    "    variance = sum(map(lambda x: (x - mean) ** 2, degree)) / len(degree)\n",
    "\n",
    "    # Append variance rounded to 4 decimals\n",
    "    variance_list.append(round(variance, 4))\n",
    "\n",
    "    # Compute and append degree standard deviation rounded to 4 decimals\n",
    "    deviation_list.append(round(variance ** 0.5, 4))\n",
    "\n",
    "# Add columns to dataframe\n",
    "df_sorted['SpanningTree'] = spanning_tree_list\n",
    "df_sorted['Biconnection'] = biconnected_list\n",
    "df_sorted['3-cycle']      = three_cycle_list\n",
    "df_sorted['4-cycle']      = four_cycle_list\n",
    "df_sorted['5-cycle']      = five_cycle_list\n",
    "df_sorted['6-cycle']      = six_cycle_list\n",
    "df_sorted['Degree']       = degree_list\n",
    "df_sorted['Variance']     = variance_list\n",
    "df_sorted['Deviation']    = deviation_list\n",
    "\n",
    "# Display dataframe\n",
    "df_sorted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "96d803c8",
   "metadata": {
    "ExecuteTime": {
     "start_time": "2023-04-12T09:39:09.468033Z",
     "end_time": "2023-04-12T09:39:22.436956Z"
    }
   },
   "outputs": [],
   "source": [
    "# This function determines if two chromatic vectors are incomparable or not, it is used to find the maximum element in the partial ordered set\n",
    "# Returns False if two chromatic vector are comparable, True if incomparable\n",
    "def incomparable(v1, v2):\n",
    "    greater = [True if a >= b else False for a, b in zip(v1, v2)]\n",
    "    lesser  = [True if a <= b else False for a, b in zip(v1, v2)]\n",
    "    return not all(greater) != all(lesser)\n",
    "\n",
    "\n",
    "# Create new column for indicating maximum element within its group, default to False\n",
    "df_sorted = df_sorted.assign(Maximum=False)\n",
    "\n",
    "maximum_list = list()\n",
    "\n",
    "# Group by vertices and edges, and for each group dataframe:\n",
    "groups = df_sorted.groupby(['Vertices', 'Edges'])\n",
    "for name, group in groups:\n",
    "\n",
    "    # Get the maximum of current group, which is always the last element\n",
    "    maximum = group.iloc[-1]\n",
    "    # Apply the comparison function to all vectors to the maximum in the group, and extend result to end of list\n",
    "    maximum_list.extend(list(group['Vector'].transform(lambda x: incomparable(make_tuple(maximum['Vector']), make_tuple(x)))))\n",
    "\n",
    "# Set result to column\n",
    "df_sorted['Maximum'] = maximum_list\n",
    "\n",
    "# Display dataframe\n",
    "display(df_sorted)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Output (or overwrite) to new csv\n",
    "df_sorted.to_csv('dataset/sorted.csv')\n",
    "\n",
    "# Output (or overwrite) to new csv\n",
    "maximum_df = df_sorted[df_sorted['Maximum'] == True]\n",
    "maximum_df.to_csv('dataset/maximum.csv')\n",
    "\n",
    "# Group by vertices and edges, and for each group dataframe:\n",
    "groups = df_sorted.groupby(['Vertices', 'Edges'])\n",
    "\n",
    "for name, group in groups:\n",
    "\n",
    "    # Save the group into its own CSV file, for easier analytics\n",
    "    group.to_csv(f'dataset/group/{name[0]}_{name[1]}.csv')"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-04-12T10:02:22.286565Z",
     "end_time": "2023-04-12T10:02:26.503089Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "# This loads in the intermediate CSV with result saved halfway through so that no expensive computation needs to be recalculated\n",
    "df_sorted = pd.read_csv('dataset/sorted.csv', index_col=0)\n",
    "\n",
    "# Initialize new empty dataframe to hold stats data\n",
    "df_stat = pd.DataFrame()\n",
    "\n",
    "# Group by vertices and edges, and for each group dataframe:\n",
    "groups = df_sorted.groupby(['Vertices', 'Edges'])\n",
    "for name, group in groups:\n",
    "\n",
    "    # Skip all groups with less than 30 elements (central limit theorem), or if group is a tree\n",
    "    if len(group) < 30 or name[0] == name[1] + 1:\n",
    "        print(f\"Skipping group {name} because it has less than 30 graphs or it was a tree group\")\n",
    "        continue\n",
    "\n",
    "    # Split into non-max and max graphs, and drop columns that we can't perform percentile calculations on\n",
    "    non_maximum = group[group['Maximum'] == False].drop(columns=['G6id', 'Vertices', 'Edges', 'Vector', 'Degree', 'Maximum'])\n",
    "    maximum     = group[group['Maximum'] == True ].drop(columns=['G6id', 'Vertices', 'Edges', 'Vector', 'Degree', 'Maximum'])\n",
    "\n",
    "    # Calculate percentile of score with strict mode, meaning only values less than the value is counted\n",
    "    for col in non_maximum.columns:\n",
    "        maximum[col] = stats.percentileofscore(non_maximum[col], maximum[col], kind='strict')\n",
    "\n",
    "    # Insert group name for first column\n",
    "    maximum.insert(0, 'Group', [name] * len(maximum))\n",
    "\n",
    "    # Append result to stat Dataframe\n",
    "    df_stat = pd.concat([df_stat, maximum])\n",
    "\n",
    "# Output to new csv\n",
    "df_stat.to_csv('dataset/stat.csv')\n",
    "\n",
    "#Display dataframe\n",
    "display(df_stat)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-04-14T00:54:25.238508Z",
     "end_time": "2023-04-14T00:54:25.714368Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "97f38adf",
   "metadata": {
    "ExecuteTime": {
     "start_time": "2023-04-06T19:38:51.558413Z",
     "end_time": "2023-04-06T19:39:06.011426Z"
    }
   },
   "outputs": [],
   "source": [
    "# Graph visualization cell, don't run if you already have the images, also it takes about 30 seconds to run\n",
    "\n",
    "# Set graph image size\n",
    "plt.rcParams[\"figure.figsize\"] = (5, 5)\n",
    "\n",
    "# Create and save graph images of 3 different types of layout for each graph\n",
    "for index, graph6id in zip(maximum_df.index, maximum_df['G6id']):\n",
    "\n",
    "    # Create NetworkX graph instance from graph6id\n",
    "    G = nx.from_graph6_bytes(graph6id.encode(\"ascii\"))\n",
    "\n",
    "    # Skip all tree graphs and all complete graphs\n",
    "    if nx.is_tree(G) or G.size() == G.order() * (G.order() - 1) / 2:\n",
    "        continue\n",
    "\n",
    "    # Draw and save Kamada-Kawai layout\n",
    "    nx.draw_kamada_kawai(G)\n",
    "    plt.savefig(f\"images/kamada_kawai/kamada_kawai_{index}.png\")\n",
    "    plt.clf()\n",
    "\n",
    "    # Draw and save shell layout\n",
    "    nx.draw_shell(G)\n",
    "    plt.savefig(f\"images/shell_layout/shell_{index}.png\")\n",
    "    plt.clf()\n",
    "\n",
    "    # Draw and save spring layout\n",
    "    nx.draw_spring(G)\n",
    "    plt.savefig(f\"images/spring_layout/spring_{index}.png\")\n",
    "    plt.clf()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}