Pointer auf Datenobjekte in einem vector heap speichern.

Max3000

Hallo alle zusammen.

Ich knüpfe mit der Frage mal an den letzten Thread an den ich eröffnet habe. Dieser hat leider 10 Seiten und darum hier nochmal mein aktuelles Problem.

Ich möchte einen Graphenalgorithmus nach Dijkstra implementieren und dazu den std::vector mit make_heap, push_heap und pop_heap nehmen.

Erstmal lese ich die Daten aus einem File ein, lege dynamisch Vertex-Objekte an und speichere die Pointer in einem std::vector.

Dann will ich noch einen std::vector, der dann meine Priority-Queue sein soll.
Wichtig ist, ich muss einmal auf ein Element in der Mitte des vectors zugreifen, wesswegen keine std::priotity_queue geht und ich auch nicht die pointer ganz normal reintun möchte.

Hier mein Code:

Die Vertex-Klasse leicht vereinfacht:

class Vertex
{
 public:
  friend class MovableVertex;

  Vertex(int number, double key) : number(number), key(key), state(UNLABELED), pred(NULL), revref(NULL) {}

  int number;
  double key;

  // Zur Übersicht wurde hier etwas weggelassen

  bool operator<(const Vertex &that) const
  {
    return this->key <= that.key;
  }
  friend std::ostream& operator<<(std::ostream &os, const Vertex &v);

  MovableVertex* revref;
};

MovableVertex ist jetzt quasi mein Proxy-Objekt, was einen Pointer zu seinem Vertex hält und diese MovableVertexes sollen dann im Heap gehalten und sortiert werden:

class MovableVertex
{
public:
  MovableVertex(Vertex* vertex) : ref(vertex) 
  {
    assert(vertex != 0);
    assert(ref->revref == 0);
    ref->revref = this;
  }
  ~MovableVertex() 
  {
    if(ref != 0)// && this == ref->revref (das sollte eigentlich immer erfüllt sein, ist es aber nicht
      {
	ref->revref = 0;
      }
  }

  MovableVertex(MovableVertex&& vertex) : ref(vertex.ref)
  {
    assert(ref != 0);
    assert(&vertex != this);
    ref->revref = this;
    vertex.ref = 0;   
  } 

  MovableVertex& operator=(MovableVertex&& rhs) {
    ref = rhs.ref;
    assert(ref != 0);
    ref->revref = this;
    rhs.ref = 0;        

    return *this;
  } 

  Vertex* ref;

  friend bool operator<(const MovableVertex &v1, const MovableVertex &v2)
  {
    return *v2.ref < *v1.ref;
  }
};

Und hier meine Schleife, in der der Heap geschrieben und gelesen wird:

for(int i = 0; i < v->incomingEdges.size(); i++)
		  {
		    Edge *currentEdge = v->incomingEdges[i];
		    Vertex *headOfCurrentEdge = currentEdge->tail;

		    if(headOfCurrentEdge->state != SCANNED)
		      {
			if(headOfCurrentEdge->state == UNLABELED)
			  {
			    // Insert a vertex with to heap
			    headOfCurrentEdge->state = LABELED;
			    headOfCurrentEdge->pred = v;
			    headOfCurrentEdge->key = v->key + currentEdge->length;

			    heap.push_back(MovableVertex(headOfCurrentEdge));
			    std::push_heap(heap.begin(), heap.end());
			  }
			else if(headOfCurrentEdge->key > v->key + currentEdge->length )
			  {
			    // decrease the key of a vertex with finite key
			    headOfCurrentEdge->pred = v;
			    headOfCurrentEdge->key = v->key + currentEdge->length;

			    std::push_heap(&heap[0], headOfCurrentEdge->revref + 1);
			  }
		      }
		  }

Zur Zeit bekomme ich einen Fehler in der Zeile:

MovableVertex(MovableVertex&& vertex) : ref(vertex.ref)

ref ist zwar nicht 0, aber kann auch nicht als Vertex interpretiert werden.

Sieht von euch vielleicht jemand den Fehler?
Ich verzweifle langsam.

Danke schonmal!

life

Poste doch einfach mal den kompletten Quellcode + Beispieldatei, bei dem der Fehler auftritt. Dann schaue ich es mir später vielleicht mal an..

