ICD0001 Algoritmid ja andmestruktuurid kodutöö 6 - aruanne (0)

  Tallinn 2020  TALLINNA TEHNIKAÜLIKOOL  Infotehnoloogia teaduskond        INDIVIDUAALTÖÖ AINES "ALGORITMID  JA ANDMESTRUKTUURID"                                       


  2  Lühendite ja mõistete sõnastik  Graaf  Järjestatud paar mittetühjast hulgast V ja selle hulga elementide 
paaride hulgast E.  Hulk V  Lõplik tippude hulk.  Hulk E  Tipupaaride hulga alamhulk.  Lihtgraaf    Silmuste ja kordsete servadeta orienteerimata graaf.  Ekstsentrilisus  Suurus, mis näitab tipu lühima tee pikkust temast kõige 
kaugemasse punkti.   Arvutatakse valemiga: e(v)  , 
kus d(u, v) on tipu u kaugus tipust v (lühima tee pikkus tipust u 
tippu v).  Klass    Objektorienteeritud programmeerimisel keelekonstruktsioon, 
mille põhjal luuakse objekte. Klass kirjeldab kindla objekti 
tüübi ja käitumise.  Meetod  Klassiga seotud funktsioon(id).  Kujutis ehk Map  Andmekogum, kus on võtmete hulga igale elemendile 
vastavuses üks väärtuste hulga element.  Loend ehk List  Loend on korrastatud andmekogum.  Massiiv ehk Array  Järjestatud andmete kogum. (Massiivil on kindel pikkus)  ArrayList  Dünaamiline masiiv. Töötab enamjaolt nagu massiiv, kuid selle 
pikkus on dünaamiline.       


  3    Sisukord   
