Dateien einlesen und in Vektoren speichern + Vektoren dynamisch erstellen

Euler

Guten Abend,

ich habe hier ein Problem und habe keine Ahnung, wie ich das angehen soll:

Ich möchte einen Graphen als Adjazenzliste speichern. Hierzu möchte ich die Knoten des Graphen in einen Vektor schreiben. Die Nachbarknoten dieser Knoten sollen ebenfalls in Vektoren gespeichert werden. D.h. ich benötige quasi einen Vektor, dessen Elemente Vektoren sind, also so in etwa:

vector< vector<int> > nodeList;

.
Ich mag den äußeren Vektor jetzt mal als Hauptvektor und die inneren Vektoren als Nebenvektoren bezeichnen.

Die Graphen, die ich einlesen möchte, sind in txt-Dateien gespeichert und zwar in folgendem Format:

2 3 4 5
3 5 6
1 2 4 6
2 3 5 6
1 2
1 4 5

Die erste Zeile entspricht Knoten 1. Die Zahlen in Zeile eins sind die Nachbarknoten von Knoten 1. Die zweite Zeile entspricht Knoten 2 und die Zahlen in Zeile zwei sind die Nachbarknoten von Knoten 2, usw.
Die Nachbarknoten sind stets durch Leerzeichen getrennt.

Problem1: Wie kann ich solche Dateien einlesen und den Inhalt in die Nebenvektoren speichern?

Problem2: Wie schaffe ich es, dass c++ jedesmal wenn eine Zeile eingelesen wird automatisch ein neuer Nebenvektor erstellt und der Inhalt reingeschrieben wird?

Um das Ganze nochmal zu verdeutlichen, schreibe ich den Pseudocode mal hin:

Öffne Graph-Datei
Falls Datei nicht leer gehe zu 3 sonst gehe zu 8
Lies Zeichen
Speichere dieses Zahl in entsprechenden Nebenvektor
falls Leerzeichen folgt, gehe zu 6, sonst gehe zu 7
Lies nächste Zahl, gehe zu 3
falls Ende der Zeile erreicht, Rücke eine Zeile vor und gehe zu 3, sonst gehe zu 8
Ende der Datei

Mein bisheriger Code ist leider sehr lücken- und fehlerhaft. Bisher sieht er so aus:

#include <iostream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for(vector<T>::const_iterator i=v.begin(); i!=v.end();++i)
		os<<*i<<" ";
	return os;
}
int main(void) {
   vector< vector<int> > hauptvektor;
   vector<int> nebenvektor1;
   vector<int> nebenvektor2;
   //Nebenvektoren sollen dynamisch erstellt werden, je nachdem wie viele Zeilen
   //die eingelesene Datei hat

   int c;

   FILE *datei;

   datei=fopen("test.txt", "r");
   if(datei != NULL) {
      while( (c=fgetc(datei)) != EOF)
		  if( c != '\n') {
				nebenvektor1.push_back(c);

		  } else {
			  hauptvektor.push_back(nebenvektor1);
			  //erstelle nächsten Nebenvektor und speichere da die nächste Zeile
			  goto ausgabe;
		  }
	  }
   else {
      printf("Konnte Datei nicht finden bzw. oeffnen!\n");
	  return EXIT_FAILURE;
   }
ausgabe:
   cout << "Nebenvektor1: " << nebenvektor1 << endl;
   cin.get();
   return EXIT_SUCCESS;
}

Jetzt bitte nicht an dem goto stören. Das ist nur ersatzweise da.

Der Code fügt den Inhalt der Datei "test.txt" zwar in den nebenvektor1 ein, aber nicht die Ganzzahlen in der Datei, sondern deren Ascii-Codes. Des Weiteren weiß ich nicht, wie ich die Vektoren je nach Anzahl der Zeilen dynamisch erstellen kann.

Falls jemand ein Code-Grundgerüst oder Ideen für diese Probleme hat, dann wäre ich demjenigen sehr verbunden.

Vielen Dank schon mal für eure Hilfe

Ungefähr so:

#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <string>

using namespace std;

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for( typename vector<T>::const_iterator i=v.begin(); i!=v.end();++i)
        os<<*i<<" ";
    return os;
}