Ponto

Was für einen Fehler bekommst du? Bist du sicherm dass std::push_heap schon den neuen Standard benutzt?

Max3000

Meinst du mit neuen Standard den mit dem && Referenzen und so?
Den benutzt er denke ich. Da steht im Quellcode jedenfalls was von glibcxx und sowas (z.B. _GLIBCXX_MOVE).

Die Beispieldateien sind so um die 1 MB groß.
Kann ich dir das irgendwie per Mail schicken?

Das wär echt nett wenn du dir das mal anschauen könntest.
Danke.

Max3000

Hab doch noch ne kleine Beispieldatei gefunden.
Hier der komplette Code (bitte verzeiht den Mix aus C und C++, dazu bin ich noch nicht gekommen den zu ändern ^^):

#include <stdlib.h>
#include <fstream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>

#include <boost/progress.hpp>

enum State
{
  LABELED, UNLABELED, SCANNED
};

class MovableVertex;
class Vertex;

/*
 * The edge class which is connecting 2 vertices
 */
class Edge
{
 public:
  Vertex* tail;
  Vertex* head;
  double length;
  double delta;

 Edge(Vertex* tail, Vertex* head, double length) 
   : tail(tail), head(head), length(length) {}
};

class Vertex
{
 public:
  friend class MovableVertex;

  Vertex(int number, double key) : number(number), key(key), state(UNLABELED), pred(NULL), revref(NULL) {}

  std::vector<Edge*> incomingEdges;
  std::vector<Edge*> outgoingEdges; 

  int number;
  double key;

  State state;  

  Vertex *pred;

  void addIncomingEdge(Edge *edge)
  {
    incomingEdges.push_back(edge);
  }
  void addOutgoingEdge(Edge *edge)
  {
    outgoingEdges.push_back(edge);
  }

  bool operator<(const Vertex &that) const
  {
    return this->key <= that.key;
  }

  bool operator>(const Vertex &that) const
  {
    return this->key > that.key;
  }

  friend std::ostream& operator<<(std::ostream &os, const Vertex &v)
  {
    os << "Vertex " << v.number << " (key=" << v.key <<
      ", incoming edges from=";
    for(int i=0; i<v.incomingEdges.size(); ++i)
      os << v.incomingEdges[i]->tail->number << ' ';
    os << ')';
    return os;
  }

  MovableVertex* revref;
};

namespace std
{
  void swap(MovableVertex& v1, MovableVertex& v2)
  {
    std::cout << "Swap\n";
  }

  void move(MovableVertex& v1)
  {
      std::cout << "Move\n";
  }
}

class MovableVertex
{
public:
  MovableVertex(Vertex* vertex) : ref(vertex) 
  {
    assert(vertex != 0);
    assert(ref->revref == 0);
    ref->revref = this;
  }
  ~MovableVertex() 
  {
    std::cout << "Destroyed " << ref->number << std::endl;
    if(ref != 0)// && this == ref->revref)
      {
	ref->revref = 0;
      }
  }
  MovableVertex(const MovableVertex &vertex) : ref(vertex.ref) {
    assert(ref != 0);
    ref->revref = this;
    std::cout << "Copy Constructor\n";
    //vertex.ref = 0;   
  }

  MovableVertex(MovableVertex&& vertex) : ref(vertex.ref)
  {
    std::cout << "Copied " << ref->number << std::endl;
    assert(ref != 0);
    assert(&vertex != this);
    ref->revref = this;
    //vertex.ref = 0;   
  } 

  MovableVertex& operator=(const MovableVertex &rhs) {
    std::cout << "Assigned " << ref->number << std::endl;
    ref = rhs.ref;
    assert(ref != 0);
    ref->revref = this;
    //rhs.ref = 0;        

    return *this;
  } 

  MovableVertex& operator=(MovableVertex&& rhs) {
    ref = rhs.ref;
    assert(ref != 0);
    ref->revref = this;
    rhs.ref = 0;        

    return *this;
  } 

  Vertex* ref;

  friend bool operator<(const MovableVertex &v1, const MovableVertex &v2)
  {
    return v1.ref->key > v2.ref->key;
  }

  friend void std::swap(MovableVertex& v1, MovableVertex& v2);
  friend void std::move(MovableVertex& v1);
};