Lühendite ja mõistete sõnastik ......................................................................................... 2   Sisukord ............................................................................................................................ 3   1 Ülesande püstitus ........................................................................................................... 4   2 Kitsendused ................................................................................................................... 4   3 Muudatused etteantud klassides .................................................................................... 4   3.1 Klass Vertex ........................................................................................................... 4   3.2 Klass Graph ............................................................................................................ 5   4 Algoritmi kirjeldus ........................................................................................................ 5   5 Programmi kasutusjuhend ............................................................................................. 6   6 Testimiskava .................................................................................................................. 7   7 Algoritmi testimine suure koguse andmetega ............................................................. 10   Kasutatud allikad ............................................................................................................ 11   Lisa 1 – Programmi täielik tekst ..................................................................................... 12   Lisa 2 – Lahendusnäidete tulemused .............................................................................. 21    
 
 
 


  4  1 Ülesande püstitus  Etteantud  graafi  klasse  (Graph,  Vertex,  Arc)  kasutades  koostada  meetod,  mis  arvutab  etteantud sidusa lihtgraafi G = (V, E) iga tipu v jaoks välja selle ekstsentrilisuse.  2 Kitsendused  Graafi kõikide servade pikkus on 1.  3 Muudatused etteantud klassides  Etteantud graafi klassidesse on lisatud järgmised uued andmeväljad:  3.1 Klass Vertex   List mis hoiab endas tipu kõrval olevate tippude indekseid (int info)  ArrayList adjacentVertexesInfo = new ArrayList<>();       


  5    3.2 Klass Graph  Kujutis ehk Map mis hoiab endas kõiki graafi tippe ja nendele vastavaid ekstsentrilisusi.  Map vertexEccentricities;    List mis hoiab endas graafi kõiki tippe.  LinkedList vertexList = new LinkedList<>();    4 Algoritmi kirjeldus  Sidus  lihtgraaf  on  silmuste  ja  kordsete  servadeta  orienteerimata  graaf,  kus  leidub  tee  mistahes tipust mistahes teise tippu.  Tipu v ekstsentrilisuseks nimetatakse suurust  e(v) = max {d(u, v)| u kuulub hulka V } , kus d(u, v) on tipu u kaugus tipust v (lühima  tee pikkus tipust u tippu v).  Iga  uue  tipu  loomisel  lisatakse  see  graafi  klassis  olevasse  listi,  mis  hoiab  endas  kõiki  tippe.  Tippude  ekstsentrilisuse  arvutamiseks  on  vaja  teada,  milliste  tippudega  on  iga  tipp  ühendatud.  Selleks  käime  läbi  kõik  tipust  väljuvad  kaared  ja  nende  tagumised  otspunktid  (Vertex  target)  ning  lisame  leitud  otspunktide  indeksid  listi  adjacentVertexesInfo.  Tippude ekstsentrilisue leidmiseks  kasutame laiuti otsimist.  Algoritm alustab etteantud  tipust, läbib kõik selle tipu naabrid, siis naabrite naabrid jne. Algoritm lõpetab töö, kui  kõik võimalikud teed on läbitud ning salvestab tipu ekstsentrilisuse.   Viimaks väljastab kõikide tippude ekstsentrilisused e(v). 


  6  5 Programmi kasutusjuhend  1.  Luua  sidus  lihtgraaf  käsitisi  või  kasutades  meetodit  createRandomSimpleGraph  (tahab sisenditeks tippude arvu n ja kaarte arvu m), mis loob suvalise sidusa lihtgraafi.  2. Käivitada graafis meetod computeEccentricityOfEachVertex(), mis arvutab graafi iga  tipu ekstsentrilisuse.  3. Käsklus System.out.println(graafi nimi) väljastab konsooli graafi kuju tekstesitluses  4.  System.out.println(g.outputEccentricityOfEachVertex())  väljastab  konsooli  iga  tipu  ekstsentrilisuse kujul: e(v) = ?  , kus v on tipu id.    Lisa: Meetod outputEccentricityOfVertex(Vertex v) tagastab String kujul ette antud tipu  v ekstsentrilisuse kujul: e(v) = ?  , kus v on tipu id.     


  7  6 Testimiskava  Initisialiseerimata graaf  Exception in thread "main" java.lang.RuntimeException: Graph is null!  Tühi graaf  Exception  in  thread  "main"  java.lang.RuntimeException:  Graph  "Empty  graph"  is  empty!  Graaf ei ole sidus  Exception  in  thread  "main"  java.lang.RuntimeException:  No  adjacent  vertexes  found  for vertex (vertex id).    Graafi tippude ekstsentrilisuse leidmise test 1    Test graaf 1  Tippude ekstsentrilisused  A --> AB (A->B) AF (A->F) AD (A->D)  B --> BA (B->A) BC (B->C)  C --> CB (C->B) CD (C->D) CF (C->F)  D --> DC (D->C) DE (D->E) DA (D->A)  E --> ED (E->D) EF (E->F)  F --> FE (F->E) FA (F->A) FC (F->C)  e(A) = 2  e(B) = 3  e(C) = 2  e(D) = 2  e(E) = 3  e(F) = 2    Time elapsed to calculate eccentricity for 6 vertexes: 16ms 


  8  Graafi tippude ekstsentrilisuse leidmise test 2 
  Test graaf 2  Tippude  ekstsentrilisused  A --> AB (A->B) AF (A->F) AD (A->D) AG (A->G)  B --> BA (B->A) BC (B->C) BF (B->F)  C --> CB (C->B) CD (C->D) CF (C->F)  D --> DC (D->C) DE (D->E) DA (D->A)  E --> ED (E->D) EF (E->F)  F --> FE (F->E) FA (F->A) FC (F->C) FG (F->G) FB (F->B)  G --> GF (G->F) GA (G->A)  e(A) = 2  e(B) = 2  e(C) = 2  e(D) = 2  e(E) = 2  e(F) = 2  e(G) = 2    Time elapsed to calculate eccentricity for 7 vertexes: 16ms       


  9  Graafi tippude ekstsentrilisuse leidmise test 3 
  Test graaf 3  Tippude  ekstsentrilisused  A --> AB (A->B) AF (A->F) AD (A->D) AC (A->C) AE (A->E)  B --> BA (B->A) BC (B->C) BF (B->F)  C --> CB (C->B) CD (C->D) CF (C->F) CA (C->A)  D --> DC (D->C) DE (D->E) DA (D->A)  E --> ED (E->D) EF (E->F) EA (E->A)  F --> FE (F->E) FA (F->A) FC (F->C) FG (F->G) FB (F->B)  G --> GF (G->F)  e(A) = 2  e(B) = 2  e(C) = 2  e(D) = 3  e(E) = 2  e(F) = 2  e(G) = 3    Time elapsed to calculate eccentricity for 7 vertexes: 15ms         


  10  Graafi tippude ekstsentrilisuse leidmise test 4 
  Test graaf 4  Tippude  ekstsentrilisused  A --> AB (A->B) AF (A->F) AD (A->D) AC (A->C) AE (A->E)  B --> BA (B->A) BC (B->C) BF (B->F)  C --> CB (C->B) CD (C->D) CA (C->A)  D --> DC (D->C) DA (D->A)  E --> EF (E->F) EA (E->A)  F --> FE (F->E) FA (F->A) FG (F->G) FB (F->B)  G --> GF (G->F)  e(A) = 2  e(B) = 2  e(C) = 3  e(D) = 3  e(E) = 2  e(F) = 2  e(G) = 3    Time elapsed to calculate eccentricity for 7 vertexes: 15ms  7 Algoritmi testimine suure koguse andmetega   
