From:        Olli P Lahti <olahti@cs.Helsinki.FI>
Subject:     TiRa 2. vk: tehtävän 4 arvosteluperusteet
Date:        Wed, 2 May 2001 14:11:42 +0300 (EET DST)

Tietorakenteet, 2. välikoe, kevät 2001

Arvosteluperusteet, tehtävä 4.                Olli Lahti


a)  --- 3 pistettä ---


[katso luvut 7.3.1 ja 7.4.1 intranetin luentomateriaalista
https://www.cs.helsinki.fi/i/wikla/Tira/Sisalto/7/Verkko.html#3]


VIERUSMATRIISI
--------------
 - Solmut numeroidaan ja särmät esitetään
   lähtösolmu-kohdesolmu -matriisin alkioina.
 - painotettu tai painottamaton
    o painotettu: puuttuva särmä esitetään
      mahdottomana painona
    o painottamaton: särmäalkion arvona joko
      1/0 tai true/false sen mukaisesti, onko
      särmää vai ei
 * hyvä suurelle ja tiheälle, huono suurelle
   ja harvalle verkolle


VIERUSLISTA
-----------
 - Solmut asetetaan taulukkoon, jonka jokaisesta
   alkiosta lähtee linkitetty lista.
 - Lähtevät särmät ovat kunkin solmun omassa
   listassa. Listan alkiot - yksi särmää kohden -
   kertovat kohdesolmut.
 - Listan alkioissa esitetään myös särmien painot
   ja muut mahdollisesti tarvittavat tiedot.
 * Tilavaativuus on lineaarinen, O(solmut+särmät).
 * Rinnakkaiset samansuuntaiset särmät ovat
   mahdollisia.
 * verkkoalgoritmeille kirjanpitoa solmujen
   yhteydessä sekä kulkurein

Ellei vähintään kahta tähdellä merkittyä asiaa mainittu,
a-kohdasta sai enintään 2 1/2 p.



b)  --- 2 pistettä ---


Solmun lähtöaste on solmusta alkavien särmien lukumäärä. 
Lähtöaste saadaan selville laskemalla yhteen vierusmatriisissa
solmun rivillä esiintyvien särmien lukumäärä.

Solmun tuloaste on solmuun päättyvien särmien lukumäärä.
Tuloaste saadaan selville laskemalla yhteen vierusmatriisissa
solmun sarakkeessa esiintyvien särmien lukumäärä.


Tapa 1:
=======

public static void tulostaLjaTasteet(int[][] vierusmatr) {
    int solmuja = vierusmatr.length;  // neliömatriisi
    for (int i=0; i<solmuja; i++) {   // rivit, solmujen lähdöt
      int lahto=0, tulo=0;            // laskurien nollaus
      for (int j=0; j<solmuja; j++) { // sarakkeet, tulot
        /* Sovitaan, että arvo 0 edustaa puuttuvaa särmää */
        if (vierusmatr[i][j] != 0)
          lahto++;                    // yksi lähtö lisää
        if (vierusmatr[j][i] != 0)
          tulo++;                     // yksi tulo lisää
        /* Lasketaan särmien määriä; painot eivät vaikuta */
      }
      System.out.println("solmu (" + i + ") \t lähtöaste " +
             lahto + " ja tuloaste " + tulo);
    }
}


Tapa 2:
=======

public static void tulostaLjaTasteet(int[][] vierusmatr) {
    int solmuja = vierusmatr.length;     // neliömatriisi
    int[][] laskutaulu = new int[solmuja][2];
    for (int i=0; i<solmuja; i++) {      // nollaus
        laskutaulu[i][0] = 0;            // solmun lähtöaste
        laskutaulu[i][1] = 0;            // solmun tuloaste
    }
    for (int i=0; i<solmuja; i++) {      // rivit, lähdöt
      for (int j=0; j<solmuja; j++) {    // sarakkeet, tulot
        /* Sovitaan, että arvo 0 edustaa puuttuvaa särmää */
        if (vierusmatr[i][j] != 0) {
          laskutaulu[i][0]++;            // yksi lähtö lisää
          laskutaulu[j][1]++;            // yksi tulo lisää
        }
        /* Lasketaan särmien määriä; painot eivät vaikuta */
      }
    }
    for (int i=0; i<solmuja; i++)    // tulostus solmuittain
      System.out.println("solmu (" + i + ") \t lähtöaste " +
             laskutaulu[i][0] + " ja tuloaste " +
             laskutaulu[i][1]);
}