int main(int argc, char *argv[])
{
	printf("K-Shortest Path Algorithm\n\n");

	/*
		STEP 0: Initialization
	*/
	long n;
	const int repetitions = 1;

	if(argv[1]== NULL)
	{	
		printf("1 Argument required: shortestpath.exe [graph file name]\n");
		printf("Example: ./Dijkstra.exe scotland_big.dat\n");
		return 0;
	}	

	// Define test vertices
	std::vector<Vertex*> vertices;
	std::vector<Edge*> edges;

	// Read source file
	printf("Loading %s\n", argv[1]);
	std::ifstream indat(argv[1]);

	if(indat)
	{
	        indat >> n;

		for(int j=0; j<n-1 ; j++)
		{
			Vertex *v = new Vertex(j, -1);
			vertices.push_back(v);
		}

		printf("Vertices loaded...\n");

		vertices.push_back(new Vertex(n-1, 0)); 
		vertices[n-1]->state = LABELED;

		// Read edges and initialize
		while(!indat.eof())
		{
                        int tail, head, tmp;
			double length;
			indat >> tail >> head >> tmp >> length;

			Edge *edge = new Edge(vertices[tail], vertices[head], length);
			edge->head->addIncomingEdge(edge);
			edge->tail->addOutgoingEdge(edge);
			edges.push_back(edge);
		}	
	}
	else
	{
		printf("Could not open input data...\n");
		return 0;
	}

	printf("Edges loaded...\n");
	printf("Vertices: %d\nEdges: %d\n\n", vertices.size(), edges.size());
	printf("Building shortest path tree...");
	/*
		STEP 1: Shortest Path Tree
	*/

	boost::progress_display progress(repetitions);
	double elapsed = 0;
	for(int i=0; i<repetitions; ++i)
	  {
	    // Set all vertices to unlabeled
	    for(std::vector<Vertex*>::iterator i=vertices.begin(); i!=vertices.end(); ++i)
	      {
		(*i)->state = UNLABELED;
	      }

	    // Here the actual algorithm starts, so start the timer
	    boost::timer tmr;	    

	    std::vector<MovableVertex> heap;
	    heap.reserve(vertices.size());
	    heap.push_back(MovableVertex(vertices[n-1]));

	    bool abort = false;
	    long j = 0;
	    // Scan
	    do
	      {
		// Delete minimum path
		std::pop_heap(heap.begin(), heap.end());
		Vertex *v = heap.back().ref;
		heap.pop_back();

		v->state = SCANNED;

		std::cout << "Scanning vertex " << *v << std::endl;
		for(int i = 0; i < v->incomingEdges.size(); i++)
		  {
		    Edge *currentEdge = v->incomingEdges[i];
		    Vertex *headOfCurrentEdge = currentEdge->tail;

		    if(headOfCurrentEdge->state != SCANNED)
		      {
			if(headOfCurrentEdge->state == UNLABELED)
			  {
			    // Insert a vertex with infinite key
			    headOfCurrentEdge->state = LABELED;
			    headOfCurrentEdge->pred = v;
			    headOfCurrentEdge->key = v->key + currentEdge->length;

			    heap.push_back(MovableVertex(headOfCurrentEdge));
			    std::push_heap(heap.begin(), heap.end());
			  }
			else if(headOfCurrentEdge->key > v->key + currentEdge->length )
			  {
			    // decrease the key of a vertex with finite key
			    headOfCurrentEdge->pred = v;
			    headOfCurrentEdge->key = v->key + currentEdge->length;

			    std::push_heap(&heap[0], headOfCurrentEdge->revref + 1);
			  }
		      }
		  }
	      }
	    while(heap.size() != 0);
	    elapsed += tmr.elapsed();
	    ++progress;
	  }
	std::cout << "\nAlgorithm finished after " << elapsed*1000./repetitions << "ms\n";

	// Print out path
	Vertex *temp = vertices[0];

	if(!temp->pred)
	{
		printf("There exist no s-t paths\n");
		return 0;
	}

	int vertexCount = 0;

	printf("Shortest Path found:\n");
	printf("Distance: %f\n", vertices[0]->key);

	while(temp)
	{
		printf("%d", temp->number);
		temp = temp->pred;
		if(temp)
			printf(" - ");

		vertexCount++;
	}

	printf("\nVertices passed: %d\n", vertexCount);

	return 0;
}

