Heap und std::vector und das ganze auf Pointern

[Max3000]

headOfCurrentEdge->key = v->key + currentEdge->length;
push_heap(&heap[0], (&headOfCurrentEdge)+1, comp);

Das geht leider nicht.
heap ist ein std::vector und das push_heap und alle anderen heap-funktionen wollen einen iterator über meinen vector als argument.
statt &heap[0] sollte also heap.begin() sein.
statt (&headOfCurrentEdge)+1 brauch ich doch sowas wie heap.begin()+positionOfHeadOfEdge+1, oder nicht?

Hab sowieso grad mit diesen Iteratoren zu kämpfen und ich nie weiß an welcher stelle mein Element in der Liste ist.
Das selbe versuch ich grad mit erase, also als kleines Beispiel:

Node<T> *minRoot;
  std::vector<Node<T>*> roots;

  // ...

  roots.erase(minRoot); // wie mach ich sowas?

Also minRoot ist dann in der roots-Liste, aber ich weiß später nicht mehr wo weil ich zuviel hinzufüge.
Der Aufruf erase ist natürlich falsch, weil die Funktion einen Iterator benötigt.

[life]

Doch das geht so. Probiers doch einfach mal aus.

Abgesehen davon, dass es kompiliert, ist es sogar korrekt: Es ist garantiert, dass die Elemente des vectors direkt hintereinander im Speicher stehen.

Entsprechend kannst du auch die Position eines Elements folgendermaßen erhalten: std::size_t pos = &my_element - &my_vector[0] .

[Max3000]

Das minRoot ist aber auch ein Pointer. Könnte es daran liegen?
Ich bekomme den Fehler:

error: no matching function for call to ‘std::vector<Node<Vertex>, std::allocator<Node<Vertex>> >::erase(Node<Vertex>**)’

[life]

Ich bezog mich auf push_heap . erase benötigt tatsächlich einen Iterator.

[volkard]

life schrieb:

Doch das geht so. Probiers doch einfach mal aus.

Abgesehen davon, dass es kompiliert, ist es sogar korrekt: Es ist garantiert, dass die Elemente des vectors direkt hintereinander im Speicher stehen.

Entsprechend kannst du auch die Position eines Elements folgendermaßen erhalten: std::size_t pos = &my_element - &my_vector[0] .

Wenn ich recht verstanden habe, kommt er deswegen nicht dran:

Node* hierGuck=vec[0];
pop_heap(vec.begin(),vec.end(),comp);vec.pop_back();
for each Node* dortMach in hierGuck.getNeighbors(){
   dortMach->neuBewert();
   push_heap(vec.begin(),/*mistWoLiegtDennDortMach?*/);
}

[Max3000]

Genau das ist mein Problem ;).
Vielleicht nehm ich ja auch die falsche Datenstruktur?
Ich bräuchte ne verlinkte Liste, wobei ich ein beliebiges Element daraus löschen kann. Dazu müsste ich die Pointer zu den Nachbarn kennen. Also gibts da irgendeinen STL Datentyp, z.b. List mit ListNode, von der ich erben könnte oder sowas? Man könnte sich das zwar selber programmieren, aber das wird sicherlich sehr aufwendig wenn mans ordentlich macht und nicht so schnell wie so ein STL Typ, oder?

[volkard]

Max3000 schrieb:

Genau das ist mein Problem ;).
Vielleicht nehm ich ja auch die falsche Datenstruktur?
Ich bräuchte ne verlinkte Liste, wobei ich ein beliebiges Element daraus löschen kann. Dazu müsste ich die Pointer zu den Nachbarn kennen. Also gibts da irgendeinen STL Datentyp, z.b. List mit ListNode, von der ich erben könnte oder sowas? Man könnte sich das zwar selber programmieren, aber das wird sicherlich sehr aufwendig wenn mans ordentlich macht und nicht so schnell wie so ein STL Typ, oder?

