Detecting whether digraph has cycles

[Reginald Anderson]

Hello,

I am constructing a digraph in Macaulay2 from an adjacency matrix, and I'd like to know whether there is a pre-existing way to determine whether this digraph has any cycles. 

Thanks,

[Reginald Anderson]

Ah -- perhaps this is just "isCyclic(--)"

[Mahrud Sayrafi]

Hi Reggie,

You may have realized this already, but isCyclic only checks if the graph is a literal cycle, not that it has cycles. I couldn't find any existing methods for this, and I think it would be a useful thing to have.

If your graph isn't too large, an overkill solution might be to compute the distance matrix (where entry i,j is the distance from vertex i to vertex j) and check that all entries are non-negative (the documentation claims that if a vertex is unreachable, the matrix entry is -1). For instance, this should work:

hasCycles = G -> all(flatten entries distanceMatrix G, d -> d >= 0)

Mahrud

[Trevor Karn]

Hi Reggie,

This is another approach that might work for you. You can create the digraph using your adjacency matrices, but then the natural thing to do from the matroid theory perspective is to look at the edge matrix. Sample code is below, but I have created the digraph from edges to more clearly see the cycles.

HTH,

Trevor

restart
needsPackage("Graphs")

Gd = digraph ({{1,2},{2,3},{3,1}}, EntryMode => "edges") -- a graph with a directed cycle
Gu = digraph ({{1,2},{1,3},{2,3}}, EntryMode => "edges") -- a graph with an undirected cycle and no directed cycle
T = digraph({{1,2},{2,3},{3,4}}, EntryMode => "edges") --  a tree
TwoCycles = digraph({{1,2},{2,3},{3,1},{2,4},{4,1}}, EntryMode => "edges")
OneCycle = digraph({{1,2},{2,3},{3,1},{2,4},{1,4}}, EntryMode => "edges") -- the same undirected graph with only one cycle

-- indicator vectors
v = (i,n) -> (e = matrix {for j from 1 to n list if j == i then 1 else 0}; e)
z = (n) -> matrix {for j from 1 to n list 0}

hasDirectedCycles = G -> (
    n = length vertices G;
    M = transpose matrix (
for e in edges(G) list (
    {vout, vin} = toSequence e;
    flatten entries (v(vin, n) - v(vout, n))));

    K = ker M;

    dependencies = entries transpose generators K;

    any(apply(dependencies, c ->  all(apply(c, ci-> ci >= 0))), i->(i==true))
   
    )

hasDirectedCycles(Gd)
hasDirectedCycles(Gu)
hasDirectedCycles(T)
hasDirectedCycles(TwoCycles)
hasDirectedCycles(OneCycle)

[Reginald Anderson]

Hi Mahrud,

That's what I thought at first, but for digraphs "isCyclic" seems to check whether the graph contains a cycle: https://macaulay2.com/doc/Macaulay2-1.22/share/doc/Macaulay2/Graphs/html/_is__Cyclic_lp__Digraph_rp.html

[Reginald Anderson]

A nice minimal example I used to determine whether "isCyclic" does check for cycles in a directed graph in the way that I am looking for was the following.

Thanks,

[Mahrud Sayrafi]

Oh, is that the standard definition for a cyclic digraph? It seems like a bad choice to me, especially given that isCyclic(Graph) definitely checks for the graph being a literal cycle. Probably the digraph version should be changed into isAcyclic(Digraph) instead.

Trevor, I also like your approach which is closer to what I would have done if I wrote this from scratch, but looking at your code I wondered if ker M could return something like {-1,-1,-1} somehow? I would hope not but I'm not sure. Assuming it doesn't, for the last few lines I think this is simpler:

    dependencies := generators ker M;

    all(flatten entries dependencies, x -> x >= 0)

Also, I usually go for something like this for indicator functions:

N = ZZ^n

N^{i}      --  instead of v(i,n), and N_{i} gives the transpose

0 * N^{0} -- instead of z(n), and similarly for the transpose

Mahrud

--
You received this message because you are subscribed to the Google Groups "Macaulay2" group.
To unsubscribe from this group and stop receiving emails from it, send an email to macaulay2+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/macaulay2/5f74b457-5cd0-4a08-b80b-4bdef5ee9549n%40googlegroups.com.

[Reginald Anderson]

Hi Mahrud,

Yes -- I saw the documentation for graphs first and therefore posted the question originally because I had ruled "isCyclic" out. However, when I looked closer at "isCyclic" for digraphs, it seemed to work.

