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?