Il cablatore

op1.cpp

#include <iostream>
#include <cstring>
using namespace std;

struct Arco {
    string nodo1;
    string nodo2;
    int peso;
};

struct Grafo {
    vector<Arco> listaArchi;
};

vector<Grafo> listaGrafi;

bool leggiFile(char*);
bool numerico(string);
int getNumero(string);
int getIntero(int, int, int);
int* getCoppia(int, int);

int main(int argc, char** argv) {
    if (leggiFile("input.txt")) {
        vector<Grafo>::iterator i;
        i = listaGrafi.begin();
        while (i != listaGrafi.end()) {
            cout << i->listaArchi.at(0).nodo1 << endl;
            cout << i->listaArchi.at(0).nodo2 << endl;
            cout << i->listaArchi.at(0).peso << endl;
            i++;
        }

    }
    return 0;
}

bool leggiFile(char* file) {
    ifstream input;
    input.open(file);
    int N;
    while (!input.eof()) {
        Grafo grafo;
        string peso;
        input >> N;
        // N deve essere un intero compreso tra 0 e 1.000.000 (0 <= N <= 1.000.000)
        if (N < 0 || N > 1000000) {
            cout << "Errore, il file di input non è ben formato [N = " << N << "]" << endl;
            return false;
        }
        // se N è pari a zero siamo arrivati a fine file
        if (N == 0) return true;
        // se la condizione è verificata leggiamo gli archi dal file
        for (int i = 1; i <= N; i++) {
            Arco arco;
            input >> arco.nodo1 >> arco.nodo2 >> peso;
            // le due stringhe (che descrivono i nodi) devono avere lunghezza esattamente 5
            if (arco.nodo1.length() != 5) {
                cout << "Errore, il file di input non è ben formato.";
                cout << " Il nome del nodo 1 non ha esattamente 5 caratteri [" << arco.nodo1 << "]" << endl;
                return false;
            }
            if (arco.nodo2.length() != 5) {
                cout << "Errore, il file di input non è ben formato.";
                cout << " Il nome del nodo 2 non ha esattamente 5 caratteri [" << arco.nodo2 << "]" << endl;
                return false;
            }
            // il peso dev'essere una stringa numerica
            if (!numerico(peso)) return false;
            arco.peso = getNumero(peso);
            // se il peso è una quantità positiva l'arco viene aggiunto
            if (arco.peso > 0) {
                grafo.listaArchi.push_back(arco);
            }
        } // for
        listaGrafi.push_back(grafo);
    } // while
    input.close();
}

/**
 * Converte la stringa numerica in un intero.
 * @param number la stringa numerica.
 * @return la rappresentazione intera della stringa number
 */
int getNumero(string number) {
    return atoi(number.data());
}

/**
 * Verifica se la stringa corrisponde ad un numero.
 * @param number la stringa numerica da verificare.
 * @return true se la stringa number è un numerico.
 */
bool numerico(string number) {
    string::const_iterator it = number.begin();
    while (it != number.end() && isdigit(*it)) {
        it++;
    }
    if (!number.empty() && it == number.end()) {
        return true;
    } else {
        return false;
    }
}

/**
 * Mappa una coppia di indici con un intero.
 * @param i varia tra 0 a size - 1.
 * @param j varia tra 0 a size - 1.
 * @param size il numero di nodi del grafo.
 * @return restituisce un numero intero compreso tra zero e (size^2) - 1.
 */
int getIntero(int i, int j, int size) {
    return i * size + j;
}

/**
 * Riceve
 * @param n un numero intero compreso tra zero e (size^2) - 1.
 * @param size il numero di nodi del grafo.
 * @return restituisce un array di dimensione due. Il primo elemento è l'indice
 * i, il secondo l'indice j.
 */
int* getCoppia(int n, int size) {
    int i = n / size;
    int j = n % size;
    // la variabile viene dichiarata static in maniera
    // tale che quando il metodo termina la locazione di memoria
    // non viene deallocata e viene assegnata al puntatore
    static int coppia[] = {i, j};
    return coppia;
}

op2.cpp

#include <fstream>
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <climits>
using namespace std;

struct Arco {
    string nodo1;
    string nodo2;
    int peso;
};

struct Grafo {
    vector<Arco> archi;
};

int letturaFile(vector<Grafo>& grafi);
vector<Arco> quickSortArchi(vector<Arco>& archi);
int algoritmoRisolutivo(Grafo g);
int numeroNodi(Grafo g);
bool toccatoNodoDaAltriArchi(vector<string>& nodiGiaToccati, string nodo);

