COIN-OR::LEMON - Graph Library

Opened 7 years ago

Last modified 17 months ago

#384 new enhancement

Adaptor class for complementary graph

Reported by: kpeter Owned by: deba
Priority: major Milestone: LEMON 1.5 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

It would be nice to have an adaptor class to obtain the complementary graph of a simple, undirected graph.

Attachments (1)

Change History (6)

comment:1 Changed 7 years ago by kpeter

I think, the adaptor should not check if the original graph is simple or not, just leave out such edges that can be found in it.

comment:2 in reply to: ↑ description ; follow-up: Changed 7 years ago by alpar

Replying to kpeter:

It would be nice to have an adaptor class to obtain the complementary graph of a simple, undirected graph.

Do you have any idea how to implement it?

A function to statically create a complementary graph seems to be an easier target.

comment:3 in reply to: ↑ 2 Changed 7 years ago by kpeter

Replying to alpar:

It would be nice to have an adaptor class to obtain the complementary graph of a simple, undirected graph.

Do you have any idea how to implement it?

Such an adaptor class could be implemented as if it was a combination of FullGraph and FilterEdges using an ArcLookup solution for filtering the edges of the original graph. It wouldn't be so fast, but it would be convenient.

A function to statically create a complementary graph seems to be an easier target.

Adaptor classes are typically harder to implement and slower to use than creating another structure explicitly. However, they are more convenient, especially because they are dynamic. That's why I would prefer an adaptor class for this purpose.

(In fact, such an adpator class could be used easily to create an explict complementary graph using GraphCopy.)

comment:4 Changed 5 years ago by alpar

  • Milestone changed from LEMON 1.3 release to LEMON 1.4 release

comment:5 Changed 17 months ago by alpar

  • Milestone changed from LEMON 1.4 release to LEMON 1.5 release
Note: See TracTickets for help on using tickets.