und der Beispielgraph der in einer Textdatei stehen muss und als Programmargument übergeben wird:

Wenn ich noch eine Minimal-Version schicken soll nur bescheid sagen.
Den ganzen Boost-Schnickschnack für Zeitmessung und die Konsolen-Progressbar brauch man ja eigentlich nicht für den Algorithmus.

Vielen Dank.

Max

Max3000

Hab noch ein anderes Beispielfile gebastelt was vielleicht etwas besser ist:

Ponto

1. Eigentlich kann das nicht funktionieren. Du verlässt dich auf Eigenschaften der Implementierung von push_heap. Wenn irgendwo nicht mit std::move gearbeitet wird, so dass eine Kopie erzeugt wird, kannst du dir nicht sicher sein, dass die Version, die im Heap liegt, auch beim Zuweisen von ref gewinnt.

2. Wenn ref im Destruktor NULL sein kann, dann solltest nicht ref->number rausgeben.

3. Da ein Objekt, vom dem per std::move die Daten geholt wurden, immer noch destruiert wird, solltest du ref auf NULL setzen.

4. Sollte nicht incomming und outgoing vertauscht sein?

Max3000

1. Da könntest du recht haben aber das ist die einzige Lösung die wir im letzten Thread gefunden haben. Eigentlich brauch ich ja nur ein Paar Objekte die hintereinander im Speicher liegen, damit die push_heap(&heap[0], headOfCurrentEdge)-Operation funktioniert. Wenn du eine andere Lösung kennst lass es mich wissen

2. Das ist nur ne Debug-Ausgabe und sollte nur zur Überprüfung da sein auf welchen Objekten was ausgeführt wird

3. Hab ich gemacht aber ändert auch nix. Man geht ja davon aus, dass das Objekt nach Aufruf des Destruktors nie wieder verwendet wird.

4. Das ist Ansichtssache ^^. Im eigentlichen Graphen sind die begriffe richtig. Im Dijkstra Algorithmus gehst du ja aber den Weg rückwärts. Fängst beim Ziel an und suchst die alle Knoten die eine Kante ZU dem Ziel haben und so weiter. Die Begriffe sind wirklich etwas verwirrend. headOfCurrentEdge müsste auch eigentlich tailOfCurrentEdge sein.

life

class Vertex
{
public:
	friend class MovableVertex;

	Vertex(int number, double key) : number(number), key(key), state(UNLABELED), pred(NULL), revref(NULL) {}

	std::vector<Edge*> incomingEdges;
	std::vector<Edge*> outgoingEdges;

	int number;
	double key;

	State state;  

	Vertex *pred;

	void addIncomingEdge(Edge *edge)
	{
		incomingEdges.push_back(edge);
	}
	void addOutgoingEdge(Edge *edge)
	{
		outgoingEdges.push_back(edge);
	}

	bool operator<(const Vertex &that) const
	{
		//TODO: operator< sollte nicht mit '<=' vergleichen
		return this->key <= that.key;
	}

	bool operator>(const Vertex &that) const
	{
		return this->key > that.key;
	}

	friend std::ostream& operator<<(std::ostream &os, const Vertex &v)
	{
		os << "Vertex " << v.number << " (key=" << v.key <<
			", incoming edges from=";
		for(int i=0; i<v.incomingEdges.size(); ++i)
			os << v.incomingEdges[i]->tail->number << ' ';
		os << ')';
		return os;
	}

	MovableVertex* revref;
};

class MovableVertex
{
public:
	MovableVertex(Vertex* vertex) : ref(vertex)
	{
		assert(vertex != 0);
		assert(ref->revref == 0);
		ref->revref = this;
	}
	~MovableVertex()
	{
		if(ref != 0)
		{
			assert(this == ref->revref);
			std::cout << "Destroyed " << ref->number << std::endl;
			ref->revref = 0;
		}
	}

	MovableVertex(MovableVertex&& vertex) : ref(vertex.ref)
	{
		std::cout << "Copied " << ref->number << std::endl;
		assert(ref != 0);
		assert(&vertex != this);
		ref->revref = this;
		vertex.ref = 0;  
	}

