4

The definition for directed acyclic graph is this: "there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again."

So far so good, but I am trying to find some premises that will be simpler to test and that will also guarantee the graph is acyclic. I came up with those premises, but they are pretty basic so I am sure other people figured it out in the past (or they are incorrect). The problem is I couldn't find anything related on books/online, hence why I decided to post this question.

Premise 1: If all vertices of the graph have an incoming edge, then the graph can't be acyclic. Is this correct?

Premise 2: Assume the graph in question does have one vertex with no incoming edges. In this case, in order to have a cycle, at least one of the other vertices would need to have two or more incoming edges. Is this correct?

Improve this question
1
  • 1
    A fairly simple way to establish whether your graph is acyclic is to do a depth first search from each of the nodes with no incoming edges. If you encounter a situation where continuing the search would see the same node in the spine of the tree twice, the graph is not acyclic. An optimization to this is that after the first 'root' has been scanned, if you encounter a node that has been visited in a previous run, skip it. With this optimization you only need to visit each node once.
    – dan_waterworth
    Commented Nov 12, 2011 at 12:59

2 Answers 2

Reset to default
4

Yes, both of your premises describe necessary conditions for a cyclic graph. However, they only exclude trivial graphs from cycle analysis, and you'll want to use one of the standard algorithms to make sure a given graph is actually cycle-free.

There are actually fairly cheap algorithms for detecting cycles in graphs; if you are performing a topological sort on a graph, for example, you'll detect cycles during the sort. The exact choice of algorithm naturally depends on your graph (one outgoing edge or multiple?) and your requirements.

Improve this answer
3
  • Gotcha. And yeah to verify those on large/complex graphs the cost would be (n^2) if I am not wrong (you basically would need to traverse the adjacency matrix). But for simple ones it might be a good idea. Thanks for the answer.
    – Daniel Scocco
    Commented Nov 12, 2011 at 13:00
  • @Daniel: Definitely not n^2. More like O(n + e).
    – kevin cline
    Commented Nov 12, 2011 at 15:43
  • @kevin cline, I mean to verify the cyclyes analyzing the adjacency matrix only, so this would be n^2 (you basically need to traverse the matrix n x n (where n is the number of vertices). If you use a better algorithm then yeah the complexity will probably be O(V+E).
    – Daniel Scocco
    Commented Nov 12, 2011 at 20:30
1

a simple test would be

  1. let S be the set of all nodes with no incoming paths (if there aren't you have a cycle)

  2. take out a node P out of S and add all nodes directly accessible to B and mark P traversed,

    if one of the added nodes is marked traversed you have a cycle

  3. find all nodes in B with only incoming paths from nodes that are marked traversed and add them to S

  4. repeat 2 and 3 until S is empty

  5. if there are nodes that are not traversed you have a cycle

loop invariant: S has only nodes that are proven to not be part of a cycle (only incoming paths form those that are not part of a cycle)

this is O(n*k) with k the average number of outgoing paths from a node

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.