Opened 2 years ago
Closed 23 months ago
#25002 closed enhancement (fixed)
Ear Decomposition
Reported by:  saiharsh  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  graph theory  Keywords:  Ear Decomposition 
Cc:  dcoudert, dimpase  Merged in:  
Authors:  Tondomker Sai Harsh  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  9b43b3e (Commits)  Commit:  9b43b3e65623545d549e0003887e36d73d72a00d 
Dependencies:  Stopgaps: 
Description
Adding Ear Decomposition Algorithm to Graph Decomposition,
Current efficient algorithm for ear decomposition. https://www.sciencedirect.com/science/article/pii/S0020019013000288?via%3Dihub
The above one works for Undirected connected graph.
Change History (52)
comment:1 followup: ↓ 2 Changed 2 years ago by
comment:2 in reply to: ↑ 1 Changed 2 years ago by
There is a small problem with my college network for ssh, I will let you know as soon as solved.
Thanks for quick response.
Replying to dcoudert:
I cannot access the branch. Please check.
comment:3 Changed 2 years ago by
 Commit set to a495a2160290621c942aecfd0fc728d1b1ab2a09
Branch pushed to git repo; I updated commit sha1. New commits:
a495a21  Initial Commit

comment:4 Changed 2 years ago by
 Commit changed from a495a2160290621c942aecfd0fc728d1b1ab2a09 to 6d747be667f7c886d787189791bd26703a92840c
Branch pushed to git repo; I updated commit sha1. New commits:
6d747be  Code Updated

comment:5 Changed 2 years ago by
Please have a look, the branch is up and accessible. The main objective of Ear Decomposition is to decompose the graph into cycles and chains that can be used to study properties of graph.
Jens algorithm:
 Construct a depthfirst search (dfs) spanning tree T of G ;
 Traverse in Spanning Tree using GT nontree edges.
Potential Applications:
 A graph G is biconnected if and only if it has an open ear decomposition.
 A graph G is factorcritical if and only if G has an odd ear decomposition.
 Verification to check if graph is 2edge connected.
P.S : For the first step, we not only need tree but also some extra information which will be used in Tree traversal because of this I didn't use the existing DFS function and created my own.
Please let me know what more I can do to improve the code performance.
comment:6 Changed 2 years ago by
Welcome to Sagemath and thank you for this contribution.
There is no need to add a new file. This method should be inside graph.py
.
Note that you don't need a class. You can define local methods inside a method like:
def my_function(G): def DFS(G, u): some code for u in G: DFS(G, u)
The local method can access local data list/dict, etc.
comment:7 Changed 2 years ago by
 Commit changed from 6d747be667f7c886d787189791bd26703a92840c to ffe58a9894001159136e891bde96b7ea36e467fb
Branch pushed to git repo; I updated commit sha1. New commits:
ffe58a9  Removed ear_decomposition.py

comment:8 Changed 2 years ago by
As suggested by you, I have removed ear_decomposition.py and added ear_decomposition method to graph.py with updated comments.
Please have a look and let me know, what more improvements can be done.
comment:9 followup: ↓ 11 Changed 2 years ago by
Some (unordered) comments.
 Please use the same indentation style than for other methods.
 in the name of variables:
vertice
>vertices
 instead of
visited_vertice
you could name this dictionaryseen
. A matter of choice. traverse_visited_vertice
could simply betraversed
? why using a list for
count
? it's only an integer, right ? If I understand well, you use it to store invalue
the index of vertex v in the listtime_of_visit
, i.e., the order in which vertices are visited by DFS. So, we have:value = {v:i for i,v in enumerate(time_of_visit)}
 instead of
time_of_visit
, you could useorder
ofdfs_order
. Could be (at least for me) easier to understand, especially sincetime_of_visit[4]
is a vertex, not a time.
 why are you introducing variable
graph
instead of usingself
?
n = graph.num_verts()
>n = self.order()
I prefer this way, but both are working. Also, I'm not sure you really need the extra variablen
, but it's a detail.
 since
graph.py
is for undirected graphs only, you can removeif graph.is_directed(): raise ValueError("Graph must be undirected")
if not graph.is_connected():
why ? can't we decompose the connected components of the graph ?
if(n<3):
>if n < 3:
Please input a undirected connected graph with number of vertices > 2
>ear decomposition is defined for graphs of order at least 3
could be better.
vertices = graph.get_vertices().keys()
>vertices = graph.vertices()
is the correct method.
 the only interest of the
DFS
method is to record the parent of a vertex in a DFS order. If so, please add it in the description of the DFS method.
 when you write comments like
#make v are
, please add a space after#
.# make v are
is easier to read.
 I'm not sure to understand method
traverse
. Please add description.  In the
while True
loop, you should start bychain.append(pointer)
. No need to have it 3 times since you do it in all cases.  why using the term
pointer
?
for i in range(n):
>for u in time_of_visit:
I understand that I'm asking a lot of modifications, and I will ask for more, but it is very important to have an easy to read code, so that others can go inside an correct/improve parts if needed.
comment:10 Changed 2 years ago by
 Commit changed from ffe58a9894001159136e891bde96b7ea36e467fb to 6b19098fe004cb71c03eeb8369a7c4d4b8ca46a4
Branch pushed to git repo; I updated commit sha1. New commits:
6b19098  Code updated with modifications

