Opened 6 years ago

Last modified 6 years ago

#12656 new Bugs

`vf2_subgraph_iso` fails to find matchings in mutually connected vertices

Reported by: araijn@… Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost Release Branch Severity: Problem
Keywords: Cc:

Description

The attached example tries to find graph1 in graph2 defined as follows:
graph1

(0) ---> (1)

graph2

          +--------+
          V        |
(0) ---> (1) ---> (2)

I expect that vf2_subgraph_iso finds matchings (0) ---> (1), (1) ---> (2), and (2) ---> (1), but it finds (0) ---> (1) only.

Attachments (1)

example.cc (872 bytes ) - added by araijn@… 6 years ago.
Source to show the problem

Download all attachments as: .zip

Change History (3)

by araijn@…, 6 years ago

Attachment: example.cc added

Source to show the problem

comment:1 by fdlorenzi@…, 6 years ago

I don't think that's a bug, because vf2_subgraph_iso requires that all edges between equivalent vertices are present. You may use vf2_subgraph_mono instead, which will (hopefully) give the expected result.

Best regards, Flavio

in reply to:  1 comment:2 by araijn@…, 6 years ago

Thank you for your response.
I understood difference between _iso and _mono and got the expected result. Sorry for the wrong report.

Note: See TracTickets for help on using tickets.