Ear Decomposition

[61453475-51f7-4d25-8062-038d85d714fa]

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.

CC: @dcoudert @dimpase

Component: graph theory

Keywords: Ear Decomposition

Author: Tondomker Sai Harsh

Branch/Commit: 9b43b3e

Reviewer: David Coudert

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

[dcoudert]

comment:1

I cannot access the branch. Please check.

[61453475-51f7-4d25-8062-038d85d714fa]

comment:2

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Commit: a495a21

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a495a21

Initial Commit

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a495a21 to 6d747be

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

6d747be

Code Updated

[61453475-51f7-4d25-8062-038d85d714fa]

comment:5

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:

1. Construct a depth-first search (dfs) spanning tree T of G ;
2. Traverse in Spanning Tree using G-T non-tree edges.

Potential Applications:

1. A graph G is biconnected if and only if it has an open ear decomposition.
2. A graph G is factor-critical if and only if G has an odd ear decomposition.
3. Verification to check if graph is 2-edge 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.

[dcoudert]

comment:6

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6d747be to ffe58a9

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ffe58a9

Removed ear_decomposition.py

[61453475-51f7-4d25-8062-038d85d714fa]

comment:8

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.

[dcoudert]

comment:9

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 dictionary seen. A matter of choice.

• traverse_visited_vertice could simply be traversed ?

• why using a list for count ? it's only an integer, right ? If I understand well, you use it to store in value the index of vertex v in the list time_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 use order of dfs_order. Could be (at least for me) easier to understand, especially since time_of_visit[4] is a vertex, not a time.

• why are you introducing variable graph instead of using self ?

• 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 variable n, but it's a detail.

• since graph.py is for undirected graphs only, you can remove if 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 by chain.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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ffe58a9 to 6b19098

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

6b19098

Code updated with modifications

[61453475-51f7-4d25-8062-038d85d714fa]

comment:11

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 dictionary seen. A matter of choice.
• traverse_visited_vertice could simply be traversed ?

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 in value the index of vertex v in the list time_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 use order of dfs_order. Could be (at least for me) easier to understand, especially since time_of_visit[4] is a vertex, not a time.

Yes

• why are you introducing variable graph instead of using self ?

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 variable n, 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 remove if 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 by chain.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

[dcoudert]

comment:12

• since graph.py is for undirected graphs only, you can remove if 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 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']

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.

[61453475-51f7-4d25-8062-038d85d714fa]

comment:13

Replying to @dcoudert:

• since graph.py is for undirected graphs only, you can remove if 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 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']

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6b19098 to aea7461

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

aea7461

Updated the code with necessary modifications

[61453475-51f7-4d25-8062-038d85d714fa]

comment:15

The code is updated, please have a look. Replying to @dcoudert:

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

aea7461

Updated the code with necessary modifications

[dcoudert]

comment:16

Quick comments before going to a meeting :(

• the test if(pointer==start): is useless due to previous test if(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.

[61453475-51f7-4d25-8062-038d85d714fa]

comment:17

Thanks for quick response. Replying to @dcoudert:

Quick comments before going to a meeting :(

• the test if(pointer==start): is useless due to previous test if(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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

8def07b

Updated Traverse function

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from aea7461 to 8def07b

[dcoudert]

comment:19

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8def07b to 60cb3ed

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

60cb3ed

dfs_order reset

[61453475-51f7-4d25-8062-038d85d714fa]

comment:21

Replying to @dcoudert:

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.

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.

[dcoudert]

comment:22

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)

[61453475-51f7-4d25-8062-038d85d714fa]

comment:23

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 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.

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 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.

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

713062b

Updated DFS, doctests passed, Reference and defination added

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 60cb3ed to 713062b

[61453475-51f7-4d25-8062-038d85d714fa]

comment:25

parent[vertices[0]] = None

As first non-tree 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 multi-graph 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 2018-03-21-22-33-16-27e4502a.

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

[dcoudert]

comment:26

• 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) or g = 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 ?

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:27

Don't forget to add your full name in the "authors" field of this page

[61453475-51f7-4d25-8062-038d85d714fa]

Author: Tondomker Sai Harsh

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 713062b to e8a817c

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e8a817c

Examples, definition and reference updated

[61453475-51f7-4d25-8062-038d85d714fa]

comment:30

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 non-tree 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 12-13(12 & 13 are vertices). When we do ear decomposition 12-13 vertices won't be available in any of the chains as 12-13 is a tree edge.

• We might have an issue with non connected graph, for instance with g = Graph(4) or g = Graph([(0,1), (1,2)]). Any idea on how to handle these cases ?

According to current algorithm, the output will be [] as no non-tree 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.

1. 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.

2. We use non-tree edges in DFS tree of an undirected graph, bottom-up 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.)

[dcoudert]

comment:31

• 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 12-13(12 & 13 are vertices). When we do ear decomposition 12-13 vertices won't be available in any of the chains as 12-13 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) or g = Graph([(0,1), (1,2)]). Any idea on how to handle these cases ?

According to current algorithm, the output will be [] as no non-tree 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.

1. 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.

2. We use non-tree edges in DFS tree of an undirected graph, bottom-up 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.

[61453475-51f7-4d25-8062-038d85d714fa]

comment:32

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 12-13(12 & 13 are vertices). When we do ear decomposition 12-13 vertices won't be available in any of the chains as 12-13 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) or g = Graph([(0,1), (1,2)]). Any idea on how to handle these cases ?

According to current algorithm, the output will be [] as no non-tree 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 n-1 edges or no non-tree 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.

1. 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.

2. We use non-tree edges in DFS tree of an undirected graph, bottom-up 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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c5c8fca

updated example, doctest passed.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e8a817c to c5c8fca

[dcoudert]

comment:34

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 the g =

• 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 be

sage: 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 line sage: 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/git-trac-command b/git-trac-command
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 !

[61453475-51f7-4d25-8062-038d85d714fa]

comment:35

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 the g =

• 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 be

sage: 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 line sage: 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/git-trac-command b/git-trac-command
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...

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 SPQR-tree decomposition for 2-vertex-connected graphs.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

79b64d6

Updated

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c5c8fca to 79b64d6

[dcoudert]

comment:37

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 be Ear 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 be The 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 use sage: h = g.to_simple()

• When I checkout your code, I see:

Fast-forward (no commit created; -m option ignored)
 git-trac-command                          |   1 +
 src/doc/en/reference/references/index.rst |   5 +++
 src/sage/graphs/graph.py                  | 175 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 181 insertions(+)
 create mode 160000 git-trac-command

• 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 do git 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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e7ec5d6

Extra spaces removed, minor updations