int main() {
  vector< vector<int> > hauptvektor;
  vector<int> nebenvektor;

  ifstream datei("test.txt");

  if( !datei.good() ) return 1;

  std::string line;

  while( getline( datei, line ) ) {  // Zeile lesen
    istringstream s( line );         // in stringstream verpacken
    int val;
    while( s ) {
      s >> val;                      // einzelne Zahl aus stream lesen
      if( s ) {
	nebenvektor.push_back( val );
      }
      else {                         // Zeilenende erreicht
	hauptvektor.push_back(nebenvektor);
	cout << nebenvektor << endl;
	nebenvektor.resize( 0 );     // Zwischenpuffer leeren
      }
    }
  }

  cout << "\nErgebnis:\n";
  for( vector< vector<int> >::iterator i = hauptvektor.begin(); i != hauptvektor.end(); ++i ) {
    cout << *i << endl;
  }
  return 0;
}

knivil

Die Aufgabenstellung suggeriert eine Loesung mittels goto.

knivil schrieb:

Die Aufgabenstellung suggeriert eine Loesung mittels goto.

Du bist bestimmt leicht zu hypnotisieren

Lars

Werner Salomon

Euler schrieb:

Die Graphen, die ich einlesen möchte, sind in txt-Dateien gespeichert und zwar in folgendem Format:

2 3 4 5
3 5 6
1 2 4 6
2 3 5 6
1 2
1 4 5

Die Problematik bei so einem Format besteht darin, dass das Zeilenende als formatierendes Element benutzt wird. In C++ liest man Standard gemäß mit std::istream. Hier wird aber nicht zwischen einem Leerzeichen und einem Zeilenende unterschieden. Das sind alles Whitespace Character.

Ich habe mal so ein kleines Helferlein is_endl() gebaut, welches das Zeilenende erkennt. Damit geht es dann relativ einfach.

#include <iostream>
#include <fstream>
#include <vector>

#include "is_endl.h" // s.u.

int main()
{
    using namespace std;
    vector< vector< int > > hauptvektor;

    ifstream datei( "test.txt" );
    if( !datei.is_open() )
    {
        cerr << "Fehler beim Oeffnen der Datei" << endl;
        return -1;
    }
    while( datei >> ws ) // überliest ggf. Leerzeilen; bricht ab bei Fehler; bzw. Fehler wg. EOF
    {
        vector< int > nebenvektor;
        for( int nr; !is_endl( datei ) && datei >> nr; ) // liest bis Zeilenende
            nebenvektor.push_back( nr );
        if( !nebenvektor.empty() )
            hauptvektor.push_back( nebenvektor );
    }
    if( datei.eof() )
        cout << "Ok - " << hauptvektor.size() << " Eintraege gelesen" << endl;
}

Ich unterstelle mal, dass es keine Knoten ohne Nachbarknoten gibt. Falls doch, also eine Leerzeile einen leeren Knoten darstellt, so müsstest Du das '>> ws' in der while-Schleife weglassen.

Und das is_endl kommt hier:

// -- Datei is_endl.h
#ifndef SAM_IS_ENDL_H_
#define SAM_IS_ENDL_H_
#include <istream>
#include <locale>
#include <streambuf>

template< typename E, typename Traits >
bool is_endl( std::basic_istream< E, Traits >& in )
{
    if( in.eof() ) // EOF vorher abfangen, da sentry den Stream auf fail setzt, falls eof()==true ist!
        return false;
    typename std::basic_istream< E, Traits >::sentry ok( in, true ); // true := noskipws
    if( ok )
    {
        const bool skipws_ = in.flags() & std::ios_base::skipws;
        const std::ctype< E >& ct = std::use_facet< std::ctype< E > >( in.getloc() );
        for( typename std::basic_istream< E, Traits >::int_type m = in.rdbuf()->sgetc(); ; m = in.rdbuf()->snextc() )
        {
            if( Traits::eq_int_type( Traits::eof(), m ) )
            {
                in.setstate( std::ios_base::eofbit );
                break;
            }
            const E c = Traits::to_char_type( m );
            if( c == in.widen( '\n'  ) )
            {
                in.rdbuf()->sbumpc();   // consume the char (here LF)
                return true;
            }
            if( !skipws_ || !ct.is( std::ctype_base::space, c ) )
                break;          // noskipws || readable char follows
        }
    }
    return false;
}
#endif  // ifndef SAM_IS_ENDL_H_

