Da Python a C++

[Giova411]

Qualcuno di buon cuore potrebbe "tradurmi" questo pezzo di codice da Python a C++?

    fi = open(filein,"r")
    fo = open(fileout,"w")
    n, m = [int(x) for x in fi.readline().split()]
    dt = dict()
    out = set()
    for i in range(n):
	    dt[i]=0
	    pass
    while m:
        a, b = [int(x) for x in fi.readline().split()]
        dt[a] +=1
        dt[b] +=1
        m -= 1
        pass
    for i in dt:
        if dt[i] == 1: out.add(i)
        pass
    out.pop()
    fo.write(str(len(out))+"\n")
    for i in out:
	    fo.write(str(i)+"\n")
	    pass
    pass

grazie mille

[Giova411]

Ops, manca la prima riga ossia il nome della function che prende un file dove legge ed uno dove scrive

[apatriarca]

Perché hai bisogno di tradurre quel codice in C++?

[Giova411]

Volevo capirci qualcosa visto che sto guardando qualcosina di semplice sui grafi...
Python è molto espressivo =(

[apatriarca]

Una traduzione richiederebbe un po' troppo tempo, ma provo a spiegarti cosa fa questo codice.

fi = open(filein,"r")
fo = open(fileout,"w")

Apre due file, uno in scrittura e uno in lettura.

n, m = [int(x) for x in fi.readline().split()]

Legge due numeri interi dalla prima riga del file di input e li scrive in n ed m.

dt = dict()
out = set()

Crea un dizionario e un insieme. dt viene usato per indicare il numero di occorrenze di alcuni numeri, mentre out viene usato per memorizzare i valori che compaiono solo una volta.

for i in range(n):
    dt[i]=0
    pass

Inizializza dt in modo che associ il valore zero a tutti i numeri da 0 ad n-1 (probabilmente sarebbe stato più comodo usare defaultdict al posto di dict e poi inizializzare a zero tutti i valori).

while m:
    a, b = [int(x) for x in fi.readline().split()]
    dt[a] +=1
    dt[b] +=1
    m -= 1
    pass
[code]
Legge 2 numeri da m righe nel file di input e incrementa i contatori corrispondenti a quei valori.
[code]
for i in dt:
    if dt[i] == 1: out.add(i)
    pass

Inserisce in out tutti i numeri il cui contatore in dt sia uguale a uno.

out.pop()

Non mi è chiaro lo scopo di questa riga. Rimuove un elemento dall'insieme.

fo.write(str(len(out))+"\n")
for i in out:
       fo.write(str(i)+"\n")
       pass
    pass

Scrive la dimensione di out in una riga e poi tutti i valori in esso contenuto in righe separate.

Se dovessi dare una interpretazione al codice direi che il primo file contiene un grafo rappresentato da un numero di nodi e archi e poi da una lista di archi. L'obiettivo sembra essere quello di scrivere in un secondo file tutti i nodi che hanno un solo arco entrante o uscente. In C++ puoi ovviamente usare strutture dati simili e leggere il file riga per riga come nel codice Python, ma credo che lo scriverei diversamente. Utilizzerei probabilmente un singolo array (che rappresenta dt) e nessuna struttura dati per out.

[Giova411]

Apa sei un grande! Io a te dovrei pagarti!!!!
Grazie!!

Avevo pensato che facesse una specie di visita DFS in "stile" topologico e forse visita un grafo, non orientato ed aciclico fatto a linea dritta. Poi valuta i nodi con un solo nodo che toglie dall'insieme e stampa semplicemente.

[Giova411]

Cmq Apa il mio problema è anche (direi soprattutto!) di non avere esempi concreti di implementazioni di grafi.
Troppo complicato passare a produrre codice vero!
Forse li vedo ancora un po' troppo astratti sti grafi....
Il C++ è il linguaggio che più conosco.. ma non sono un genio come avrai ben capito.....

[apatriarca]

Che genere di implementazioni vorresti? Esistono librerie per lavorare con i grafi in C++ che sono molto potenti (ma il cui codice non è particolarmente accessibile), ma anche codici didattici. I grafi sono comunque un concetto abbastanza astratto, esistono tantissimi modi diversi per rappresentarli nel proprio codice a seconda degli utilizzi.

[Giova411]

Sì per imparare qualcosa di semplice. Esercizi implementati per la didattica.. In rete si trova poco e niente... Almeno per ora..
Grazie Apatriarca!

[Giova411]

 
#include <fstream>
#include <set>
using namespace std;

void prescelto(ifstream in, ofstream out){
int n;
in >> n;
int m;
in >> m;
set<int> no;

int *dt = new int[n];
for (int i = 0; i<n; i++)
  dt[i] = 0;

while(m>0)
{
 int n1, n2;
 in>> n1; in>>n2;
 dt[n1] += 1;
 dt[n2] +=1;
 m -=1;
}

for(int i = 0; i<n; i++)
{
 if (dt[i] == 1) no.insert(i);
}
// non so come estrarre. Cosa estrae? Un elemento a caso?
// non capisco bene come tradurre quel  fo.write(str(len(out))+"\n") dovrebbe essere len come la grandezza della Set

for (int d = 0; d<no.size(); d++)
    out << d << endl;
}
int main ()
{
ifstream in ("input.txt");
ofstream out ("output.txt");
prescelto(in, out);
return 0;

}

Ci provo dai!!!

PS: Apa non sembra così difficile!

[Giova411]

#include <fstream>
#include <queue>
using namespace std;


int main ()
{
ifstream in ("input.txt");
ofstream out ("output.txt");
int n;
in >> n;
int m;
in >> m;
queue<int> coda;

int *dt = new int[n];
for (int i = 0; i<n; i++)
  dt[i] = 0;

while(m>0)
{
 int n1, n2;
 in>> n1; in>>n2;
 dt[n1] += 1;
 dt[n2] +=1;
 m -=1;
}


for(int i = 0; i<n; i++)
 if (dt[i] == 1) coda.push(i);

coda.pop();
out << coda.size()<< endl;

for (int d = 0; d<coda.size(); d++)
    out << d << endl;


return 0;

}

Qualcosa fa... Ma non è efficente come il codice di Python (stitico ma elegante)