Opened 3 years ago

Closed 2 years ago

#25410 closed enhancement (duplicate)

Addition of SPQR-Tree to graph.py

Reported by: saiharsh Owned by:
Priority: minor Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords: SPQRT-Tree
Cc: Merged in:
Authors: Reviewers: Julian Rüth
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by saiharsh)

This ticket is to fill the gaps present in Ticket #22157.

Change History (14)

comment:1 Changed 3 years ago by saiharsh

  • Component changed from PLEASE CHANGE to graph theory
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 3 years ago by saiharsh

  • Description modified (diff)
  • Keywords SPQRT-Tree added

comment:3 Changed 3 years ago by saiharsh

  • Branch set to public/22157_spqrtree

comment:4 Changed 3 years ago by git

  • Commit set to e407edbfce9de3192352dca88e6ffab009441e3f

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

e407edbFirst commit

comment:5 Changed 3 years ago by saiharsh

  • Cc dcoudert added

comment:6 Changed 3 years ago by saiharsh

The cleave function is a helper function for spqr_tree. Which takes input as biconnected multigraph and output:
f: cut vertices
C: cocycles (A a dipole graph on the two-vertex cut with virtual edges)
S: list of the graphs that are sides of the two-vertex separation with a virtual edge at the separation
Below are the following steps it follows:

  1. Make input graph simple and find cut vertices.
  2. Remove cut vertices from input graph and get connected components from it.
  3. For each connected component add cut vertices and edges with it's neighbour vertices with reference to input graph.
  4. create cocycles with the information of the number of connected components.

Finally, return (S,F,C).

Reference added in index.rst file and doctest updated.

Please have a look and let me know your feedback.

Last edited 3 years ago by saiharsh (previous) (diff)

comment:7 Changed 3 years ago by git

  • Commit changed from e407edbfce9de3192352dca88e6ffab009441e3f to ad12f54045500ef0f9884fd36eb21073ac5815c3

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

ad12f54Minor change in definition.

comment:8 follow-up: Changed 3 years ago by dcoudert

Hello,

  • Meghana is currently moving connectivity methods to file connectivity.pyx. See #25436. So you will certainly have to move your method to that file at some point. Not yet.
  • WARNING: your patch is changing the mode of files graph.py and index.rst from -rw-r--r-- to -rwxr-xr-x. You should not do that. This is certainly a default setting of your system. Please change.
  • I don't understand why you have not worked in #22157. It was possible to change the branch name and let credit to the work of the original contributor. A ticket can have multiple authors as well as multiple reviewers.
  • `cocycles` is a dipole graph but before you use letter C.
  • The method should not modify the input graph !!! If you need, you can make a local copy. and you can have:
    H = Graph(G.edges(labels=False), loops=G.has_loops(), multiedge=G.has_multiple_edges())
    
  • Furthermore, I don't understand why you need to remove loops or multiple edges here. I seems that all your step are also working with loops or multiple edges, no ?

comment:9 in reply to: ↑ 8 Changed 3 years ago by saiharsh

Replying to dcoudert:

Hello,

  • Meghana is currently moving connectivity methods to file connectivity.pyx. See #25436. So you will certainly have to move your method to that file at some point. Not yet.

Yes soon I will be updating graph.py functions in it.

  • WARNING: your patch is changing the mode of files graph.py and index.rst from -rw-r--r-- to -rwxr-xr-x. You should not do that. This is certainly a default setting of your system. Please change.

I will update my system setting.

  • I don't understand why you have not worked in #22157. It was possible to change the branch name and let credit to the work of the original contributor. A ticket can have multiple authors as well as multiple reviewers.

Yes, the Original contributor should get his credits as he started the work first. Sorry this didn't come to my mind. I will do appropriate changes and update it.

  • `cocycles` is a dipole graph but before you use letter C.

The cocyle is represented by letter C.

  • The method should not modify the input graph !!! If you need, you can make a local copy. and you can have:
    H = Graph(G.edges(labels=False), loops=G.has_loops(), multiedge=G.has_multiple_edges())
    

Yes, I won't change the input graph.

  • Furthermore, I don't understand why you need to remove loops or multiple edges here. I seems that all your step are also working with loops or multiple edges, no ?

The initial version was testing whether the graph is simple or not i.e self._scream_if_not_simple(), so I did it.
I assumed the input is in simple(for SPQRT-Tree).
It's better if multiple edges graph could be passed to cleave function.
I will do the necessary changes, close this ticket.

Start working on the old ticket of spqr-tree.

Thanks, Harsh

comment:10 Changed 3 years ago by saiharsh

  • Branch public/22157_spqrtree deleted
  • Commit ad12f54045500ef0f9884fd36eb21073ac5815c3 deleted

comment:11 Changed 3 years ago by saiharsh

  • Cc dcoudert removed
  • Milestone changed from sage-8.3 to sage-duplicate/invalid/wontfix

Please close this ticket.

comment:12 Changed 3 years ago by saiharsh

  • Priority changed from major to minor
  • Status changed from new to needs_review

comment:13 Changed 3 years ago by saraedum

  • Reviewers set to Julian Rüth
  • Status changed from needs_review to positive_review

comment:14 Changed 2 years ago by embray

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.