PY: graph_tools

[sglyon]

Don't have a julia version of the graph_tools module

[sglyon]

@ZacCranko when you have the time, I think you have a better idea about what is in the Julia library already and what is available on the Python side, but not the Julia side.

[sglyon]

Given that we REQUIRE Graphs.jl, the user will have that available. I don't know that we need to supply our own graph_tools also.

[ZacCranko]

The only particularly special thing that graph_tools.py as far as I can tell is providing a method for computing the period of a Markov chain. Also I've been looking at the new module LightGraphs.jl as a possible replacement for Graphs.jl since it's a lot more lightweight and much easier to use.

To address this issue I could just implement this particular algorithm. Additionally, what are your thoughts on a move to LightGraphs.jl?

[sglyon]

I also saw LightGraphs recently and am definitely in favor of moving to it if we can.

If we can just add methods to cover all the different properties defined in the python version of mc tools I don't think we also need to do the graphs. We'll let the developers of the LightGraphs handle that 😏

[ZacCranko]

Totally agree, we don't need to become a graphing library in addition to a computational economics library. I've been chatting with @sbromberger, just waiting on a couple new algorithms to be pushed in LightGraphs.jl, then I'll implement all of the python features.

[sbromberger]

Hi all, just wanted to stick my nose in. I'm working on retooling BFS and DFS in LightGraphs. This will give us (hopfeully very fast) cycle detection and connected components (with both strong and weak for DiGraphs). I've currently got DAGs for the traversals working, so we've got a nice traversal tree.

Let me know if you need any other base functionality. I'm gratefully accepting PRs to code so if you wind up developing some great algorithms using LightGraphs, please share them!

[sbromberger]

Just following up - if you want to check out the "bfsdfs" branch of LightGraphs.jl, it'll have connectivity, traversal DAGs, and some other neat stuff. Comments appreciated.

[sglyon]

Thanks for the heads up. I'm looking forward to our move to LightGraphs.

@ZacCranko is handling this issue so I look forward to his report.

[oyamad]

Hi @sbromberger

As @spencerlyon2 and @ZacCranko discuss, it would be great if LightGraphs.jl could include the functionality of computing the period and cyclic components of a digraph as in graph_tools.py, where I just coded the algorithm described in "Graph-Theoretic Analysis of Finite Markov Chains" by J. P. Jarvis and D. R. Shier, Section 17.3.

[sbromberger]

Hm. This is outside my area of expertise, unfortunately. However, perhaps the following can be used as a starting point? I've implemented cycle detection (is_cyclic()) which uses DFS and have connected_components for Graphs, and strongly_connected_components, and weakly_connected_components for DiGraphs.

I'll look into periodicity today or tomorrow.

[ZacCranko]

@sbromberger I'll help you get this happening, but I needed to be asleep 40 minutes ago

[sbromberger]

@ZacCranko totally on your schedule :) Have a good night.

[sglyon]

@ZacCranko @sbromberger I'm starting to look at this right now.

[sglyon]

@sbromberger I know almost nothing about graph theory, so I apologize in advance for my ignorance. However, I did notice something. The DiGraph code in QuantEcon.py supports adjacency matrices of the form [1 0; 0 1] as shown in the tests. When I tried to construct a DiGraph here using that adjacency matrix, I got this error:

ERROR: LightGraphs does not support self-loops

Is there a way we can make this possible? That would be great because we use the DiGraph to analyze markov transition matrices. It is very common (actually uncommon not to) to have non-negative entries along the diagonal.

[sbromberger]

@spencerlyon2 yes - I spoke with @ZacCranko about this this morning (my time). I don't know of any reason off the top of my head that self-loops wouldn't work, but there are a couple of changes to graphs.jl and digraphs.jl (specifically in add_edge!) to support it, and then we'd probably want to change DefaultDistance() just to be safe.

@ZacCranko said he'd be testing this and will report back any unusual behavior.

[sglyon]

Oh ok great. I didn't realize you guys were already working on this.

I'll leave it to the experts and move on to something else then :)

p.s.: where are you located (i.e. what is "my time")?

[sbromberger]

Normally it's US Pacific Time (currently UTC-7) but until middle of next month I'm in Bogotá, so UTC-5.

[sbromberger]

@ZacCranko @spencerlyon2 also - a good way of doing this might be to create a new concrete type

SelfLoopDiGraph <: AbstractGraph

and define/override the appropriate functions/methods there. That way you keep the self-loop stuff independent of the regular stuff, and if it turns out it works, we can incorporate it easily.

[oyamad]

In fact, no support for digraphs with self-loops is not an issue for our purpose.

