Map utilities

[Peter Kovacs]

It would be nice to have some functions to make it easier to work with graph maps.

I could imagine the following functions (similarly to STL tools in <algorithm>). Let K and V denote the Key and Value type of Map.

• K mapMin(Map), K mapMin(Map, Comp)
• K mapMax(Map), K mapMax(Map, Comp)
• V mapMinValue(Map), V mapMinValue(Map, Comp)
• V mapMaxValue(Map), V mapMaxValue(Map, Comp)
• K mapFind(Map, V), K mapFindIf(Map, Cond)
• int mapCount(Map, V), int mapCountIf(Map, Cond)
• void mapFill(Map, V)
• void mapReplace(Map, V, V)

• bool mapCompare(Map1, Map2)
• void mapCopy(Map1, Map2) (see also #146)

• And maybe: V mapSum(Map), V mapSum(Map, V init)

Some of these names could be misleading, e.g. mapReplace or mapCount, since they operate on map values, not maps. On the other hand, mapCompare and mapCopy would operate on maps.

Since the standard graph maps have iterator classes to traverse the corresponding item set, these functions could be implemented easily. However if we would like to support all maps whose key type is the Node, Arc or Edge type of graph, than we should provide overloaded versions that take the graph as well, e.g. mapMin(Map, Graph). But it could be confusing if we also have mapMin(Map, Comp) and mapMin(Map, Graph, Comp).

[Peter Kovacs]

Replying to kpeter:

Since the standard graph maps have iterator classes to traverse the corresponding item set, these functions could be implemented easily. However if we would like to support all maps whose key type is the Node, Arc or Edge type of graph, than we should provide overloaded versions that take the graph as well, e.g. mapMin(Map, Graph). But it could be confusing if we also have mapMin(Map, Comp) and mapMin(Map, Graph, Comp).

It does not seem a significant disadvantage to only have common interfaces including the graph as a parameter.

Thus I suggest the following functions:

• K mapMin(Graph, Map), K mapMin(Graph, Map, Comp)
• K mapMax(Graph, Map), K mapMax(Graph, Map, Comp)
• V mapMinValue(Graph, Map), V mapMinValue(Graph, Map, Comp)
• V mapMaxValue(Graph, Map), V mapMaxValue(Graph, Map, Comp)
• K mapFind(Graph, Map, V), K mapFindIf(Graph, Map, Cond)
• int mapCount(Graph, Map, V), int mapCountIf(Graph, Map, Cond)
• void mapFill(Graph, Map, V)
• void mapReplace(Graph, Map, V, V)

• bool mapCompare(Graph, Map1, Map2)
• void mapCopy(Graph, Map1, Map2) (see also #146)

• And maybe: V mapSum(Graph, Map), V mapSum(Graph, Map, V init)

Some of these names could be misleading, e.g. mapReplace or mapCount, since they operate on map values, not maps. On the other hand, mapCompare and mapCopy would operate on maps.

[Peter Kovacs]

What do you think? Could you help me make a decision about these function names (and interface)?

[Peter Kovacs]

I attached a changeset [8ddb7deabab9] introducing these utilities. I omitted mapSum() and mapSetAll() since they not seemed so fundamental as the others.

Note that the STL algorithms that operate on ranges can also be applied to standard graph maps using their MapIt or ConstMapIt iterators, though it is not so convenient. E.g.

  typedef SmartDigraph::NodeMap<int>::ConstMapIt MapIt;
  Map map(g);
  for_each(MapIt(map), MapIt(INVALID), action_functor);

It is also tested in map_test.cc, but the bugfix in #330 is required for this. Thus, if it is also merged, these parts of the test file can be "turned on".

[Peter Kovacs]

Replying to kpeter:

I attached a changeset [8ddb7deabab9] introducing these utilities.

It went to the main branch.

I omitted mapSum() and mapSetAll() since they not seemed so fundamental as the others.

I made a mistake here. Correctly: I omitted mapSum() and mapReplace(), since they not seemed so fundamental as the others.

I think, the only questionable name is mapFill. It is analogous to std::fill. On the other hand, we have set() functions for all writable maps, and some of them also has setAll(). Thus mapSetAll() would also be a logical name for this global function. What do you think?

[Alpar Juttner]

Is there anything to do here?

[Peter Kovacs]

Replying to alpar:

Is there anything to do here?

As I wrote:

I think, the only questionable name is mapFill. It is analogous to std::fill. On the other hand, we have set() functions for all writable maps, and some of them also has setAll(). Thus mapSetAll() would also be a logical name for this global function. What do you think?

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

Is there anything to do here?

As I wrote:

I think, the only questionable name is mapFill. It is analogous to std::fill. On the other hand, we have set() functions for all writable maps, and some of them also has setAll(). Thus mapSetAll() would also be a logical name for this global function. What do you think?

I don't care.

[Peter Kovacs]

Replying to alpar:

I don't care.

Then the ticket can be closed.