add `line_graph` (vertex-edge-dual)

[lampretl]

Hey, thank you for all your awesome work on graphs! : )

I have a request: could you add to operators the function line_graph?

Could be something as simple as:

function line_graph(g::SimpleGraph)
    edge_list = collect(edges(g))
    n_edges = length(edge_list)
    lg = SimpleGraph(n_edges)

    for i = 1:n_edges-1
        ei = edge_list[i]
        for j = i+1:n_edges
            ej = edge_list[j]
            if !isempty(intersect((src(ei), dst(ei)), (src(ej), dst(ej))))
                add_edge!(lg, i, j)
            end
        end
    end

    return lg
end

[lampretl]

My code above is slow for graphs with many edges (complexity O(n_edges^2)), so I'm proposing a better one:

function line_graph(g::SimpleGraph)
   edge_list = edges(g)
   vertex_to_edges = Dict{Int, Vector{Int}}()
   for (i,e) ∈ enumerate(edge_list)
      push!(get!(vertex_to_edges, src(e), Int[]), i)
      push!(get!(vertex_to_edges, dst(e), Int[]), i) 
   end
   lg = SimpleGraph(length(edge_list))
   for edges_from_v ∈ values(vertex_to_edges)
      for i = 1:length(edges_from_v)-1
         for j = i+1:length(edges_from_v)
            add_edge!(lg, edges_from_v[i], edges_from_v[j]) 
         end 
      end 
   end
   return lg 
end

[lampretl]

I'd appreciate any response.

[simonschoelly]

I'd appreciate any response.

Sorry, I was a bit inactive in the recent months. I think line graphs would be a welcome addition. Would you be willing to create a PR?

Such an implementation should also work correctly with self-loops.

Furthermore - perhaps the user wants to know which edge in the old graphs maps to which vertex in the new graph or the other way around? So we might also return the mapping.

[lampretl]

No worries, happy I got a response.

I can prepare a PR, but this would be my first contribution to Julia open source, so I'd appreciate if you'd be willing to answer any questions I will have, and offer some guidance. Starting with:
(1) Probably you'd like line_graph to be in /src/operators.jl?
(2) Should I also write some unit-tests for this? If so, where are they?
(3) How could I add line_graph to the documentation?

Yeah, I can make the function return also a vector correspondence, such that correspondence[i] = edge in g corresponding to vertex i in lg.

Regarding selfloops (and digraphs and multigraphs more generally), in SageMath I see there's some functionality dedicated to that. When I have the time, I will probably try to rewrite the best things to Julia.
But Graphs.jl supports only DiGraphs, not MultiGraphs, or have I missed something?

[thchr]

Building on the last implementation, we can go a bit faster (partly by using a plain vector for the vertex-edge mapping rather than a dictionary, partly by not using add_edge!, which is quite slow, to assemble the new graph):

function line_graph1(g::SimpleGraph)
    vertex_to_edges = [Int[] for _ in 1:ne(g)]
    for (i,e) ∈ enumerate(edges(g))
        push!(vertex_to_edges[src(e)], i)
        push!(vertex_to_edges[dst(e)], i) 
    end

    fadjlist = [Int[] for _ in 1:ne(g)]
    _ne = 0
    for es′ in vertex_to_edges
        n′ = length(es′)
        for i = 1:n′-1
            for j = i+1:n′
                eᵢ = es′[i]
                eⱼ = es′[j]
                push!(fadjlist[eᵢ], eⱼ)
                eᵢ ≠ eⱼ && push!(fadjlist[eⱼ], eᵢ) # don't push loops twice
                _ne += 1
            end 
        end 
    end
    foreach(sort!, fadjlist)

    return SimpleGraph(_ne, fadjlist)
end

Is about 1.5-4 times faster in cases below:

using Chairmarks

g = wheel_graph(10)
@b line_graph($g)  # 2.628 μs (108 allocs: 8.859 KiB)
@b line_graph1($g) # 1.525 μs (79 allocs: 7.781 KiB)

g = wheel_graph(50)
@b line_graph($g)  # 45.289 μs (639 allocs: 123.062 KiB)
@b line_graph1($g) # 14.530 μs (449 allocs: 112.312 KiB)

