Bug in NaiveLcaFinder

[hulk-baba]

Hello all, while trying to parse a dot file I used a graph whose all LCAs should be Robert and Cersei but instead, received nothing. Please check if it really is a bug. This bug happens to be in function findLcas of NaiveLcaFinder.

@Test
    public void testPseudoLcas(){
     public final String NL = "\n";
    	String input = "digraph GOT {"+NL+
			"graph [ bgcolor = whitesmoke ]"+NL+
			"subgraph cluster_stark {"+NL+
				"style = filled ;"+NL+
				"color = lightblue ;"+NL+
				"label = \" House Stark \" ;"+NL+
				"node [ style = filled , color = white ];"+NL+
				"Rickard ;"+NL+
				"Brandon ; Eddard ; Benjen ; Lyanna ;"+NL+
				"Robb ; Sansa ; Arya ; Brandon ; Rickon ;"+NL+
				"node [ shape = doublecircle , style = filled , color = white ];"+NL+
				"Jon ;"+NL+
				"Rickard -> Brandon ;"+NL+
				"Rickard -> Eddard ;"+NL+
				"Rickard -> Benjen ;"+NL+
				"Rickard -> Lyanna ;"+NL+
				"Eddard -> Robb ;"+NL+
				"Eddard -> Sansa ;"+NL+
				"Eddard -> Arya ;"+NL+
				"Eddard -> Brandon ;"+NL+
				"Eddard -> Rickon ;"+NL+
				"Eddard -> Jon [ label = \" bastard \" , color = azure4 ];"+NL+
			"}"+NL+
			"subgraph cluster_baratheon {"+NL+
				"style = filled ;" +NL+
				"color = chocolate3 ;" +NL+
				"label = \" House Baratheon \" ;" +NL+
				"node [ style = filled , color = white ];" +NL+
				"Ormund ; Steffon ; Robert ; Stannis ; Renly ; Shireen ; Joffrey ; Myrcellar ; Tommen ;" +NL+
				"Ormund -> Steffon ;" +NL+
				"Rhaelle -> Steffon ;" +NL+
				"Ormund -> Rhaelle ;" +NL+
				"Rhaelle -> Ormund ;" +NL+
				"Steffon -> Robert ;" +NL+
				"Steffon -> Stannis ;" +NL+
				"Steffon -> Renly ;" +NL+
				"Stannis -> Shireen ;" +NL+
				"Robert -> Joffrey ;" +NL+
				"Robert -> Myrcellar ;" +NL+
				"Robert -> Tommen ;" +NL+
			"}" +NL+
			"subgraph cluster_lannister {"+NL+
				"style = filled ;"+NL+
				"color = cornsilk3 ;"+NL+
				"label = \" House Lannister \" ;"+NL+
				"node [ style = filled , color = white ];"+NL+
				"Tywin ; Joanna ; Jaime ; Cersei ; Tyrion ;"+NL+
				"Tywin -> Joanna ;"+NL+
				"Joanna -> Tywin ;"+NL+
				"Joanna -> Jaime ;"+NL+
				"Joanna -> Cersei ;"+NL+
				"Joanna -> Tyrion ;"+NL+
				"Tywin -> Jaime ;"+NL+
				"Tywin -> Cersei ;"+NL+
				"Tywin -> Tyrion ;"+NL+
				"Jaime -> Cersei ;"+NL+
				"Cersei -> Jaime ;"+NL+
				"Robert -> Cersei ;"+NL+
				"Cersei -> Robert ;"+NL+
				"Cersei -> Joffrey ;"+NL+
				"Cersei -> Myrcellar ;"+NL+
				"Cersei -> Tommen ;"+NL+
				"Jaime -> Joffrey [ style = dashed ];"+NL+
				"Jaime -> Myrcellar [ style = dashed ];"+NL+
				"Jaime -> Tommen [ style = dashed ];"+NL+
			"}"+NL+
			"Lyanna -> Rhaegar [ style = dashed , label = \" ? \" ];"+NL+
			"Rhaegar -> Lyanna [ style = dashed , label = \" ? \" ];"+NL+
			"Lyanna -> Jon [ style = dashed , label = \" ? \" ];"+NL+
			"Rhaegar -> Jon [ style = dashed , label = \" ? \" ];"+NL+
			"labelloc = \" t \" ;"+NL+
			"fontsize =50;"+NL+
			"fontcolor = lightslategrey ;"+NL+
			"fontname = \" Bookman Old Style Bold Italic \" ;"+NL+
			"label = \" Game of Thrones Family Tree \""+NL+
			"}" ; 
    	
            VertexProvider<String> vp = (a, b) -> a;
	    EdgeProvider<String, DefaultEdge> ep = (f, t, l, a) -> new DefaultEdge();
	    GraphImporter<String, DefaultEdge> importer = new DOTImporter<String, DefaultEdge>(vp, ep);
	    DirectedPseudograph<String, DefaultEdge> graph = new DirectedPseudograph<String, DefaultEdge>(DefaultEdge.class);
	    try {
			importer.importGraph(graph, new StringReader(input));
		} catch (ImportException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	NaiveLcaFinder<String, DefaultEdge> graphFinder = new NaiveLcaFinder<>(graph);
        checkLcas(graphFinder, "Joffrey", "Tommen", Arrays.asList("Robert"));
    }

[jkinable]

What did you do to debug this issue?

[hulk-baba]

Since the NaiveLcaFinder class constructor only ensures that the graph must be directed but does not check if it contains a cycle. LCAs must be found on DAGs but for the given test, I later realised that it was not a DAG. It was supposed to be a DAG but it was not. Should I go ahead and implement this check?

[jkinable]

No, it would not be a good idea to add this as a check. There's always a trade-off between: spending computational effort on input validation, and just assuming that the user provides the correct input. I currently don't have access to the code, but what you could do is:

1. Check whether GraphTests contains a method isDirectedAcyclicGraph. If not, add it.
2. in theNaiveLCAs code, add an assertion: assert GraphTests.isDirectedAcyclicGraph(g); Perhaps in the NaiveLCA one should make it more explicit in the documentation/parameter specification that the input graph needs to be a DAG.
3. There are plenty of algorithms in jgrapht which can be used to assert whether a graph is acyclic, so no need to implement that.

Nevertheless, double check whether there doesn't exist already some method equivalent to the isDirectedAcyclicGraph test (I don't know this by heart).