Similarly, Trevor: I thought originally that I might need to use the matroid package based on what I was seeing for graphs, but "isCyclic" for digraphs seems to be simpler, and to not require this. 

Thanks,

[jche...@gmail.com]

Looking at the code, it seems that "isCyclic(Digraph)" attempts to find a topological sort, which exists iff the input is a DAG (directed acyclic graph). I do like the change "isCyclic(Digraph)" -> "isAcyclic(Digraph)" (with a negation in the output of course).

There is a method "getCycles" in the Matroids package to compute all cycles in the underlying graph (which is how the graphic matroid is actually built), and once you have this list you can check whether any of these are directed. However, I think checking for topological sort should be much faster in general.

Justin

[jche...@gmail.com]

Mahrud: I think the line 

all(flatten entries distanceMatrix G, d -> d >= 0)

is checking whether any vertex is (directed) reachable from any other, which is a lot stronger than saying that a directed cycle exists (e.g. if the underlying graph is disconnected, as in Reggie's 3-vertex example). 

Incidentally, after upgrading to v1.25.06, on loading "Graphs" I see a bunch of warnings about symbols being shadowed between Complexes and OldChainComplexes. What's the preferred way to get rid of these?

[Reginald Anderson]

Noted: Then I will ask that you please not change the name/function of "isCyclic" while I am using it, if possible, for the next few months :) 

[Trevor Karn]

I would suggest that "isCyclic" is not the best name for the original graph function. If I were writing it from scratch I might call it "isCycle", as is done in Sage.

https://en.wikipedia.org/wiki/Cycle_graph

https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.is_cycle

I do like the idea of "isAcyclic" partially because acyclicity shows up in the first paragraph on a graph cycle in Wikipedia https://en.wikipedia.org/wiki/Cycle_(graph_theory). 

You could aways add the "isAcyclic" function and "isCycle" functions now and deprecate the "isCyclic" functions down the road.

Reggie, you don't need to use the matroid theory package, sorry for any confusion, this is all linear algebra. I was just thinking about it like a matroid theorist. I'm sure pure graph theorists would use the same linear algebra.

Mahrud, thanks for the feedback on my code! That is helpful. I was thinking that there was a preference for the first entry to be positive, but one could always add a line to force the situation and negate the vector if all were negative. 

Also, to Justin's comment, "checking for topological sort should be much faster in general." +1

[Thomas Kahle]

Hi everyone.

Tobias fixed this earlier this year:
https://github.com/Macaulay2/M2/issues/3626
https://github.com/Macaulay2/M2/pull/3628

As said, this method is used in detecting if a directed graph is a DAG.

(Most of the discussion in the pull request is about the interaction with the StatsGraphs package)

Best,
Thomas

To view this discussion visit https://groups.google.com/d/msgid/macaulay2/8bd20907-6a09-4918-b4fa-ae39ac8ec035n%40googlegroups.com.

--
Thomas Kahle
https://www.thomas-kahle.de

[Reginald Anderson]

Hello,

I'm now having some issue with the "isCyclic" diGraph function, because I would like to check for cycles which do not include self-loops. Depending on your convention (i.e., if a self-loop has length 1), then this would mean only checking for cycles with length >1.

Is there a way to check for whether a diGraph has cycles only of length >1, i.e., not including self-loops from a vertex to itself?

Thanks,

You received this message because you are subscribed to a topic in the Google Groups "Macaulay2" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/macaulay2/AS-mDr6W0tY/unsubscribe.
To unsubscribe from this group and all its topics, send an email to macaulay2+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/macaulay2/870EC927-201F-46DB-A15E-31F530DC2087%40jpberlin.de.

--

Reginald Anderson

Postdoctoral Scholar and Visiting Assistant Professor of Mathematics
Mathematical Sciences Department

Claremont McKenna College

[Reginald Anderson]

To clarify from previous suggestions:

-The digraph need not be connected

- The entire digraph itself does not need to be a cycle. 

i.e., if the digraph G had multiple connected components and no connected components had a cycle of length >1, then I would still like to say "isCylic(G) = false" 

That is, I would like to modify isCyclic(-) for digraphs, which currently only checks whether the digraph G contains a directed cycle, to now only check for whether G contains a directed cycle of length >1.

Thanks,

Reginald 

[Reginald Anderson]

Ah -- 

I suppose one can also just create a digraph without including the self-loops 😊.

So this should work as a solution for what I'm considering.

Thanks!