Verwenden Sie eine Grafik-Bibliothek/Knoten-Netzwerk-Bibliothek oder Schreibe Meine Eigenen?

Kann ich vielleicht eine kleine Anleitung auf der BGL.

Die Bibliothek ist sehr flexibel. Die Kosten für dieses ist, dass die syntax kann sehr Barock, um Platz für alle Möglichkeiten. Es ist jedoch ausreichend flexibel, dass einfache Dinge, die getan werden kann, einfach.

Leider die boost-Dokumentation geht in Sachen full tilt Poker bietet nur eine Beschreibung des ganzen Komplexität, ohne eine Andeutung, wie einfach die Dinge sein können.

( "Jede hinreichend fortschrittliche Technologie ist von Magie nicht unterscheiden" - Arthur C. Clarke. Was sollte er haben, sagte ist "Jede fortschrittliche Technologie, ausreichend schlecht dokumentiert ist, ist von Magie nicht unterscheiden )

Betrachten:

typedef property_map<Graph, vertex_index_t>::type IndexMap;
IndexMap index = get(vertex_index, g);
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
   std::cout << index[*vp.first] <<  " ";
}

Dies ist, wie die "quick-tour" schlägt vor, wir drucken Sie eine Liste der graph-Knoten. Jedoch, eine kleine Studie zeigt, dass ein vertex nicht mehr als ein integer-index, und Sie können den code stark vereinfacht,

for (int v = *vertices(g).first; v != *vertices(g).second; ++v)
    std::cout << v << " ";

Vielleicht gibt es einige Magische Dinge, die nicht erreicht werden kann mit diesem vereinfachten code, aber für den alltäglichen Gebrauch ist es sinnvoll, drastisch beschneiden die syntax, encrust BGL, so dass Sie sehen können, was Ihre Codierung.

Manchmal die aufwändige syntax kann nicht entfernt werden. ( Oder vielleicht habe ich nur nicht bemerkt, die zugrunde liegende Wahrheit ). Dann habe ich in der Regel verwenden Sie eine kleine utility-Funktion zu Kapseln, die Komplexität abd halten Sie es Weg von dem Algorithmus, den ich auf Arbeit bin.

Beispielsweise, brauche ich oft eine Schleife über die Kinder eines Knotens

vector<int> getVertexChildren( int v )
{
    vector<int> vc;
    typedef std::pair<graph_traits<graph_t>::out_edge_iterator, graph_traits<graph_t>::out_edge_iterator> out_edge_iter_pair_t;
    for( out_edge_iter_pair_t ep = out_edges(v,m_tree);
        ep.first != ep.second; ++(ep.first))
    {
        vc.push_back( target( *ep.first, m_tree ) );
    }
    return vc;
}
#define FOR_ALL_CHILDREN( v ) vector<int> vc=getVertexChildren(v); BOOST_FOR_EACH( int child, vc )

In der unteren Zeile ist: gehen Sie voran und verwenden BGL. Es kann vereinfacht werden, einfache Dinge zu tun, aber sobald Sie gelernt haben, es zu benutzen, all die immensen Flexibilität wird verfügbar sein, Wann immer Sie es brauchen.

Ich habe vor kurzem gab die boost graph library eine Studie für Dijkstras shortest-path-problem. Ergebnisse:

• Sehr Hohe Leistung

• Sehr wenig code benötigt

• Sehr flexibel und erweiterbar

• Schwer zu verstehen, oder Debuggen

Beratung: Verwenden aber bevor Sie dies tun Lesen Die Boost Graph Library: User Guide and Reference Manual

Können Sie auch einen Versuch mit ZITRONE graph-Bibliothek.

Konnte ich es verwenden, um durchzuführen Dijsktra kürzesten Weg suchen, nach dem Lesen des Graphen aus einer Konfigurationsdatei.

Eine neue version gerade raus gekommen.

Rollte ich meinen eigenen. Sie sollten nicht Folgen Sie diesem Beispiel, es sei denn, Sie absolut sicher sind, müssen Sie.

Immer noch, es ist eine großartige Lernerfahrung, wenn Sie Graphentheorie ist rostig.

Ich hatte viel "Spaß" mit der Kombination Digraphen mit EBNF-Operatoren, und das tun epsilon-elimination und Hopcroft-basierte Minimierung. Vor allem mit der Verharmlosung, wenn Sie anrufen können, verzweifelt versuchen zu finden gute Informationen und herauszufinden, wie es funktioniert "Spaß" 🙁

Wenn Sie Rollen Sie Ihre eigenen, empfehle ich die Trennung von high-level-Operationen von dem niedrigen Niveau digraph Datenstrukturen - Klassen nicht nur verschiedene Methoden. Ich nicht - und schon bald werde ich die Umgestaltung stark, weil der, dass eine schlechte Entscheidung.

Einige Diagramme mit Anmerkungen versehen von Knoten, einige Anmerkungen Kanten einige beide. Manchmal zwei Anmerkungen sind hilfreich, auch wenn Sie nur Fremdschlüssel für externe Daten. Zum Beispiel in finite-state-machines, eine Kante kann mit Anmerkungen versehen werden mit einem Eingang und einem Ausgang. Sie sind wahrscheinlich daran interessiert, Determinismus WRT die Eingabe aber nicht den Ausgang, so dass Sie beide versteckt hinter einer einzigen ID ist ein Schmerz - und das ist neben dem ganzen Problem der sekundären Behälter für die was-hat-dieses-ID-verweisen-zu-lookups.

Auch, manchmal Sie nur wollen, um die Arbeit mit Dingen, die nicht konstruiert waren explizit als digraph IYSWIM - z.B. eine Reihe von Daten-Struktur werden Knoten, die miteinander verlinkt sind.

IOW, ist es sinnvoll, in der Lage sein zu Stecker in verschiedenen digraph Darstellungen, aber immer noch die gleichen high-level-Werkzeuge für viele Vorgänge.

IMO bekam ich es richtig, wenn ich schrieb einen 'Baum-tool" - Klasse, die nicht Dinge wie Iteration und subscripting im treeview -, um-und XML-element-tag um. Der zugrunde liegende Baum-Darstellung ist steckbar (policy based template). Mit Digraphen, ich Durcheinander.

Sowieso, ich weiß nicht, was der Boost-oder andere Grafik-Bibliothek bietet tatsächlich, aber wenn es das bietet, was Sie brauchen, sage ich es verwenden. Sie sparen eine Menge Kopfschmerzen.

Ich die BGL sehr viel, aber das, was mich stört, mit BGL ist der Mangel an grundlegenden algorithmen wie edge-und vertex-connectivity -, min-cost-flow und Allgemeine maximum weight perfect matching, um nur diejenigen, die ich am meisten vermisse.

ZITRONE bietet all das und hat auch einen einfacheren syntax ist es, was mich nervt mit ZITRONE ist die installation und Kompilierungs-Probleme auf WINDOWS-Plattformen, aber ich werde wohl wechseln ZITRONE trotz dieser Probleme ist.