Boost und Dijkstra [solved]



  • Hallo,

    ich hoffe ich bin hier richtig und ev. hat jmd schon mit BGL Erfahrungen.
    Ich hab bereits einen Graphen definiert, jedoch weiß ich nun nicht, warum ich dijkstra_shortest_paths nicht anwenden kann...

    Hier mein Code,
    danke im Voraus

    #include "boost/config.hpp"
    #include <iostream>
    #include <fstream>
    
    #include "boost/graph/graph_traits.hpp"
    #include "boost/graph/adjacency_list.hpp"
    #include "boost/graph/dijkstra_shortest_paths.hpp"
    
    using namespace std;
    using namespace boost;
    
    typedef enum {
    	ePositive,
     	eNegative
    } EdgeDirection_t;
    
    struct EdgeProperties {
    	uint8_t level;
    	uint16_t length;
    	uint8_t angle;
    	EdgeDirection_t direction;
    };
    
    struct VertexProperties {
    	uint32_t index;
    	uint32_t id;
    	uint8_t level;
    };
    
    // define type for graph types
    typedef adjacency_list <vecS , listS, directedS, VertexProperties, EdgeProperties> Graph;
    
    int main(int argc, char** argv)
    {
    	Graph graph;
    
    	property_map<Graph, uint32_t VertexProperties::*>::type vIndex = get(&VertexProperties::index, graph);
    	property_map<Graph, uint32_t VertexProperties::*>::type vId = get(&VertexProperties::id, graph);
    	property_map<Graph, uint8_t VertexProperties::*>::type vLevel = get(&VertexProperties::level, graph);
    
    	typedef graph_traits<Graph>::vertex_descriptor Vertex;
    	Vertex v1, v2;
    	v1 = add_vertex(graph);
    	vIndex[v1] = 0;
    	vId[v1] = 1;
    	vLevel[v1] = 1;
    
    	v2 = add_vertex(graph);
    	vIndex[v2] = 1;
    	vId[v2] = 2;
    	vLevel[v2] = 1;
    
    	EdgeProperties e1;
    	e1.level = 10;
    	e1.length = 2000;
    	e1.angle = 90;
    	e1.direction = ePositive;
    	add_edge(v1, v2, e1, graph);
    
    	typedef graph_traits<Graph>::vertex_descriptor VertexDescriptor;
    	std::vector<VertexDescriptor> p(num_vertices(graph));
    	std::vector<int> d(num_vertices(graph));
    
    // HIER IST DAS PROBLEM
    // KEINE DER BEIDEN ZEILEN FUNKTIONIERT - und ich weiß nicht warum ;(
    	//dijkstra_shortest_paths(graph, v1, predecessor_map(&p[0]).distance_map(&d[0]));
    	dijkstra_shortest_paths(graph, v1,
    		vertex_index_map(vIndex).
    		predecessor_map(&p[0]).
    		weight_map(get(&EdgeProperties::length, graph)).
    		distance_map(&d[0])
    	);
    
    	exit(EXIT_SUCCESS);
    }
    


  • hey,

    hier die auflösung:

    typedef adjacency_list <vecS , listS, directedS, VertexProperties, EdgeProperties> Graph;

    listS darf bei der VertexList nicht angegeben werden. Es muss vecS verwendet werden (sofern man keine argen Umwege machen möchte).



  • hephaistos6 schrieb:

    hey,

    hier die auflösung:

    typedef adjacency_list <vecS , listS, directedS, VertexProperties, EdgeProperties> Graph;

    listS darf bei der VertexList nicht angegeben werden. Es muss vecS verwendet werden (sofern man keine argen Umwege machen möchte).

    jo, sonst mußt Du die Knoten selbst nummerieren, damit im Algorithmus schnell auf zu die Daten zu den Knoten zugegriffen werden kann. Das kannst Du erledigen, indem Du Deinen Knoten einer vertex_index-property mitgibst, die ein int ist und du dafür sorgst, dass bei n knoten jede der zahlen 0..n-1 genau einem knoten zugeordnet ist.


Log in to reply