Add/line graph

[lampretl]

I added the function line_graph (one method for undirected graphs, one for directed graphs) and several unit tests that check the correctness of the output graph on simple cases (cycle, path, star graph, and a small graph with 2 or 3 vertices and a loop).

I also edited runtests.jl to use ARGS, so that when running

using Pkg;  Pkg.activate(".");  Pkg.instantiate();  Pkg.test("Graphs", test_args=["operators","juliaformatter"]);

only those two tests are performed. This was necessary, because running the whole set of tests took 15min on my computer (6-core i7-8850H CPU), but doing only those two tests took <50sec, so it was easier to iterate.

[codecov[bot]]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 97.42%. Comparing base (2d6f4d5) to head (d2fdc73). Report is 1 commits behind head on master.

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #440      +/-   ##
==========================================
+ Coverage   97.41%   97.42%   +0.01%     
==========================================
  Files         120      120              
  Lines        6959     7002      +43     
==========================================
+ Hits         6779     6822      +43     
  Misses        180      180              

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

:rocket: New features to boost your workflow:

• :snowflake: Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[simonschoelly]

@Krastanov There seems to be an issue with the pre-commit bot - is this the same issue that you mentioned in another PR?

[lampretl]

@simonschoelly I'd appreciate any feedback. Are the unit tests sufficient, should I add or remove some of them? Do you find the implementations and docstrings ok?

[Krastanov]

Same issue. Currently the bot works only on PRs from branches of this repo. PRs from forks fail. All tests pass, so that is not a blocker.

I would suggest editing the PR description to actually describe what this PR is about.

[simonschoelly]

@simonschoelly I'd appreciate any feedback. Are the unit tests sufficient, should I add or remove some of them? Do you find the implementations and docstrings ok?

I haven't had the time to look at it entirely - but I wrote a comment yesterday that somehow did not get posted:

I was wondering about the behavior for loops. Currently a graph with edges (1 -- 1) and (1 --2) while result in the line graph with the single edge (1--1) -- (1--2). But should the there not also be a an edge (1--1) - (1--1)?

[simonschoelly]

So the literature is quite sparse with regards to line graphs and self-loops but I just checked the behavior of networkx and igraph on a single vertex with a self-loop.

For directed graphs they line graph for both packages result in a single vertex with a self-loop again.

For undirected graphs, networkx produces a single vertex without any loops. Igraph produces a single vertex with a self-loop.

[lampretl]

I would suggest editing the PR description to actually describe what this PR is about.

Done.

[lampretl]

I would add a few tests for example for SimpleGraph{UInt8}.

Ok, I did the test for the smallest (di)graph (2 vertices) for Int8,...,Int128,Uint8,...,UInt128.

[lampretl]

I was wondering about the behavior for loops. Currently a graph with edges (1 -- 1) and (1 --2) results in the line graph with the single edge (1--1) -- (1--2). But should there not also be an edge (1--1) - (1--1)?

If so, by the same 'logic', shouldn't there also be an edge (1--2) - (1--2) in lg? I prefer not spamming self-loops in lg.

So the literature is quite sparse with regards to line graphs and self-loops but I just checked the behavior of networkx and igraph on a single vertex with a self-loop.

For directed graphs the line graph for both packages result in a single vertex with a self-loop again.

For undirected graphs, networkx produces a single vertex without any loops. Igraph produces a single vertex with a self-loop.

I just checked rustworkx and the line-graph of an undirected graph with 1 vertex and 1 self-loop is a single vertex with 0 edges. It seems line graph is not even implemented there for digraphs.

I don't know. I'll do as you suggest.

Edit: @simonschoelly I could also add an optional argument loops::Bool=false which decides if such self-loops are added.

[lampretl]

I was wondering about the behavior for loops. Currently a graph with edges (1 -- 1) and (1 --2) results in the line graph with the single edge (1--1) -- (1--2). But should there not also be an edge (1--1) - (1--1)?

If so, by the same 'logic', shouldn't there also be an edge (1--2) - (1--2) in lg? I prefer not spamming self-loops in lg.

So the literature is quite sparse with regards to line graphs and self-loops but I just checked the behavior of networkx and igraph on a single vertex with a self-loop.

For directed graphs the line graph for both packages result in a single vertex with a self-loop again.

For undirected graphs, networkx produces a single vertex without any loops. Igraph produces a single vertex with a self-loop.

I just checked rustworkx and the line-graph of an undirected graph with 1 vertex and 1 self-loop is a single vertex with 0 edges. It seems line graph is not even implemented there for digraphs.

I don't know. I'll do as you suggest.

Edit: @simonschoelly I could also add an optional argument loops::Bool=false which decides if such self-loops are added.

@simonschoelly What is your decision regarding self-loops in a line-graph? Shall I add an optional argument, like loops::Int=0, whose value determines: 0 $\Rightarrow$ we add no self-loops; 1 $\Rightarrow$ we add loops to lg from loops in g; 2 $\Rightarrow$ we add loops to lg from every edge in g?

Also, what is your decision regarding sort!/issorted of fadjlist (the 3 options I described above?

I'd like to finish this PR in a timely manner.

[elvcastelo]

@simonschoelly What is your decision regarding self-loops in a line-graph? Shall I add an optional argument, like loops::Int=0, whose value determines: 0 ⇒ we add no self-loops; 1 ⇒ we add loops to lg from loops in g; 2 ⇒ we add loops to lg from every edge in g?

Sorry for interrupting the discussion :)

Maybe it should follow from the definition of line graphs, as it make easier to understand the output. For the undirected case, we have a single loopless vertex. Then the options would not be necessary (unless for some specific reason?).

SageMath seems to follow this convention (https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/line_graph.html#module-sage.graphs.line_graph) when mentioning «Loops are not adjacent to themselves».

For example, consider the P_3 {{1, 2}, {2}, {2, 3}} with a self-loop in the middle vertex. The intersection graph of the edges is a triangle.