Regarding Possible Contributions to Graphs.jl

[Harman Singh]

Hi, my name is Harman Singh and I am a third-year Computer Science Engineering undergraduate from BITS-Pilani K.K. Birla Goa Campus. I am primarily interested in graph algorithms, and am looking to contribute something significant to the Graphs.jl library. I'm still extremely new to Julia, so there's a lot I don't know, but I'm learning fast, so bear with me.

The current Graphs library is a bit basic, and I intend on adding implementations of several classic algorithms. I've started by implementing the A-Star algorithm for finding the shortest path between nodes of a graph given an admissible heuristic. I began by trying to imitate the coding style given in the Dijkstra implementation already present in the library, but it ended up diverging quite a lot, so please let me know if there's something coding convention or practice that I've missed.

I want to follow this up with several other features and algorithm that the package currently doesn't have. Off the top of my head, these include Fleury's algorithm and Hierholzer's algorithm for finding Eulerian paths, Floyd-Warshall, and even more basic things such as creating a graph for a given degree sequence (which ought to be a pretty useful feature). If I learn enough by then, I hope to eventually add methods to find the Eigenvector centrality of a node, so that users can experiment with algorithms like PageRank themselves (Incidentally, this last one is missing even in popular libraries such as Networkx and Java's JGraphT).

Are there any other features that users hope to see in the Graphs library? Any suggestions about what I should start with? I'm currently checking out the issue tracker on GitHub to see if there's anything I can help out with.

Additionally, I realise that nothing of this sort exists on the GSoC ideas page. But if there's anyone I can contact regarding the Graphs package, I'd really appreciate some help in formulating a precise and significant project idea.

Thanks in advance for your help,

Harman Singh

[Jiahao Chen]

Did you mean to write this line of code in this way?

hmap[sindex]=push!(heap,AstarHEntrysource(source,0,heuristic(source,target)))

https://github.com/harman28/Graphs.jl/blob/master/src/astar_spath.jl#L58

it seems like you intended to save the element being pushed onto the
heap, but the return value of push! is a reference to the heap itself.


Thanks,

Jiahao Chen, PhD
Staff Research Scientist
MIT Computer Science and Artificial Intelligence Laboratory

[Harman Singh]

Actually, I intended on maintaining a reference to the Vertex I pushed into the heap, and did this by creating an hmap array to keep track of each element added to the heap. This makes it possible to update the value of its g_score attribute later in the loop, at L95 (corresponding the 'relax' step of a typical Dijkstra implementation:

update!(heap, hmap[v_index], AstarHEntry(v,tentative_g_score,heuristic(v,target)))

https://github.com/harman28/Graphs.jl/blob/master/src/astar_spath.jl#L95

Forgive me if there's something I'm missing, but I think this is as it should be. Please correct me if it isn't.

[Iain Dunning]

Another idea: random graph generation algorithms - quite a few classic and often-cited papers in this area.

[Harman Singh]

There's already an Erdos-Renyi implementation in the random.jl file, but did you have something else in mind?

There's Issue #47 that asks for a function to compute all simple paths, so I'm working on that right now.