Improvements and test coverage for line.py#6215
Conversation
* due to the discussion in the documentation of `line_graph`, line graphs are generated with no loops.
It makes therefore sense to exclude graphs with loops from `inverse_line_graphs`
* we can always pop u from `partitioned_vertices` since the cell `new_cell` contains all the neighbors of u,
and thus `deg_u = 0` after line 403.
* we only ever use the length of ac_edges and bc_edges
* the only way to have `len(triangle_nodes) != s+2` is if `G` has self-loops (otherwise each odd triangle contributes
exactly one new vertex to `triangle_nodes`).
|
Notes :
Fixes #6191 |
No worries @Aufinal , thanks for pointing this out. @Mjh9122 want to take a look at this one? |
|
Yep definitely looks a lot more put together than mine. I closed mine and also took a second to add matches to all of the exceptions on this one. IDK about the best way to solve the self loop issue either but I made a quick fix warning based on @Aufinal 's suggestion. What would be the best way to make those changes, can I do it on this PR or should I make a new one? |
|
I'm not sure that matching on the precise error messages is meaningful: they depend on a lot of hidden details, such as the order of edges in G and even the order of vertices in edges, so a lot of unrelated API changes could cause the tests to fail. That's also why there are a lot of redundant negative examples, to try and make sure the coverage will stay OK no matter what. With that in mind, I've replaced some tests with one less dependent on the precise API. I welcome any suggestions about the self-loop behavior, but I don't know the best way to proceed either... |
|
Changed the behavior for self-loops (and the associated tests) to a simple warning. I am making a copy of G to avoid removing edges in-place, is that the correct to deal with such cases @rossbar ? |
dschult
left a comment
There was a problem hiding this comment.
I've looked through this and it looks good.
The only question I have is about whether warnings are the right way to handle graphs with selfloops. I worry that many users have warnings set so they don't show up. Did we discuss the possibility of raising a NetworkXError with a message telling the user what happened and suggesting that they remove selfloops before calling this function?
Agreed - let's avoid warnings. >>> G = nx.path_graph(2)
>>> L_1 = nx.inverse_line_graph(G) # Works fine
>>> G.add_edge(0, 0)
>>> nx.inverse_line_graph(G)
Traceback (most recent call last)
...
NetworkXError: G is not a line graph (odd triangles do not form complete subgraph)I would vote to preserve this behavior, though raising an exception message specific to the self-loop case would be an improvement! |
|
Agreed with the sentiment of keeping the current behavior as much as possible. I've changed the selfloop behavior to raise an error. |
dschult
left a comment
There was a problem hiding this comment.
This is very close to being ready to merge. I have some minor suggestions below and it looks like we'll need to merge "main" into this branch. If you don't have time let me know and I'll do it.
Co-authored-by: Dan Schult <dschult@colgate.edu>
|
The suggestions are applied, and I think the merge went ok :) |
* Improvements to `inverse_line_graph` function
* due to the discussion in the documentation of `line_graph`, line graphs are generated with no loops.
It makes therefore sense to exclude graphs with loops from `inverse_line_graphs`
* we can always pop u from `partitioned_vertices` since the cell `new_cell` contains all the neighbors of u,
and thus `deg_u = 0` after line 403.
* we only ever use the length of ac_edges and bc_edges
* the only way to have `len(triangle_nodes) != s+2` is if `G` has self-loops (otherwise each odd triangle contributes
exactly one new vertex to `triangle_nodes`).
* New tests for line.py
* Replace test_diamond_graph by a more consistent version
* Runs one forgotten test
* Change selfloops behavior to simple warning
* Change warning to error for selfloops
* Apply suggestions from code review
Co-authored-by: Dan Schult <dschult@colgate.edu>
Co-authored-by: Ludovic Stephan <ludovic.stephan@pm.me>
Co-authored-by: Dan Schult <dschult@colgate.edu>
* Improvements to `inverse_line_graph` function
* due to the discussion in the documentation of `line_graph`, line graphs are generated with no loops.
It makes therefore sense to exclude graphs with loops from `inverse_line_graphs`
* we can always pop u from `partitioned_vertices` since the cell `new_cell` contains all the neighbors of u,
and thus `deg_u = 0` after line 403.
* we only ever use the length of ac_edges and bc_edges
* the only way to have `len(triangle_nodes) != s+2` is if `G` has self-loops (otherwise each odd triangle contributes
exactly one new vertex to `triangle_nodes`).
* New tests for line.py
* Replace test_diamond_graph by a more consistent version
* Runs one forgotten test
* Change selfloops behavior to simple warning
* Change warning to error for selfloops
* Apply suggestions from code review
Co-authored-by: Dan Schult <dschult@colgate.edu>
Co-authored-by: Ludovic Stephan <ludovic.stephan@pm.me>
Co-authored-by: Dan Schult <dschult@colgate.edu>
* Improvements to `inverse_line_graph` function
* due to the discussion in the documentation of `line_graph`, line graphs are generated with no loops.
It makes therefore sense to exclude graphs with loops from `inverse_line_graphs`
* we can always pop u from `partitioned_vertices` since the cell `new_cell` contains all the neighbors of u,
and thus `deg_u = 0` after line 403.
* we only ever use the length of ac_edges and bc_edges
* the only way to have `len(triangle_nodes) != s+2` is if `G` has self-loops (otherwise each odd triangle contributes
exactly one new vertex to `triangle_nodes`).
* New tests for line.py
* Replace test_diamond_graph by a more consistent version
* Runs one forgotten test
* Change selfloops behavior to simple warning
* Change warning to error for selfloops
* Apply suggestions from code review
Co-authored-by: Dan Schult <dschult@colgate.edu>
Co-authored-by: Ludovic Stephan <ludovic.stephan@pm.me>
Co-authored-by: Dan Schult <dschult@colgate.edu>
Changes to
line.pyitself:line_graph, line graphs are generated with no loops.It makes therefore sense to exclude graphs with loops from
inverse_line_graphspartitioned_verticessince the cellnew_cellcontains all the neighbors of u,and thus
deg_u = 0after line 403.len(triangle_nodes) != s+2is ifGhas self-loops (otherwise each odd triangle contributesexactly one new vertex to
triangle_nodes).Test changes: