3. Boost Graph und AStar_Search

Boost Graph und AStar_Search

  • S

    Hallo zusammen,

    ich habe eine Frage zum Thema des in der Boost Graph Library implementierten A*-Algorithmus'. Genauer gesagt zu der Anwendung.

    In dem entsprechenden Beispielcode von Boost besteht der Graph aus

    typedef adjacency_list<listS, vecS, undirectedS, no_property, property<edge_weight_t, cost> > mygraph_t; // Zeile 73

    Das bedeutet, die Vertizes haben keinerlei Eigenschaft oder Besitz (4. Parameter = no_property) und die Kanten halten "cost" als Eigenschaft (was oben als nichts anderes als ein float getypedeft ist).

    Frage 1: Wie ist das mit der (oder heisst es die oder das Property??) Property?
    Wenn ich das Richtig verstanden habe kann ich später mit

    boost::get(edge_weight, someGraphObject)

    auf eine Map von allen kanten und den dazugehörigen cost's zugreifen ?!

    Frage 2: Wenn Frage 1 von mir richtig verstanden ist, wie kann ich dann das Gewicht (also den Wert) einer einzelnen Kante belegen (sprich ihr einen Wert von mir geben)? Geht das nur über eben diese property_map? Und wenn ja, woher weiss dann der Graph den Wert? oder synchronisieren diese beiden Strukturen sich gegenseitig?

    Das Boost Beispiel zum A-Stern ist ja noch so halbwegs zu begreifen (für mich).
    Aber wie muss der Graph-typedef aussehen, wenn ich meine eigenen Strukturen für Knoten und Kanten einsetzen will?

    Bisher habe ich laut Vertex folgendes gemacht:

    struct MyVertex 
{
    int a;
    float b;
    // some shit
};
struct MyEdge
{
    int a;
    float b;
    // some shit
};
typedef adjacency_list<listS, vecS, undirectedS, MyVertex, MyEdge> mygraph_t;

    Darauf baut auch mein bisheriges Programm auf.

    Und jetzt will ich A-Stern auf meinen Graphen anwenden. Wo sind die Knackpunkte? Ich meine, es kompiliert nichtmals bei mir...

    Ich werde jetzt ein kleines Beispiel zusammenzuschustern versuchen und das später posten...

    0
  • N

    Als ich mal etwas mit Graphen machen musste und Boost.Graph angeschaut habe, fand ich das API die Hölle. Der Generizitätswahnsinn und die schlecht dokumentierten und impliziten Konzepte (im Gegensatz zu Typen, die man im Code nachschauen könnte) machen es meiner Meinung nach sehr schwer, vernünftig mit der Bibliothek zu arbeiten.

    Dazumals habe ich mir LEMON heruntergeladen, und alles war wunderbar einfach und sauber. Könntest du dir eventuell auch mal anschauen. In letzter Zeit scheint die Bibliothek allerdings nicht mehr aktiv entwickelt zu werden.

    A* gibts scheinbar nicht nativ in LEMON, allerdings könnte das (Link von hier) interessant sein.

    0
  • S

    What??
    Ich dachte, die Architektur, die Generizität und die Konzepte hinter Boost.Graph sind sehr gut? Implying ich versteh solche Sachen einfach nur schlecht und bin dumm oO

    0
  • S

    So, ich habe hier etwas Code:

    #include <boost\graph\adjacency_list.hpp>
#include <boost\graph\astar_search.hpp>
#include <cassert>
#include <iostream>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS> mygraph_t;

struct Goal_Found_Ex {};

template<class Vertex>
struct astar_vis : public boost::default_astar_visitor
{
	astar_vis(Vertex goal)
		: m_goal(goal)
	{ }

	template<typename Graph>
	void examine_vertex(Vertex v, Graph const& g)
	{
		if ( v == m_goal )
			throw Goal_Found_Ex();
	}

	Vertex m_goal;
};

