Generic edgeMap function for graph algorithms like Bellman-Ford

Specific Domains Graphs
,
1

Hi everyone,

Apologies for this being a long one. I am working with the bellman ford algorithm from lightgraphs.jl but having an issue with some of my functions. My intension behind this is to have a general mapping function that goes over all edges in a graph and applies a function. Many algorithms loop over edges and apply calculations so a generic edgeMap function could be useful.

My edgeMap function:

function edgeMapSparse(g::AbstractGraph,f::Function,active,x...)
    @threads for u in vertices(g)
        if active[u] == true
            for v in outneighbors(g,u)
                f(u,v,g,x...)
            end
        end
    end
end

Bellman ford algorithm

function bf_compute(graph,distance,distance_max,predecessor,no_changes,new_active,active)
    for v in vertices(graph)
        if active[v] == true
            for u in outneighbors(graph, v)
                relax_dist = distance_max[v,u] + distance[v]
                if distance[u] > relax_dist
                    distance[u] = relax_dist
                    predecessor[u] = v
                    no_changes = false
                    new_active[u] = true
                end
            end
        end
    end
    return new_active,no_changes
end

function b_ford(graph::AbstractGraph{<:Integer},source::AbstractVector{<:Integer},distance_max::AbstractMatrix=weights(graph))
   if has_negative_edge_cycle(graph) == true
       error("Graph contains a negative edge cycle")
   end
    n = nv(graph)

    active = falses(n) #BitArray that holds actie edges (edge becomes active when it is visited)
    active[source] .= true

    predecessor = zeros(Integer, n)

    int_max = typemax(Int64)
    distance = fill(int_max, n) #initialize the distance to all vertices to maximum of Int64
    distance[source] .= 0 #the distance from the source to itself (the source) is 0

    no_changes = false #Array that tracks if
    new_active = falses(n) #BitArray that will be used to track if an edge is newly active

    for _ in 1:n
        no_changes = true
        new_active .= false
        edgeMapSparse(graph,bf_compute,distance,distance_max,predecessor,no_changes,new_active)
        no_changes && break
        active, new_active = new_active, active
    end
    return predecessor, distance
end

When I try some simple output from the following code I get the wrong answer. This is because I need to return the variables “new_active” & “no_changes”. My question is whether there is a way to return these values without making the edgeMap non-generic?

g1 = SimpleDiGraph(4) #Create a directed graph with 4 nodes and add edges to each node
add_edge!(g1, 1, 2);
add_edge!(g1, 1, 3);
add_edge!(g1, 2, 4);
add_edge!(g1, 3, 1);
add_edge!(g1, 3, 2);
add_edge!(g1, 3, 4);
add_edge!(g1, 4, 3);
bf_g1 = b_ford(g1,[2])
#returns 0,0,0,0 & 9223372036854775807,0,9223372036854775807,9223372036854775807
#correct answer is 3,0,2,4 & 3,0,2,1.

I appreciate that this is a very long one and any help would be much appreciated.

1 Like