Opened 6 years ago
Closed 6 years ago
#5633 closed Bugs (wontfix)
BGL isomorphism documentation improvements
Reported by: | Evan Driscoll <driscoll@…> | Owned by: | jewillco |
---|---|---|---|
Milestone: | To Be Determined | Component: | graph |
Version: | Boost 1.46.1 | Severity: | Problem |
Keywords: | Cc: |
Description
Some of the documentation for isomorphism is somewhere between confusing and outright wrong. (I'm not sure what type & severity to use so I left it on default.)
- In the literate description of the algorithm (http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/isomorphism-impl.pdf), starting at the bottom of page 3 in the list of the three cases, I'm guessing i and j are supposed to be u and v instead. (Or the preceeding paragraph could be changed to say (i,j) instead of (u,v).)
- On the actual documentation page (http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/isomorphism.html) I think the description of the vertex invariants should be reworked completely. For starters, it's confusing. (I can elaborate on what I find confusing about it if desired, but I ramble too much so I'll leave that off.) Second, since the interface changed in 1.35 to have two separate invariant parameters, I think it's a bit wrong. In particular, it says A mapping i from vertices to integers such that if there is some isomorphism that maps v onto v' then i(v) == i(v'), but assuming I read the algo description right, there are two separate maps, where v can map to v' if vertex_invariant1(v,g1) == vertex_invarant2(v',g2). There's also just a straight-up typo in vertex_invariant2.
Anyway, here's what I suggest as a rewrite, inspired by a very helpful email from Aaron Windsor on the boost-users list:
IN: vertex_invariant1(!VertexInvariant1 x)
IN: vertex_invariant2(!VertexInvariant2 y)
Mappings from vertices to integers which restrict which vertices may be considered isomorphic. If a candidate isomorphism maps v to v' but x(v,g1) != y(v',g2), that candidate is rejected. This mapping can be used to etiher speed up the search (as is done by the default value, which requires that the degrees of v and v' are equal) on to impose extra conditions on the result. The type of each VertexInvariant must be a BinaryFunction where the first argument is a vertex descriptor, the second argument is a graph, and the result type is an integer.
(Also, please say what you mean by "an integer". Is it an int specifically, is it any integer type, is it anything convertible to an int, anything convertible to any integer type, or what?)
Attachments (0)
Change History (6)
comment:1 Changed 6 years ago by Evan Driscoll <driscoll@…>
comment:2 Changed 6 years ago by Evan Driscoll <driscoll@…>
Also from the literate programming PDF: page 3, line -1, and later in the description of case 2: "eligible vertices in V_2 - S." What is S?
(That's somewhat rhetorical; I think I know the answer. But making your readers play "guess the symbol's meaning" is bad form.)
comment:3 Changed 6 years ago by jewillco
- Owner changed from asutton to jewillco
- Status changed from new to assigned
comment:4 Changed 6 years ago by jewillco
comment:5 Changed 6 years ago by jewillco
comment:6 Changed 6 years ago by jewillco
- Resolution set to wontfix
- Status changed from assigned to closed
I tried to recompile the PDF file (the (u, v) -> (i, j) thing is already fixed in the source file, for example), and was not able to get it to work (I do have jweb and lgrind, but I think other things are broken). I'm therefore closing the PDF issues as wontfix.
Of course I meant to say "or to impose" instead of "on to impose" in my proposed rewrite.