Hinzufügen von Kanten zu einem Graphen in Boost.Graph

Question

Ich versuche, die Boost.Graph-Bibliothek zu verwenden, um Goldbergs Max-Flow-Algorithmus auszuführen. Boost.Graph nennt es push_relabel_max_flow.

Allerdings habe ich eine sehr schwere Zeit, die Bibliothek und ihr Typ-System zu verstehen. Die Dokumentation, die ich oben verlinkt habe, gibt einen Beispielcode. Aber in diesem Beispiel wird der Graph aus einer Datei gelesen. Ich möchte den Graph zur Laufzeit erzeugen. Dies ist der Code, den ich bisher (vor allem aus dem Beispiel kopiert):

typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> Traits; 
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, 
     boost::property<boost::vertex_name_t, std::string>, 
     boost::property<boost::edge_capacity_t, long, 
      boost::property<boost::edge_residual_capacity_t, long, 
       boost::property<boost::edge_reverse_t, Traits::edge_descriptor>>>> DirectedGraph; 

DirectedGraph g; 
Traits::vertex_descriptor s, t; 


s = boost::add_vertex(g); 
t = boost::add_vertex(g); 
boost::add_vertex(g); 
boost::add_vertex(g); 

Nachdem ich hinzugefügt 4 Eckpunkte der grafischen Darstellung sollte ich „connect“ sie, das heißt Kanten mit einer Kapazität, Restkapazität zu machen und die umgekehrter Wert. Die Funktion für diese Aufgabe ist boost::add_edge(), aber ich habe keine Ahnung, wie ich meine Argumente weitergeben kann. Der Beispielcode zeigt es nicht, denn wie gesagt, die Daten werden aus einer Datei gelesen und dann direkt zu einem Graphen geparst. Vielleicht kann jemand mit Erfahrung in der Boost.Graph-Bibliothek mir zeigen, wie.

Answer 1

Sie können eine Kante zwischen dem Scheitel s und t wie so hinzufügen:

boost::add_edge(s, t, {33, 44}, g); 

Hier edge_capacity-33 Einstellung und edge_residual_capacity bis 44.

Um tatsächlich die Randeigenschaften einzustellen, soweit ich weiß, dass Sie etwas tun müssen:

std::cout << boost::get(boost::edge_capacity, g, boost::edge(s,t,g).first) << '\n'; 

was nervig ist. Es ist einfacher, wenn Sie stattdessen gebündelt Eigenschaften verwenden, etwa so:

typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> Traits; 

struct VertexProps { 
    std::string name; 
}; 

struct EdgeProps { 
    long capacity; 
    long residual_capacity; 
    Traits::edge_descriptor reverse; 
}; 

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, 
           VertexProps, EdgeProps > DirectedGraph; 

Dann können Sie hinzufügen, Ecken und Kanten nur die gleiche Art und Weise, aber es ist einfacher Kante Eigenschaften zuzugreifen, z.B.

auto e = boost::edge(s,t,g).first; // get the edge descriptor for an edge from s to t, if any 
std::cout << g[e].capacity << '\n'; 

Um eine Kante zwischen den anonymen dritten und vierten Scheitelpunkte hinzufügen, die Sie hinzugefügt haben, können Sie mit

boost::add_edge(2, 3, {17, 26}, g); 

weg, da die zugrunde liegenden Speicher vector ist, und so vertex_descriptor ist nur der Vektorindex (aka size_t, aka unsigned long hier herum). Aber um mehr ganz korrekt Sie

boost:add_edge(boost::vertex(2, g), boost::vertex(3, g), {17, 26}, g); 

tun soll, um die vertex_descriptor für die 3. und 4. Ecken zu erhalten.