Untitled.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# FHA minimal realization algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "using LinearAlgebra"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die erste Funktion ist der Algorithmus aus dem IFAC-Paper. Der Schritt 2, eine volle Adjazenzmatrix in einen Cycle zu transformieren, ist dabei weggelassen.\n",
    "Der Algorithmus ist in drei `while`-Schleifen implementiert:\n",
    "1. Die erste Schleife umfasst den ganzen Algorithmus und führt ihn aus, bish in einem Durchgang kein Element mehr geändert wird also solange `noAction=false`. Ist wahrscheinlich unnötig, wollte ich aber testen. \n",
    "2. Die zweite Schleife iteriert über alle Spalten. In jeder Iteration wird die Spalte mit der höchsten Summe ausgewählt. Die Summe wird um 1 reduziert, damit in den nächsten Durchgängen eine andere Spalte die höchste Summe hat. Diese Schleife läuft, bis alle Spalten-Summen 0 sind.\n",
    "3. Die drite Schleife iteriert über die Zeilen in der gewählten Spalte. Es wird die Zeile mit der höchsten Summe und Eintrag =1 ausgewählt. Die Zeilensumme wird temporär auf 0 gesetzt, um die Zeile nur einmal zu untersuchen.u Das Element wird entfernt und die Bedingung für _connectivity_ geprüft. Fällt die Prüfung negativ aus, wird das Element wieder eingefügt.\n",
    "\n",
    "Klicken Sie in ein Feld und drücken Strg+Enter, um das Feld auszuühren. Variablen können mit der Zeile `@show name` an beliebigen Stellen ausgegeben werden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "reduceAdjaciency (generic function with 1 method)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function reduceAdjaciency(Ad)\n",
    "    A = copy(Ad)\n",
    "    n = size(A,1)\n",
    "    \n",
    "    # Hauptdiagonale auf 0 setzen\n",
    "    [A[i,i] = 0 for i in 1:n]\n",
    "    \n",
    "    # Marker, ob in einem Durchgang kein Eintrag geändert wurde\n",
    "    noAction = false\n",
    "\n",
    "    # Algorithmus wiederholen, bis kein Eintrag mehr geändert wird\n",
    "    while noAction == false\n",
    "        println(\"Outer Loop\")\n",
    "        \n",
    "        # Zeilen- und Spaltensummen berechnen\n",
    "        colSums = sum(A,dims=1)\n",
    "        rowSums = sum(A,dims=2)\n",
    "\n",
    "        # marker, ob Eintrag zu 0 gesetzt wurde\n",
    "        removed = false\n",
    "\n",
    "        # Abbruchbedingungen\n",
    "        sum(colSums.==1) == size(colSums,2) && return A\n",
    "        sum(colSums.>1) == 0 && return A\n",
    "        \n",
    "        # bisher kein Eintrag geändert\n",
    "        noAction = true\n",
    "        \n",
    "        # Schritte 3a-3c\n",
    "        while true\n",
    "            # Höchste Spaltensumme\n",
    "            ~,i = findmax(colSums)\n",
    "            i = i[2] # wählt den index des Maximums\n",
    "\n",
    "            # Reduziere Spaltensumme, damit in nächster Runde die nächste Spalte genommen wird\n",
    "            colSums[i] -=1\n",
    "\n",
    "            # Berechne Zeilensummen in jeder Schleife neu\n",
    "            rowSums = sum(A,dims=2)\n",
    "            \n",
    "            # iteriere über Zeileneinträge in Spalte\n",
    "            while removed == false\n",
    "\n",
    "                # Höchste Zeilensumme\n",
    "                ~,j = findmax(rowSums.*A[:,i])\n",
    "                j = j[1] # wählt den index des Maximums\n",
    "                \n",
    "                # Wenn alle Einträge in Spalte =0, dann nächste Schleife\n",
    "                sum(rowSums.*A[:,i]) == 0 && break\n",
    "\n",
    "                # Eintrag auf 0 und irreducibility überprüfen\n",
    "                if A[i,j] == 1\n",
    "                    A[i,j] = 0\n",
    "                    println(\"removed Element\")\n",
    "                    removed = true\n",
    "                    noAction = false\n",
    "                    if sum((I+A)^(n-1) .> 0) != n^2\n",
    "                        A[i,j]=1\n",
    "                        removed = false\n",
    "                        println(\"reversed remove\")\n",
    "                        noAction = true\n",
    "                    end\n",
    "                end\n",
    "                \n",
    "                # höchste Zeilensumme auf 0, damit nächstes Element im neuen Durchgang gewählt wird\n",
    "                rowSums[j] = 0\n",
    "                \n",
    "                # prüfe, ob alle Zeilensummen = 0\n",
    "                sum(rowSums) == 0 && break\n",
    "            end \n",
    "            \n",
    "            removed = false\n",
    "            \n",
    "            # Überprüfe, ob alle Spaltensummen\n",
    "            sum(colSums)==0 && break\n",
    "        end\n",
    "    end\n",
    "    return A\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der naive Algorithmus  setzt nur die Hauptdiagonale auf 0 und iteriert dann über alle Elemente der Matrix. Ist ein Element 1, prüft er, ob das Element entfernt werden kann, und entfernt es gegebenenfalls. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "naiveReduction (generic function with 1 method)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function naiveReduction(x)\n",
    "    l=copy(x)\n",
    "    n = size(l,1)\n",
    "    # Hauptdiagonale auf 0 setzen\n",
    "    [l[i,i] = 0 for i in 1:n]\n",
    "    for i in 1:n, j in 1:n\n",
    "        if l[i,j]==1 \n",
    "            l[i,j]=0\n",
    "        end\n",
    "        if sum((I+l)^(n-1) .> 0) != n^2 \n",
    "            l[i,j] =1\n",
    "        end\n",
    "    end\n",
    "    return l\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun erzeugen wir eine zufällige `dims`x`dims`-Matrix, die irreduzibel ist. Ändern Sie einfach die Variable `dims`, um verschiedene Größen zu testen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sum(sum(Ad)) = 13\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5×5 Array{Int64,2}:\n",
       " 1  1  0  1  1\n",
       " 1  1  0  0  0\n",
       " 1  0  1  0  1\n",
       " 0  1  0  0  0\n",
       " 0  1  1  0  1"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dims = 5\n",
    "while true\n",
    "    global Ad = rand([0,1],dims,dims)\n",
    "    sum((I+Ad)^(dims-1).>0) == dims^2 && break\n",
    "end\n",
    "@show (sum(sum(Ad)))\n",
    "Ad"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Algorithmus 1 liefert folgendes Ergebnis:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Outer Loop\n",
      "removed Element\n",
      "reversed remove\n",
      "removed Element\n",
      "removed Element\n",
      "reversed remove\n",
      "removed Element\n",
      "Outer Loop\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5×5 Array{Int64,2}:\n",
       " 0  0  0  1  1\n",
       " 1  0  0  0  0\n",
       " 1  0  0  0  0\n",
       " 0  1  0  0  0\n",
       " 0  1  1  0  0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Ared = reduceAdjaciency(Ad)\n",
    "Ared"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Algorithmus 2:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 Array{Int64,2}:\n",
       " 0  0  0  1  1\n",
       " 1  0  0  0  0\n",
       " 0  0  0  0  1\n",
       " 0  1  0  0  0\n",
       " 0  1  1  0  0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AredNaive = naiveReduction(Ad)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hier der Vergleich, wie viele Einträge $\\neq0$ noch vorhanden sind, und welche Elemtente sich unterscheiden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sum(sum(AredNaive)) = 7\n",
      "sum(sum(Ared)) = 7\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5×5 Array{Int64,2}:\n",
       " 0  0  0  0   0\n",
       " 0  0  0  0   0\n",
       " 1  0  0  0  -1\n",
       " 0  0  0  0   0\n",
       " 0  0  0  0   0"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@show (sum(sum(AredNaive)))\n",
    "@show (sum(sum(Ared)))\n",
    "\n",
    "Ared.-AredNaive"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 BitArray{2}:\n",
       " 1  1  1  1  1\n",
       " 1  1  1  1  1\n",
       " 1  1  1  1  1\n",
       " 1  1  1  1  1\n",
       " 1  1  1  1  1"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(I+Ared)^(dims-1).>0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 BitArray{2}:\n",
       " 1  1  1  1  1\n",
       " 1  1  1  1  1\n",
       " 1  1  1  1  1\n",
       " 1  1  1  1  1\n",
       " 1  1  1  1  1"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(I+AredNaive)^(dims-1).>0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.3.1",
   "language": "julia",
   "name": "julia-1.3"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.3.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}