Opened 9 years ago
Closed 9 years ago
#9246 closed Patches (fixed)
VF2 (sub)graph isomorphism algorithms, return value and empty graphs
| Reported by: | Owned by: | Jeremiah Willcock | |
|---|---|---|---|
| Milestone: | To Be Determined | Component: | graph |
| Version: | Boost 1.54.0 | Severity: | Problem |
| Keywords: | Cc: |
Description
The algorithms are supposed to return true if and only if the relevant morphism exist. However, for not trivial searches the return value is not correct. Related to this is the handling of empty graphs. When a morphism exist involving an empty graph it is not reported to the callback and thus the client must trust the return value. The attached patch contains:
- A test to reveal the bugs.
- Fixes to the algorithms such that the return value can be reliably used.
- Documentation changes to explicitly explain the special cases with empty graphs.
Attachments (1)
Change History (2)
by , 9 years ago
| Attachment: | vf2_fixes.diff added |
|---|
comment:1 by , 9 years ago
| Resolution: | → fixed |
|---|---|
| Status: | new → closed |
Note:
See TracTickets
for help on using tickets.
(In [86336]) Made some of changes from #9246: added new test case (modifying tests on callback usage to match current documentation); removed special-casing of empty graphs; added patch from #9246 for correct return values; did not make change to documentation suggested there since I chose to have the callback called even for empty graphs; fixes #9246