Gruß Werner

@Edit: typename in Zeile 13 und 18 eingefügt.

Tachyon

Werner Salomon schrieb:

[...]

Du solltest mal einen Artikel zum Thema Streams schreiben, der etwas ins Detail geht. Das wäre echt super.

Euler

Hey sauber, das funzt bestens Vielen Dank an alle Helfer!

Nur noch eine Frage: Bei manchen Dateien liegt der Inhalt in folgender Form vor:

1 5
1 3
2 1
2 3
3 1

Das bedeutet, dass eine Kante zwischen Knoten 1 und 5, eine Kante zwischen Knoten 1 und 3, eine Kante zwischen Knoten 2 und 1, usw. existiert. D.h. beim Einlesen entscheidet immer die linke Zahl, in welches Element vom Hauptvektor die rechte Zahl eingefügt wird.
Dann dürfte doch eure Lösung dennoch funktionieren. Man müsste einfach noch ne Abfrage einbauen, die entscheidet, in welches Hauptvektoren-Element die rechte Zahl eingefügt werden muss, oder?

eher nicht, da zZ die Source-Zeilen-Nr. als Hauptknoten genommen wird. Bei

1 2
1 3 <<-- krachts hier da er das zu Knoten 2 packt.

Lösung wäre hier:
a) ein einheitliches Inputformat
b) eine Vorverarbeitung (falls zB alle Dateien die maximal 2 Zahlen pro Zeile besitzen garantiert in Format2 gespeichert sind, könntest du das ganze File parsen zum testen welches Format genommen wurde und sobald mehr als 2 Zahlen in einer Zeile kommen von vorne mit Format1 importieren und ansonsten Format2 annehmen
c) du schaust mal was es so gibt, zB google "boost graph library tutorial"

Tachyon schrieb:

Werner Salomon schrieb:

[...]

Du solltest mal einen Artikel zum Thema Streams schreiben, der etwas ins Detail geht. Das wäre echt super.

Aber sowas von!

Ingeborg

Ich knabbere gerade selbst an solch einem Problem rum. Ich brauche einen nx2 integer Vector, nur klappt das nicht so wie erhofft. Es gibt immer Inkompatibilitäten die ich nicht verstehe. Ich versuche simpel zwei Integer in einen Vec2i - Vector zu packen. Irgendwie treibt es mich gerade zum Wahnsinn.

[code="cpp"]
vector<Vec2f> corners;
vector<int> v;
int h = 0;
for( int j = 0; j < imgcorner.rows; j++ )
for( int i = 0; i < imgcorner.cols; i++ )
if( imgcorner.at<float>(j,i) > minVal + ( maxVal - minVal )*quality/100 )
{
v.push_back(j);
v.push_back(i);
corners.push_back(v);
v.resize(0);
}
[code="cpp"]

Würd mich über fixe Hilfe freuen.

Grüße,
Inge

SeppJ

Bitte mach für neue Fragen neue Threads auf, anstatt Uraltthreads mit einem vage ähnlichen Thema auszugraben.

Die Formatierungstags musst du mit dem normalen Tag "[tag]" öffnen und mit dem gleichen Tag mit Slash "[/tag]" schließen. Dann klappt es auch mit der Formatierung.

Stell deine Fragen präzise. Es ist unklar, was du mit Inkompatibilitäten meinst. Reiß nicht zu viel Code aus dem Zusammenhang. Am besten ist ein minimales Beispiel, welches sich compilieren lässt (oder eben nicht, wenn es einen Fehler gibt) und dein Problem verdeutlicht, aber nichts anderes enthält. Siehe den ersten und dritten Link in meiner Signatur, wie du selber deine Fragen so stellen kannst, dass dir optimal geholfen werden kann. Nimm das Lesen dieser Links und der Folgelinks ernst, du wirst sehen, dass du dann wesentlich bessere Antworten erhältst.