COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 10 years ago

#34 closed task (fixed)

Find a better name for StoreBoolMap

Reported by: alpar Owned by: kpeter
Priority: major Milestone: LEMON 1.0 release
Component: core Version: hg main
Keywords: Cc: deba
Revision id:

Description

StoreBoolMap is necessary for kruskal.h and it also seems to have a more general usage. Its name however hardly express what it is for.

Therefore a better name is a must.

Attachments (1)

loggerboolmap.patch (4.9 KB) - added by kpeter 10 years ago.

Download all attachments as: .zip

Change History (21)

comment:1 Changed 10 years ago by alpar

  • Owner changed from alpar to kpeter

comment:2 follow-up: Changed 10 years ago by kpeter

And maybe the name of SparseMap should also be revised. This name was voted by the most of us, however it seems still misleading for me. Maybe StdMap (the former name) or GeneralMap or something similar could be better, since using this class as a "sparse" map is in fact only a special (but important) usage.

comment:3 in reply to: ↑ 2 ; follow-up: Changed 10 years ago by alpar

Replying to kpeter:

... since using this class as a "sparse" map is in fact only a special (but important) usage.

What would be the general usage of it? I can't see any other useful application.

comment:4 in reply to: ↑ 3 Changed 10 years ago by kpeter

Replying to alpar:

What would be the general usage of it? I can't see any other useful application.

It can be used with arbitrary key type that can be ordered and arbitrary value type. That's why it is general, as std::map<> is general.

However maybe there isn't any important usage apart from using it as a "sparse" map. I don't know.

comment:5 Changed 10 years ago by alpar

  • Version set to hg main

comment:6 Changed 10 years ago by alpar

  • Cc deba added

Peter suggested to move StoreBoolMap into kruskal.h and hide it, as it is only used there and only used internally.

What do you think of this idea?

comment:7 follow-up: Changed 10 years ago by deba

In my opinion, such thing should be in the public stuffs of lemon. The several lemon algorithms returns solution in boolean map, and many of them assigns the map just one time. It is a natural request, that the list of the true elements should be retrieveable instead of the bool map, because in many case it provides more information (for example processing order of dfs) and it could be more efficient.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 10 years ago by alpar

Replying to deba:

In my opinion, such thing should be in the public stuffs of lemon. The several lemon algorithms returns solution in boolean map, and many of them assigns the map just one time.

Just for a reference, could you list these algorithms?

It is a natural request, that the list of the true elements should be retrieveable instead of the bool map, because in many case it provides more information (for example processing order of dfs) and it could be more efficient.

Basically, I agree. However, if we cannot find an acceptable name for it soon, we have no option but "hide" it temporarily. Currently it is used only by kruskal, so it is not a big loss now.

comment:9 in reply to: ↑ 8 ; follow-up: Changed 10 years ago by deba

Replying to alpar:

Replying to deba:

In my opinion, such thing should be in the public stuffs of lemon. The several lemon algorithms returns solution in boolean map, and many of them assigns the map just one time.

Just for a reference, could you list these algorithms?

Dfs, Bfs, Dijkstra as reached and processed Map, cut edge and node enumeration with strongly connected and biconnected component enumerations, flow algorithms as cut description, minimum cost arborescence algorithm as the directed tree, planarity algorithm as kuratowski minor enumeration, min cut algorithms. (It is not a full list, but it seems that many algorithms in lemon 1.0 or 1.1 plans use once-set bool maps)

It is a natural request, that the list of the true elements should be retrieveable instead of the bool map, because in many case it provides more information (for example processing order of dfs) and it could be more efficient.

Basically, I agree. However, if we cannot find an acceptable name for it soon, we have no option but "hide" it temporarily. Currently it is used only by kruskal, so it is not a big loss now.

It is a wrong idea, if one thing is not or only once used in the library, then it can be removed or hided. We are developing a library, the most of the stuffs should be used by the users, and not by us in the the library. With this logic, the dijkstra or kruskal could be thrown out, because it is not used in the library.

I rather suggest, that it should be stay in the library even with wretched name (if the StoreBoolMap? is that). There are popular libraries with more important misnamings.

comment:10 in reply to: ↑ 9 Changed 10 years ago by kpeter

Replying to deba:

I rather suggest, that it should be stay in the library even with wretched name (if the StoreBoolMap? is that). There are popular libraries with more important misnamings.