int main()
{
	mygraph_t graph;

	mygraph_t::vertex_descriptor aVertex = boost::add_vertex(graph);
	mygraph_t::vertex_descriptor bVertex = boost::add_vertex(graph);

	mygraph_t::edge_descriptor edge; bool success;
	boost::tie(edge, success) = boost::add_edge(aVertex, bVertex, graph);
	assert(success);

	try {
		boost::astar_search(graph, aVertex, boost::astar_heuristic<mygraph_t, double>(), 
			boost::visitor(astar_vis<mygraph_t::vertex_descriptor>(aVertex)));
	}
	catch(Goal_Found_Ex gf)
	{
		gf;
		std::cout << "Way found" << std::endl;
		return 0x0;
	}

	std::cout << "Way not found" << std::endl;
	return 0x1;
}

    Natürlich kompiliert dieser nicht. Die Frage ist wieso? Die Fehlermeldungen sagen mir nichts mehr (bei der ganzen Template Magie) und finden auch alle nur noch in den Boost-Dateien statt, von wegen dass die Typen nicht stimmen und dass keine Referenz auf void erzeugt werden kann.

    Ich habe hier einfach mal die Fehler gelistet -> hier

    Hat einer eine Idee, was ich an dem kleinen Quellcode ändern muss, damit er wenigstens kompiliert?

    (Der Sinn ist in dem Miniprogramm ja eh nicht vorhanden...)

    0
  • E

    Skym0sh0 schrieb:

    What??
    Ich dachte, die Architektur, die Generizität und die Konzepte hinter Boost.Graph sind sehr gut? Implying ich versteh solche Sachen einfach nur schlecht und bin dumm oO

    Ich muss sagen dass ich mit Boost.Graph garnichts auf die Reihe gebracht habe - und dir geht's anscheinend genauso. Wird wohl nicht umsonst empfohlen sich das Buch dazu zu kaufen.

    Von daher finde ich die Library einfach nur schlecht - eine gute Library ist nie so schlecht dokumentiert bei gleichzeitig so hohem Scchwierigkeitsgrad.

    0
  • N

    Skym0sh0 schrieb:

    Ich dachte, die Architektur, die Generizität und die Konzepte hinter Boost.Graph sind sehr gut?

    Ich kenne nicht das komplette Design, da es mir relativ schnell zu blöd geworden ist und ich viel zu viel Zeit für die Einarbeitung aufgewendet habe. Boost hat an vielen Orten die Tendenz, mit Generizität zu übertreiben. Sowas halte ich nicht für gut, auch wenn offensichtlich viele Entwickler anderer Meinung sind. Dass mehr Templates in jedem Falle besser sind, scheint zumindest in der Boost-Community zum Dogma erhoben worden zu sein 😉

    Ich glaube schon, dass Boost.Graph mächtig ist, aber dazu muss man die Bibliothek erst mal benutzen können. Ich muss Ethon zustimmen, eine gute API zeichnet sich durch Ausdrucksstärke und Intuitivität aus. Bei Boost.Graph könnte man z.B. nie anhand des Codes herausfinden, wie die Bibliothek zu benutzen ist -- bei LEMON schon. Es fängt ja schon mit der "adjacency_list" an, ohne Dokumentation kann man deren Bedeutung höchstens erahnen.

    Und die API-Komplexität ist auch nicht mit dem Schwierigkeitsgrad der Graphentheorie zu rechtfertigen. Viele Probleme wären grundsätzlich einfach modellierbar, aber die Generizität steht einem unnötigerweise im Weg. LEMON beweist schön, dass es besser geht. Ein Blick darauf kann sich wirklich lohnen.

    0
  • S

    Naja, das Buch habe ich sogar. Speziell auf mein Problem betrachtet bringt mir das jedoch nichts, da der A* erst später dazukam, demnach also in dem Buch nicht erwähnt wird (werden kann, weil das Buch jünger ist).

    Ich mein, einige der Konzepte, die Boost da verwendet, sind echt gut. Vielleicht nicht simpel (zu verstehen), aber schon hart, was alles möglich ist.

    Ok, ich werde mal schauen, ob LEMON für mich in Frage kommt. Zeitlich wird das jetzt sehr knapp, naja egal...

    Aber sonst hat keiner Erfahrungen oder Ideen zu meinem Problem?

    0
  • M

    Skym0sh0 schrieb:

    Aber sonst hat keiner Erfahrungen oder Ideen zu meinem Problem?

    Zumindest keine abweichenden. Bei Boost.Graph habe ich kein Land gesehen. Mit LEMON liefs wunderbar.

    0
  • J

    Du hast keine kantengewicht angegeben. Deswegen wirds implizit mit dem edge_weight_tag versucht, aber so eine property gibts in deinem graph leider auch nicht.

    Vielleicht hilft dir das bsp. Aus der doku? http://www.boost.org/doc/libs/1_53_0/libs/graph/example/astar-cities.cpp

    Imo ist das das einzig brauchbare an der doku: auf jeder seite ganznrunter scrollen und dann den beispielcode anschauen... Und LEMON ist wirklich eine gute alternative.

    0
  • S

    Ja, das ist mir mittlerweile aufgefallen. Und in meinem ursprünglichen Problem hatte ich zwar "Eigenschaften" zur Edge hinzugefügt, aber nicht als Property.

    Aber mit Buch, ein wenig Durchhaltevermögen und den Dokuseiten hab ichs jetzt geschafft.

    Ich poste den Code nachher nochmal für eventuelle Trittbrettfahrer 😉

    0
Anmelden zum Antworten