comment:11 in reply to: ↑ 9 ; followup: ↓ 12 Changed 2 years ago by
Thanks for your valuable comments.
Replying to dcoudert:
Some (unordered) comments.
 Please use the same indentation style than for other methods.
Sure I will
 in the name of variables:
vertice
>vertices
Okay
 instead of
visited_vertice
you could name this dictionaryseen
. A matter of choice.traverse_visited_vertice
could simply betraversed
?
Yes, actually I always have a habit of adding some extra pieces of information in variable names, but seen and traversed are more meaningful than current ones.
 why using a list for
count
? it's only an integer, right ? If I understand well, you use it to store invalue
the index of vertex v in the listtime_of_visit
, i.e., the order in which vertices are visited by DFS. So, we have:value = {v:i for i,v in enumerate(time_of_visit)}
 instead of
time_of_visit
, you could useorder
ofdfs_order
. Could be (at least for me) easier to understand, especially sincetime_of_visit[4]
is a vertex, not a time.
Yes
 why are you introducing variable
graph
instead of usingself
?
graph gives more readability, now onwards I will use self to access input graph.
Reference: treewidth() function in graph.py
n = graph.num_verts()
>n = self.order()
I prefer this way, but both are working. Also, I'm not sure you really need the extra variablen
, but it's a detail.
I thought I will be using number of vertices value very often so I stored it in a variable, instead of calling graph.num_verts() but now it's of no use.
 since
graph.py
is for undirected graphs only, you can removeif graph.is_directed(): raise ValueError("Graph must be undirected")
But few methods like clique_complex(), checks weather the input graph is directed or not. Yes graph.py is for undirected graphs, it's mentioned at the top, I have updated the code.
if not graph.is_connected():
why ? can't we decompose the connected components of the graph ?
Yes we can do it, updated.
if(n<3):
>if n < 3:
Please input a undirected connected graph with number of vertices > 2
>ear decomposition is defined for graphs of order at least 3
could be better.
Okay.
vertices = graph.get_vertices().keys()
>vertices = graph.vertices()
is the correct method.
graph.vertices()
will return a dict
{'11': None, '10': None, '12': None, '1': None, '0': None, '3': None, '2': None, '5': None, '4': None, '7': None, '6': None, '9': None, '8': None}
where as graph.get_vertices().keys()
will give me all the keys of the dict i.e a list of vertices.
['11', '10', '12', '1', '0', '3', '2', '5', '4', '7', '6', '9', '8']
 the only interest of the
DFS
method is to record the parent of a vertex in a DFS order. If so, please add it in the description of the DFS method.
Yes.
 when you write comments like
#make v are
, please add a space after#
.# make v are
is easier to read.
 I'm not sure to understand method
traverse
. Please add description.
I added the describtion.
 In the
while True
loop, you should start bychain.append(pointer)
. No need to have it 3 times since you do it in all cases. why using the term
pointer
?
Made necessary changes.
for i in range(n):
>for u in time_of_visit:
Yes
I understand that I'm asking a lot of modifications, and I will ask for more, but it is very important to have an easy to read code, so that others can go inside an correct/improve parts if needed.
Indirectly it benefits me to write better code.
Please let me know what more I can do to improve the code performance.
New commits:
6b19098  Code updated with modifications

New commits:
6b19098  Code updated with modifications

comment:12 in reply to: ↑ 11 ; followup: ↓ 13 Changed 2 years ago by
 since
graph.py
is for undirected graphs only, you can removeif graph.is_directed(): raise ValueError("Graph must be undirected")
But few methods like clique_complex(), checks weather the input graph is directed or not.
Should not since in graph.py, the methods are for Graph, and so not directed. It's different in generic_graph.py
of course.
vertices = graph.get_vertices().keys()
>vertices = graph.vertices()
is the correct method.
graph.vertices()
will return a dict
{'11': None, '10': None, '12': None, '1': None, '0': None, '3': None, '2': None, '5': None, '4': None, '7': None, '6': None, '9': None, '8': None}
where asgraph.get_vertices().keys()
will give me all the keys of the dict i.e a list of vertices.
['11', '10', '12', '1', '0', '3', '2', '5', '4', '7', '6', '9', '8']
Read carefully what I wrote.
sage: G = graphs.PetersenGraph() sage: G.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: print G.get_vertices() {0: None, 1: None, 2: None, 3: None, 4: None, 5: None, 6: None, 7: None, 8: None, 9: None}
and in a loop it's better to use G.vertex_iterator()
, G.neighbor_iterator(u)
, G.edge_iterator()
, etc. to avoid building the list before iterating on it.
comment:13 in reply to: ↑ 12 Changed 2 years ago by
Replying to dcoudert:
 since
