Modify

Ticket #1326 (reopened Bugs)

Opened 10 years ago

Last modified 5 years ago

Unable to check graph isomorphism using LEDA adapter

Reported by: iouri.smirnov@… Owned by: jewillco
Milestone: To Be Determined Component: graph
Version: Boost Development Trunk Severity: Problem
Keywords: LEDA Cc: ich@…

Description

I tried to use isomorphism() algorithm with LEDA graphs and encountered several compilation issues:

  1. "leda::" namespace is not used in LEDA 4.3.1, therefore declaration "leda::GRAPH<vtype,etype>" might be wrong.
  1. EdgeListGraph? concept must be supported by a graph in order to use it by the isomorphism() algorithm. For me it's unclear why this interface is not implemented in LEDA adapter. Generally, it is possible to iterate through edges in LEDA graphs. Moreover, EdgeListGraph? interface implementation may look very similar to VertexListGraph? one.
  1. All LEDA adapter iterators publicly inherit from iterator_facade< Derived, Value, CategoryOrTraversal?, Reference, Difference >

but const pointers to Value are incorrectly passed as the last argument (i.e. Difference) while ptrdiff_t is expected. It causes wrong instantiation of count() and count_if() algorithms used by isomorphism() one.

I would like to present my fixes of these problems in LEDA adapter for review. Thanks!

Attachments

leda_graph.hpp Download (19.0 KB) - added by iouri.smirnov@… 10 years ago.
Patched LEDA graph adapter

Change History

Changed 10 years ago by iouri.smirnov@…

Patched LEDA graph adapter

comment:1 Changed 8 years ago by jewillco

  • Owner changed from dgregor to jewillco
  • Status changed from new to assigned
  • Version changed from Boost 1.34.1 to Boost Development Trunk
  • Milestone changed from To Be Determined to Boost 1.40.0

I think your patch would be useful, but it needs to be updated to be against the new version of the LEDA adapter. Could you please update it?

comment:2 Changed 7 years ago by jewillco

  • Milestone changed from Boost 1.40.0 to To Be Determined

comment:3 Changed 7 years ago by jewillco

  • Status changed from assigned to closed
  • Resolution set to wontfix

I am closing all of the LEDA-related bugs unless someone else is willing to fix them.

comment:4 Changed 5 years ago by Jens Müller <ich@…>

  • Cc ich@… added
  • Status changed from closed to reopened
  • Resolution wontfix deleted

ad 1: well, LEDA 6.3 uses the LEDA namespace. I guess we should stick to the current version.

ad 3: I also encountered the wrong template parameter to iterator_facade - I will submit the patch soon.

ad 2: leda_graph.hpp now contains an edges(g) function. I will add a concept check for EdgeListGraph? to the test case.

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as reopened
Author


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

 
Note: See TracTickets for help on using tickets.