int main() {
    //LETTURA FILE
    vector<Grafo> grafi;

    cout << endl;
    if (letturaFile(grafi) != -1) {

        for (int i = 0; i < grafi.size(); i++) {
            int k = algoritmoRisolutivo(grafi[i]);
            if (k != -1)
                cout << "Caso# " << i + 1 << ": " << k << endl;
            else
                cout << "Caso# " << i + 1 << ": impossibile" << endl;
        }

    }
    cout << endl;

    return 0;


}

int letturaFile(vector<Grafo>& grafi) {
    ifstream InFile("input.txt");
    int i;
    Arco a;
    while (!InFile.eof()) //RIEMPIMENTO GRAFI CON ARCHI
    {

        InFile >> i;
        if (i < 0 || i > 1000000 || (i < 0 && i > 1000000)) {
            cout << endl;
            cout << "errore di lettura , numero di collegamenti non valido" << endl;
            cout << endl;
            return -1;
        }

        if (i != 0) {
            Grafo g;
            for (int j = 0; j < i; j++) {
                InFile >> a.nodo1 >> a.nodo2 >> a.peso; // se a.peso == 0 vuol dire che tra a.nodo1 e a.nodo2 non è possibile
                // un collegamento

                if (a.nodo1.size() != 5 || a.nodo2.size() != 5 || (a.nodo1.size() != 5 && a.nodo2.size() != 5)) {
                    cout << endl;
                    cout << "errore di lettura, le stringhe devono avere esattamente 5 caratteri" << endl;
                    cout << endl;
                    return -1;
                }
                if (a.peso != 0)
                    g.archi.push_back(a);

            }
            grafi.push_back(g);
        }
    }
    InFile.close();
    return 0;
}

int algoritmoRisolutivo(Grafo g) {
    int costoMinimo = 0;
    vector<string> nodiGiaToccati;
    vector<Arco> archiOrdinati;
    int n = numeroNodi(g);
    Arco a;
    // Viene utilizzato l'algoritmo di Kruskal.
    // INIZIO
    // Ordinamento degli archi in ordine crescente di peso
    archiOrdinati = quickSortArchi(g.archi);

    int count = 0;
    while (count < archiOrdinati.size()) {
        // prendo l'arco con peso minimo
        Arco e = archiOrdinati[count];
        // Mi assicuro poi che "almeno uno" dei  nodi relativi all'arco preso in considerazione non sia toccato piu di una volta per evitare la possibilità che l'arco generi un ciclo.
        // Se l'arco non può generare cicli allora lo prendo e sommo il suo peso alla variabile costoMinimo.
        // Se  uno dei due nodi dell'arco  non è toccato da altri archi,allora questo è sufficiente per dire che l'arco corrente non può generare cicli.

        if (!toccatoNodoDaAltriArchi(nodiGiaToccati, e.nodo2)) {
            nodiGiaToccati.push_back(e.nodo2);
            costoMinimo += e.peso;
        } else if (!toccatoNodoDaAltriArchi(nodiGiaToccati, e.nodo1)) {
            nodiGiaToccati.push_back(e.nodo1);
            costoMinimo += e.peso;
        }
        count++;

    }



    // se tutti i nodi sono connessi restituisco il costo minimo altrimenti -1;
    if (nodiGiaToccati.size() == n)
        return costoMinimo;
    else
        return -1;



}

bool toccatoNodoDaAltriArchi(vector<string>& nodiGiaToccati, string nodo) {
    if (nodiGiaToccati.empty())
        nodiGiaToccati.push_back(nodo);

    for (int i = 0; i < nodiGiaToccati.size(); i++) {
        if (nodiGiaToccati[i] == nodo)
            return true;
    }
    return false;
}

int numeroNodi(Grafo g) {

    list<string> nodi;


    for (int i = 0; i < g.archi.size(); i++) {

        bool presente1 = false;
        bool presente2 = false;
        for (list<string>::iterator it = nodi.begin(); it != nodi.end(); it++) {
            if (g.archi[i].nodo1 == *it)
                presente1 = true;
            if (g.archi[i].nodo2 == *it)
                presente2 = true;

        }

        if (!presente1)
            nodi.push_back(g.archi[i].nodo1);
        if (!presente2)
            nodi.push_back(g.archi[i].nodo2);

    }

    int n = nodi.size();

    return n;
}