	MovableVertex& operator=(MovableVertex&& rhs) {
		if(ref != 0)
			ref->revref = 0;
		ref = rhs.ref;
		assert(ref != 0);
		ref->revref = this;
		rhs.ref = 0;        

		return *this;
	}

	friend bool operator<(const MovableVertex &v1, const MovableVertex &v2)
	{
		//TODO: operator< sollte nicht mit '>' vergleichen
		return v1.ref->key > v2.ref->key;
	}

	Vertex* ref;

private:
	MovableVertex(const MovableVertex &vertex) {
		//MovableVertex is not copyable but only moveable
		assert(false);
	}

	MovableVertex& operator=(const MovableVertex &rhs) {
		//MovableVertex is not copyable but only moveable
		assert(false);
	}	
};

So funktionieren beide Eingabedateien bei mir (VS2010).

Ponto

Max3000 schrieb:

1. Da könntest du recht haben aber das ist die einzige Lösung die wir im letzten Thread gefunden haben. Eigentlich brauch ich ja nur ein Paar Objekte die hintereinander im Speicher liegen, damit die push_heap(&heap[0], headOfCurrentEdge)-Operation funktioniert. Wenn du eine andere Lösung kennst lass es mich wissen

Eigener Heap. Sollte weniger Code als MovableVertex haben.

Max3000

