Lazy graphs

[acxz]

Hello JuliaGraph!,

Pardon me if this is a very naive question, however, I was looking for an A* implementation in Julia and found the one here in Graphs.jl.

For problems where I know my graph before hand, A* can be easily used since I just define my graph, heuristic and go on my merry way.

However, A* itself doesn't require the complete graph structure, just the neighbors of the current vertex it is expanding from. This is primarily evident if your search space is enourmous. Would it be possible incorporate this feature, where given a user defined neighbor functin, a graph can be dynamically created within a_star? In fact this could be even be seen as a way to generate a graph, rather than just a Path Traversal method.

[etiennedeg]

You can totally create your own graph type that lazily computes neighborhoods. See here for the full list of methods to implement. inneighbors and outneighbors will just call your user-defined neighbor function.

[acxz]

I see thank you for the guidance. I believe that gives me the functionality I would deserve of dynamically creating the graph during search!

[acxz]

As a follow up, I have created a prototype package for lazy graphs: https://github.com/acxz/SimpleLazyGraphs.jl/

[gdalle]

Another example of dynamic edge generation is https://github.com/gdalle/GridGraphs.jl

[acxz]

@gdalle thanks for sharing this package, however, I don't think it solves the issue.

I believe I would still need to specify the entire graph, before I pass the graph to the a_star method right?

[acxz]

Also, would you be willing to incorporate lazy functionality in Graphs.jl? (maybe with a is_lazy field?)

To get astar to work with lazy graphs I have had to add some code in astar to expand the vectors used to keep track of information:

https://github.com/acxz/SimpleLazyGraphs.jl/blob/4365b73d12060be104b4bc0820b4a00e5d215d12/src/simplelazygraph.jl#L161-L170

        for neighbor in outneighbors(g, current)
            if neighbor > length(closed_set)
                push!(closed_set, zero(typeof(closed_set[1])))
                push!(g_score, Inf)
                # TODO(acxz) can custom distmx be done in a lazy setting with
                # the same astar api or do we need to piggyback off weights(g)?
                distmx = weights(g)
                push!(came_from, -one(goal))
            end
            closed_set[neighbor] && continue

Would it be possible that such functionality can be incorporated inside of Graphs.jl (again maybe wrapped with a is_lazy conditional)?

Maybe this is also a consideration for Graphs.jl 2.0?

[gdalle]

I believe I would still need to specify the entire graph, before I pass the graph to the a_star method right?

In that case yes, but a grid graph is stored as a matrix of vertices, and the connections between these vertices are generated on the fly. It was just meant as an example anyway

[gdalle]

To get astar to work with lazy graphs I have had to add some code in astar to expand the vectors used to keep track of information

I'm not sure I understand your code. At any rate, potentially reallocating distmx = weights(g) in every loop will ruin performance. As for alternatives to the distmx argument, they are indeed on the menu for Graphs v2.0 (see #146), and they were also discussed in the context of SimpleWeightedGraphs (see this issue). Feel free to weigh in!

[acxz]

I'm not sure I understand your code.

closed_set is created with size of the number of vertices in the graph at the time. However, if the graph is lazy and increases the next time the outneighbors is called, then indexing closed_set at a larger value than the original number of vertices in the graph will cause an error. Therefore closed_set needs to be increased to accommodate this indexing. Similarly, other sets like g_score and came_from need to be increased as well.

As for distmx = weights(g) I totally agree with you and I still need to think about it.
It great to hear that weights is a topic for Graphs v2.0. I would also love to see lazy being a part of the conversation as well. Once, I stress this the SimpleLazyGraphs.jl package a bit more, I'll chime in with some feature requests/suggestions to those issues.

[gdalle]

Okay, I had not understood what you meant by "lazy".

• If the graph doesn't change, retrieving the neighbors lazily (with a function instead of a fixed container) is supported by Graphs.jl functions
• If the graph does indeed change midway through the algorithm, then you're right that Graphs.jl will probably break. But I'm not sure re-implementing all algorithms for this case would be useful, especially since many algorithms would no longer make sense.

I'll take a look at your LazySimpleGraphs.jl package, but in the meantime I'm closing this if that's okay

[acxz]

many algorithms would no longer make sense.

I would like to argue this statement. Can we be more specific here? All traversal based algorithms lend themselves well to lazy graphs. This includes any algorithm that requires neighbor information.

not sure re-implementing all algorithms for this case would be useful

the only addition would be changing preallocated arrays to be dynamic and this check could even be done under a is_lazy conditional.

If the graph doesn't change, retrieving the neighbors lazily (with a function instead of a fixed container) is supported by Graphs.jl functions

The "graph" as I see it in my head does not change, I have a function that determines the neighbors for any given vertex. However, what if my graph is enormous? Adding neighbors lazily to the Graph in the code as my algorithm needs them is the goal of SimpleLazyGraphs.jl. Retrieving neighbors with a function vs a fixed container does not help me tackle this problem, as my neighbors don't exist in the Graph yet.

Right now there are two workarounds to this issue (want to find shortest path from vertex a -> vertex b using astar (as provided in Graphs.jl), given a, b, and the neighbors of any given vertex)

1. Create a subset of the graph using a user written traversal method such as BFS that adds vertices to the graph as the algorithm is exploring. Once b is located in the subset of the graph created, stop the creation of the graph and then pass this graph to the astar algorithm in Graphs.jl (Note: at this point you might as well write your own astar algorithm without using Graphs.jl)

2. Use SimpleLazyGraphs.jl and modify Graphs.jl algorithms to support dynamic allocated variables as needed in the algorithm.

In fact, you can think of this as a Generator for the Graph.

Lazy refers to adding neighbors lazily not retrieving them lazily

I'll take a look at your SimpleLazyGraphs.jl package, but in the meantime I'm closing this if that's okay

That would be wonderful! Please do, I am willing to edit and change much of the code and the necessary things to incorporate a solution to this problem inside of Graphs.jl.