vector<Arco> quickSortArchi(vector<Arco>& archi) {
    if (archi.size() <= 1)
        return archi;

    int indiceElementoCentrale = archi.size() / 2;
    Arco elementoCentrale = archi[indiceElementoCentrale];

    // creo due vettori, uno contenente gli archi con peso minore del peso dell'elemento centrale,e l'atro contenente gli archi con peso maggiore del peso dell'elemento centrale
    vector<Arco> minori;
    vector<Arco> piuGrandi;

    for (int i = 0; i < archi.size(); i++) {
        // se trovo l'indice dell'elemento centrale non lo devo considerare
        if (i == indiceElementoCentrale)
            continue;
        if (archi[i].peso <= elementoCentrale.peso)
            minori.push_back(archi[i]);
        else
            piuGrandi.push_back(archi[i]);
    }

    vector<Arco> risultato;
    // ordino ricorsivamente gli elementi con peso minore
    vector<Arco> minoriOrdinati = quickSortArchi(minori);
    // ordino ricorsivamente gli elementi con peso maggiore
    vector<Arco> piuGrandiOrdinati = quickSortArchi(piuGrandi);
    // riempio il vettore risultato inserendo prima gli elementi con peso minore ordinati,poi l'elemento centrale, e poi gli elementi con peso maggiore ordinati.
    risultato.insert(risultato.end(), minoriOrdinati.begin(), minoriOrdinati.end());
    risultato.push_back(elementoCentrale);
    risultato.insert(risultato.end(), piuGrandiOrdinati.begin(), piuGrandiOrdinati.end());

    return risultato;
}

op3.cpp

#include <cstdlib>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;

struct Arco {
    string nodo1;
    string nodo2;
    int peso;
};

struct Grafo {
    vector<Arco> archi;
};

int main(int argc, char** argv) {
    vector<Arco> archiOrdinati;

    set<string> nodi;
    cout << nodi.size() << endl; // cout

    Arco arco1;
    arco1.nodo1 = "pippo";
    arco1.nodo2 = "pluto";
    nodi.insert(arco1.nodo1);
    nodi.insert(arco1.nodo2);
    cout << nodi.size() << endl; // cout
    arco1.peso = 3;

    Arco arco2;
    arco2.nodo1 = "pippo";
    arco2.nodo2 = "minni";
    nodi.insert(arco2.nodo1);
    nodi.insert(arco2.nodo2);
    cout << nodi.size() << endl; // cout
    arco2.peso = 1;

    Arco arco3;
    arco3.nodo1 = "pluto";
    arco3.nodo2 = "minni";
    nodi.insert(arco3.nodo1);
    nodi.insert(arco3.nodo2);
    cout << nodi.size() << endl; // cout
    arco3.peso = 5;

    Arco arco4;
    arco4.nodo1 = "minni";
    arco4.nodo2 = "pluto";
    nodi.insert(arco4.nodo1);
    nodi.insert(arco4.nodo2);
    cout << nodi.size() << endl; // cout
    arco4.peso = 3;

    archiOrdinati.push_back(arco2);
    archiOrdinati.push_back(arco4);
    archiOrdinati.push_back(arco1);
    archiOrdinati.push_back(arco3);

    cout << endl;
    
    map<string, int> mapping;
    set<string>::iterator iterator;
    int index = 0;
    for (iterator = nodi.begin(); iterator != nodi.end(); iterator++) {
        mapping[iterator->data()] = index;
        index++;
        //mapping.insert(pair<string, int>(iterator->data(), index));
    }
    int nodo1 = mapping["pippo"];
    int nodo2 = mapping["pluto"];
    
    int insiemi[3];
    if (insiemi[mapping["pippo"]] != insiemi[mapping["pluto"]]) {
        
    }
    
    cout << nodo1 << " --> " << nodo2 << endl;
    return 0;
}

op4.cpp

#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <map>
using namespace std;

struct Entry {
   string name;
   int number;
};

void exList();
void exVector();
void exMap();
void exString();

int main(int argc, char** argv) {
   exMap();
   return 0;
}

void exList() {
   // dichiaro la lista
   list<int> lista;
   // la inizializzo
   for (int i = 0; i < 10; i++) {
      lista.push_back(i);
   }

   list<int>::iterator it;
   list<int> copy;
   for (it = lista.begin(); it != lista.end(); it++) {
      copy.push_back(*it);
   }
   for (it = copy.begin(); it != copy.end(); it++) {
      cout << *it << endl;
   }
}

void exVector() {
   vector<int> phoneBook(10);
   for (int i = 0; i < 10; i++) {
      phoneBook[i];
   }
   
   try {
      for (int i = 0; i < 11; i++) {
         cout << phoneBook.at(i) << endl;
      }
   } catch (exception e) {
      cout << e.what() << endl;
   }
}

void exMap() {
   map<string, int> phoneBook;
}

void exString() {
   string name;
   cout << "Please, enter your name: ";
   getline(cin, name);
   cout << "Hello " << name << endl;
}