Longest Path for Directed Cyclic Graph

Question

What algorithm is used to find the longest path thru a directed cyclic unweighted graph. Each node points to only one other node. The graphs have up to 10^9 nodes. (I searched here and google to no avail.)

Answer 1

So you don't have one single graph but rather a series of distinct graphs which each form a closed chain with various number of nodes.

If that is the case, you can implement an algorithm which roughly uses O(n) time complexity and O(n) space complexity (assuming random access to all nodes and that each node has an ascending ID).

Start at the first node, and traverse the chain until you are back on the first node. For each visited node, mark it with a chain identifier. Store the number of visited nodes for this chain ID. Then you go to the next node (by ID, not in the chain), check if it has already been marked as being part of a chain. If yes, move on; if not, process the chain. Do that until you're on the last node ID. At this point you're done and you know the length of all chains, and then you pick the longest one.

Answer 2

First recursively remove every vertex of in-degree zero (in O(n)). The resulting graph is just a disjoint union of cycles.

Take arbitrary node, run dfs, and find the length of the cycle it belongs to (just by visiting neighbour, a natural dfs). Continue this for every unvisited node. At the end you can output the largest cycle.

Answer 3

See the tortoise and hare loop detection - you send one iterator with step increment of 1 (tortoise) and another one with step increment of two (hare). If the list has a cycle, they are bound to meet. (also in another question on SO).

1. Take a node
2. start the "tortoise and hare", marking the nodes visited by the tortoise (O(N) space complexity, array of bools suffice)

3. once the tortoise meets the hare, once the hare steps onto a node already visited by the tortoise (i.e. both are inside a loop), stop the hare, bring the tortoise at the same position as the hare and let the tortoise go around the loop once more and count the length of the loop (to check against the maximum so far)

4. take another not yet visited node and go to step 2

---

C++ solution

size_t maxLoopLen(const std::vector<size_t>& nextNodeIndexes) {
  size_t len=nextNodeIndexes.size();
  std::vector<bool> visitTrace(len, false);
  size_t ret=0; // the max number of elements in the loop
  for(;;) {
    // find the first non-visited node
    size_t pos=0;
    for(pos=0; pos<len && visitTrace[pos]; pos++);
    if(pos>=len) { // no more unvisited nodes
      break;
    }

    // this is needed for the "ring with string attached" topology
    // The global visitTrace contains the exploration of the prev
    // loos or **string leading to the same loop** - if the hare
    // steps on one of those prev strings, it may stop prematurely
    // (on the string, not inside the loop)
    std::vector<bool> currCycleTrace(len, false);

    size_t hare=pos, tortoise=pos;
    bool hareOnKnownPosition=false;
    while ( !currCycleTrace[hare] && !hareOnKnownPosition) {
      if(visitTrace[hare]) {
        // the hare just got to revisit something visited on prev cycles
        // *** ***********************************************************
        // *** this is where the algo achieves sub-O(N^2) time complexity
        // *** ***********************************************************
        hareOnKnownPosition=true;
        break;
      }
      // mark the tortoise pos as visited
      visitTrace[tortoise]=currCycleTrace[tortoise]=true;
      // tortoise steps with increment of one
      tortoise=nextNodeIndexes[tortoise];
      // hare steps two
      hare=nextNodeIndexes[hare];
      hare=nextNodeIndexes[hare];
    }
    // we got out of that cycle because the hare stepped on either:
    // - a tortoise-visited place on the current cycle - in this case
    //   both the tortoise and the hare are inside a not-yet-explored
    //   loop.
    // - on a place where the tortoise has been when it discovered a
    //   loop at prev cycles (think "ring with multiple string attached"

    if(!hareOnKnownPosition) {
      // The hare stepped on a new loop, not a loop visited before

      // Bring the tortoise to the same position as the hare. keep the
      // hare still and start counting how many steps until the tortoise
      // gets back to the same place
      tortoise=hare;
      size_t currLoopElemCount=0;
      do {
        tortoise=nextNodeIndexes[tortoise];
        currLoopElemCount++;
      } while(tortoise!=hare);
      ret=std::max(currLoopElemCount, ret);
    }
  }
  return ret;
}

#include <iostream>
int main() {
  std::vector<size_t> lasso={3,3,1,2,0};
  // expected 3, with cycle at nodes at indexes 1,2,3
  std::cout << "lasso max loop len " << maxLoopLen(lasso) << std::endl;

  // expected 2. The ring index 1 and 2. Two connected strings
  // - starting at index 0 - 0->3->2 and we are inside the ring
  // - starting at index 4 - 4->1  and we are inside the ring
  std::vector<size_t> ringWith2Strings={3,2,1,2,1};
  std::cout << "ringWith2Strings max loop len " 
            << maxLoopLen(ringWith2Strings) << std::endl;

  std::vector<size_t> singleElem={0};
  std::cout << "singleElem max loop len " << maxLoopLen(singleElem) << std::endl;

  std::vector<size_t> allTogether={
    3,3,1,2,0, // lasso
    8,7,6,7,6, // ringWith2Strings shifted up 5 pos
    10 // single element pointing to itself
  };
  std::cout << "allTogether max loop len " << maxLoopLen(allTogether) << std::endl;
}

Example of exploring the "nodes"

lasso={3,3,1,2,0};

• node 4 says "go to node 0"
• node 0 says "go to node 3"
• node 3 says "go to node 2"
• node 2 says "go to node 1"
• node 1 says "go to node 3" (loop)