COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 9 years ago

#320 closed enhancement (done)

Map utilities

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

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).

Attachments (1)

320-maputils-8ddb7deabab9.patch (20.4 KB) - added by Peter Kovacs 9 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 in reply to:  description Changed 9 years ago by 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.

comment:2 Changed 9 years ago by Peter Kovacs

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

Changed 9 years ago by Peter Kovacs

comment:3 Changed 9 years ago by Peter Kovacs

Status: newassigned

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".

comment:4 in reply to:  3 Changed 9 years ago by 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?

comment:5 Changed 9 years ago by Alpar Juttner

Is there anything to do here?

comment:6 in reply to:  5 ; Changed 9 years ago by 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?

comment:7 in reply to:  6 ; Changed 9 years ago by 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.

comment:8 in reply to:  7 Changed 9 years ago by Peter Kovacs

Replying to alpar:

I don't care.

Then the ticket can be closed.

comment:9 Changed 9 years ago by Peter Kovacs

Resolution: done
Status: assignedclosed
Note: See TracTickets for help on using tickets.