I agree. According to the many examples you have given, I support public StoreBoolMap. In fact, I do not feel annoyed by this name, maybe only Alpar find it hardly acceptable.

comment:11 follow-up: Changed 10 years ago by kpeter

I can't imagine any better name for this class, but I don't find it a bad choice. It was a bit confused when we also had InserterBoolMap, BackInserterBoolMap etc., but now I support this name.

Alpar wrote:

However, if we cannot find an acceptable name for it soon, we have no option but "hide" it temporarily.

What is the reason for your regarding this name unacceptable?

comment:12 in reply to: ↑ 11 Changed 10 years ago by alpar

Alpar wrote:

However, if we cannot find an acceptable name for it soon, we have no option but "hide" it temporarily.

What is the reason for your regarding this name unacceptable?

This name is very bad (therefore unacceptable) because

  • Grammatically very incorrect. ("Store" should be adjective or at least a noun. Alternatively, if "store" is a verb, then the expression is a kind of imperative, and "BoolMap" should be interpreted as its object. Do we really want to say that this tool stores a BoolMap somewhere?)
  • Because of the previous problem, the name looks quite stupid
  • This name is really confusing. The usual bool maps also "store" their values, thus this word says nothing about the additional feature of this tool.

Something with Logging, Logger or History might result in a better name.

comment:13 follow-up: Changed 10 years ago by kpeter

  • Status changed from new to assigned

Replying to alpar:

This name is very bad (therefore unacceptable) because

  • Grammatically very incorrect.

I agree, but I thought it is for simplicity.

What about the followings?

  • LoggingMap / LoggingBoolMap
  • LoggerMap / LoggerBoolMap
  • StoringMap / StoringBoolMap
  • InserterMap / InserterBoolMap
  • InsertingMap / InsertingBoolMap
  • HistoryMap / HistoryBoolMap

I think Log* names would be the best. Apart from that I also support Insert* names. I know that InserterMap was a different class, but now we only have this one, so we can choose a name like that.

comment:14 follow-up: Changed 10 years ago by kpeter

Another idea: do we need a read-write variant of this class?

This map is only readable, so e.g. it can be used for ProcessedMap but it cannot be used for ReachedMap in Bfs, Dfs, Dijkstra.
Now the simplest way for creating such a map is

typedef StoreBoolMap<...> LoggingMap;
BoolEdgeMap map;
LoggingMap log;
ForkMap<BoolEdgeMap, LoggingMap> m(map, log);

comment:15 in reply to: ↑ 14 ; follow-up: Changed 10 years ago by alpar

Replying to kpeter:

Another idea: do we need a read-write variant of this class?

It may be, but it is obviously of low priority now. I suggest creating a post-1.0 new ticket about it.

comment:16 in reply to: ↑ 13 ; follow-up: Changed 10 years ago by alpar

I think Log* names would be the best. Apart from that I also support Insert* names. I know that InserterMap was a different class, but now we only have this one, so we can choose a name like that.

I strongly prefer the Bool versions as later we may have other maps with similar functionality. I slightly prefer *er* to *ing*.

comment:17 in reply to: ↑ 16 Changed 10 years ago by kpeter

Replying to alpar:

I strongly prefer the Bool versions as later we may have other maps with similar functionality. I slightly prefer *er* to *ing*.

Okay. LoggerBoolMap or InserterBoolMap? I support both.

comment:18 in reply to: ↑ 15 Changed 10 years ago by kpeter

Replying to alpar:

Another idea: do we need a read-write variant of this class?

It may be, but it is obviously of low priority now. I suggest creating a post-1.0 new ticket about it.

When the new name is found, this ticket can be closed and I will make a post-1.0 ticket about the read-write variant.

Changed 10 years ago by kpeter

comment:19 follow-up: Changed 10 years ago by kpeter

I uploaded a patch that renames StoreBoolMap to LoggerBoolMap.
A new ticket (#98) is made about the read-write variant.

comment:20 in reply to: ↑ 19 Changed 10 years ago by alpar

  • Resolution set to fixed
  • Status changed from assigned to closed

Replying to kpeter:

I uploaded a patch that renames StoreBoolMap to LoggerBoolMap.

It is now in the main branch, see [d57ae6f0a335].

Note: See TracTickets for help on using tickets.