<p>Finding mixed cycles in a mixed graph is equivalent to finding elementary directed cycles (of length >=3) in the corresponding directed graph. The corresponding directed graph is obtained from the mixed graph by replacing each undirected edge by two directed edges pointing in opposite directions. <strong>Proof:</strong> (1) Each elementary directed cycle (of length >=3) in the digraph corresponds directly to a mixed cycle in the mixed graph. (2) Each mixed cycle in the mixed graph contains an elementary mixed cycle of length >=3, and each such cycle corresponds directly an elementary directed cycle (of length >=3) in the directed graph. (1) and (2) together prove both directions of the statement, <strong>qed</strong>. So we are looking for references how to compute (all?) elementary cycles (of length >=3) in a directed graph.</p>

<p>The comments indicate that cs.stackexchange contains <a href="https://cs.stackexchange.com/questions/33949/assign-undirected-edges-in-a-mixed-graph-to-make-graph-cyclic-acyclic">some</a> <a href="https://cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph">answers</a> to this question, but it is unclear how to organize the results into a concise answer. This <a href="https://blog.mister-muffin.de/2012/07/04/enumerating-elementary-circuits-of-a-directed_graph/" rel="nofollow noreferrer">blog post</a> seems to nicely summarize the (most?) important references:</p>

<blockquote>
  <p><strong>Algorithm by R. Tarjan</strong></p>
  
  <p>The earliest algorithm that I included was published by R. Tarjan in 1973.</p>

<pre><code>Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017
</code></pre>
  
  <p><strong>Algorithm by D. B. Johnson</strong></p>
  
  <p>The algorithm by D. B. Johnson from 1975 improves on Tarjan's algorithm by its complexity.</p>

<pre><code>Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007
</code></pre>
  
  <p>In the worst case, Tarjan's algorithm has a time complexity of O(n⋅e(c+1)) whereas Johnson's algorithm supposedly manages to stay in O((n+e)(c+1)) where n is the number of vertices, e is the number of edges and c is the number of cycles in the graph.</p>
  
  <p><strong>Algorithm by K. A. Hawick and H. A. James</strong></p>
  
  <p>The algorithm by K. A. Hawick and H. A. James from 2008 improves further on Johnson's algorithm and does away with its limitations.</p>

<pre><code>Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf
http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf
</code></pre>
  
  <p>In contrast to Johnson's algorithm, the algorithm by K. A. Hawick and H. A. James is able to handle graphs containing edges that start and end at the same vertex as well as multiple edges connecting the same two vertices.</p>
</blockquote>

<p>The acyclicity testing itself seems to be easy: Compute the <a href="https://en.wikipedia.org/wiki/Strongly_connected_component" rel="nofollow noreferrer">strongly connected components</a> of the graph. Any (elementary) cycle is completely contained in a strongly connected component. A strongly connected component contains an elementary cycle iff it is not an undirected tree.</p>

<p>David Eppstein's proposed algorithm additionally computes one elementary cycle as evidence, and the above algorithms enumerate all elementary cycles. Any vertex or edge not contained in an elementary cycle could be deleted as a preprocessing step to improve the speed of the above algorithms. David Eppstein's algorithm could be used for that purpose, but even if only used on the strongly connected components, it won't delete every possible vertex or edge that can be deleted. But even if it could be extended to do so (computing the <a href="https://en.wikipedia.org/wiki/Biconnected_component" rel="nofollow noreferrer">block-cut tree</a> at least allows to delete every possible vertex that can be deleted), it is unclear whether this would really improve the speed of the above algorithms.</p>

