Implement a bidirectional directed adjacency graph

[doudou]

[monora]

@doudou : Thank you for your pull request. I have some comments:

1. DirectedAdjacencyGraph and BidirectionalDirectedAdjacencyGraph contain much code duplication (several methods are identical). We should factor out this common code.
2. Using an array tuple for in and out edges is not well readable. Perhaps two maps out_neighbors and in_neighbors would be more readable. Then you could also solve 1: Rename vertices_dict to out_neighbors and then derive BidirectionalDirectedAdjacencyGraph from DirectedAdjacencyGraph.
3. Why do you dup when returning in_neighbours? This is not done so in DirectedAdjacencyGraph. We should be consistent.

[doudou]

1. and 2. - the goal was to avoid resolving the hash entry, but I agree that's really not a very good goal given how much code duplication it implies. I will do as you suggest.
2. DirectedAdjancencyGraph does not have a specialized version of #adjacent_vertices, which means that the list is duplicated (in an extremely inefficient way). I would personally prefer keeping the duplication to avoid leaking internal state (and class users modify the in/out lists without noticing)

[monora]

I do not insist on using the base.rb implementations. If you prefer reimplementing with the more efficient versions, just go for it. This should then be mentioned in the method comment.

[doudou]

OK ... will do the rest of the fixes.

[doudou]

Another question (I made a separate commit, but not sure you noticed). The #each_adjacent name is awkward for bidirectional graphs (we have #each_in_neighbour but #each_adjacent). I added #each_out_neighbour as an alias to #each_adjacent. Are you OK with it ? Should I move this to the Bidirectional module ?

[monora]

Yes, as I said above: each_in_neighbour should be included in BidirectionalGraph.

• each_in_neighbour # only method which has to be implemented
• in_neighbours # Should be included in module BidirectionalGraph
• in_degree # can be reused from module BidirectionalGraph

[doudou]

I am talking about the out version. each_out_neighbour makes more sense than each_adjacent for bidirectional directed graphs, but it is also normal than the rest of the algorithms use each_adjacent (or is it ? each_out_neighbour would also make it clearer for algorithms that require a directed graph)

[monora]

Ah, sorry. Yes each_out_neighbour should go to bidirectional.rb, as well as the aliases:

alias :each_adjacent :each_out_neighbour
alias :adjacent_vertices :out_neighbours

out_neighbours could also be implemented in bidirectional module with the help of each_out_neighbour.

[doudou]

OK ... Will do !

[doudou]

I'm on a tight schedule right now ... so it's going to take a while though :(

[StevenJenkinsJPL]

I just discovered this long-dormant thread. It seem to me BidirectionalGraph could be cleanly implemented using Ruby's DelegateClass. It would simply delegate to an out DirectedAdjacencyGraph; all existing methods would work initially as they do now. It would also maintain an internal in graph. Methods that mutate graph state would be overridden to apply changes to both out and in graphs. Methods unique to BidirectionalGraph (e.g., each_in_neighbor() would operate on the in graph only.

Perhaps not the most time- or memory-efficient implementation but reasonable in both respects with very little implementation code.

Thoughts?

[StevenJenkinsJPL]

Barring that, any reason not to implement each_in_neighbor() in the straightforward naive fashion? Efficiency is not really an issue for graphs of moderate size.

[monora]

Perhaps not the most time- or memory-efficient implementation but reasonable in both respects with very little implementation code.

But that is the promise in https://monora.github.io/rgl/RGL/BidirectionalGraph.html:

The BidirectionalGraph concept refines IncidenceGraph and adds the requirement for efficient access to the in-edges of each vertex. This concept is separated from IncidenceGraph because, for directed graphs, efficient access to in-edges typically requires more storage space, and many algorithms do not require access to in-edges.

Your solution is elegant but not memory efficient, because we would have doubled space with the internal graph.

[monora]

Barring that, any reason not to implement each_in_neighbor() in the straightforward naive fashion? Efficiency is not really an issue for graphs of moderate size.

Here, this would not be time efficient as promised above. To compute the in edges, you would have to iterate the whole graph.

[monora]

That said, we could relax the promise in the documentation and provide @StevenJenkinsJPL's inefficient but elegant solution. @doudou What do you think?

[doudou]

First of all, apologies to @monora here. I did not have the time and then completely forgot about it. Because we need to have information stored with the edges, we ended up having our own RGL-compatible bidirectional graph implementation, which is why I left it at that.

@StevenJenkinsJPL idea sounds good. A nice byproduct performance-wise is that reversing the graph would be O(1)

[StevenJenkinsJPL]

I don't know the RGL code well and am not trying to solve a problem if it's already been solved. I'll play around with it a bit.

[jsjuni]

[Steve again, logged into my personal GitHub account.]

I tried the DelegateClass approach, adding an internal reversed graph to store in-edges. I refactored the tests from directed_graph_test.rb to bidirectional_graph_test.rb as a baseline. Some tests passed but most failed with NotImplementedError. I don't understand why the delegation ended up invoking methods from base.rb. The examples of delegation are pretty simple and didn't help much.

After thinking about it, however, I don't see any reason not to subclass here. A BidirectionalGraph is a DirectedAdjacencyGraph; it just has some additional state. That approach was also simple and concise and passed all the tests. With that as a baseline, I beefed up the tests a little and added tests for bidirectional-specific methods. The result is here. Obviously, this approach is inefficient but it's a working baseline.

Looking more closely at adjacency.rb, I saw I could refactor @vertices_dict (as @doudou had) as a 2-tuple of edge lists to eliminate the redundant vertex list. I needed to override only a handful of methods that accessed edge lists. That version is here. It's also pretty clean and concise and passes all tests.

There are a couple of lines of duplicated code but refactoring them would actually add code, so it's a matter of style.

No changes to existing RGL code. Two new files:

• lib/rgl/bidirectional.rb
• test/bidirectional_test.rb

What do you think?

[monora]

@jsjuni Thank you, looks promising. Could you create a PR, where we can comment the changes.

[monora]

Close and release in #83