Das Problem ist, daß Du keine Zeiger auf Nodes nehmen kannst, wenn Du zugleich die Nodes im binären Heap verschieben könen willst.
Da fallen mir auch irgendwie nur häßliche Tricks ein.
Zum Beispiel der:
Du verwaltest nicht Node* im heap, sondern

struct MovableNodePrt{
  Node* ptr;
  MovableNodePrt(Node* p){
    assert(p->revptr==0);//zwei MovableNodePrts für einen Node böse sein
    ptr=p;
    ptr->revptr=this;
  }
  ~MovableNodePrt(){
    ptr->revptr=0;
  }
  friend void swap(MovableNodePrt& a,MovableNodePrt& b){
     swap(a.ptr,b.ptr);
     swap(a.ptr->revptr,a.ptr->revptr);//Damit die Nodes ihren MovableNodePrt im heap 
  //nicht vergessen
  }
  friend bool operator<(MovableNodePrt const& a,MovableNodePrt const& b){
    return *a.ptr<*b.ptr;//juhu, wir sind comp losgeworden
  }
};

Oder Nodes swappeble machen und evtl eine (globale?) Indextabelle dazwischenschalten, auf den der Comparator zugreift. Oder den binären Heap zwar binär lassen aber nicht mehr in ein Array legen, sondern als normalen Baum, allerdings Heap und nicht Sortierbaum. Alles recht unhandlich.

[Max3000]

Was macht das swap? Wird das intern von dem vector bzw. den heap-funktionen aufgerufen?

Ich habe hier noch das gefunden:
http://www.cplusplus.com/reference/stl/list/

Da kann man ein erase(value) machen.
Die Frage ist nur was passiert im Hintergrund?
Irgendwie muss der dann ja auch erstmal sein node-Element für den Wert finden oder?

[life]

Am einfachsten wärs wohl in der Node zu speichern, wo die Node im Heap liegt. Problem ist nur, dass man diese Info updaten muss, wenn man push_heap etc aufruft. -> push_heap müsste man selbst implementieren

Also vielleicht doch lieber volkards Lösung ;).

[Max3000]

Was ist revptr?
Versuch das ganze grad noch zu verstehen ;).
Aber vielen Dank schonmal. Ich glaube auch dass es anders gar nicht mehr geht.

[volkard]

Max3000 schrieb:

Was macht das swap? Wird das intern von dem vector bzw. den heap-funktionen aufgerufen?

Ja.
Um sicherzugehen noch den Kopierkostruktor wegmachen. Ich editier's oben rein. Dann KANN nur noch swap benutzt werden und DU hast die Garantie, daß alles klappt. Nee, ohne Kopierkonstruktor kein push_back. Oh. Also auch temporär zwei MoveableNodes für einen Node. *heul*

[Max3000]

Hab ich das jetzt richtig verstanden, dass ich dann sowas machen kann:

std::vector<Node> nodes;
// ... Nodes einlesen

