[Lemon-user] Printing Labels in Topological Order

[Balázs Dezső]

It's a bit tricky. The topoligicalSort() sets the item values in
descending order, so we can use a special map to store the order. The
LoggerBoolMap stores each set item with an output iterator (now we
misusing the map, because we use as int map and not bool map).

So my code looks:
  std::vector<lemon::ListDigraph::Node> nodes;
  lemon::LoggerBoolMap<std::back_insert_iterator<std::vector<lemon::ListDigraph::Node>
> >
      map(std::back_inserter(nodes));
  lemon::topologicalSort(graph, map);

  for (std::vector<lemon::ListDigraph>::reverse_iterator it = nodes.rbegin();
       it != nodes.rend(); ++it) {
    std::cerr << labels[*it] << std::endl;
  }

Other option is to sort the nodes by map values, but that is n log(n) time.

Balazs




On Thu, Aug 9, 2012 at 4:02 PM, Zeev Sands <zeev.sands at gmail.com> wrote:
> Hello Lemon users,
>
> I'm new to lemon and is figuring out the basics. My question is about
> iterating over a DAG in topological order. Suppose I have a large
> labeled Graph (DAG), a map holding labels and a map holding its
> topological order, as follows:
>
>      // create some graph
>      Digraph d;
>
>      // add some nodes
>      Digraph::Node n1 = d.addNode();
>      ...
>      Digraph::Node n234342434 = d.addNode();
>
>      // add some arcs
>      d.addArc(n1, nn234342434);
>
>      // Label it
>      DiraphGraph::NodeMap<string> lables(g);
>      labels[n1] = "foo";
>      ...
>      labels[n234342434] = "bar";
>
>      // Now sort it
>      Digraph::NodeMap<int> order(d);
>      topologicalSort(d, order);
>
> How do I now print the labels in the topological order? Something like
>
>      Digraph::Node n = first_in_tipological_order();
>      while (  n != order.last_in_topological_order()) {
>          std::cout << labels[n] << std::endl;
>          n = order.next_in_topological_order();
>      }
>
>
> Thank you very much,
> Zeev.
>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user