• Strongly connected components (SCCs) are invariant even if one removes self-loops (by definition, each node has access to that node itself, whether or not there is a self-loop). In the case of [1 0; 0 1] for example, we can instead consider [0 0; 0 0], for both of which the SCCs are {1} and {2}.
• If a digraph has a node with a self-loop, then its period is automatically one (assuming that the digraph is strongly connected). So we can just focus on digraphs with no self-loop when computing the period.

[ZacCranko]

Thanks for that @oyamad, I'll be looking at this today.

[sbromberger]

Confirmed that this appears to be working as intended in LightGraphs (you'll need the bfsdfs branch for this):

julia> g = DiGraph([0 0; 0 0])
{2, 0} directed graph

julia> strongly_connected_components(g)
2-element Array{Array{Int64,1},1}:
 [1]
 [2]

Also note that bfsdfs is currently broken in 0.3 due to lack of constructors for Vector{Int}()

[oyamad]

Hi @sbromberger: I was playing with your LightGraphs.jl (bfsdfs branch) (to try to implement the algorithm for periodicity), but I found something strange about LightGraphs.strongly_connected_components.

I was considering the digraph in Figure 8 on page 12 in "Graph-Theoretic Analysis of Finite Markov Chains" by J. P. Jarvis and D. R. Shier, which is clearly strongly connected, but LightGraphs.strongly_connected_components returns three components:

julia> g = DiGraph(6)
{6, 0} directed graph

julia> eds = [(1, 3), (3, 4), (4, 2), (2, 1), (3, 5), (5, 6), (6, 4)]
7-element Array{Tuple{Int64,Int64},1}:
 (1,3)
 (3,4)
 (4,2)
 (2,1)
 (3,5)
 (5,6)
 (6,4)

julia> for (ed_from, ed_to) in eds
           add_edge!(g, ed_from, ed_to)
       end

julia> edges(g)
Set([edge 3 - 5,edge 5 - 6,edge 6 - 4,edge 3 - 4,edge 1 - 3,edge 2 - 1,edge 4 - 2])

julia> strongly_connected_components(g)
3-element Array{Array{Int64,1},1}:
 [6]      
 [5]      
 [1,3,4,2]

I wonder if I am missing anything.

Just in case, NetworkX returns the whole set of nodes as a unique strongly connected component:

>>> import networkx as nx
>>> nodes = list(range(1, 7))
>>> edges = [(1, 3), (3, 4), (4, 2), (2, 1), (3, 5), (5, 6), (6, 4)]
>>> G = nx.DiGraph()
>>> G.add_nodes_from(nodes)
>>> G.add_edges_from(edges)
>>> G.edges()
[(1, 3), (2, 1), (3, 4), (3, 5), (4, 2), (5, 6), (6, 4)]
>>> nx.number_strongly_connected_components(G)
1
>>> list(nx.strongly_connected_components(G))
[[1, 3, 5, 6, 4, 2]]

(quantecon.DiGraph.strongly_connected_components, or in fact scipy.sparse.csgraph.connected_components, yields the same result as NetworkX.)

[sbromberger]

@oyamad almost definitely a bug. Could you open an issue in lightgraphs and I'll look into it next week? Thanks.

[oyamad]

@sbromberger Sure, copied.

[ZacCranko]

@oyamad That pdf is a great resource, I'm going to be coding up all the examples to use for tests in LightGraphs.jl

[sbromberger]

Please checkout the latest bfsdfs - I think it's fixed (track sbromberger/LightGraphs.jl#71 for status, and please place feedback there).

Bottom line: this was actually a bug in the Graphs.jl code (which LightGraphs "appropriated" :) - I filed a PR there as well.

[oyamad]

Hi @ZacCranko
I had a look at your PR on periodicity sbromberger/LightGraphs.jl#75 for LightGraphs.jl.
Let me write some comments/questions here (tell me if I should write these there in LightGraphs.jl).

1. If we want to import all the functionalities from mc_tools.py into the Julia side, we will also need cyclic_components, which are obtained simultaneously with the period. Do you plan to add that feature in strongly_connected_period later?
2. In your periods, the period is defined for each node. For an (irreducible) Markov chain, what is important is the period of the chain itself and not for each state. Do you have in mind any (probably graph theoretic?) use cases in which the period of each node is important?
3. I think it s better to follow the instruction by Jarvis and Shier in computing the GCD (on page 12, second last paragraph); see also graph_tools.py#L239. (For example, if the first two values of value are 2 and 3, then we know that GCD is 1, so we can immediately stop the for loop.)

[sglyon]

@ZacCranko is this now complete?

[ZacCranko]

Yep. For now.

[sbromberger]

Just FYI - with @ZacCranko's help, we've implemented support for self-loops in LightGraphs, so the earlier concerns about having to manipulate the adjacency matrices might now be moot. Please have a look at the latest master branch and let me know (via issues in LightGraphs) if you run into any problems.

@ZacCranko - thanks again. Your work has definitely improved the quality and feature set of LightGraphs!