1. Ekstsentrilisuse leidmine graafile, milles on 2000 tippu ja 2500 kaart: 
 
Graph g = new Graph ("Graph 2000-2500"); 
g.createRandomSimpleGraph (2000, 2500); 
 
Time elapsed to calculate eccentricity for 2000 vertexes: 15912ms 
 
2. Ekstsentrilisuse leidmine graafile, milles on 5000 tippu ja 6000 kaart: 
 
Graph g = new Graph ("Graph 5000-6000"); 
g.createRandomSimpleGraph (5000, 6000); 
 
Time elapsed to calculate eccentricity for 5000 vertexes: 378612ms 
   


  11  Kasutatud allikad  1. Aine koduleht (Graafid) 
https://enos.itcollege.ee/~jpoial/algoritmid/graafid.html 
 
2. Graafid 
https://research.cyber.ee/~peeter/teaching/graafid02s/graafid.pdf 
 
3. Vikipeedia (Laiuti otsing) 
https://et.wikipedia.org/wiki/Laiuti_otsing 
 
4. Eccentricity class 
https://github.com/ambye85/sedgewick_algorithms/blob/master/src/main/java/uk/ashley
bye/sedgewick/graph/Eccentricity.java 
 
5. Queue class 
https://github.com/ambye85/sedgewick_algorithms/blob/master/src/main/java/uk/ashley
bye/sedgewick/collections/Queue.java 
 
6. Graaf 
https://et.wikipedia.org/wiki/Graaf 
 
7. Klass 
https://et.wikipedia.org/wiki/Klass_(programmeerimine) 
 
8.   Java õppematerjalid 
https://ained.ttu.ee/javadoc/index.html


  12  Lisa 1 – Programmi täielik tekst  import java.util.*; 
 
 
public class GraphTask { 
 
   /* 
   ÜLESANNE: 
   Koostada meetod, mis arvutab etteantud sidusa lihtgraafi G=(V, E) 
iga TIPU v jaoks välja selle EKSTSENTRILISUSE. 
      e(v) , kus d(u, v) on tipu u 
kaugus tipust v (lühima tee pikkus tipust u tippu v) 
   */ 
 
   public static void main (String[] args) 
 
   /** Actual main method to run examples and everything. */ 
   public void run() 
 
   class Vertex implements Comparable 


  13   
      Vertex (String s) 
 
      @Override 
      public String toString() 
 
