Ticket #4141 (assigned defect)

Opened 5 years ago

Last modified 5 years ago

subiso test examples have stopped working

Reported by: jberry Owned by: gemacke
Priority: normal Milestone: 1.2
Version: 1.1.1 Severity: normal
Keywords: Cc:

Description

subiso_triangles and subiso_5cycles don't work anymore. This needs debugging. For example, subiso_triangles er 64 0.25 has plenty of hits that used to be found. Now zero of them are found.

Change History

comment:1 Changed 5 years ago by jberry

  • Owner set to gemacke
  • Status changed from new to assigned

The problem appears to have arisen from recent changes to dynamic array. The resize()/uninitialized_copy() methods don't copy properly from the old to the new allocation. To see this, run "subiso_triangles 12 0.4" with the current trunk. In my sandbox, I inserted more debug prints before and after the b_sources, b_dests, and b_eid_map resize(b_size2) calls around Line 2210 of subgraph_isomorphism.hpp. They provide the following output:

..................
<everything correct to this point, with dense bipartite graph making sense>
15'th bip edge after update: (6, 4)
before resize:
b_sources[0]: 5, b_dests[0]: 9
b_sources[1]: 5, b_dests[1]: 0
b_sources[2]: 8, b_dests[2]: 7
b_sources[3]: 8, b_dests[3]: 0
b_sources[4]: 8, b_dests[4]: 3
b_sources[5]: 7, b_dests[5]: 2
b_sources[6]: 7, b_dests[6]: 1
b_sources[7]: 7, b_dests[7]: 6
b_sources[8]: 9, b_dests[8]: 1
b_sources[9]: 9, b_dests[9]: 6
b_sources[10]: 0, b_dests[10]: 1
b_sources[11]: 3, b_dests[11]: 6
b_sources[12]: 2, b_dests[12]: 10
b_sources[13]: 1, b_dests[13]: 10
b_sources[14]: 1, b_dests[14]: 4
b_sources[15]: 6, b_dests[15]: 4
after resize:
b_sources[0]: 0, b_dests[0]: 0
b_sources[1]: 0, b_dests[1]: 0
b_sources[2]: 0, b_dests[2]: 0
b_sources[3]: 0, b_dests[3]: 0
b_sources[4]: 8, b_dests[4]: 3
b_sources[5]: 7, b_dests[5]: 2
b_sources[6]: 7, b_dests[6]: 1
b_sources[7]: 7, b_dests[7]: 6
b_sources[8]: 9, b_dests[8]: 1
b_sources[9]: 9, b_dests[9]: 6
b_sources[10]: 0, b_dests[10]: 1
b_sources[11]: 3, b_dests[11]: 6
b_sources[12]: 2, b_dests[12]: 10
b_sources[13]: 1, b_dests[13]: 10
b_sources[14]: 1, b_dests[14]: 4
b_sources[15]: 6, b_dests[15]: 4
......

The first four entries are lost during copy. This occurs as we prepare to add the edges from the super-source and to the super-sink of the dense-id bipartite graph. After that, the algorithm is corrupted.

Note: See TracTickets for help on using tickets.