examples/FlexRiLoG_demo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# FlexRiLoG - Rigid and Flexible Labelings of Graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic notions\n",
    "\n",
    "**Definition**\n",
    "\n",
    "Let $G=(V_G,E_G)$ be a graph with an edge labeling $\\lambda:E_G\\rightarrow \\mathbb{R}_+$.\n",
    "\n",
    "A realization $\\rho:V_G\\rightarrow\\mathbb{R}^2$ is called *compatible* with $\\lambda$ if\n",
    "$||\\rho(u)-\\rho(v)||=\\lambda(uv)$ for all $uv\\in E_G$.\n",
    "\n",
    "The labeling $\\lambda$ is called\n",
    "\n",
    "- *(proper) flexible* if the number of (injective) realizations of $G$ compatible with $\\lambda$ is infinite,\n",
    "- *rigid* if the number of realizations of $G$ compatible with $\\lambda$ is finite and positive,\n",
    "\n",
    "where the counting is up to direct Euclidean isometries.\n",
    "A graph is called *movable* iff it has a proper flexible labeling."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sys.path.insert(0, \"..\") #this is necessary if flexrilog is not installed, only downloaded\n",
    "from flexrilog import GraphGenerator\n",
    "from flexrilog import FlexRiGraph\n",
    "C4 = FlexRiGraph([[0,1],[1,2],[2,3],[0,3]], name='4-cycle', pos={0:(0,0),1:(1,0), 2:(0.8,0.8), 3:(0.3,0.6)})\n",
    "S = GraphGenerator.SmallestFlexibleLamanGraph()\n",
    "T = GraphGenerator.ThreePrismGraph()\n",
    "M = GraphGenerator.MaxEmbeddingsLamanGraph(7)\n",
    "K33 = FlexRiGraph(graphs.CompleteBipartiteGraph(3,3))\n",
    "N = FlexRiGraph(448412, pos={0 : (-0.5,-0.75), 1 : (0.5,0.5), 2 : (1.5,0.5), 3 : (2.5,-0.75),\n",
    "                                       4 : (0.5,1.5), 5 : (1.5,1.5), 6 : (1,-0.25)}, name='No NAC')\n",
    "Q1 = GraphGenerator.Q1Graph()\n",
    "examples = [C4, S, T, M, K33, N, Q1]\n",
    "# show(*[G.plot().show(figsize=[4,4], dpi=80) for G in examples])\n",
    "figs = graphics_array([G.plot() for G in examples],\n",
    "                      ncols=3)\n",
    "figs.show(figsize=[10,5], axes=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Theorem** [Pollaczek-Geiringer, Laman]\n",
    "\n",
    "A graph is *generically rigid*, i.e., a generic realization defines a rigid labeling,\n",
    "if and only if the graph contains a *Laman* subgraph with the same set of vertices.\n",
    "\n",
    "A graph $G=(V_G,E_G)$ is called *Laman* if $|E_G| = 2|V_G|-3$, and $|E_H|\\leq 2|V_H|-3$ for all subgraphs $H$ of $G$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "table([['', 'is Laman']]+[[G.name(), str(G.is_Laman())] for G in examples])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Flexible labelings\n",
    "\n",
    "**Definition**\n",
    "\n",
    "Let $G$ be a graph. A coloring of edges $\\delta\\colon  E_G\\rightarrow \\{\\text{blue, red}\\}$ \n",
    "is called a *NAC-coloring*, if it is surjective and for every cycle $C$ in $G$,\n",
    "either all edges of $C$ have the same color, or\n",
    "$C$ contains at least 2 edges in each color.\n",
    "\n",
    "**Theorem** [Grasegger, L., Schicho]\n",
    "\n",
    "A graph $G$ has a flexible labeling if and only if it has a NAC-coloring."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "table([['', 'has NAC-coloring']]+[[G.name(), str(G.has_NAC_coloring())] for G in examples])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "for G in [C4, S, T]:\n",
    "    print(G.name())\n",
    "    G.show_all_NAC_colorings()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Motion construction from a NAC-coloring"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from flexrilog.graph_motion import GraphMotion\n",
    "delta = T.NAC_colorings()[0]\n",
    "motion_T = GraphMotion.GridConstruction(T, delta)\n",
    "motion_T.parametrization()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "motion_T.animation_SVG(edge_partition='NAC')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "motion_T = GraphMotion.GridConstruction(T, delta, zigzag=[[[0,0], [3/4,1/2], [2,0]], [[0,0], [1,0]]])\n",
    "motion_T.parametrization()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "motion_T.animation_SVG()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "delta = S.NAC_colorings()[0]\n",
    "delta.plot().show(figsize=[4,4])\n",
    "motion_S = GraphMotion.GridConstruction(S, delta, check=False)\n",
    "motion_S.animation_SVG(edge_partition='NAC')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "table([['', 'NAC-coloring', 'injective grid'\n",
    "       ]]+[[G.name(), str(G.has_NAC_coloring()), str(G.has_injective_grid_construction())] for G in examples])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Movable graphs\n",
    "\n",
    "Recall - we look for a **proper** flexible labeling, i.e., infinitely many **injective** realizations\n",
    "\n",
    "**Definition**\n",
    "$\\DeclareMathOperator{\\CDC}{CDC} \\newcommand{\\cdc}[1]{\\CDC(#1)}$\n",
    "$\\DeclareMathOperator{\\Upairs}{U} \\newcommand{\\upairs}[1]{\\Upairs(#1)}$\n",
    "\n",
    "Let $\\upairs{G}$ denote the set of all pairs $\\{u,v\\}\\subset V_G$ such that $uv\\notin E_G$ and \n",
    "there exists a path from $u$ to $v$ which is unicolor for all NAC-colorings $\\delta$ of $G$.\t\n",
    "If there exists a sequence of graphs $G=G_0, \\dots, G_n$ such that\n",
    "$G_i=(V_{G_{i-1}},E_{G_{i-1}} \\cup \\upairs{G_{i-1}})$ for $i\\in\\{1,\\dots,n\\}$\n",
    "and $\\upairs{G_n}=\\emptyset$,\n",
    "then the graph $G_n$ is called *the constant distance closure* of $G$, denoted by $\\cdc{G}$.\n",
    "\n",
    "**Theorem** [Grasegger, L., Schicho]\n",
    "\n",
    "A graph $G$ is movable if and only $\\cdc{G}$ is movable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CDC = M.constant_distance_closure()\n",
    "M.show_all_NAC_colorings()\n",
    "CDC.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Corollary**\n",
    "\n",
    "If $G$ is movable, then $\\cdc{G}$ is not complete."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "table([['', 'NAC-coloring', 'injective grid', 'CDC non-complete']]+\n",
    "      [[G.name(), str(G.has_NAC_coloring()), \n",
    "        str(G.has_injective_grid_construction()), str(not G.cdc_is_complete())] for G in examples])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Lemma** [Grasegger, L., Schicho]\n",
    "\n",
    "Let $G=(V,E)$ be a graph with an injective embedding $\\omega:V\\rightarrow\\mathbb{R}^3$ such that for every edge \n",
    "$uv\\in E$, the vector $\\omega(u)-\\omega(v)$ is parallel to one of the four vectors $(1,0,0)$, $(0,1,0)$, $(0,0,1)$, $(-1,-1,-1)$, and all four directions are present.\n",
    "Then $G$ is movable.\n",
    "\n",
    "Moreover, there exist two NAC-colorings such that two edges are parallel in the embedding $\\omega$ if and only if they\n",
    "receive the same pair of colors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "res, NACs = Q1.has_injective_spatial_embedding(certificate=True)\n",
    "print(res)\n",
    "graphics_array([col.plot() for col in NACs])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "motion_Q1 = GraphMotion.SpatialEmbeddingConstruction(Q1,NACs)\n",
    "motion_Q1.fix_edge([5,6])\n",
    "motion_Q1.parametrization()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "motion_Q1.animation_SVG()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "table([['', 'movable', 'reason']]+\n",
    "      [[G.name()]+list(G.is_movable()) for G in examples])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S1 = GraphGenerator.S1Graph()\n",
    "show(S1)\n",
    "S1.is_movable()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Motion Classification - $K_{3,3}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from flexrilog import MotionClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = GraphGenerator.K33Graph()\n",
    "MC = MotionClassifier(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "motion_classes = MC.possible_motion_types_and_active_NACs({0:'Dixon I',\n",
    "                                          3: 'special case of Dixon I',\n",
    "                                          7: 'special case of Dixon I',\n",
    "                                          4: 'Dixon II',\n",
    "                                         })"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dixonII_mt = motion_classes[2][0]; dixonII_mt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "edge lengths enforced by motion types:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "MC.show_factored_eqs(MC.motion_types2same_lengths_equations(dixonII_mt))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "active NAC-colorings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "active_NACs = MC.motion_types2active_NACs(dixonII_mt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "MC.singletons_table(active_NACs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "equations from motion types and comparing leading coefficients:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "MC.show_factored_eqs(MC.motion_types2equations(dixonII_mt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.0",
   "language": "sage",
   "name": "sagemath"
  },
  "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.7.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}