Merging vertices in directed graphs

[jpfairbanks]

I found this code in https://github.com/IBM/semanticflowgraph/blob/master/src/SemanticEnrichment.jl#L202 and figured it might want to come home to LG. Does anyone know if the merge_vertices in https://github.com/JuliaGraphs/LightGraphs.jl/blob/84c21997a5df176cfc142d2309c8e21189fff283/src/operators.jl#L746 works on directed graphs?

""" Merge the vertices into a single vertex, preserving edges.
Note: LightGraphs.merge_vertices! only supports undirected graphs.
"""
function merge_vertices_directed!(graph::AbstractGraph, vs::Vector{Int})
  @assert is_directed(graph)
  vs = sort(vs, rev=true)
  v0 = vs[end]
  for v in vs[1:end-1]
    for u in inneighbors(graph, v)
      if !(u in vs)
        add_edge!(graph, u, v0)
      end
    end
    for u in outneighbors(graph, v)
      if !(u in vs)
        add_edge!(graph, v0, u)
      end
    end
    rem_vertex!(graph, v)
  end
  v0
end

[sbromberger]

Let's bring it in.

julia> g = path_digraph(10)
{10, 9} directed simple Int64 graph

julia> merge_vertices(g, [4,5,6])
{8, 6} undirected simple Int64 graph

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[sbromberger]

For HackIllinois: even though we have #1291, it'd be good to get benchmarks using the above code to compare against the PR.

[birm]

@sbromberger we can probably close this too :)