{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Rigidity and Flexibility of Graphs in SageMath\n", "\n", "Jan Legerský\n", "\n", "[jan.legersky.cz](https://jan.legersky.cz)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![S1](./animations/S_1.svg)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Tools\n", "\n", "- [SageMath](http://www.sagemath.org/)\n", "- [Binder](https://mybinder.org/)\n", "- [Documentation](https://jan.legersky.cz/public_files/documentation_rigidflexiblegraphs/) generated from docstrings using [Sphinx](http://sphinx-doc.org/) (tests)\n", "- Animated SVG\n", "- [POV-Ray](http://www.povray.org/)" ] }, { "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": [ "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[:4]],\n", " [text(G.name(),(0,0)) for G in examples[:4]],\n", " [G.plot() for G in examples[4:]]+[plot(Graph([]))],\n", " [text(G.name(),(0,0)) for G in examples[4:]],\n", " ], ncols=4, nrows=4)\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$.\n", "\n", "**Our main interest - non-generic (proper) flexible labelings of generically rigid graphs**" ] }, { "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", " graphics_array([col.plot() for col in G.NAC_colorings()], ncols=4).show(\n", " figsize=[10,3])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Construction of a motion from a NAC-coloring" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from flexrilog 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=[delta.red_edges(), delta.blue_edges()], colors=['red', 'blue'])" ] }, { "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=[delta.red_edges(), delta.blue_edges()], colors=['red', 'blue'])" ] }, { "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", "show(graphics_array([col.plot() for col in M.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" ] }, { "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": [ "![S1](./animations/S_1.svg)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Collision-free models\n", "\n", "Can a movable graph be modelled by a planar linkage in 3D that is collision-free?\n", "\n", "$\\implies$ Place edges into different layers and avoid collision with the axis." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%%HTML\n", "" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "edges = [(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 5), (3, 6), (3, 4)]\n", "K33 = FlexRiGraph(edges); K33" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t = var('t')\n", "P = {\n", " 1: vector([sin(t),0]),\n", " 2: vector([sqrt(1+sin(t)^2),0]),\n", " 3: vector([-sqrt(2+sin(t)^2),0]),\n", " 4: vector([0,cos(t)]),\n", " 5: vector([0,sqrt(1+cos(t)*cos(t))]),\n", " 6: vector([0,-sqrt(2+cos(t)^2)]),\n", "}; P" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "K33" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "M = GraphMotion.ParametricMotion(K33, P, 'symbolic')\n", "M" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "collisions = {\n", " 1: [[4,2],[4,3]],\n", " 4: [[1,6], [1,5]]\n", "}\n", "h_fun = M.height_function(collisions); h_fun" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%%HTML\n", "" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 7.5.1", "language": "", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.13" } }, "nbformat": 4, "nbformat_minor": 1 }