Opened 3 years ago

Closed 3 years ago

#28198 closed enhancement (fixed)

Add method is_bipartite to BipartiteGraph

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-8.9
Component: graph theory Keywords:
Cc: Merged in:
Authors: David Coudert Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 0436491 (Commits, GitHub, GitLab) Commit: 0436491078f2d5ee834bfdfcd07a996f539b5754
Dependencies: Stopgaps:

Status badges

Description

A member of class BipartiteGraph is obviously bipartite, so we can avoid to test it.

Change History (18)

comment:1 Changed 3 years ago by dcoudert

  • Branch set to public/graphs/28198_is_bipartite
  • Commit set to d239b5ef03368c540b5ee1227a047dbf7d148eda
  • Status changed from new to needs_review

If you have in mind a smarter way to handle initialization, please share it. The branch is in public, so you can implement it directly.


New commits:

d239b5etrac #28198: is_bipartite for BipartiteGraph

comment:2 Changed 3 years ago by vdelecroix

Insteed of having a weird and mostly useless special case

+        if not hasattr(self, 'left') or not hasattr(self, 'right'):
+            # This case may occur during the initialization (i.e., in __init__)
+            return GenericGraph.is_bipartite(self, certificate=certificate)

Why don't you call GenericGraph.is_bipartite(self) in __init__ instead of `self.is_bipartite()?

comment:3 Changed 3 years ago by git

  • Commit changed from d239b5ef03368c540b5ee1227a047dbf7d148eda to 564fa99c10956c63139ad0dbd9075dd1f2c020c4

Branch pushed to git repo; I updated commit sha1. New commits:

564fa99proposition of simplification for 28198

comment:4 Changed 3 years ago by git

  • Commit changed from 564fa99c10956c63139ad0dbd9075dd1f2c020c4 to c909cdcbbf0601b99351b3abe5a01dd38f1682a9

Branch pushed to git repo; I updated commit sha1. New commits:

c909cdctrac #28198: small correction

comment:5 Changed 3 years ago by dcoudert

I agree with your improvement. I did a small correction to avoid this issue

sage: a = b = set()
sage: a.add(1)
sage: b
{1}

For me this ticket is good to go. I let you conclude. Thank you.

comment:6 Changed 3 years ago by vdelecroix

  • I don't like so much the duplication in the BipartiteGraph.__init__.
  • The sets_from_colors would be more natural if it would return ans instead of ans.values(). That is it would transform a dictionary k -> v in v -> {keys with that values}.

Is that ok if I try something to fix these.

comment:7 Changed 3 years ago by dcoudert

Sure, the branch is in public so that we can interact (and I'm not the author of the commit "proposition of simplification for 28198")

comment:8 Changed 3 years ago by git

  • Commit changed from c909cdcbbf0601b99351b3abe5a01dd38f1682a9 to f2e3d83a91a55c61b3a138b0271a258d3e6211b5

Branch pushed to git repo; I updated commit sha1. New commits:

f2e3d83cleanup

comment:9 Changed 3 years ago by vdelecroix

I like it better now :-)

comment:10 Changed 3 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix

comment:11 Changed 3 years ago by git

  • Commit changed from f2e3d83a91a55c61b3a138b0271a258d3e6211b5 to 17d54019a0aedc0744999ebb7547b867d4e9246b

Branch pushed to git repo; I updated commit sha1. New commits:

17d5401even simpler

comment:12 Changed 3 years ago by dcoudert

we can simplify more putting the content of sets_from_colors inside _upgrade_from_graph, no ?

comment:13 Changed 3 years ago by vdelecroix

make sense

comment:14 Changed 3 years ago by git

  • Commit changed from 17d54019a0aedc0744999ebb7547b867d4e9246b to 0436491078f2d5ee834bfdfcd07a996f539b5754

Branch pushed to git repo; I updated commit sha1. New commits:

0436491trac #28198: more simplifications

comment:15 Changed 3 years ago by dcoudert

Should be good now.

comment:16 Changed 3 years ago by vdelecroix

  • Status changed from needs_review to positive_review

good for me at least

comment:17 Changed 3 years ago by dcoudert

Thank you.

comment:18 Changed 3 years ago by vbraun

  • Branch changed from public/graphs/28198_is_bipartite to 0436491078f2d5ee834bfdfcd07a996f539b5754
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.