[C++] Boost Graph Library, pret met <VertexList=listS>

[Stukfruit]

Sinds een tijdje ben ik aan het prutsen met Boost, en ik vind het werkelijk geweldig wat daar allemaal in te vinden is, maar de template-wirwar en de bijbehorende documentatie maakt het niet altijd bepaald makkelijker..

Zo wil ik vanuit de Boost Graph Library een std::list gebruiken voor de VertexList die je als (template)argument aan adjacency_list moet meegeven. Maar wanneer je dat doet betekent het wel dat bepaalde algoritmes niet meer werken omdat de vertex_index property dan opeens ontbreekt.

Goed, die kan ik zelf nog wel toevoegen, maar daar komt dan het tweede probleem om de hoek kijken, want ik gebruik property bundles ipv property lists. Dit betekent dat ik (voor zover ik weet) de benodigde vertex_index property in m'n struct moet gooien die ik als bundle gebruik voor de vertices in m'n graph en hem later via de get-functie moet doorgeven als extra argument voor een van de algoritmes. In dit geval gaat het om een topological sort die ik wil uitvoeren op de graph.

Een stukje code om het verhaal te verduidelijken:

C++:

struct VertPropBundle {
  size_t  index;
  string  name;

  iets    bla;
  nog     meer;
  en      zo;
};

// Variabelen, definities, bla bla
typedef adjacency_list<listS, listS, bidirectionalS, VertPropBundle> tItemGraph;
tItemGraph  myGraph;

// Vul de graph met data, bla bla
// ...

Wanneer ik een std::vector (vecS) als VertexList zou gebruiken voor de adjacency_list dan zou ik als volgt de sort kunnen uitvoeren:

C++:

typedef list<tVertexDescriptor> tTopSort;
tTopSort::iterator              it;

tTopSort TopSortList;
topological_sort(myGraph, std::front_inserter(TopSortList));

Helaas gaat die vlieger niet op wanneer de listS gebruikt wordt, omdat dan zoals hierboven verteld de vertex_index property ontbreekt. Nu heb ik nog wat verder gezocht en bleek dat er aan veel functies extra argumenten kunnen worden meegegeven voor (oa?) de properties, zodat in mijn geval bijvoorbeeld de juiste variabele gevonden kan worden voor gebruik als de vertex index:

C++:

topological_sort(myGraph, std::front_inserter(TopSortList), vertex_index(get(&VertPropBundle::index, myGraph)) );

Ik vind dat er trouwens ook vies uitzien ja..

Dit zou moeten werken, maar om een of andere reden krijg ik dan steeds de volgende errormeldingen:

C2064: term does not evaluate to a function taking 1 arguments
C2780: 'void boost::topological_sort(VertexListGraph &,OutputIterator)' : expects 2 arguments - 3 provided

Hij pakt dus de verkeerde topological_sort.. (er zijn er twee gedefinieerd in de BGL-header)

Heeft iemand hier misschien enig idee wat ik verkeerd doe?

Ik zie na uren zoeken door de templates de code niet meer, en de documentatie voor dit soort spul is net als de template wirwar niet erg duidelijk over dit soort situaties...

[MSalters]

De grootste vraag is: waarom wil je een std::list gebruiken? Zowel je sorteer als je indexeer probleem lijkt een simpel gevolg van het feit dat std::vector wel, en dstd::list geen random access heeft.

[Stukfruit]

Nouja, het is wel mogelijk met een std::list, want met een gewone property list werkt het wel, maar daar heb ik niet zoveel aan ivm het gebruik van bundles.

Ik wil een std::list gebruiken omdat ik niet wil dat er iedere keer een hoop elementen gecopieerd worden wanneer ik items toevoeg of verwijder (wat redelijk vaak zal gebeuren).