graph.py
is for undirected graphs only, you can removeif graph.is_directed(): raise ValueError("Graph must be undirected")
But few methods like clique_complex(), checks weather the input graph is directed or not.
Should not since in graph.py, the methods are for Graph, and so not directed. It's different in
generic_graph.py
of course.
Yes but still some functions are still checking it, might be there are not updated yet.
vertices = graph.get_vertices().keys()
>vertices = graph.vertices()
is the correct method.
graph.vertices()
will return a dict
{'11': None, '10': None, '12': None, '1': None, '0': None, '3': None, '2': None, '5': None, '4': None, '7': None, '6': None, '9': None, '8': None}
where asgraph.get_vertices().keys()
will give me all the keys of the dict i.e a list of vertices.
['11', '10', '12', '1', '0', '3', '2', '5', '4', '7', '6', '9', '8']
Read carefully what I wrote.
sage: G = graphs.PetersenGraph() sage: G.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: print G.get_vertices() {0: None, 1: None, 2: None, 3: None, 4: None, 5: None, 6: None, 7: None, 8: None, 9: None}
My mistake, thanks for correcting it again.
and in a loop it's better to use
G.vertex_iterator()
,G.neighbor_iterator(u)
,G.edge_iterator()
, etc. to avoid building the list before iterating on it.
Yes this will save space and time.
Update you as soon as I complete these changes.
Thanks.
comment:14 followup: ↓ 15 Changed 2 years ago by
 Commit changed from 6b19098fe004cb71c03eeb8369a7c4d4b8ca46a4 to aea74614d348a084fa3470802578f8363d7912c1
Branch pushed to git repo; I updated commit sha1. New commits:
aea7461  Updated the code with necessary modifications

