3. Distanzgraph einlesen + Klasse erstellen

Distanzgraph einlesen + Klasse erstellen

  • D

    Hallo zusammen,

    meine Aufgabe ist es, den Algorithmus von Dijkstra zu implementieren.
    Mit diesem soll in einem gegebenen Distanzgraphen von einem Knoten aus
    die kürzesten Wege zu den übrigen Knoten berechnet werden.

    Ich weiß jedoch nicht, wie ich die gegebenen Dateien einlese:

    Als Beispiel: "Graph1.dat"

    4
    5

    0 1 2.0
    0 2 1.5
    1 0 1.0
    1 2 3.0
    3 1 1.0

    Das Eingabeformat ist dabei wie folgt festgelegt: Als erstes kommen die Anzahl der Knoten 𝑁 und die Anzahl der Kanten |𝐸|, anschließend folgen für jede Kante 𝑒 des Graphen der Start- und der Endknoten sowie die Kosten 𝛽(𝑒).

    Das Problem liegt für mich darin, dass sich die ersten beiden Zeilen von den
    übrigen unterscheiden.
    Anderenfalls hätte ich mir den Eingabeoperator wie folgt definiert:

    std::istream& operator>> ( std::istream& s, DistGraph& g)
{
    s >> g.Start >> g.Ende >> g.Kosten;
    return s;
}

    Nur wie handhabe ich nun die ersten beiden Zeilen 😕

    Für's Einlesen habe ich mir überlegt eine Template-Funktion zu wählen

    template<typename ???>
void einlesen( std::ifstream& ifs, /*std::unordered_map<...>& daten ??*/)
{

	while (!ifs.eof())
	{
		ifs >> daten;
		if(!ifs.fail())
			//...
	}

}

    Wäre sehr dankbar, wenn mir jemand mit Tipps zur Seite stehen könnte 😃
    Bin ein absoluter Anfänger in C++

    0
  • Mod

    Du liest es eben einfach am Anfang ein, wo ist das Problem?

    stream >> anzahl_knoten >> anzahl_kanten;
while (stream >> kante)
  graph.füge_kante_ein(kante);

// eventuell prüfen, ob Anzahl der Knoten und Kanten passt

    Ein paar Dinge, die mir an deinem Code auffallen:

    std::istream& operator>> ( std::istream& s, DistGraph& g)
{
    s >> g.Start >> g.Ende >> g.Kosten;
    return s;
}

    Deine Klasse für die Kante scheint dumm benannt zu sein.

    Für's Einlesen habe ich mir überlegt eine Template-Funktion zu wählen

    Wieso nicht so wie oben, mit einem operator>>, aber eben für deine Graphenklasse? Im Prinzip ist mein Codebeispiel schon der fast fertige operator>> für den Graphen.

    while (!ifs.eof())
    {
        ifs >> daten;
        if(!ifs.fail())
            //...
    }

    Kommt dir das nicht ein wenig umständlich vor? Erst prüfst du auf Fehler, dann liest du, dann prüfst du auf Fehler, dann verarbeitest du, dann wieder von vorne. Da ist doch eine Prüfung total überflüssig. Warum nicht: Lesen, Prüfen, Verarbeiten? Siehe, wie ich das oben in meinem Pseudocode gemacht habe.

    0
  • D

    Das Ganze soll mittels einer Klasse 'DistGraph' implementiert werden.

    Und diese Klasse muss (meiner Meinung nach) fünf Attribute aufweisen:

    int knoten, kanten, start, ende;
double kosten;

    Und hier versteh' ich nun nicht wie ich mittels operator>>
    die erste Zeile als Anzahl 'knoten', die zweite als Anzahl
    'kanten', und die restlichen Zeilen eben als 'start' 'ende' 'kosten'.

    SeppJ schrieb:

    while (!ifs.eof())
    {
        ifs >> daten;
        if(!ifs.fail())
            //...
    }

    Kommt dir das nicht ein wenig umständlich vor? Erst prüfst du auf Fehler, dann liest du, dann prüfst du auf Fehler, dann verarbeitest du, dann wieder von vorne. Da ist doch eine Prüfung total überflüssig. Warum nicht: Lesen, Prüfen, Verarbeiten? Siehe, wie ich das oben in meinem Pseudocode gemacht habe.

    Nunja, in meinem letzten Programm habe ich zuerst nur mit

    while (!ifs.eof())

    gearbeitet. Dann wurde die letzte Zeile der .txt Datei jedoch immer doppelt eingelesen. Die zweite Prüfung hat das Problem gelöst.

    0
  • S

    danooh schrieb:

    Das Ganze soll mittels einer Klasse 'DistGraph' implementiert werden.

    Und diese Klasse muss (meiner Meinung nach) fünf Attribute aufweisen:

    int knoten, kanten, start, ende;
double kosten;

    Das kommt aber nicht so ganz hin.

    Offenbar willst du einen Graphen mit Knotengewichten/kosten modellieren. Ein Graph besteht dabei aus n Knoten und m Kanten (die ersten 2 Zahlend einer Datei). Jede Kante wiederum besteht aus einem Start- und einem Endknoten und einem Gewicht (die folgenden zeilen deiner Datei).

    D.h. du willst deinen Graph einlesen, was beinhaltet, dass du im Zuge dessen Kanten einliest.

    Ich würde das in etwa so machen:

    #include <fstream>
#include <vector>
#include <algorithm>
#include <iterator>

class Edge
{
	std::size_t start;
	std::size_t end;
	double weight;

public:
	friend std::istream& operator >>(std::istream & is, Edge & e)
	{
		is >> e.start >> e.end >> e.weight;
		return is;
	}
};

class Graph
{
	std::size_t vertices;
	std::vector<Edge> edges;

public:
	friend std::istream& operator >>(std::istream & is, Graph & e)
	{
		std::size_t edgeCount;
		is >> e.vertices >> edgeCount;

		e.edges.resize(edgeCount);
		std::copy_n(std::istream_iterator<Edge>(is), edgeCount, std::begin(e.edges));

		return is;
	}
};

int main()
{
	std::ifstream file("graph.txt");

	Graph g;

	file >> g;

	return 0;
}
    0
Anmelden zum Antworten