How does the fadjlist field of simplegraphs in LightGraphs package work?


#1

I think this is really strange. ;(

_/ |\__'_|_|_|\__'_|  |  Official http://julialang.org/ release
|__/                   |  x86_64-pc-linux-gnu

julia> using LightGraphs


julia> g=LightGraphs.Grid([2,2])
{4, 4} undirected simple Int64 graph


julia> g.ne
4

julia> g.fadjlist
4-element Array{Array{Int64,1},1}:
 [2, 3]
 [1, 4]
 [1, 4]
 [2, 3]

What exactly is this .fadjlist ? Is this forward adjacency list ?


#2

I figured it out. .fadjlist is a vector of vectors. Let’s call it vector v. Then, v[i] is the indices of the vertices which are adjacent to the vertex i. Apparently, each vertex in the graph has an index associated with it by default. Good to know.


#3

This is true, but you should never use .fadjlist if you want any sort of guarantee that your code will continue to work. To get the forward adjacency list of a SimpleGraph, please use the fadj accessor.

Similarly, do not access .ne directly. ne() is the accessor. In general, that is, you should not directly access fields of graph structs in LightGraphs. (The current exception is for structs returned from the shortest paths algorithms, and even that should change in time.)


#4

@sbromberger, I understand this restriction control. But I do not quite understand how to use the fadj accessor.

julia> g=LightGraphs.Grid([3,3])
{9, 12} undirected simple Int64 graph

julia> g.ne
12

julia> g.fadj
ERROR: type SimpleGraph has no field fadj
Stacktrace:
 [1] macro expansion at /home/devel/.julia/v0.6/Atom/src/repl.jl:118 [inlined]
 [2] anonymous at ./<missing>:?

Plus, fieldnames(g) would only give me two choices. one is .ne, and the other one is .fadjlist. Could you let me know?


#5

fadj and ne are functions that take the graph as an argument, so:

fadj(g)
ne(g)

#6

@sbromberger, not quite. Did I miss something?

julia> using LightGraphs

julia> g=LightGraphs.Grid([3,3])
{9, 12} undirected simple Int64 graph

julia> fadj(g)
ERROR: UndefVarError: fadj not defined
Stacktrace:
 [1] macro expansion at /home/devel/.julia/v0.6/Atom/src/repl.jl:118 [inlined]
 [2] anonymous at ./<missing>:?

julia> ne(g)
12

julia> fadjlist(g)
ERROR: UndefVarError: fadjlist not defined
Stacktrace:
 [1] macro expansion at /home/devel/.julia/v0.6/Atom/src/repl.jl:118 [inlined]
 [2] anonymous at ./<missing>:? 

#7

Yes. Because getting forward adjacencies is not part of the API contract and is not valid for other graph types (e.g., SimpleWeightedGraphs), it is not exported. Try LightGraphs.SimpleGraphs.fadj(). But be aware that use of fadj is a code smell that can indicate you’re taking the wrong approach to a given problem. Its primary use is to provide efficient / fast support for core functions like neighbors.


#8

@sbromberger, I see. Thank you so much!


#9

My pleasure. Feel free to join us on slack in the #graphs channel if you have any other questions :slight_smile:


#10

@sbromberger, could you kindly let me know how to join? Is it a open channel which everyone can join?


#11

go to https://slackinvite.julialang.org to get an invitation, then to https://julialang.slack.com to log in. We hang out in #graphs but there are dozens of other great channels.