[Lemon-user] How to order edges by weight?

[Alpár Jüttner]

Hi,

> TLDR: Does Lemon offer a way to order a graph's nodes or edges by their
> mapped values?

I LEMON itself does not provide anything for that. I suggest using
std::sort(). E.g. assuming that you have

        ListDigraph g;
        ListDigraph::NodeMap<double> weight(g);
        
in the global scope, then something like

        bool compare(ListDigraph::Node a, ListDigraph::Node)
        {
          return weight[a] < weight[b];
        }
        
        int main()
        {
          ...
          std::vector<ListDigraph::Node> nodes;
          for(ListDigraph::NodeIt n(g);n!=INVALID;++n)
            nodes.push_back(n);
          std::sort(nodes.begin(),nodes.end(),compare);
          ...
        }
        
will do the trick (the vector 'nodes' will contain the nodes sorted by
their weight).

If g and weight are local variables, you need to implement a compare
functor object.

> Of course, I could write my own algorithm, eg using merge sort, but if a
> pre-existing solution exists, I suspect it would be much better than
> anything I could do by myself. Is there some easy way, maybe using some
> kind of map, for obtaining such an order in Lemon? Part 7.4 of the Lemon
> tutorial seems to imply the possibility, but it's not clear, and maybe I'm
> misreading.

Those tools are for different purposes. For example LoggerBoolMap is
used for retrieving the order of the nodes processed by search
algorithms.

I hope this help.

Regards,
Alpar