CC BY-SA 3.0
2015-08-30T16:58:53.213Z
Do any of those references even mention mixed graphs? I know about finding cycles in directed graphs. My question was about extensions of those algorithms to mixed graphs.
David Eppstein
CC BY-SA 3.0
2015-08-30T20:01:23.957Z
@DavidEppstein Finding mixed cycles in a mixed graph is equivalent to finding elementary cycles (of length >=3) in the corresponding directed graph. Finding a reference for that statement might be challenging, but proving this statement is straightforward. I now added the statement and its proof to the answer. (Also added a remark without proof that computing the [block-cut tree](https://en.wikipedia.org/wiki/Biconnected_component) allows to delete every possible vertex that can be deleted without affecting the elementary cycles.)
Thomas Klimpel
CC BY-SA 3.0
2015-08-30T23:33:23.683Z
Ok, but they're still also not linear-time.
David Eppstein
CC BY-SA 3.0
2015-09-01T09:08:15.503Z
@DavidEppstein The acyclicity testing itself is done in linear time. But you are right, the time any of those algorithms needs to find the first elementary circuit (of length >=3) is not linear (in the worst case). Worse, most available implementations of Johnson's algorithm seem to use more than O((n+e)(c+1)) time, when applied to a single directed circle (with n vertices, e=n edges, and c=1 elementary cycles). Still, this was intended to be a correct answer, because Johnson's paper seems to be the most quoted reference for "finding elementary circuits".
Thomas Klimpel
CC BY-SA 3.0
2015-08-30T11:49:25.593Z
2015-08-30T20:03:46.143Z
2017-04-13T12:48:30.830Z
Thomas Klimpel
<p>A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction an orientation of a mixed graph is obtained by assigning a direction to each undirected edge. A set of edges forms a cycle in a mixed graph if it can be oriented to form a directed cycle. A mixed graph is acyclic if and only if it has no cycles.</p>

<p>This is all standard and there are many published papers mentioning acyclic mixed graphs. So the following algorithm for testing acyclicity of mixed graphs must be known:</p>

<p>Repeat the following steps:</p>

<ul>
<li>Remove any vertex that has no incoming directed edges and no incident undirected edges, as it cannot be part of any cycle.</li>
<li>If any vertex has no incoming directed edges but it has exactly one incident undirected edge, then any cycle using the undirected edge must come in on that edge. Replace the undirected edge by an incoming directed edge.</li>
</ul>

<p>Stop when no more steps can be performed. If the result is an empty graph, then the original graph must necessarily have been acyclic. Otherwise, starting from any vertex that remains, one can backtrack through the graph, at each step following backwards through an incoming edge or following an undirected edge that is not the one used to reach the current vertex, until seeing a repeated vertex. The sequence of edges followed between the first and second repetition of this vertex (in reverse order) forms a cycle in the mixed graph.</p>

<p>The Wikipedia article on mixed graphs mentions acyclic mixed graphs but doesn't mention how to test them, so I'd like to add to it something about this algorithm, but for that I need a published reference. Can someone tell me where it (or any other algorithm for testing acyclicity) appears in the literature?</p>

CC BY-SA 3.0
2015-08-24T18:34:48.743Z
what happens when a vertex has two incident undirected edges, and no other edge? For instance in a undirected triangle.  I mean do the rules above cover this case?
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2015-08-24T18:56:09.477Z
You can't do anything about such a vertex until a different vertex applies the rule that orients one of the edges. If you get stuck with a situation where such vertices exist, and you can't apply any more rules, then your graph contains a cycle.
David Eppstein
CC BY-SA 3.0
2015-08-24T19:06:23.677Z
Maybe it would make it clearer to consider what happens in the case that your graph is undirected. One way to test whether it's a forest is to remove leaves (degree one vertices) and isolated vertices until you get either an empty graph (it's a forest) or a nontrivial 2-core (a subgraph in which all vertices have degree ≥ 2, which necessarily contains a cycle). The mixed graph algorithm degenerates to this in the undirected case (except that it orients the leaves rather than immediately removing them), just as it degenerates to a standard topological sorting algorithm in the directed case.
David Eppstein
CC BY-SA 3.0
2015-08-25T06:45:10.543Z
Not sure if you've seen: there's a post on cs.stackexchange that asks a similar question [ref](http://cs.stackexchange.com/questions/33949/assign-undirected-edges-in-a-mixed-graph-to-make-graph-cyclic-acyclic). The answerer gives an algorithm to find a cycle in a mixed graph by orienting undirected edges, rejecting the graph if it doesn't exist. There's also paper(s) on determining whether a mixed graph is strongly orientable [ref](http://www.math.ucsd.edu/~fan/mypaps/fanpap/79scoomm.PDF) but strangely, couldn't find anything on actually finding connected components in mixed graphs.
Quanquan Liu
CC BY-SA 3.0
2015-08-25T07:08:53.680Z
Thanks — no, I hadn't seen that. The "find an orientation to make the graph contain a directed cycle" question is definitely the same one, and the algorithm in the answer looks correct. But unlike the one I describe, it's not linear time.
David Eppstein
CC BY-SA 3.0
2015-09-01T09:20:28.567Z
Your algorithm can still be implemented to be linear time, even if the graph is represented as a digraph (with lists for the incoming and outgoing directed edges for each vertex). If a vertex has only a single incoming edge left, you remove the corresponding outgoing edge if it is there, and then remember that this step doesn't need to be done again for this vertex.
Thomas Klimpel
CC BY-SA 3.0
2015-09-01T10:32:36.157Z
On second thought, it is a bit more complicated, because we need a dynamic digraph representation instead of a static digraph representation, such that deletion of edges can be performed in O(1) time. I know that you are an expert in dynamic graphs, but let me describe one possible solution nevertheless. The lists of incoming and outgoing edges would not just contain the neighbouring vertex, but also point to the identical edge in the opposite list at the neighbouring vertex. But this issue is independent of whether mixed graph representations or digraph representations are used.
Thomas Klimpel
<ds.algorithms><reference-request><graph-theory><graph-algorithms><directed-acyclic-graph>
Reference for mixed graph acyclicity testing algorithm?
David Eppstein
# Reference for mixed graph acyclicity testing algorithm?

(Asked by: username_0 on 2015-08-20)

A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction an orientation of a mixed graph is obtained by assigning a direction to each undirected edge. A set of edges forms a cycle in a mixed graph if it can be oriented to form a directed cycle. A mixed graph is acyclic if and only if it has no cycles.

This is all standard and there are many published papers mentioning acyclic mixed graphs. So the following algorithm for testing acyclicity of mixed graphs must be known:

Repeat the following steps:

* Remove any vertex that has no incoming directed edges and no incident undirected edges, as it cannot be part of any cycle.
* If any vertex has no incoming directed edges but it has exactly one incident undirected edge, then any cycle using the undirected edge must come in on that edge. Replace the undirected edge by an incoming directed edge.

Stop when no more steps can be performed. If the result is an empty graph, then the original graph must necessarily have been acyclic. Otherwise, starting from any vertex that remains, one can backtrack through the graph, at each step following backwards through an incoming edge or following an undirected edge that is not the one used to reach the current vertex, until seeing a repeated vertex. The sequence of edges followed between the first and second repetition of this vertex (in reverse order) forms a cycle in the mixed graph.

The Wikipedia article on mixed graphs mentions acyclic mixed graphs but doesn't mention how to test them, so I'd like to add to it something about this algorithm, but for that I need a published reference. Can someone tell me where it (or any other algorithm for testing acyclicity) appears in the literature?

**Tags:** ds.algorithms, reference-request, graph-theory, graph-algorithms, directed-acyclic-graph

> **Comments:**
> **username_1**: what happens when a vertex has two incident undirected edges, and no other edge? For instance in a undirected triangle.  I mean do the rules above cover this case?  
> **username_0**: You can't do anything about such a vertex until a different vertex applies the rule that orients one of the edges. If you get stuck with a situation where such vertices exist, and you can't apply any more rules, then your graph contains a cycle.  
> **username_0**: Maybe it would make it clearer to consider what happens in the case that your graph is undirected. One way to test whether it's a forest is to remove leaves (degree one vertices) and isolated vertices until you get either an empty graph (it's a forest) or a nontrivial 2-core (a subgraph in which all vertices have degree ≥ 2, which necessarily contains a cycle). The mixed graph algorithm degenerates to this in the undirected case (except that it orients the leaves rather than immediately removing them), just as it degenerates to a standard topological sorting algorithm in the directed case.  
> **username_2**: Not sure if you've seen: there's a post on cs.stackexchange that asks a similar question [ref](http://cs.stackexchange.com/questions/33949/assign-undirected-edges-in-a-mixed-graph-to-make-graph-cyclic-acyclic). The answerer gives an algorithm to find a cycle in a mixed graph by orienting undirected edges, rejecting the graph if it doesn't exist. There's also paper(s) on determining whether a mixed graph is strongly orientable [ref](http://www.math.ucsd.edu/~fan/mypaps/fanpap/79scoomm.PDF) but strangely, couldn't find anything on actually finding connected components in mixed graphs.  
> **username_0**: Thanks — no, I hadn't seen that. The "find an orientation to make the graph contain a directed cycle" question is definitely the same one, and the algorithm in the answer looks correct. But unlike the one I describe, it's not linear time.  
> **username_3**: Your algorithm can still be implemented to be linear time, even if the graph is represented as a digraph (with lists for the incoming and outgoing directed edges for each vertex). If a vertex has only a single incoming edge left, you remove the corresponding outgoing edge if it is there, and then remember that this step doesn't need to be done again for this vertex.  
> **username_3**: On second thought, it is a bit more complicated, because we need a dynamic digraph representation instead of a static digraph representation, such that deletion of edges can be performed in O(1) time. I know that you are an expert in dynamic graphs, but let me describe one possible solution nevertheless. The lists of incoming and outgoing edges would not just contain the neighbouring vertex, but also point to the identical edge in the opposite list at the neighbouring vertex. But this issue is independent of whether mixed graph representations or digraph representations are used.  

---

## 1 answers

### Answer by username_3 on 2015-08-30. Score: 1

Finding mixed cycles in a mixed graph is equivalent to finding elementary directed cycles (of length >=3) in the corresponding directed graph. The corresponding directed graph is obtained from the mixed graph by replacing each undirected edge by two directed edges pointing in opposite directions. Proof: (1) Each elementary directed cycle (of length >=3) in the digraph corresponds directly to a mixed cycle in the mixed graph. (2) Each mixed cycle in the mixed graph contains an elementary mixed cycle of length >=3, and each such cycle corresponds directly an elementary directed cycle (of length >=3) in the directed graph. (1) and (2) together prove both directions of the statement, qed. So we are looking for references how to compute (all?) elementary cycles (of length >=3) in a directed graph.
The comments indicate that cs.stackexchange contains some answers to this question, but it is unclear how to organize the results into a concise answer. This blog post seems to nicely summarize the (most?) important references:

Algorithm by R. Tarjan
The earliest algorithm that I included was published by R. Tarjan in 1973.
Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017

Algorithm by D. B. Johnson
The algorithm by D. B. Johnson from 1975 improves on Tarjan's algorithm by its complexity.
Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007

In the worst case, Tarjan's algorithm has a time complexity of O(n⋅e(c+1)) whereas Johnson's algorithm supposedly manages to stay in O((n+e)(c+1)) where n is the number of vertices, e is the number of edges and c is the number of cycles in the graph.
Algorithm by K. A. Hawick and H. A. James
The algorithm by K. A. Hawick and H. A. James from 2008 improves further on Johnson's algorithm and does away with its limitations.
Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf
http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf

In contrast to Johnson's algorithm, the algorithm by K. A. Hawick and H. A. James is able to handle graphs containing edges that start and end at the same vertex as well as multiple edges connecting the same two vertices.

The acyclicity testing itself seems to be easy: Compute the strongly connected components of the graph. Any (elementary) cycle is completely contained in a strongly connected component. A strongly connected component contains an elementary cycle iff it is not an undirected tree.
username_0's proposed algorithm additionally computes one elementary cycle as evidence, and the above algorithms enumerate all elementary cycles. Any vertex or edge not contained in an elementary cycle could be deleted as a preprocessing step to improve the speed of the above algorithms. username_0's algorithm could be used for that purpose, but even if only used on the strongly connected components, it won't delete every possible vertex or edge that can be deleted. But even if it could be extended to do so (computing the block-cut tree at least allows to delete every possible vertex that can be deleted), it is unclear whether this would really improve the speed of the above algorithms.

> **Comments:**
> **username_0**: Do any of those references even mention mixed graphs? I know about finding cycles in directed graphs. My question was about extensions of those algorithms to mixed graphs.  
> **username_3**: @DavidEppstein Finding mixed cycles in a mixed graph is equivalent to finding elementary cycles (of length >=3) in the corresponding directed graph. Finding a reference for that statement might be challenging, but proving this statement is straightforward. I now added the statement and its proof to the answer. (Also added a remark without proof that computing the [block-cut tree](https://en.wikipedia.org/wiki/Biconnected_component) allows to delete every possible vertex that can be deleted without affecting the elementary cycles.)  
> **username_0**: Ok, but they're still also not linear-time.  
> **username_3**: @DavidEppstein The acyclicity testing itself is done in linear time. But you are right, the time any of those algorithms needs to find the first elementary circuit (of length >=3) is not linear (in the worst case). Worse, most available implementations of Johnson's algorithm seem to use more than O((n+e)(c+1)) time, when applied to a single directed circle (with n vertices, e=n edges, and c=1 elementary cycles). Still, this was intended to be a correct answer, because Johnson's paper seems to be the most quoted reference for "finding elementary circuits".  

---

