3

Possible Duplicate:
Finding all cycles in graph

I have a task I've been wrapping my brain around and still have a trouble inplementing it. Here it goes: There is a class: 

public class Package {
private String name;
public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

private List<Package> dependencies;

public List<Package> getDependencies() {
    return dependencies;
}

public void setDependencies(List<Package> dependencies) {
    this.dependencies = dependencies;
}

public Package(String name){
    this.name = name;
    this.dependencies = new ArrayList<Package>();
}
  //any bunch of methods here))
}

And there is another one: 

public class Project {
private String name;
private List<Package> packages = new ArrayList<Package>();

public boolean hasCyclic(){
    //**//implementation should be here
}

}

I need to find whether a list of packages in a project has a cyclic dependency or not. For example A->B->C->B - found, return true or A->C->Z->A - found, return true. First thing that comes to mind is to get all packages' names, sort them and find duplicates. But somewhere, deep in my brain, something tells me it is not the most optimal solution. Can you guys help me out here? Thank you so much in advance.

Community
  • 1
  • 1
Anton K.
  • 933
  • 3
  • 9
  • 22

5 Answers5

3

This is basically a "Detect Cycles in a Directed Graph" problem.

I can't beat this answer already posted in SO that explains how to solve this problem.

Community
  • 1
  • 1
Marcelo
  • 11,218
  • 1
  • 37
  • 51
  • 3
    Well, you could beat the answer, since this question is much simpler. There the question is finding the cycles themselves, and finding all of them, whereas here it's simply whether or not there exists a cycle, and you don't even need to find it. The answer there is overkill. – davin Jul 07 '11 at 19:28
2

There is a cycle <==> The DFS forest (from any starting point) has a back branch.

Linear running time. Simple implementation.

davin
  • 44,863
  • 9
  • 78
  • 78
  • @Crash, http://en.wikipedia.org/wiki/Depth-first_search – davin Jul 07 '11 at 16:32
  • -1 A simple DFS fails for a directed graph. – tskuzzy Jul 07 '11 at 16:51
  • @tskuzzy, ummmm, no it doesn't. – davin Jul 07 '11 at 17:19
  • Consider the directed graph with 3 vertices (A,B,C) and 3 edges (A->B, A->C, B->C). If you start your DFS at A, your algorithm will falsely report a cycle since C will be visited twice. – tskuzzy Jul 07 '11 at 18:18
  • Well, it depends on how you implement the terminating condition of your DFS. I think you should clarify what you mean by a "back branch". I assumed you meant if you encounter a node you've visited before. – tskuzzy Jul 07 '11 at 18:25
  • @tskuzzy, you obviously aren't familiar with the branch classifications. A back branch is a branch of the original graph that when looked at in the context of the DFS tree/forest connects a node to its ancestor. There is no such branch in your example and it is easily provable that there exists such a branch iff there is a cycle. You're getting confused with a cross branch, which will point to a visited node, but doesn't indicate the existence of a cycle. Please understand what people are saying before you downvote them, especially on the premise of an incorrect example. – davin Jul 07 '11 at 18:26
  • @tskuzzy, it has nothing to do with terminating conditions. Read the wikipedia article, or study the topic from a text book and you'll see that "back branch" or "back edge" is the accepted terminology. – davin Jul 07 '11 at 18:28
  • 1
    I have never heard the terminology "back branch" before and I assure you that I did a Google search on it before down-voting. If you edit your answer, I'd be more than happy undo my vote. – tskuzzy Jul 07 '11 at 18:57
  • https://www.geeksforgeeks.org/detect-cycle-in-a-graph/ for an explanation of davin's idea. A back branch is simply a branch that points back to where you have already been (within the same depth-search-step) – lucidbrot Apr 04 '18 at 15:09
1

Think of the project's dependencies as a tree, and then simply do a depth-first traversal of the tree, keeping track of the package name when you visit each node. If you encounter a duplicate name before the traversal reaches the furthest level it can, then you have a cyclic dependency.