      /** Comparator for sorting Vertexes in TreeMap */ 
      public int compareTo(Vertex v) 
   } 
 
 
   /** Arc represents one arrow in the graph. Two-directional Arcs are 
    * represented by two Arc objects (for both directions). 
    */ 
   class Arc { 
 
      private String id; 
      private Vertex target; // kaare tagumine otspunkt (Arc A->B siis 
target = B) 
      private Arc next;      // ahela viit lihtahela jaoks 
      // private int info = 0; 
 
      Arc (String s, Vertex v, Arc a) 
 
      Arc (String s) 
 
      @Override 
      public String toString() 
 
   }  
 
 
   class Graph { 
 
      private String id; // graafi nimi 
      private Vertex first;  // viit esimesele tipule. Kui null siis 
on tegemist tühja graafiga 
      private int info = 0; 
      private Map vertexEccentricities; 
      private LinkedList vertexList = new LinkedList<>(); 
 
      private final String newLine = System.getProperty 
("line.separator"); // For StringBuilder 
 
      Graph (String s, Vertex v)-->
  14        } 
 
      Graph (String s) 
 
      /** 
       * Print graph as string. 
       * @return visual representation of Graph connections. 
       */ 
      @Override 
      public String toString() 
            sb.append (nl); 
            v = v.next; 
         } 
         return sb.toString(); 
      } 
 
 
      /** 
       * Print out eccentricity e(V) for every Vertex in Graph. 
       * @return visual representation of eccentricity e(V) for every 
Vertex in Graph. 
       */ 
      public String outputEccentricityOfEachVertex() 
 
         return output.toString(); 
      } 
 
 


  15        /** 
       * Print out eccentricity e(V) of given Vertex. 
       * @param vertex Vertex object 
       * @return visual representation of eccentricity e(V) for given 
Vertex in Graph. 
       */ 
      public String outputEccentricityOfVertex(Vertex vertex) 
         } 
 
         return output.toString(); 
      } 
 
 
      /** 
       * Find Adjacent Vertexes of each Vertex and add adjacent vertex 
info to List Vertex.adjacentVertexesInfo 
       */ 
      public void computeAdjacentVertexesOfEachVertex() 
            v = v.next; 
         } 
      } 
 
      /** 
       * Construct a new instance of Eccentricity and compute the 
eccentricity of each vertex in the Graph. 
       * Update Map vertexEccentricities 
       * Key = Vertex 
       * Value = Vertex Eccentricity 
       */ 
      public void computeEccentricityOfEachVertex() 
 
         computeAdjacentVertexesOfEachVertex(); 
 
         Eccentricity eccentricity = new Eccentricity(); 
         vertexEccentricities = new TreeMap<>(); 
 
         for (int vertex = 0; vertex < this.vertexList.size(); 


  16  vertex++) 
            } 
         } 
      } 
 
 
      public Vertex createVertex (String vid) 
 
      public Arc createArc (String aid, Vertex from, Vertex to) 
 
      public Vertex findVertexByInfo(int info) 
         } 
         throw new RuntimeException("No vertex found in this graph 
with info: " + info); 
      } 
 
 
      /** 
       * Create a connected undirected random tree with n vertices. 
       * Each new vertex is connected to some random existing vertex. 
       * @param n number of vertices added to this graph 
       */ 
      public void createRandomTree (int n)-->
  17              } else {} 
         } 
      } 
 
      /** 
       * Create an adjacency matrix of this graph. 
       * Side effect: corrupts info fields in the graph 
       * @return adjacency matrix 
       */ 
      public int[][] createAdjMatrix() 
         int[][] res = new int [info][info]; 
         v = first; // jooksev muutuja 
         while (v != null) 
            v = v.next; 
         } 
         return res; 
      } 
 
      /** 
       * Create a connected simple (undirected, no loops, no multiple 
       * arcs) random graph with n vertices and m Arcs. 
       * @param n number of vertices 
       * @param m number of Arcs 
       */ 
      public void createRandomSimpleGraph (int n, int m) 
         int[][] connected = createAdjMatrix(); 
         int ArcCount = m - n + 1;  // remaining Arcs 
         while (ArcCount > 0)-->
  18                 continue;  // no loops 
            if (connected [i][j] != 0 || connected [j][i] != 0)  
               continue;  // no multiple Arcs 
            Vertex vi = vert [i]; 
            Vertex vj = vert [j]; 
            createArc ("a" + vi.toString() + "_" + vj.toString(), vi, 
vj); 
            connected [i][j] = 1; 
            createArc ("a" + vj.toString() + "_" + vi.toString(), vj, 
vi); 
            connected [j][i] = 1; 
            ArcCount--;  // a new Arc happily created 
         } 
      } 
 
 
   class Eccentricity { 
 
 
      /** 
       * For each vertex of the graph, the algorithm conducts a 
breadth first search for all connected vertices. 
       * The maximal shortest path from each vertex to any other 
vertex, the eccentricity of that vertex, is recorded. 
       * Also checks whether the eccentricity for the vertex is less 
than the current radius (smallest eccentricity in the graph) 
       * or longer than the current diameter (largest eccentricity in 
the graph), and updates them if either is true. 
       * 
       * @param graph the graph to conduct the breadth first search on 
       * @param sourceVertex the vertex from which to conduct the 
search 
       * @return int value of sourceVertex Eccentricity. 
       */ 
      private int breadthFirstSearch(Graph graph, Vertex sourceVertex) < -->
  19   
            ArrayList adjacentVertexesInfo = new 
ArrayList<>(); 
 
            for (Vertex vertex : graph.vertexList) 
            } 
 
            if (adjacentVertexesInfo.size() <= 0 || 
adjacentVertexesInfo == null) { 
               throw new RuntimeException("No adjacent vertexes found 
for vertex " + graph.findVertexByInfo(thisVertexInfo)); 
            } 
 
            for (int adjacentVertex : adjacentVertexesInfo) 
               } 
            } 
         } 
 
         return eccentricity; 
      } 
 
   } 
 
   /** 
    * Queue helps Breadth first search queue the source vertex, then 
iteratively dequeue the vertex and 
    * enqueue its adjacent vertices. 
    */ 
   class Queue implements Iterable 
 
      public boolean isEmpty() 
 
      public int size() -->
  20           return nodeCount; 
      } 
 
      public void enqueue(T item) else { 
            temp.next = back; 
         } 
 
         nodeCount++; 
      } 
 
      public T dequeue() 
 
         nodeCount--; 
 
         return item; 
      } 
 
      @Override 
      public Iterator iterator() 
 
   private class ListIterator implements Iterator 
 
         @Override 
         public T next() 
 
         @Override 
         public void remove() 
      } 
 
   } 
 
   } 
} 


  21  Lisa 2 – Lahendusnäidete tulemused    1. Test graaf 1 tulemuse ekraanipilt    Tulemuste seletused:  Tipu A ekstsentrilisus on 2, sest lühim tee temast kõige kaugemasse punkti on 2.  Antud näites on mitu tippu mis on tipust A 2 liikumise kaugusel.  Näiteks tippu C saamiseks on tipust A üks lühimatest teedest A -> D -> C       


  22  Tipu B ekstsentrilisus on 3, sest lühim tee temast kõige kaugemasse punkti E on 3.  Näiteks tippu E saamiseks on tipust B üks lühimatest teedest B -> A -> D -> E    2. Test graaf 2 tulemuse ekraanipilt      Tulemuste seletused:  Antud näites on iga tipu ekstsentrilisus 2. See tähendab, et mistahes tipust mistahes teise 
tippu kõige pikem lühim tee on 2.     


  23  3. Test graaf 3 tulemuse ekraanipilt     
   


  24  4. Test graaf 4 tulemuse ekraanipilt     
  5. Tühja graafi tulemuse ekraanipilt       


  25  6. Mitte sidusa graafi tulemuse ekraanipilt