g = wheel_graph(500)
@b line_graph($g)  # 3.913 ms (7137 allocs: 5.343 MiB)
@b line_graph1($g) # 1.141 ms (5501 allocs: 3.834 MiB)

[lampretl]

@thchr Thank you for the improvement, your solution is indeed 2x faster. Good idea to use Vector instead of Dict.

A bit of nitpicking, I had trouble understanding what all ' mean, until I realized they mean nothing, ' is treated just like any other character. But x' does mean the conjugate transpose of x and computes that. So I think it would be better to avoid using ' in cases like above.

You have a mistake in the declaration of vertex_to_edges, you should've used nv instead of ne.

What I don't understand is why you have eᵢ!=eⱼ && push!(fadjlist[eⱼ], eᵢ) # don't push loops twice? Since the graph is simple, there are no self-loops. I think your code is equivalent to this (a bit easier to understand):

function line_graph1(g::SimpleGraph)
    vertex_to_edges = [Int[] for _ ∈ 1:nv(g)]
    for (i,e) ∈ enumerate(edges(g))
        push!(vertex_to_edges[src(e)], i)
        push!(vertex_to_edges[dst(e)], i) 
    end

    edge_to_neighbors = [Int[] for _ ∈ 1:ne(g)]
    for es ∈ vertex_to_edges
        n = length(es)
        for i = 1:n-1
            for j = i+1:n
                ei, ej = es[i], es[j]
                push!(edge_to_neighbors[ei], ej)
                push!(edge_to_neighbors[ej], ei)
    end end end 

    foreach(sort!, edge_to_neighbors)
    m = sum(length(nbs) for nbs ∈ edge_to_neighbors) ÷ 2  # n_edges in lg
    return SimpleGraph(m, edge_to_neighbors)
end

julia> g = barabasi_albert(10_000, 50, 50);  nv(g), ne(g)
(10000, 497500)

julia> @time lg = line_graph(g);   @time lg1 = line_graph1(g);   lg==lg1
 12.801092 seconds (4.94 M allocations: 6.675 GiB, 18.10% gc time)
  6.020784 seconds (5.07 M allocations: 5.577 GiB, 31.80% gc time)
true

[simonschoelly]

(1) Probably you'd like line_graph to be in /src/operators.jl?

Yes for now I would add it to operators. There is a bit of issues with graph types in this package - namely most operators only work for SimpleGraph and SimpleDiGraph - I have some ideas how we can avoid that but for now I would make it work for these types only.

(2) Should I also write some unit-tests for this? If so, where are they?

The file structure for the unit tests mirrors the one for the source file - so it's just the same path in /test.

(3) How could I add line_graph to the documentation?

As long as you are not creating a separate file the docstrings you add to a function should be automatically added to documentation.

[simonschoelly]

On the topic of simple graphs - technically simple graphs don't allow self-loops - but in this package we added self-loops at some point - so we always have to consider that case.

Speaking of - perhaps we can have a separate function for SimpleDiGraph.

[thchr]

A bit of nitpicking, I had trouble understanding what all ' mean, until I realized they mean nothing, ' is treated just like any other character. But x' does mean the conjugate transpose of x and computes that. So I think it would be better to avoid using ' in cases like above.

I just use it as a prime, following standard math/physics notation for related-but-different variables.

You have a mistake in the declaration of vertex_to_edges, you should've used nv instead of ne.

Huh, indeed: wonder how I managed that typo; good catch.

What I don't understand is why you have eᵢ!=eⱼ && push!(fadjlist[eⱼ], eᵢ) # don't push loops twice? Since the graph is simple, there are no self-loops. I think your code is equivalent to this (a bit easier to understand):

See @simonschoelly's reply.

---

Your implementation is good also, but it loops over the adjacency list twice (when getting the number of edges) which seems unnecessary (probably also gets the wrong number if there's self-loops).

[lampretl]

@simonschoelly Hey, I created the PR like we talked about. Would you be willing to review it and merge when it is ready? Locally, I ran all the tests successfully, but on GitHub there seem to be some that are failing. I'd appreciate if you could look at it.