matt b
  • 138,234
  • 66
  • 282
  • 345
  • That sounds reasonable but I have some doubts about this. Imagine we have a 'A' name and {'B, 'C', 'B'} packages. Memorizing 'A' and traversing a tree will not find a dependency. However, there is one. – Anton K. Jul 07 '11 at 16:30
  • If you start at A, you add A to the `visited` Set. When you visit `B`, you add it to `visited`. When you visit `C` you add it to `visited`. When you come to the duplicated dependency `B`, it exists in `visited` at this point. Alternatively I would use a `Set` to model a project's dependencies anyway, as it doesn't make sense to have a dependency listed twice for a node. – matt b Jul 07 '11 at 16:32
  • Yeah, now I get it. Thank you I think it is the simplest solution putting up with moderate performance. Well, it was a interview question I had not screwed up much. – Anton K. Jul 07 '11 at 16:34
  • Uh I don't see how that'd work. Assume we have root package X that depends on packages B and C. Both of those packages themselves depend on package A which has no dependencies. There's obviously no cycle, but package A is still visited twice. The simplest way to solve this problem is Tarjan's algorithm, which while still fairly simple is a bit more complex. – Voo Jul 07 '11 at 18:39
  • @Voo you are correct - Marcelo's answer should be accepted. – matt b Jul 07 '11 at 18:50
  • @Voo, I disagree that that's the simplest. Tarjan's algorithm is non-trivial, and finding SCC is non-trivial. I still claim that a simple DFS + back edge is the easiest solution. Your example doesn't constitute a false-positive for such a solution. – davin Jul 07 '11 at 19:20
  • In the snippet above, I simply list all packages' names and check whether they contain duplicates. – Anton K. Jul 08 '11 at 15:24
  • @davin: Possible, I just have implemented Tarjan several times already and am quite comfortable with it (easily done even in C in about 100loc) - that surely influences my perception. But it probably depends on how you implement your solution - I just think that the naive solution of your algorithm would take quite some extra memory or have non linear runtime (or be more or less identical to tarjan with some fields per node and a stack) – Voo Jul 08 '11 at 17:12
  • @Voo, I can implement mine in C in about 20 well-spaced, non-obfuscated lines (it's literally a simple DFS with 1 minor adjustment for checking edges), and it has linear time and space. Like I said, your solution is much more flexible, but total overkill in this instance. – davin Jul 08 '11 at 18:17
0

There are a number of variants with varying memory/execution time characteristics. Some ideas are

  • Put all dependencies in a HashMap, detecting cycles means to find find a non-null value in when performing the write check
  • Use two "pointers" to traverse the list with one pointer faster than the other.
    • Either the pointers will terminate or one will eventually catch up in a cyclic loop such that the element at pointer A is the same as the element in pointer B.
  • Provide checks at insertion time. When inserting a new element, traverse the list to see if element to insert is already present or not.
Johan Sjöberg
  • 47,929
  • 21
  • 130
  • 148
0

That's the code I've come up with. Seems to work)

package com.mycompany.app;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class Package {
private String name;
private List<Package> dependencies;
private List<String> allNames = new ArrayList<String>();
public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

public List<Package> getDependencies() {
    return dependencies;
}

public void setDependencies(List<Package> dependencies) {
    this.dependencies = dependencies;
}

public Package(String name){
    this.name = name;
    this.dependencies = new ArrayList<Package>();
}

public boolean hasPackages(){
    return !dependencies.isEmpty();
}

public List<String> getAllNames(){
    allNames = new ArrayList<String>();
    allNames.add(name);
    for (Package pkg : dependencies){
        if (pkg.hasPackages()){
            allNames.addAll(pkg.getAllNames());
        }
        else{
            allNames.add(pkg.getName());
        }
    }

    return allNames;
}

public Package addPackage(Package pkg){
    dependencies.add(pkg);
    return this;

}

public boolean hasCyclic(){
    List<String> names = getAllNames();
    Set<String> visited = new HashSet<String>();
    for (String name : names){
        if (visited.contains(name)){
            return true;
        }
        else{
            visited.add(name);
        }
    }
    return false;
}
}
Anton K.
  • 933
  • 3
  • 9
  • 22
  • would this work? public void getBuildOrder(Package p){ p.visited=true; if(p.getDependencies.size()==0) syso(p.getName()); for( Package p1 : p.getDependencies){ if(p1.visited) { syso("cyclic dependency"); return; } getBuildOrder(p1); } – anubhs Oct 09 '17 at 08:00