Klappt bei mir leider nicht :(.
Ich nutze gcc 4.4.1. werd aber gleich mal andere Versionen ausprobieren.
Bei mir wird eine Assertion ausgelöst:

DijkstraBinary: DijkstraBinary.cpp:186: MovableVertex& MovableVertex::operator=(MovableVertex&&): Assertion `ref != 0' failed.

Gleich die erste im Copy-Assignment.

Das passiert gleich im pop_heap, dann wird kopiert und dann assigned und da kommt der Fehler. Und zwar meine Debug ausgabe:

POP_HEAP

Copied 6 from 0x60dac0 to 0x7fffffffd920

Program received signal SIGSEGV, Segmentation fault.
0x00000000004029f8 in MovableVertex::operator= (this=0x60dac0, rhs=...) at DijkstraBinary.cpp:186

und der Debugger sagt an dieser Stelle:

(gdb) print this
$7 = (MovableVertex * const) 0x60dac0
(gdb) print &rhs
$8 = (MovableVertex 0x60dac0

also wird ein Movable Vertex sich selbst zugewiesen.
Wie kann man sowas am besten abfragen? In dem Fall sollte ja dann gar nix passieren oder?

Max3000

OK ich hab den CopyAssignment Operator mal wie folgt geändert:

MovableVertex& operator=(MovableVertex&& rhs) {

      if(&rhs == this)
	{
	  std::cout << "Assigning this. No action required\n";
	  return *this;
	}
      std::cout << "Assigned " << rhs.ref->number << " from " << &rhs << " to " << this << std::endl;
      if(ref != 0)
	ref->revref = 0;
      ref = rhs.ref;
      assert(ref != 0);
      ref->revref = this;
      rhs.ref = 0;        
      return *this;
    }

Und siehe da... es klappt. Der Fall &rhs==this tritt zwar bei mir nur beim ersten pop_heap auf aber dem werde ich noch auf den Grund gehen.

Vielen Dank nochmal an alle die sich die Zeit genommen haben.
Besonders an life der sich noch die Mühe gemacht hat das auszuprobieren.

Ponto

Die Assertion ist einfach falsch. Du musst einfach damit umgehen können, dass ref == NULL ist. Sowas kann ja leicht passieren.

life

Ponto schrieb:

Die Assertion ist einfach falsch. Du musst einfach damit umgehen können, dass ref == NULL ist. Sowas kann ja leicht passieren.

Ach ja? Wie denn?

Ponto

life schrieb:

Ponto schrieb:

Die Assertion ist einfach falsch. Du musst einfach damit umgehen können, dass ref == NULL ist. Sowas kann ja leicht passieren.

Ach ja? Wie denn?

Offensichtlich passiert es.

Irgendwas in der Art:

MovableVertex tmp = std::move(a);

a = std::move(a);

Selbstzuweisung ist natürlich auch etwas, was man beachten muss.

life

Du kannst aber nicht a in zwei Objekte moven. Das dürfte UB o.Ä. sein (müsste man sich mal den neuen Standard anschauen).

Ein Objekt in sich selbst moven finde ich auch noch etwas merkwürdig. Keine Ahnung was die g++ STL da treibt..

Ponto

life schrieb:

Du kannst aber nicht a in zwei Objekte moven. Das dürfte UB o.Ä. sein (müsste man sich mal den neuen Standard anschauen).

Ein Objekt in sich selbst moven finde ich auch noch etwas merkwürdig. Keine Ahnung was die g++ STL da treibt..

Glaube ich nicht. std::move zerstört ja nicht die Source.

life

move ist ein "potentially destructive read". Es verschiebt eben nur die Daten von a nach tmp . Anschließend kann man nicht erwarten, dass die Daten noch in a enthalten sind. Ein weiteres move von a zu irgendwoanders hin macht daher imho keinen Sinn.

Aber da müsste man mal jemanden fragen, der sich schon mehr mit dem neuen Standard beschäftigt hat. Ggf. ist es zwar sinnfrei zweimal hintereinander move vom gleichen Objekt aus auszuführen, aber nicht undefiniert. Wenn das im der g++ STL passiert, würde ich aber in jedem Fall von einem Bug ausgehen.

Max3000 schrieb:

OK ich hab den CopyAssignment Operator mal wie folgt geändert:
MovableVertex& operator=(MovableVertex&& rhs) {

Der nennt sich aber "Move-Assignment Operator".

Eventuell ist der Copy-&-Swap-Trick eleganter.

life schrieb:

move ist ein "potentially destructive read". Es verschiebt eben nur die Daten von a nach tmp . Anschließend kann man nicht erwarten, dass die Daten noch in a enthalten sind. Ein weiteres move von a zu irgendwoanders hin macht daher imho keinen Sinn.

Aber da müsste man mal jemanden fragen, der sich schon mehr mit dem neuen Standard beschäftigt hat. Ggf. ist es zwar sinnfrei zweimal hintereinander move vom gleichen Objekt aus auszuführen, aber nicht undefiniert. Wenn das im der g++ STL passiert, würde ich aber in jedem Fall von einem Bug ausgehen.

Da muss man jetzt vorsichtig sein: Die Funktion move alleine verschiebt/kopiert nichts. Sie wird benutzt, um zu sagen "Dieses Objekt interessiert mich nicht mehr, es darf verändert werden." Das einzige, was sie tut, ist einen Lvalue-Ausdruck in einen Rvalue-Ausdruck zu verwandeln. Das, was die Funktion zurückgibt ist eine Referenz auf dasselbe Objekt. Nur es ist dann eine Rvalue-Referenz. Der potentiell destruktive Teil passiert erst im Move-Konstruktor, Move-Zuweisungs-Operator (oder sonst eine Funktion, die eine non-const Rvalue-Referenz annimmt). Und wenn ein Move-Konstruktor bzw Move-Assignment-Operator das Quellobjekt "geplündert" hat, dann kann man das Quellobjekt später immer noch benutzen. Also,

vector<int> v1 = ...;
vector<int> v2 = move(v1);
vector<int> v3 = move(v1);

macht zwar nicht viel Sinn, aber alle drei Vektoren werden in einem gültigen Zustand sein. Der Move-Konstruktor beim Initialisieren von v2 wird aber wahrscheinlich sich die Elemente aus v1 geklaut haben, so dass v1 ab der zweiten Zeile ein leerer Vektor ist. Aber in welchem Zustand der genau ist, ist ja nicht so wichtig. Ein passender Name für move könnte "idontcareanymore" sein.

life

Also "sinnfrei, aber nicht undefiniert". Ich bezweifle daher immer noch, dass sowas wie

vector<int> v1 = ...;
vector<int> v2 = move(v1);
vector<int> v3 = move(v1);

im STL-Quellcode vorkommt.

btw. @krümelkacker: Wie sieht es denn mit einer Selbst-Move-Zuweisung aus? Ist die erlaubt? Edit: Zumindest bei der VS2010-STL wird eine Selbstzuweisung explizit abgefangen im Move-Assignment Operator von vector . Also wird man das wohl brauchen..