3

I'm writing an application that's parsing a data structure with something like

struct Block
{
  std::string foo;
  /* ... even more local data ... */
};

std::map<std::string, Block> blockContainer; // Each Block will have a name here

struct Signal
{
  // the direct links to the Blocks, no redundant storage of the name so that an
  // simple renaming of a Block would be possible
  std::map<std::string, Block>::iterator from; 
  std::map<std::string, Block>::iterator to;

  std::string bar;
  /* ... even more local data ... */
};

std::vector<Signal> signalContainer;

parsing and filling this list was quite easy. Now I need to do a topological sort of the Blocks depending on the Signals - also quite easy when I use Boost::Graph.

But first parsing it in a STL data structure and then copying them over to the Boost::Graph structure doesn't make much sense to me. Especially as all that'll be done with this data afterwards is perhaps some simple modifications (add/remove of Blocks and Signals, some signal rerouteing; serialising it out again) with a new topological sort afterwards.

So I'd be fine with any of these possible solutions:

  1. Make Boost::Graph work on my containers directly
  2. Parse the data directly into the Boost::Graph data structures (and e.g. use a graph with bundled properties like boost::adjacency_list<boost::mapS, boost::vecS, boost::directedS, Block, Signal>)

But it seems I'm not intelligent enough to understand the documentation here to do either. Also all the examples I found on the net were showing how to use the bundled properties - but not how to construct the graph with those on the fly. (And, of course, not with node and vertex properties at the same time, or how to use a std::map for the nodes to access them by their name, ...)

Can someone help me out?

Thanks!

Chris
  • 3,265
  • 5
  • 37
  • 50

1 Answers1

4

Nobody is intelligent enough for the boost::graph documentation ;) It takes a lot of time to learn how to use it.

You can créate a boost graph structure around your data, however, this will probably be rather painful. There is a documentation there : http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/leda_conversion.html

I would suggest to go with the second approach, but I'm not sure to understand your data structure.

Did you see this question : adding custom vertices to a boost graph does it answers your needs ?

You can also do the following to create a node (or edge) and define the properties at once :

vertex_t u = boost::add_vertex(Block(42, "hi"), g);

You might need to maintain a map while parsing.

Community
  • 1
  • 1
Tristram Gräbener
  • 9,601
  • 3
  • 34
  • 50
  • OK, now I took solution 2 - and it works :) :) :) Apart from the (now...) straight forward addition of edge and vertex parameters the biggest remaining question for me was the efficient handling of the name of the vertices. The solution was to keep the name in the `Block` as well as in a `std::map` (and making sore that both are synchronised). So I can quickly look up the stored Block by it's name (via the `map`) as well as it's name when I've got the block (via the property) – Chris Dec 16 '12 at 21:56