comment:15 in reply to: ↑ 14 Changed 2 years ago by
comment:16 followup: ↓ 17 Changed 2 years ago by
Quick comments before going to a meeting :(
 the test
if(pointer==start):
is useless due to previous testif(traversed[pointer])
 in if statements, don't add (..). It's not needed when there is a unique condition.
 in the
for v in vertices:
loop, I fear that if the graph is not connected, you might visit again all previously treated components. Please check. May be you have to initialize some variables locally (i.e., not seen) to work only on the connected component.
comment:17 in reply to: ↑ 16 Changed 2 years ago by
Thanks for quick response. Replying to dcoudert:
Quick comments before going to a meeting :(
 the test
if(pointer==start):
is useless due to previous testif(traversed[pointer])
Yes, you are correct, actually, in the algorithm, it's mention that traverses till you find start vertex or a visited vertex. As I am marking start as visited at first step, there is no use of if(pointer==start):
.
 in if statements, don't add (..). It's not needed when there is a unique condition.
Sure
 in the
for v in vertices:
loop, I fear that if the graph is not connected, you might visit again all previously treated components. Please check. May be you have to initialize some variables locally (i.e., not seen) to work only on the connected component.
That case is taken care by seen list if not seen[v]:
.
Let us suppose we have 2 connected components with 5 vertices in each component.
Component 1 = [1,2,3,4,5]
Component 2 = [6,7,8,9,10]
When first DFS(1) is run it will visit 4 vertices and mark it as seen .i.e [1,2,3,4,5]
. So those 5 vertices can't be used again to call DFS(v)
.
When vertice 6 comes it will call DFS(6), which will visit remaining 4 vertices and mark it as seen.
By this, all the vertices and connected components are covered, with extra cost(if not seen[v]
), running on all vertices. i.e. for v in vertices
P.S: seen is not reinitialized after DFS call.
comment:18 Changed 2 years ago by
 Commit changed from aea74614d348a084fa3470802578f8363d7912c1 to 8def07b9111e3dfe85fd9f40698606b29bcc0091
Branch pushed to git repo; I updated commit sha1. New commits:
8def07b  Updated Traverse function

comment:19 followup: ↓ 21 Changed 2 years ago by
the loop for u in dfs_order:
will visit all vertices, including the vertices in other connected components. If you reset dfs_order
before the DFS call, the for loop will consider only vertices in this connected component.
comment:20 Changed 2 years ago by
 Commit changed from 8def07b9111e3dfe85fd9f40698606b29bcc0091 to 60cb3ede92ad0f2fbc5dbc0b13f9967baa1857a9
Branch pushed to git repo; I updated commit sha1. New commits:
60cb3ed  dfs_order reset

comment:21 in reply to: ↑ 19 Changed 2 years ago by
Replying to dcoudert:
the loop
for u in dfs_order:
will visit all vertices, including the vertices in other connected components. If you resetdfs_order
before the DFS call, the for loop will consider only vertices in this connected component.
Yes, you are correct, I should reset dfs_order after using it. It will save time and force to find chains in current dfs_tree instead of going back to the previous dfs_tree and find none.
comment:22 followup: ↓ 23 Changed 2 years ago by
Indentation: in general, we use 4 spaces for the indentation. Please update the code accordingly.
I propose some modifications in the DFS method. For instance using an iterator over the neighbors, etc.
def DFS(v): """ Depth first search step from vertex v. """ seen[v] = True dfs_order.append(v) # Explore the neighbors of v for u in self.neighbor_iterator(v): if not seen[u]: # Set the parent of u in DFS tree as v and continue exploration parent[u] = v DFS(u)
in method traverse
:
 you can do
chain = [start]
if(traversed[pointer]):
>if traversed[pointer]:
You use a dictionary for seen and for traversed. This is fine. Note however that you could use sets instead (not list). That is, testing u in seen
or seen[u]
is the same, and one should be as fast as the other. The advantage of using sets is that you don't need to initialize them (a very minor speed up). You then have to use seen.add(u)
instead of seen[u] = True
.
You initialize parent[vertices[0]] = 1
. This is not a good idea since 1
could be a vertex.
sage: G = Graph([(1, 2)]) sage: 1 in G True
You can either initialize the parent to itself or to None
.
The next step will be to polish the documentation of the method, the examples and the tests. For instance:
This module implements the function for computing the Ear Decomposition of undirected graphs.
>Return the Ear decomposition of the graph
 Then, with a blank line separation, it is important to add explanation of what is ear decomposition.
 the terms input, output, examples should be capitalized (see other methods)
 Since the method can raise errors, we must have specific doctests for that (see other methods)
comment:23 in reply to: ↑ 22 Changed 2 years ago by
Thanks for your comments.
Replying to dcoudert:
Indentation: in general, we use 4 spaces for the indentation. Please update the code accordingly.
I use sublime text editor(https://www.sublimetext.com/), which shows me that all the other functions uses 2 spaces, sure I will use vim and update it to 4 spaces.
I propose some modifications in the DFS method. For instance using an iterator over the neighbors, etc.
def DFS(v): """ Depth first search step from vertex v. """ seen[v] = True dfs_order.append(v) # Explore the neighbors of v for u in self.neighbor_iterator(v): if not seen[u]: # Set the parent of u in DFS tree as v and continue exploration parent[u] = v DFS(u)
It will make DFS more readable.
in method
traverse
:
 you can do
chain = [start]
if(traversed[pointer]):
>if traversed[pointer]:
You use a dictionary for seen and for traversed. This is fine. Note however that you could use sets instead (not list). That is, testing
u in seen
orseen[u]
is the same, and one should be as fast as the other. The advantage of using sets is that you don't need to initialize them (a very minor speed up). You then have to useseen.add(u)
instead ofseen[u] = True
.
Yes it's true, I will update it to set, as for large input even minor speedup matters.
You initialize
parent[vertices[0]] = 1
. This is not a good idea since1
could be a vertex.sage: G = Graph([(1, 2)]) sage: 1 in G TrueYou can either initialize the parent to itself or to
None
.
I was thinking to update parent[vertices[0]] = 1
with None
.
The next step will be to polish the documentation of the method, the examples and the tests. For instance:
This module implements the function for computing the Ear Decomposition of undirected graphs.
>Return the Ear decomposition of the graph
 Then, with a blank line separation, it is important to add explanation of what is ear decomposition.
Sure I will add the formal definition of Ear Decomposition.
 the terms input, output, examples should be capitalized (see other methods)
Okay
 Since the method can raise errors, we must have specific doctests for that (see other methods)
I don't have any knowledge about doctests, currently, I am going through sage doc http://doc.sagemath.org/html/en/developer/doctesting.html, please let me know if any other better document is available for doctests.
I will update you as soon as I complete these modifications.
comment:24 followup: ↓ 25 Changed 2 years ago by
 Commit changed from 60cb3ede92ad0f2fbc5dbc0b13f9967baa1857a9 to 713062b0440319842c532f68fef26b42e9a19df9
Branch pushed to git repo; I updated commit sha1. New commits:
713062b  Updated DFS, doctests passed, Reference and defination added

comment:25 in reply to: ↑ 24 Changed 2 years ago by
parent[vertices[0]] = None
As first nontree edge will be from first vertices[0]
and in the next step traversed.add(start)
it will be marked as traversed, it doesn't matter whether its parent value is initialized or not as its parent value won't be used.
Definition, Wikipedia link and Reference is added.
Doctests:
Example1: g is simple undirected Graph.
Example2: g is disconnected graph with one component order < 3
Example3: g is disconnected graph with 2 components, both components order > 3.
Example4: G is Looped multigraph on 7 vertices and H is Graph on 7 vertices, both generates the same result.
Example5: g is disconnected graph with vertices as strings, not as numbers.
Example6: g is an empty graph.
harsh@Python:~/sage$ ./sage t src/sage/graphs/graph.py
too few successful tests, not using stored timings
Running doctests with ID 2018032122331627e4502a.
Git branch: EarDecomposition?
Using optional=mpir,python2,sage
Doctesting 1 file.
sage t src/sage/graphs/graph.py
[982 tests, 21.54 s]
All tests passed!
Total time for all tests: 21.8 seconds
cpu time: 12.3 seconds
cumulative wall time: 21.5 seconds
Please let me know if any more example needs to be added, I have one doubt many function in graph.py has @doc_index("...")
what does it mean? and if I need to add @doc_index()
to ear_decomposition()
function, what files I need to changes.
Replying to dcoudert:
Branch pushed to git repo; I updated commit sha1. New commits:
713062b Updated DFS, doctests passed, Reference and defination added
comment:26 followup: ↓ 30 Changed 2 years ago by
 comments must be formatted in 80 columns mode. Some code editors ease this formatting.
Return the Ear decomposition of the graph
>Return an Ear decomposition of the graph
I just realized that the decomposition is not unique...
An ear of an undirected graph G is a path P where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in P.
>An ear of an undirected graph `G` is a path `P` where the two endpoints of the path may coincide (i.e., form a cycle), but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in `P`.
This way, G and P will be in latex mode. Furthermore, move the definition of an ear before the definition of an ear decomposition.
 References should be placed in file
src/doc/en/reference/references/index.rst
. Use the same style than for other references.
 Then you can add:
This method implements the linear time algorithm presented in [Sch2013]_
A nested list representing the cycle and chains of input graph G.
>A nested list representing the cycles and chains of the ear decomposition of the graph.
 about examples: what is the purpose of each of these examples ?
 you should use the following structure for examples.
EXAMPLES: Ear decomposition of an outer plananr graph of order 13:: sage: g = Graph('LlCG{O@?GBOMW?')
I have turned your graph to a graph6 string for compactness.
 What's the expected behavior of the method on multigraphs ?
 You could add a simple example with a non connected graph.
 We might have an issue with non connected graph, for instance with
g = Graph(4)
org = Graph([(0,1), (1,2)])
. Any idea on how to handle these cases ?
 I don't like the block with the description of all variables / methods. I would prefer to scatter definitions where they belong: inside the methods for instance.

@doc_index("...")
is used for automatic inclusion of the method into the lists of methods implemented in this file. You can see the list when looking at the html documentation. You just have to add@doc_index("Connectivity, orientations, trees")
 how difficult would it be to extend this method for directed graphs ?
comment:27 Changed 2 years ago by
 Reviewers set to David Coudert
Don't forget to add your full name in the "authors" field of this page
comment:28 Changed 2 years ago by
comment:29 Changed 2 years ago by
 Commit changed from 713062b0440319842c532f68fef26b42e9a19df9 to e8a817cf5d84c68e920c0da3181301ada3752e29
Branch pushed to git repo; I updated commit sha1. New commits:
e8a817c  Examples, definition and reference updated

comment:30 in reply to: ↑ 26 ; followup: ↓ 31 Changed 2 years ago by
Apologies, because of classes I was unable to update it.
Replying to dcoudert:
 comments must be formatted in 80 columns mode. Some code editors ease this formatting.
Sure I will follow this format.
Return the Ear decomposition of the graph
>Return an Ear decomposition of the graph
I just realized that the decomposition is not unique...
Yes, ear decomposition is not unique, it depends on DFS Tree and process of nontree edges.
An ear of an undirected graph G is a path P where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in P.
>An ear of an undirected graph `G` is a path `P` where the two endpoints of the path may coincide (i.e., form a cycle), but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in `P`.
This way, G and P will be in latex mode. Furthermore, move the definition of an ear before the definition of an ear decomposition.
Updated ear and ear decomposition definition.
 References should be placed in file
src/doc/en/reference/references/index.rst
. Use the same style than for other references.
 Then you can add:
This method implements the linear time algorithm presented in [Sch2013]_
Updated.
A nested list representing the cycle and chains of input graph G.
>A nested list representing the cycles and chains of the ear decomposition of the graph.
 about examples: what is the purpose of each of these examples ?
 you should use the following structure for examples.
EXAMPLES: Ear decomposition of an outer planar graph of order 13:: sage: g = Graph('LlCG{O@?GBOMW?')
Updated
I have turned your graph to a graph6 string for compactness.
 What's the expected behavior of the method on multigraphs ?
It's same as when we take the simple graph of a multigraph. an example of multigraph and simple graph added.
 You could add a simple example with a non connected graph.
Added
sage: g = Graph([(0, 1),(0, 7),(0, 3),(0, 11),(2, 3),(1, 2),(1, 12),(2, 12),(3, 4),(3, 6),(4, 5),(4, 7),(4, 6),(5, 6),(7, 10),(7, 8),(7, 11),(8, 9),(8, 10),(8, 11),(9, 11), (12, 13)])
It's a non connected graph, in which one component is will have one edge i.e 1213(12 & 13 are vertices). When we do ear decomposition 1213 vertices won't be available in any of the chains as 1213 is a tree edge.
 We might have an issue with non connected graph, for instance with
g = Graph(4)
org = Graph([(0,1), (1,2)])
. Any idea on how to handle these cases ?
According to current algorithm, the output will be [] as no nontree edges are available.
 I don't like the block with the description of all variables / methods. I would prefer to scatter definitions where they belong: inside the methods for instance.
Scattered all the definitions where they belong.
@doc_index("...")
is used for automatic inclusion of the method into the lists of methods implemented in this file. You can see the list when looking at the html documentation. You just have to add@doc_index("Connectivity, orientations, trees")
Added
 how difficult would it be to extend this method for directed graphs ?
To the best of my knowledge, the current algorithm can't be used because of the following reasons.
 When we take DFS tree of a directed connected graph, there is a chance of getting a cross edge from one subtree to another subtree, which is not a case in the undirected connected graph.
 We use nontree edges in DFS tree of an undirected graph, bottomup traversal, which may not be possible in the current algorithm for a directed graph.
We can try few ways to overcome these problems but can't say whether the output represents ear decomposition or not. (I am open to any suggestions.)
comment:31 in reply to: ↑ 30 ; followup: ↓ 32 Changed 2 years ago by
 comments must be formatted in 80 columns mode. Some code editors ease this formatting.
Sure I will follow this format.
I think you are in 90 columns format. The counting includes the white spaces at the left. The same must be done for input, etc.
``graph``
> ``self``
 Then you can add:
This method implements the linear time algorithm presented in [Sch2013]_
Updated.
I don't see it and you still have a reference
block.
 What's the expected behavior of the method on multigraphs ?
It's same as when we take the simple graph of a multigraph. an example of multigraph and simple graph added.
 You could add a simple example with a non connected graph.
Added
sage: g = Graph([(0, 1),(0, 7),(0, 3),(0, 11),(2, 3),(1, 2),(1, 12),(2, 12),(3, 4),(3, 6),(4, 5),(4, 7),(4, 6),(5, 6),(7, 10),(7, 8),(7, 11),(8, 9),(8, 10),(8, 11),(9, 11), (12, 13)])It's a non connected graph, in which one component is will have one edge i.e 1213(12 & 13 are vertices). When we do ear decomposition 1213 vertices won't be available in any of the chains as 1213 is a tree edge.
First, this is a connected graph but not a biconnected graph. I suggest using simpler examples like this for non connected graphs
sage: g = graphs.CycleGraph(3) + graphs.CycleGraph(4)
or this for connected but not biconnected
sage: g = graphs.BullGraph()
or for multigraph with a loop
sage: g = graphs.BullGraph() sage: g.allow_multiple_edges(True) sage: g.add_edges(g.edges()) sage: g.allow_loops(True) sage: u = g.random_vertex() sage: g.add_edge(u, u)
 We might have an issue with non connected graph, for instance with
g = Graph(4)
org = Graph([(0,1), (1,2)])
. Any idea on how to handle these cases ?According to current algorithm, the output will be [] as no nontree edges are available.
Can you clarify the definition for non connected graphs: should the method return a decomposition of each connected component or [] ? in particular, what if a connected component is of order < 3 since the ear decomposition is defined for graphs of order >= 3 ?
 how difficult would it be to extend this method for directed graphs ?
To the best of my knowledge, the current algorithm can't be used because of the following reasons.
 When we take DFS tree of a directed connected graph, there is a chance of getting a cross edge from one subtree to another subtree, which is not a case in the undirected connected graph.
 We use nontree edges in DFS tree of an undirected graph, bottomup traversal, which may not be possible in the current algorithm for a directed graph.
We can try few ways to overcome these problems but can't say whether the output represents ear decomposition or not. (I am open to any suggestions.)
I'm not aware of existing algorithms (if any). If an algorithm has already been proposed, we can add it. If not, we can skip this question.
comment:32 in reply to: ↑ 31 Changed 2 years ago by
Replying to dcoudert:
 comments must be formatted in 80 columns mode. Some code editors ease this formatting.
Sure I will follow this format.
I think you are in 90 columns format. The counting includes the white spaces at the left. The same must be done for input, etc.
Updated.
``graph``
>``self``
replaced.
 Then you can add:
This method implements the linear time algorithm presented in [Sch2013]_
Updated.
I don't see it and you still have a
reference
block.
Updated, please let me know it's at right place or not.
 What's the expected behavior of the method on multigraphs ?
It's same as when we take the simple graph of a multigraph. an example of multigraph and simple graph added.
 You could add a simple example with a non connected graph.
Added
sage: g = Graph([(0, 1),(0, 7),(0, 3),(0, 11),(2, 3),(1, 2),(1, 12),(2, 12),(3, 4),(3, 6),(4, 5),(4, 7),(4, 6),(5, 6),(7, 10),(7, 8),(7, 11),(8, 9),(8, 10),(8, 11),(9, 11), (12, 13)])It's a non connected graph, in which one component is will have one edge i.e 1213(12 & 13 are vertices). When we do ear decomposition 1213 vertices won't be available in any of the chains as 1213 is a tree edge.
First, this is a connected graph but not a biconnected graph. I suggest using simpler examples like this for non connected graphs
sage: g = graphs.CycleGraph(3) + graphs.CycleGraph(4)or this for connected but not biconnected
sage: g = graphs.BullGraph()or for multigraph with a loop
sage: g = graphs.BullGraph() sage: g.allow_multiple_edges(True) sage: g.add_edges(g.edges()) sage: g.allow_loops(True) sage: u = g.random_vertex() sage: g.add_edge(u, u)
Updated examples, let me know if any changes are required.
 We might have an issue with non connected graph, for instance with
g = Graph(4)
org = Graph([(0,1), (1,2)])
. Any idea on how to handle these cases ?According to current algorithm, the output will be [] as no nontree edges are available.
Can you clarify the definition for non connected graphs: should the method return a decomposition of each connected component or [] ? in particular, what if a connected component is of order < 3 since the ear decomposition is defined for graphs of order >= 3 ?
The graphs(order < 3) will have either isolated single node which plays no role in decomposition or 2 nodes with multiple edges in between them which is same as v1  v2
as only one edge is present no cycle or chain is possible.
To be more formal, if an undirected graph has n1 edges or no nontree edges left after DFS traversal then ear decomposition of such graph/components will be empty.
 how difficult would it be to extend this method for directed graphs?
To the best of my knowledge, the current algorithm can't be used because of the following reasons.
 When we take DFS tree of a directed connected graph, there is a chance of getting a cross edge from one subtree to another subtree, which is not a case in the undirected connected graph.
 We use nontree edges in DFS tree of an undirected graph, bottomup traversal, which may not be possible in the current algorithm for a directed graph.
We can try few ways to overcome these problems but can't say whether the output represents ear decomposition or not. (I am open to any suggestions.)
I'm not aware of existing algorithms (if any). If an algorithm has already been proposed, we can add it. If not, we can skip this question.
Currently, we can skip it.
comment:33 Changed 2 years ago by
 Commit changed from e8a817cf5d84c68e920c0da3181301ada3752e29 to c5c8fcab58e8c504cfc839e393ab28cb5bc40dc7
Branch pushed to git repo; I updated commit sha1. New commits:
c5c8fca  updated example, doctest passed.

comment:34 followup: ↓ 35 Changed 2 years ago by
 Status changed from new to needs_review
I turned the ticket to "needs review". Otherwise I will never be able to give positive review ;)
presented in [Sch2013].
>presented in [Sch2013]_.
This is the way to cite a reference with sphynx.
outer plananr
>outer planar
g = g = graphs.CubeGraph(2)
remove one of theg =
Ear decomposition of a disconnected graph of order 17::
again, this graph IS connected but not biconnected. If the goal of this test is to show the behavior on a connected graph with 2 biconnected blocks, a simpler example (i.e., that one can understand without plotting the graph etc.) could besage: G = Graph() sage: G.add_cycle([0,1,2]) sage: G.add_edge(0,3) sage: G.add_cycle([3,4,5,6])
 add an empty line after
TESTS::
g=Graph([])
>g = Graph()
and no need for the linesage: g
, we know it's the empty graph.
ValueError("Ear decomposition is defined for graphs of order at least 3.")
>ValueError("ear decomposition is defined for graphs of order at least 3")
no capital letter at the beginning of the message, and no point at the end. It's not unified in Sagemath, but it will slowly be modified.
self.order()<3
>self.order() < 3
It's a coding recommendation (PEP...).
When at check the branch u/saiharsh/EarDecomposition, I see
diff git a/gittraccommand b/gittraccommand new file mode 160000 +Subproject 01cb18f9432a41ff32ca5922bff8fbed3156d28
I assume it's not part of this ticket. Can you check ? It's the first time I see that in a branch...
Almost done !
comment:35 in reply to: ↑ 34 Changed 2 years ago by
Replying to dcoudert:
I turned the ticket to "needs review". Otherwise I will never be able to give positive review ;)
Could you please have a look again, I have modified the code according to your suggestions. Thanks for helping me I have learned a lot about the coding and commenting style.
presented in [Sch2013].
>presented in [Sch2013]_.
This is the way to cite a reference with sphynx.
outer plananr
>outer planar
g = g = graphs.CubeGraph(2)
remove one of theg =
Ear decomposition of a disconnected graph of order 17::
again, this graph IS connected but not biconnected. If the goal of this test is to show the behavior on a connected graph with 2 biconnected blocks, a simpler example (i.e., that one can understand without plotting the graph etc.) could besage: G = Graph() sage: G.add_cycle([0,1,2]) sage: G.add_edge(0,3) sage: G.add_cycle([3,4,5,6])
 add an empty line after
TESTS::
g=Graph([])
>g = Graph()
and no need for the linesage: g
, we know it's the empty graph.
ValueError("Ear decomposition is defined for graphs of order at least 3.")
>ValueError("ear decomposition is defined for graphs of order at least 3")
no capital letter at the beginning of the message, and no point at the end. It's not unified in Sagemath, but it will slowly be modified.
self.order()<3
>self.order() < 3
It's a coding recommendation (PEP...).
Updated all the minor changes.
When at check the branch u/saiharsh/EarDecomposition, I see
diff git a/gittraccommand b/gittraccommand new file mode 160000 +Subproject 01cb18f9432a41ff32ca5922bff8fbed3156d28I assume it's not part of this ticket. Can you check ? It's the first time I see that in a branch...
I am unable to see it could you provide me more information about it.
Almost done !
Thanks.
Could you please have a look at my comment at ticket: 22157: Add SPQRtree decomposition for 2vertexconnected graphs.
comment:36 Changed 2 years ago by
 Commit changed from c5c8fcab58e8c504cfc839e393ab28cb5bc40dc7 to 79b64d603dc7cb9c342c1aea73416e12bf224090
Branch pushed to git repo; I updated commit sha1. New commits:
79b64d6  Updated

comment:37 followup: ↓ 39 Changed 2 years ago by
Please carefully check your code before pushing a commit.
Ear decomposition of a disconnected graph of order 17::
but the example is different. The text could beEar decomposition of a connected but not biconnected graph::
I have additional comments:
Ear decomposition of multigraph(g) is same as ear decomposition on simple graph(g)::
could beThe ear decomposition of a multigraph with loops is the same as the ear decomposition of the underlying simple graph::
 Instead of
sage: h = copy(g) sage: h.allow_multiple_edges(False) sage: h.allow_loops(False)
you can usesage: h = g.to_simple()
 When I checkout your code, I see:
Fastforward (no commit created; m option ignored) gittraccommand  1 + src/doc/en/reference/references/index.rst  5 +++ src/sage/graphs/graph.py  175 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 181 insertions(+) create mode 160000 gittraccommand
 Another important correction to perform: the code contains a lot of
trailing white spaces
= extra spaces at the end of a line, blank line containing some spaces at the beginning, etc. Please remove them. You can see them when you dogit diff
in your terminal, or for instance when searching for spaces in emacs (and certainly other code editors). See http://doc.sagemath.org/html/en/developer/coding_basics.html
comment:38 Changed 2 years ago by
 Commit changed from 79b64d603dc7cb9c342c1aea73416e12bf224090 to e7ec5d6f4edb8ccc13b560572723adfb6d666b23
Branch pushed to git repo; I updated commit sha1. New commits:
e7ec5d6  Extra spaces removed, minor updations

comment:39 in reply to: ↑ 37 Changed 2 years ago by
Replying to dcoudert:
Please carefully check your code before pushing a commit.
Ear decomposition of a disconnected graph of order 17::
but the example is different. The text could beEar decomposition of a connected but not biconnected graph::
Yes I should have changed it, before commiting it. I apologies for it.
I have additional comments:
Ear decomposition of multigraph(g) is same as ear decomposition on simple graph(g)::
could beThe ear decomposition of a multigraph with loops is the same as the ear decomposition of the underlying simple graph::
Thanks for the suggestion.
 Instead of
sage: h = copy(g) sage: h.allow_multiple_edges(False) sage: h.allow_loops(False)you can usesage: h = g.to_simple()
Updated.
 When I checkout your code, I see:
Fastforward (no commit created; m option ignored) gittraccommand  1 + src/doc/en/reference/references/index.rst  5 +++ src/sage/graphs/graph.py  175 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 181 insertions(+) create mode 160000 gittraccommand
Cross checked twice and removed all the extra spaces and lines.
 Another important correction to perform: the code contains a lot of
trailing white spaces
= extra spaces at the end of a line, blank line containing some spaces at the beginning, etc. Please remove them. You can see them when you dogit diff
in your terminal, or for instance when searching for spaces in emacs (and certainly other code editors). See http://doc.sagemath.org/html/en/developer/coding_basics.html
Thanks, I will go through it more carefully.
comment:40 Changed 2 years ago by
Could you please say why it's saying, build failed on patchbot, where I am able to successfully build in my system.
When I see build failed log of patchbot,
Sage build/upgrade complete!
fatal: Unable to read current working directory: No such file or directory
I found that it's able to build but can't read some files.
Could you please have a look and please let me know, is there any issue from my side?
comment:41 Changed 2 years ago by
The problem is independent from your patch.
Concerning your ticket.
 there are remaining trailing white spaces, for instance at the end of line
of the path may coincide (i.e., form a cycle), but where otherwise no
. Please check carefully.
 line
This method implements the linear time algorithm presented in [Sch2013]_.
must be break since it ends on column 81.
 in the description of the
traverse
method, you must add a space afterGT
.
I saw that the last version of networkx contains chain_decomposition
which should be similar to this algorithm. Unfortunately we don't have the last version in sagemath so we can't do the comparison.
comment:42 Changed 2 years ago by
 Commit changed from e7ec5d6f4edb8ccc13b560572723adfb6d666b23 to 618efe406a65110bd991c1568f848f9f49fc4d7b
Branch pushed to git repo; I updated commit sha1. New commits:
618efe4  Minor comments updated

comment:43 Changed 2 years ago by
 still a white space at the end of line
of the path may coincide (i.e., form a cycle), but where otherwise no
comment:44 Changed 2 years ago by
 Commit changed from 618efe406a65110bd991c1568f848f9f49fc4d7b to ad716448b924d312755abf2287fbb5b107d70624
Branch pushed to git repo; I updated commit sha1. New commits:
ad71644  Updated

comment:45 followup: ↓ 46 Changed 2 years ago by
 Cc dimpase added
For me this patch is now good to go, But I still don't understand this (should we care about it or not)
diff git a/gittraccommand b/gittraccommand new file mode 160000 +Subproject 01cb18f9432a41ff32ca5922bff8fbed3156d28
I'm adding Dima in cc for opinion.
comment:46 in reply to: ↑ 45 Changed 2 years ago by
 Status changed from needs_review to needs_work
Replying to dcoudert:
For me this patch is now good to go, But I still don't understand this (should we care about it or not)
diff git a/gittraccommand b/gittraccommand new file mode 160000 +Subproject 01cb18f9432a41ff32ca5922bff8fbed3156d28
This branch does contain a directory named gittraccommand. It should be removed.
comment:47 followup: ↓ 48 Changed 2 years ago by
 Commit changed from ad716448b924d312755abf2287fbb5b107d70624 to 9b43b3e65623545d549e0003887e36d73d72a00d
Branch pushed to git repo; I updated commit sha1. New commits:
9b43b3e  gittraccommand folder removed.

comment:48 in reply to: ↑ 47 ; followup: ↓ 50 Changed 2 years ago by
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
9b43b3e gittraccommand folder removed.
This branch does contain a directory named gittraccommand. It should be removed.
@dimpase, @dcoudert
I thought it's a file, which was created by me and I was searching in src folder.
I found that folder and deleted it.
Please let me know if any more changes are required.
comment:50 in reply to: ↑ 48 ; followup: ↓ 51 Changed 2 years ago by
Replying to saiharsh:
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
9b43b3e gittraccommand folder removed.
This branch does contain a directory named gittraccommand. It should be removed.
@dimpase, @dcoudert
I thought it's a file, which was created by me and I was searching in src folder.
most likely you were doing git commit a
 i.e. commit all the changes and all the new files  and thus you committed too much.
Great care must be exercised while using a
switch,
Yes, sometimes it is handy, but sometimes it leads to such SNAFU's.
comment:51 in reply to: ↑ 50 Changed 2 years ago by
Replying to dimpase:
Replying to saiharsh:
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
9b43b3e gittraccommand folder removed.
This branch does contain a directory named gittraccommand. It should be removed.
@dimpase, @dcoudert
I thought it's a file, which was created by me and I was searching in src folder.most likely you were doing
git commit a
 i.e. commit all the changes and all the new files  and thus you committed too much. Great care must be exercised while usinga
switch, Yes, sometimes it is handy, but sometimes it leads to such SNAFU's.
Sure, I will keep that in mind before making any new commits in future. I always try to run git status before committing, most likely it happend when I did my initial commits.
comment:52 Changed 23 months ago by
 Branch changed from u/saiharsh/EarDecomposition to 9b43b3e65623545d549e0003887e36d73d72a00d
 Resolution set to fixed
 Status changed from positive_review to closed
I cannot access the branch. Please check.