[hulk-baba]

For my project tentatively, I modified the NaiveLcaFinder constructor to require DAG. I will work on writing the method isDirectedAcyclicGraph. We already have the implementation of both if the graph is directed and if the graph contains cycles, so, May I proceed to implement isDirectedAcyclicGraph?

[AlexandruValeanu]

@hulk-baba There is a problem with your input file. I get Cersei when I run my implementation with "Robert Cersei" (which is not really correct but there is an edge from Cersei to Robert; as it is from Robert to Cersei in the input file) as its input with my version of the input file.

Please check your input file again and let me know if you find something (or maybe try a smaller graph that you simulates part of the Lannister/Baratheon subgraph and it's easier to debug).

[hulk-baba]

@AlexandruValeanu please try with same input file with different arguments Joffrey Tommen as in code checkLcas(graphFinder, "Joffrey", "Tommen", Arrays.asList("Robert"));

[AlexandruValeanu]

@hulk-baba You are right. It doesn't work in that case.

A set of common ancestors would be [Robert, Cersei, Jaime]. But then this happens. That piece of code removes all nodes that have a child in the set of ancestors. Since there are edges from Cersei to Robert and Jaime and from Robert to Cersei all three of them can (and will) be eliminated from the set of common ancestors (Cersei is eliminated because of Robert, Jaime because of Cersei and Robert because of Cersei).

This is not a problem with the actual implementation as the graph is not a DAG (the cycle between Robert and Cersei creates problems in the Lannister/Baratheon subgraph).

Possible fixes:

• Remove the edge from Robert to Cersei; I get "Robert" after I've removed the edge
• In this case, findLca works. It might not work on other cycles but it seems to work on this one
• There is a small fix I could make so that it performs betters on graphs with cycles but this is not the purpose of this implementation

[tibrewalpratik17]

@AlexandruValeanu So are we assuming that the given graph is incorrect and then removing the edge from Robert to Cersei?
What I think that there should be no outputs in case of cyclic graphs which the code is doing at present, Yeah but when we enter Joffrey and Cersei then the output is Cersei which I think should not be because Cersei is a part of a cycle thus not making us sure whether that node is a LCA or not.
So what I suggest is that we can check whether the input nodes are a part of cycle or not by calling the function detectCyclesContainingVertex and if any of them is true then we can just return without any LCA. This is what I am doing in my warmup exercise.
Please let me know if I understood this incorrectly and help me to get it right.

[AlexandruValeanu]

@tibrewalpratik17
The graph in that pdf is not a DAG so you don't have to assume anything: it is not a valid input to NaiveLcaFinder.

For the warmup challenge, it's better to simply modify the graph so that it no longer contains any cycles. You can use CycleDetector to check whether there are any cycles in your version of the graph.

My implementation of findLcas doesn't try to detect cycles or do anything smart to produce a sensible answer when given a cyclic graph (i.e. you get undefined behaviour). Therefore there is no point in analysing the output if the precondition was broken.

[tibrewalpratik17]

@AlexandruValeanu okay... but what if a user enters a cyclic graph and expects an output so the valid output in that case should be null if any of the recent ancestors of the given nodes or may be the nodes itself is involved in a cycle right?

[hulk-baba]

The user should not expect an answer, in that case, the user must validate their input, it is just as saying what is f(x) for input x, not in the domain of f, the answer is not null but not defined.

[AlexandruValeanu]

@tibrewalpratik17
NaiveLcaFinder returns the correct list of lcas if and only if it is passed a DAG.

If the input is not a DAG then the output should not be trusted. It can literally be anything. In this case, I believe that my implementation returns only lcas that are not part of a cycle but I am not really certain as I haven't tested how undefined the answer is.

[AlexandruValeanu]

Can someone please close this as it is not a bug?