std::vector<MovableNodePrt> heap;
heap.push_back(MovableNodePrt(nodes.at(0));
heap.push_back(MovableNodePrt(nodes.at(2));
//...
Node* myNode = /*irgendwoher*/;
node->key = /*irgendwas kleineres*/
heap_push(heap.begin(), (&myNode->revref)+1);

revref ist der Pointer von Node auf MocableNodePrt.
Hab ich das richtig verstanden?

[volkard]

Max3000 schrieb:

Hab ich das richtig verstanden?

Ja.

[Max3000]

Aber ich brauch doch einen iterator und keinen MovableNodePrt*. Das versteh ich noch nicht so ganz.

[volkard]

Max3000 schrieb:

Aber ich brauch doch einen iterator und keinen MovableNodePrt*. Das versteh ich noch nicht so ganz.

Ein Iterator ist was, was sich wie ein Zeiger anfühlt. Insbesondere ist ein Zeiger ein Iterator.
Aber kannst auch &heap[0],&heap[revptr-heap.begin()] machen statt &heap[0],revptr
oder heap.begin(),heap.begin()+(revptr-heap.begin()) ? Viele Wege von Rom weg.

[life]

@volkard: Das hier kompiliert zumindest mit VS2010:

#include <assert.h>
#include <algorithm>
#include <vector>
#include <iostream>

struct MovableNodePrt;

class Node {
public:
    MovableNodePrt* revptr;
    int key;
    //etc   
};

struct MovableNodePrt  {
    Node* ptr;

    MovableNodePrt() : ptr(0) {
       assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this);
    }

    MovableNodePrt(MovableNodePrt&& rhs) : ptr(rhs.ptr) {
        if(ptr != 0) {			
            ptr->revptr = this;
		}
        rhs.ptr = 0;
		assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this);
		assert(rhs.ptr == 0 || rhs.ptr->revptr == 0 || rhs.ptr->revptr == this);
    }

	MovableNodePrt& operator=(MovableNodePrt&& rhs) {
		ptr = rhs.ptr;
		if(ptr != 0) {			
            ptr->revptr = this;
		}
        rhs.ptr = 0;
		assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this);
		assert(rhs.ptr == 0 || rhs.ptr->revptr == 0 || rhs.ptr->revptr == this);
		return *this;
	}

    ~MovableNodePrt(){
		assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this);
        if(ptr != 0) {            
            ptr->revptr=0;
        }
    }

    void initPointer(Node* ptr) {
        assert(this->ptr == 0);
        this->ptr = ptr;
        assert(ptr->revptr==0);//zwei MovableNodePrts für einen Node böse sein
        ptr->revptr = this;
		assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this);
    }

    friend bool operator<(MovableNodePrt const& a,MovableNodePrt const& b){
        return a.ptr->key<b.ptr->key;//juhu, wir sind comp losgeworden
    }

private:
    MovableNodePrt(const MovableNodePrt& rhs) {
        assert(false);       
    }

	MovableNodePrt operator=(const MovableNodePrt& rhs) {
		assert(false);
	}

};

int main() {   
    std::vector<Node> nodes(42);
    std::vector<MovableNodePrt> heap(42);   
    for(std::size_t i = 0; i < heap.size(); ++i) {
        heap[i].initPointer(&nodes[i]);
    }
    std::make_heap(heap.begin(), heap.end());
    std::pop_heap(heap.begin(), heap.end());
    heap.pop_back();
    std::push_heap(heap.begin(), heap.end());
}

[Max3000]

Irgendwie funktioniert das nicht.
Ich schicke jetzt einfach mal den kompletten Code.
Das swap und Speicherfreigabe hab ich noch nicht mit drin.
Wollt das mal Schritt für Schritt machen, aber bekomme Compilerfehler:

DijkstraBinary.cpp:224: error: no matching function for call to ‘push_heap(__gnu_cxx::__normal_iterator<MovableVertex*, std::vector<MovableVertex, std::allocator<MovableVertex> > >, MovableVertex**)’

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

#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) {}
  Vertex(const Vertex &that)
  {
    std::cout << "Copy constructor\n";
  }

  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->key << ' ';
    os << ')';
    return os;
  }

  MovableVertex* revref;
};

class MovableVertex
{
public:
  MovableVertex(Vertex* vertex) : ref(vertex) {ref->revref = this;}
  Vertex* ref;

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

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

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

	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.push_back(MovableVertex(vertices[n-1]));

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

		v->state = SCANNED;

		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));
			    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;

			    push_heap(heap.begin(), &(headOfCurrentEdge->revref) + 1); // HIER IST DER FEHLER!!!
			  }
		      }
		  }
	      }
	    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;
}

[life]

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

[Max3000]

Kann mir das mal bitte jemand erklären?
Mit

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

bekomm ich ‘push_heap’ was not declared in this scope

Mit

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

Gehts dann?
Ist im STD namespace ein anderes push_heap?

[life]

Darüber bin ich auch gerade gestolpert. Warum ist push_heap überhaupt im global namespace sichtbar? std::push_heap sollte jedenfalls das richtige sein..