Opened 2 years ago

Closed 23 months ago

#25002 closed enhancement (fixed)

Ear Decomposition

Reported by: saiharsh Owned by:
Priority: major Milestone: sage-8.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 follow-up: Changed 2 years ago by dcoudert

I cannot access the branch. Please check.

comment:2 in reply to: ↑ 1 Changed 2 years ago by saiharsh

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 git

  • Commit set to a495a2160290621c942aecfd0fc728d1b1ab2a09

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

a495a21Initial Commit

comment:4 Changed 2 years ago by git

  • Commit changed from a495a2160290621c942aecfd0fc728d1b1ab2a09 to 6d747be667f7c886d787189791bd26703a92840c

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

6d747beCode Updated

comment:5 Changed 2 years ago by saiharsh

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.

comment:6 Changed 2 years ago by dcoudert

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 git

  • Commit changed from 6d747be667f7c886d787189791bd26703a92840c to ffe58a9894001159136e891bde96b7ea36e467fb

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

ffe58a9Removed ear_decomposition.py

comment:8 Changed 2 years ago by saiharsh

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 follow-up: Changed 2 years ago by dcoudert

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.

comment:10 Changed 2 years ago by git

  • Commit changed from ffe58a9894001159136e891bde96b7ea36e467fb to 6b19098fe004cb71c03eeb8369a7c4d4b8ca46a4

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

6b19098Code updated with modifications

comment:11 in reply to: ↑ 9 ; follow-up: Changed 2 years ago by saiharsh

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:

6b19098Code updated with modifications

New commits:

6b19098Code updated with modifications

comment:12 in reply to: ↑ 11 ; follow-up: Changed 2 years ago by 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.

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

comment:13 in reply to: ↑ 12 Changed 2 years ago by saiharsh

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.

comment:14 follow-up: Changed 2 years ago by git

  • Commit changed from 6b19098fe004cb71c03eeb8369a7c4d4b8ca46a4 to aea74614d348a084fa3470802578f8363d7912c1

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

aea7461Updated the code with necessary modifications

comment:15 in reply to: ↑ 14 Changed 2 years ago by saiharsh

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

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

aea7461Updated the code with necessary modifications
Last edited 2 years ago by saiharsh (previous) (diff)

comment:16 follow-up: Changed 2 years ago by dcoudert

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.

comment:17 in reply to: ↑ 16 Changed 2 years ago by saiharsh

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.

comment:18 Changed 2 years ago by git

  • Commit changed from aea74614d348a084fa3470802578f8363d7912c1 to 8def07b9111e3dfe85fd9f40698606b29bcc0091

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

8def07bUpdated Traverse function

comment:19 follow-up: Changed 2 years ago by 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.

comment:20 Changed 2 years ago by git

  • Commit changed from 8def07b9111e3dfe85fd9f40698606b29bcc0091 to 60cb3ede92ad0f2fbc5dbc0b13f9967baa1857a9

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

60cb3eddfs_order reset

comment:21 in reply to: ↑ 19 Changed 2 years ago by saiharsh

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.

comment:22 follow-up: Changed 2 years ago by dcoudert

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 saiharsh

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.

comment:24 follow-up: Changed 2 years ago by git

  • Commit changed from 60cb3ede92ad0f2fbc5dbc0b13f9967baa1857a9 to 713062b0440319842c532f68fef26b42e9a19df9

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

713062bUpdated DFS, doctests passed, Reference and defination added

comment:25 in reply to: ↑ 24 Changed 2 years ago by saiharsh

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:

713062bUpdated DFS, doctests passed, Reference and defination added

comment:26 follow-up: Changed 2 years ago by dcoudert

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

comment:27 Changed 2 years ago by dcoudert

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

  • Authors set to Tondomker Sai Harsh

comment:29 Changed 2 years ago by git

  • Commit changed from 713062b0440319842c532f68fef26b42e9a19df9 to e8a817cf5d84c68e920c0da3181301ada3752e29

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

e8a817cExamples, definition and reference updated

comment:30 in reply to: ↑ 26 ; follow-up: Changed 2 years ago by saiharsh

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

comment:31 in reply to: ↑ 30 ; follow-up: Changed 2 years ago by 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.

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

comment:32 in reply to: ↑ 31 Changed 2 years ago by saiharsh

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.

comment:33 Changed 2 years ago by git

  • Commit changed from e8a817cf5d84c68e920c0da3181301ada3752e29 to c5c8fcab58e8c504cfc839e393ab28cb5bc40dc7

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

c5c8fcaupdated example, doctest passed.

comment:34 follow-up: Changed 2 years ago by dcoudert

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

comment:35 in reply to: ↑ 34 Changed 2 years ago by saiharsh

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.

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

comment:36 Changed 2 years ago by git

  • Commit changed from c5c8fcab58e8c504cfc839e393ab28cb5bc40dc7 to 79b64d603dc7cb9c342c1aea73416e12bf224090

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

79b64d6Updated

comment:37 follow-up: Changed 2 years ago by 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 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

comment:38 Changed 2 years ago by git

  • Commit changed from 79b64d603dc7cb9c342c1aea73416e12bf224090 to e7ec5d6f4edb8ccc13b560572723adfb6d666b23

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

e7ec5d6Extra spaces removed, minor updations

comment:39 in reply to: ↑ 37 Changed 2 years ago by saiharsh

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

Updated.

  • 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
    

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

Thanks, I will go through it more carefully.

comment:40 Changed 2 years ago by saiharsh

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 dcoudert

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 after G-T.

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 git

  • Commit changed from e7ec5d6f4edb8ccc13b560572723adfb6d666b23 to 618efe406a65110bd991c1568f848f9f49fc4d7b

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

618efe4Minor comments updated

comment:43 Changed 2 years ago by dcoudert

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

  • Commit changed from 618efe406a65110bd991c1568f848f9f49fc4d7b to ad716448b924d312755abf2287fbb5b107d70624

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

ad71644Updated

comment:45 follow-up: Changed 2 years ago by dcoudert

  • 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/git-trac-command b/git-trac-command
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 dimpase

  • 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/git-trac-command b/git-trac-command
new file mode 160000
+Subproject 01cb18f9432a41ff32ca5922bff8fbed3156d28

This branch does contain a directory named git-trac-command. It should be removed.

comment:47 follow-up: Changed 2 years ago by git

  • Commit changed from ad716448b924d312755abf2287fbb5b107d70624 to 9b43b3e65623545d549e0003887e36d73d72a00d

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

9b43b3egit-trac-command folder removed.

comment:48 in reply to: ↑ 47 ; follow-up: Changed 2 years ago by saiharsh

Replying to git:

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

9b43b3egit-trac-command folder removed.

This branch does contain a directory named git-trac-command. 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:49 Changed 2 years ago by dcoudert

  • Status changed from needs_work to positive_review

Thank you Dima.

comment:50 in reply to: ↑ 48 ; follow-up: Changed 2 years ago by dimpase

Replying to saiharsh:

Replying to git:

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

9b43b3egit-trac-command folder removed.

This branch does contain a directory named git-trac-command. 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 saiharsh

Replying to dimpase:

Replying to saiharsh:

Replying to git:

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

9b43b3egit-trac-command folder removed.

This branch does contain a directory named git-trac-command. 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.

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 vbraun

  • Branch changed from u/saiharsh/EarDecomposition to 9b43b3e65623545d549e0003887e36d73d72a00d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.