Modify

Ticket #7845 (closed Bugs: fixed)

Opened 16 months ago

Last modified 16 months ago

[BGL] Bug in isomorphism when the two graphs are of different types

Reported by: tiago@… Owned by: jewillco
Milestone: To Be Determined Component: graph
Version: Boost 1.52.0 Severity: Problem
Keywords: isomorphism, bgl Cc:

Description

The isomorphism implementation checks for the source and target (i, j) of the edge being considered in G2, where it clearly should be G1:

        recur:
        if (iter != ordered_edges.end()) {
          i = source(*iter, G1);
          j = target(*iter, G2);

In the last line, G2 should be G1, otherwise it will not even compile if the graphs have different types of edge descriptors (not to mention it does not make any sense). Note that this is also wrong in the 'literate' documentation provided on the website.

Furthermore the use of "num_vertices" when checking the size of both graphs makes it impossible to use with filtered graphs.

I'm attaching a patch which fixes both these issues.

Attachments

isomorphism.patch Download (3.9 KB) - added by tiago@… 16 months ago.
Proposed patch

Change History

Changed 16 months ago by tiago@…

Proposed patch

comment:1 Changed 16 months ago by jewillco

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

(In [82358]) Applied variant of patch from #7845; fixes #7845

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.