Triconnectivity linear time algorithm

[meghanamreddy]

Addition of the linear time algorithm for building triconnected components of a biconnected graph. This is a huge algorithm and we will be coding it one function at a time.

Depends on #22157

CC: @dcoudert @dimpase @sagetrac-saiharsh

Component: graph theory

Keywords: connectivity, decomposition, gsoc2018

Author: Meghana M Reddy, Sai Harsh Tondomker, David Coudert

Branch: 65f2da3

Reviewer: David Coudert, Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/25598

[meghanamreddy]

comment:1

I have added the basic class structure of the Triconnectivity module. As discussed, we will first code it in Python and then convert to Cython. Harsh and I will together add functions to the module.

[sagetrac-git]

Changed commit from bb9c543 to c85b5e8

[sagetrac-git]

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

c85b5e8

Split_multiple_edges function is added.

[sagetrac-git]

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

f1cfce2

Added the function dfs1() which builds the palm tree.

[sagetrac-git]

Changed commit from c85b5e8 to f1cfce2

[sagetrac-git]

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

bcc5aee

Fixed a small error in split_multi_edges()

[sagetrac-git]

Changed commit from f1cfce2 to bcc5aee

[sagetrac-git]

Changed commit from bcc5aee to 078067e

[sagetrac-git]

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

078067e

Modified dfs1() to check biconnectivity

[sagetrac-git]

Changed commit from 078067e to 9875d50

[sagetrac-git]

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

9875d50

Added the function build_acceptable_adjacency_structure()

[meghanamreddy]

comment:7

For the function build_acceptable_adjacency_structure(), but we require the orientation of the edges of the palm tree. Hence, in the graph_copy we are storing, we iterate through every edge, and if the orientation in graph is different from the palm tree, we reverse it. But I discovered the following -

g = Graph()
g.add_edges([(2,1)])
g.edges()
[(1, 2, None)]

g = Graph()
g.add_edges([(1,2)])
g.edges()
[(1, 2, None)]

Irrespective of the order of source and target given in the parameter of add_edges(), the edge is stored as (1, 2, None). In such a situation, the other option of reversing an edge is possible if the graph is directed. But I do not want to convert the graph to a digraph, one of the reasons being that while converting, two edges in either direction are added to digraph corresponding to every edge in the original graph.

Hence, as of now, I have stored an additional dictionary named edge_reversed, and I'm storing all the edges as keys of the dictionary and the value as True or False to denote if the edge is in the reverse direction or not. Every place where the orientation of the edge matters, I have an if and else blocks.

I don't think this is the best method. I am still looking for other methods. Please advice if SageMath has some feature which can be used here.

Also, the function dfs1() has been thoroughly tested. I am still testing the function build_acceptable_adjacency_structure(), it is hard to test without the dfs2() function I think.

[dcoudert]

comment:8

I don't think this is the best method. I am still looking for other methods. Please advice if SageMath has some feature which can be used here.

Using dictionary here is a good option. Another solution could be to use a directed graph. I'll let you know if I think about a better solution.

[sagetrac-git]

Changed commit from 9875d50 to 49293bf

[sagetrac-git]

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

49293bf

Added adjacency list to make adjacency queries linear time.

[meghanamreddy]

comment:10

Instead of using the O(n) edges_incident() to get the incident edges of a vertex during dfs, added a list graph_copy_adjacency which stores the incident edges of vertex i in graph_copy_adjacency[i]. Harsh, please use this list while coding the function dfs2().

[dcoudert]

comment:11

Just a few comments on coding style

• if (self.dfs_number[w] < self.lowpt1[v]):. You don't need to add the brackets.

• if check == True: -> if check:

• if len(comp): -> if comp:. Indeed, if comp == [], the test is false, and if comp is not empty, the test will be true.

• if self.edge_status[e] != 0 : -> if self.edge_status[e]:. It's False only if the status is 0.

• first_son == None -> first_son is None is better I think.

• use range and not xrange. In Python 3, range becomes an iterator.

• edge_reverse. Instead of a dictionary, you could use a set and consider that an edge is reversed if it belongs to that set. It's not very important.

[sagetrac-git]

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

4b79b27

Some changes in coding style

[sagetrac-git]

Changed commit from 49293bf to 4b79b27

[meghanamreddy]

comment:13

I have made the changes. We will follow the same style from now on.

[sagetrac-git]

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

9e69d10

Merge to version 8.3beta7.

[sagetrac-git]

Changed commit from 4b79b27 to 9e69d10

[sagetrac-git]

Changed commit from 9e69d10 to 4d7cbe5

[sagetrac-git]

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

4d7cbe5

Added DFS2 and Path Finder

[sagetrac-git]

Changed commit from 4d7cbe5 to 84cc2cf

[sagetrac-git]

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

84cc2cf

Updated dfs2 and path finder. Added some helper functions for path_search().

[sagetrac-git]

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

fbc4759

Bug fix

[sagetrac-git]

Changed commit from bbef207 to fbc4759

[sagetrac-git]

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

b4fec47	Merge branch 'develop' of git://github.com/sagemath/sage into develop
1abed3d	update to 8.4.beta4.

[sagetrac-git]

Changed commit from fbc4759 to 1abed3d

[sagetrac-git]

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

65f2da3

trac #25598: remove storing of vertices in _Component

[sagetrac-git]

Changed commit from 1abed3d to 65f2da3

[dcoudert]

comment:141

Excellent ! Thank you.

We no longer need to count the number of vertices per components, so I removed that part.

I did several tests and for me every thing is going well now. If you also agree, I will finally set this ticket to positive review. It was quite a lot of work.

[meghanamreddy]

comment:142

Yes, I think we can set the ticket to positive review.

[dcoudert]

comment:143

This ticket was a big piece of work and you did a great job. Thanks to both of you.

[vbraun]

comment:144

Author name...

[dimpase]

Author: Meghana M. Reddy, Sai Harsh Tondomker, David Coudert

[fchapoton]

comment:146

hey, ladies and gentlemen ! coverage is supposed to be 100%

+Decreased doctests in graphs/connectivity.pyx: from 21 / 21 = 100% to 24 / 60 = 40%

[dimpase]

comment:147

perhaps a follow-up ticket to address testing?

[dcoudert]

comment:148

We implement a big algorithm that is split into sub methods. I don't know how to add doctests that are meaningful for the sub methods. Any suggestion is more than welcome.

But for sure I plan to continue working on it (remove recursions, cythonise what I can, etc.).

[vbraun]

Changed branch from public/graphs/triconnectivity to 65f2da3

[jdemeyer]

Changed commit from 65f2da3 to none

[jdemeyer]

Changed author from Meghana M. Reddy, Sai Harsh Tondomker, David Coudert to Meghana M Reddy, Sai Harsh Tondomker, David Coudert

[dcoudert]

comment:151

This is certainly something technical but I'll be happy to know (learn) what's going on. Thanks.

[embray]

comment:152

This should be re-targeted for 8.5.