Ear Decomposition

[sagetrac-saiharsh]

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.

[sagetrac-saiharsh]

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.

[sagetrac-git]

Commit: a495a21

[sagetrac-git]

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

a495a21

Initial Commit

[sagetrac-git]

Changed commit from a495a21 to 6d747be

[sagetrac-git]

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

6d747be

Code Updated

[sagetrac-saiharsh]

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.

[sagetrac-git]

Changed commit from 6d747be to ffe58a9

[sagetrac-git]

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

ffe58a9

Removed ear_decomposition.py

[sagetrac-saiharsh]

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.

[sagetrac-git]

Changed commit from ffe58a9 to 6b19098

[sagetrac-git]

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

6b19098

Code updated with modifications

[sagetrac-saiharsh]

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.

[sagetrac-saiharsh]

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.

[sagetrac-git]

Changed commit from 6b19098 to aea7461

[sagetrac-git]

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

aea7461

Updated the code with necessary modifications

[sagetrac-saiharsh]

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.

[sagetrac-saiharsh]

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.

[sagetrac-git]

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

8def07b

Updated Traverse function

[sagetrac-git]

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.

[sagetrac-git]

Changed commit from 8def07b to 60cb3ed

[sagetrac-saiharsh]

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.

[sagetrac-git]

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

79b64d6

Updated

[sagetrac-git]

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

[sagetrac-git]

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

e7ec5d6

Extra spaces removed, minor updations

[sagetrac-git]

Changed commit from 79b64d6 to e7ec5d6

[sagetrac-saiharsh]

comment:39

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.

[sagetrac-saiharsh]

comment:40

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?

[dcoudert]

comment:41

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.

[sagetrac-git]

Changed commit from e7ec5d6 to 618efe4

[sagetrac-git]

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

618efe4

Minor comments updated

[dcoudert]

comment:43

• still a white space at the end of line of the path may coincide (i.e., form a cycle), but where otherwise no

[sagetrac-git]

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

ad71644

Updated

[sagetrac-git]

Changed commit from 618efe4 to ad71644

[dcoudert]

comment:45

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.

[dimpase]

comment:46

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.

[sagetrac-git]

Changed commit from ad71644 to 9b43b3e

[sagetrac-git]

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

9b43b3e

git-trac-command folder removed.

[sagetrac-saiharsh]

comment:48

Replying to @sagetrac-git:

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

9b43b3e	git-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.

[dcoudert]

comment:49

Thank you Dima.

[dimpase]

comment:50

Replying to @sagetrac-saiharsh:

Replying to @sagetrac-git:

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

9b43b3e	git-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.

[sagetrac-saiharsh]

comment:51

Replying to @dimpase:

Replying to @sagetrac-saiharsh:

Replying to @sagetrac-git:

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

9b43b3e	git-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.

[vbraun]

Changed branch from u/saiharsh/EarDecomposition to 9b43b3e