DEV Community: John Calabrese

virtual and override in C++

John Calabrese — Wed, 26 Jan 2022 15:58:12 +0000

Here's an example I wish I'd seen earlier when learning about inheritance in C++.

Let's start with a simple base class.

class Base {
public:
    void method() {
        speak("base method\n");
    }
};

Here speak is just a wrapper around cout and endl.

void speak(const string out) {
    cout << out << endl;
}

Let's now inherit from Base and re-use the same method name.

class Derived : public Base {
public:
    void method() {
        speak("derived method\n");
    }
};

So: base classes print "base", derived classes print "derived". However, what happens if we mix types? Concretely, what would the output of the following program be?

#include <iostream>
using std::cout;
using std::endl;
using std::string;

// convenience function to print
void speak(const string out) {
    cout << out << endl;
}

class Base {
public:
    void method() {
        speak("base method\n");
    }
};

class Derived : public Base {
public:
    void method() {
        speak("derived method\n");
    }
};


int main() {
    speak("ex1: base class");
    Base base = Base();
    base.method();

    speak("ex2: derived class");
    Derived derived = Derived();
    derived.method();

    speak("ex3: base class ref");
    Base& derived_ref = derived;
    derived_ref.method();

    // Derived& base_ref_error = base;
    // error: non-const lvalue reference to type 'Derived' cannot bind to a 
    // value of unrelated type 'Base'
}

Examples 1 and 2 are straightforward. What about example 3? Intuitively, we expect derived_ref.method() to print out "derived". It is a reference to a Derived object. However, this is the output:

ex1: base class
base method

ex2: derived class
derived method

ex3: base class ref
base method

Shock! The reason is that, in example 3, derived_ref is of type Base&. The name is misleading: it's really a base_ref :). When it looks for method it looks it up in the Base class.

When dealing with inheritance this situation is more common than one would like, especially when dealing with abstract classes / interfaces.

As an aside: the last example Derived& base_ref_error = base; would not compile if uncommented.

runtime polymorphism

So, how do we fix example 3 above? The solution is to mark the base class method as virtual.

#include <iostream>
using std::cout;
using std::endl;
using std::string;

// convenience function to print
void speak(const string out) {
    cout << out << endl;
}

class Base {
public:
    virtual void method() {
        speak("base method\n");
    }
};

class Derived : public Base {
public:
    void method() override {
        speak("derived method\n");
    }
};


int main() {
    speak("ex1: base class");
    Base base = Base();
    base.method();

    speak("ex2: derived class");
    Derived derived = Derived();
    derived.method();

    speak("ex3: base class ref");
    Base& derived_ref = derived;
    derived_ref.method();
}

This time the output is:

ex1: base class
base method

ex2: derived class
derived method

ex3: base class ref
derived method

Great! This makes more sense. The variable derived_ref is, after all, built from derived, which is of type Derived.

Note: the override keyword in the Derived class is unnecessary. However, it's useful to have it there to help the compiler find bugs.

abstract classes

A typical scenario where the virtual stuff comes up is with abstract classes. Here is an example:

class AbstractBase {
public:
    virtual void method() = 0;
    virtual ~AbstractBase() = default;
};

We have modified base to have method be unimplemented. The =0 means we require any derived class to implement that method.

We also mark the destructor as virtual, as subtle bugs can arise if we don't. See below.

#include <iostream>
using std::cout;
using std::endl;
using std::string;

// convenience function to print
void speak(const string out) {
    cout << out << endl;
}

class AbstractBase {
public:
    virtual void method() = 0;
    virtual ~AbstractBase() = default;
};

class Derived : public AbstractBase {
public:
    void method() override {
        speak("derived method\n");
    }
};


int main() {
    // AbstractBase abstractbase = AbstractBase();
    // error: allocating an object of abstract class type 'AbstractBase''Base'

    speak("ex2: derived class");
    Derived derived = Derived();
    derived.method();

    speak("ex3: base class ref");
    AbstractBase& derived_ref = derived;
    derived_ref.method();
}

The output is

ex2: derived class
derived method

ex3: base class ref
derived method

as expected.

As an aside: the first example AbstractBase abstractbase = AbstractBase(); does not compile, as AbstractBase is, indeed, abstract.

destructors

Let's clarify what happens if we don't have a destructor marked as virtual. Here is a first example.

#include <iostream>
using std::cout;
using std::endl;
using std::string;

// convenience function to print
void speak(const string out) {
    cout << out << endl;
}

class Base {
public:
    ~Base() {
        speak("base destruct");
    }
};

class Derived : public Base {
public:
    ~Derived() {
        speak("derived destruct");
    }
};

int main() {
    Derived der; 
}

If we run this, the output is

derived destruct
base destruct

as the destructors for der are invoked in order. However, tweaking this slightly, we get some unexpected behavior (I got this example from "C++ Crash Course" by Josh Lospinoso).

#include <iostream>
using std::cout;
using std::endl;
using std::string;

// convenience function to print
void speak(const string out) {
    cout << out << endl;
}

class Base {
public:
    ~Base() {
        speak("base destruct");
    }
};

class Derived : public Base {
public:
    ~Derived() {
        speak("derived destruct");
    }
};

int main() {
    Base* x{new Derived()};
    delete x;
}

The output is

base destruct

so ~Derived is never invoked! This could lead to serious issues. The simple fix is to have the destructor be virtual.

#include <iostream>
using std::cout;
using std::endl;
using std::string;

// convenience function to print
void speak(const string out) {
    cout << out << endl;
}

class Base {
public:
    virtual ~Base() {
        speak("base destruct");
    }
};

class Derived : public Base {
public:
    ~Derived() {
        speak("derived destruct");
    }
};

int main() {
    Base* x{new Derived()};
    delete x;
}

so now the output is

derived destruct
base destruct

as expected.

C++ noob stuff: copies, return references, constructors.

John Calabrese — Sat, 08 Jan 2022 05:57:34 +0000

I started to learn C++ for work, and it's been "fun". One of the first things I learned is passing function arguments by reference, instead of by value (or by passing a raw pointer). You can also return references, but I haven't seen this covered explicitly, so I wrote a small program to test things out. Here is a first version.

Gadgets

struct Gadget {
    // members
    int giovanni;
    int giorgio;
    // constructor
    Gadget(int giov, int gior): giovanni(giov), giorgio(gior) {}
    // a convenient method
    void tellMe() {
        cout << "giovanni: " << giovanni << ", " << &giovanni << "\n";
        cout << "giorgio: " << giorgio << ", " << &giorgio << "\n";
    }
};

int main() {
    Gadget g{-3,7};
    cout << "Defined a new Gadget g at " << &g << "\n";
    g.tellMe();
}

(I'm using struct here, and class later, for no good reason)
Running it spits out something like this.

Defined a new Gadget g at 0x7ffee700d918
giovanni: -3, 0x7ffee700d918
giorgio: 7, 0x7ffee700d91c

Interestingly, the address of g is the same as the one for g.giovanni. This is probably C++ being smart about memory. This seems to be ok. While the lines below are fine

    Gadget* p = &g;
    (*p).tellMe();

the compiler will complain if we try this

    Gadget* p = &(g.giovanni); // incompatible types

or this

    int* p = &(g.giovanni);
    (*p).tellMe(); // *p does not have a tellme method

Widgets

Let's add a second class (this time a class with everything explicitly public).

class Widget {
public:
    // members
    int myInto;
    Gadget myGadget;
    // constructor
    Widget(int giov, int gior, int myo): myGadget(giov, gior), myInto(myo) {}
    // info
    void tellMe() {
        cout << "myInto: " << myInto << ", " << &myInto << "\n";
        myGadget.tellMe();}
    // getters: by value, by reference
    Gadget getGadget_val() {return myGadget;}
    Gadget& getGadget_ref() {return myGadget;}
};

Let's write a main to use this.

int main() {
    Widget w{2,-3,77};
    cout << "defined new widget w at " << &w << "\n";
    w.tellMe();

    cout << "\ncalling tellMe from w.getGadget_ref()\n";
    w.getGadget_ref().tellMe();

    cout << "\ncalling tellMe from w.getGadget_val()\n";
    w.getGadget_val().tellMe();
}

Running this will output something like this

defined new widget w at 0x7ffeec970910
myInto: 77, 0x7ffeec970910
giovanni: 2, 0x7ffeec970914
giorgio: -3, 0x7ffeec970918

calling tellMe from w.getGadget_ref()
giovanni: 2, 0x7ffeec970914
giorgio: -3, 0x7ffeec970918

calling tellMe from w.getGadget_val()
giovanni: 2, 0x7ffeec970908
giorgio: -3, 0x7ffeec97090c

and we see that indeed the members of w.getGadget_val() have different memory addresses.

Sanity check

As confirmation, let's try modifying getGadget_val() and getGadget_ref(). Here's a complete snippet.

#include <iostream>
using std::cout;

struct Gadget {
    // members
    int giovanni;
    int giorgio;
    // constructor
    Gadget(int giov, int gior): giovanni(giov), giorgio(gior) {}
    // a convenient method
    void tellMe() {
        cout << "giovanni: " << giovanni << ", " << &giovanni << "\n";
        cout << "giorgio: " << giorgio << ", " << &giorgio << "\n\n";
    }
};

class Widget {
public:
    // members
    int myInto;
    Gadget myGadget;
    // constructor
    Widget(int giov, int gior, int myo): myGadget(giov, gior), myInto(myo) {}
    // info
    void tellMe() {
        cout << "myInto: " << myInto << ", " << &myInto << "\n";
        myGadget.tellMe();}
    // getters: by value, by reference
    Gadget getGadget_val() {return myGadget;}
    Gadget& getGadget_ref() {return myGadget;}
};

int main() {
    Widget w{2,-3,77};
    cout << "defined new widget w at " << &w << "\n";
    w.tellMe();

    Gadget g1 = w.getGadget_ref();
    g1.giovanni--;
    w.tellMe();
    // does not change w: g1 is a copy of w.myGadget!!

    Gadget& g2 = w.getGadget_ref();
    g2.giovanni--;
    w.tellMe();
    // works: notice when we create g2 we use Gadget&

    Gadget g3 = w.getGadget_val();
    g3.giovanni--;
    w.tellMe();
    // does not change w, as expected

    // Gadget& g4 = w.getGadget_val();
    // does not even compile, as RHS is temp
}

This all makes sense, however the difference between g1 and g2 is subtle: it's only in the type we use. We could easily make that mistake and copy something without noticing (or viceversa). What if we don't want to allow copies? Or references? For this we can tinker with Gadget's constructors.

Constructors

Let's delete the copy and move constructors. We also need to delete getGadget_val as that implicitly uses those.

#include <iostream>
using std::cout;

struct Gadget {
    // members
    int giovanni;
    int giorgio;
    // constructor
    Gadget(int giov, int gior): giovanni(giov), giorgio(gior) {}
    Gadget(const Gadget&) = delete;
    Gadget(const Gadget&&) = delete;
    // a convenient method
    void tellMe() {
        cout << "giovanni: " << giovanni << ", " << &giovanni << "\n";
        cout << "giorgio: " << giorgio << ", " << &giorgio << "\n\n";
    }
};

class Widget {
public:
    // members
    int myInto;
    Gadget myGadget;
    // constructor
    Widget(int giov, int gior, int myo): myGadget(giov, gior), myInto(myo) {}
    // info
    void tellMe() {
        cout << "myInto: " << myInto << ", " << &myInto << "\n";
        myGadget.tellMe();}

    Gadget& getGadget_ref() {return myGadget;}
    // we had to eliminate the _val version
};

int main() {
    Widget w{2,8,77};
    w.tellMe();

    Gadget& g1{w.getGadget_ref()};
    g1.tellMe();

    // Gadget g2{w.getGadget_ref()};
    // does not compile: we deleted the copy constructor
}

As we can see in the last line, we can't make a copy as the copy constructor has been deleted. Just for fun, let's keep the move constructor deleted, but not the copy constructor. This should allow us to make copies, right? Well, as it turns out this code does not compile:

// does not compile!
#include <iostream>
using std::cout;

struct Gadget {
    // members
    int giovanni;
    int giorgio;
    // constructor
    Gadget(int giov, int gior): giovanni(giov), giorgio(gior) {}
    Gadget(const Gadget&&) = delete;
    // a convenient method
    void tellMe() {
        cout << "giovanni: " << giovanni << ", " << &giovanni << "\n";
        cout << "giorgio: " << giorgio << ", " << &giorgio << "\n\n";
    }
};

class Widget {
public:
    // members
    int myInto;
    Gadget myGadget;
    // constructor
    Widget(int giov, int gior, int myo): myGadget(giov, gior), myInto(myo) {}
    // info
    void tellMe() {
        cout << "myInto: " << myInto << ", " << &myInto << "\n";
        myGadget.tellMe();}
    // getters: by value, by reference
    Gadget getGadget_val() {return myGadget;}
    Gadget& getGadget_ref() {return myGadget;}
};

int main() {
    Widget w{2,8,77};
    Gadget g1{w.getGadget_val()};
}
// does not compile!

The reason being the copy constructor has been implicitly deleted by our deletion of the move constructor. To remedy, we need to be a bit more explicit about the copy constructor. For example by making it default.

#include <iostream>
using std::cout;

struct Gadget {
    // members
    int giovanni;
    int giorgio;
    // constructor
    Gadget(int giov, int gior): giovanni(giov), giorgio(gior) {}
    Gadget(const Gadget&) = default;
    Gadget(const Gadget&&) = delete;
    // a convenient method
    void tellMe() {
        cout << "giovanni: " << giovanni << ", " << &giovanni << "\n";
        cout << "giorgio: " << giorgio << ", " << &giorgio << "\n\n";
    }
};

class Widget {
public:
    // members
    int myInto;
    Gadget myGadget;
    // constructor
    Widget(int giov, int gior, int myo): myGadget(giov, gior), myInto(myo) {}
    // info
    void tellMe() {
        cout << "myInto: " << myInto << ", " << &myInto << "\n";
        myGadget.tellMe();}
    // getters: by value, by reference
    Gadget getGadget_val() {return myGadget;}
    Gadget& getGadget_ref() {return myGadget;}
};

int main() {
    Widget w{2,8,77};
    Gadget g1{w.getGadget_val()};
}

Binary Classifiers

John Calabrese — Mon, 06 Sep 2021 04:32:43 +0000

Some ML concepts I tend to regularly forget and refresh.

Binary Classifiers

We have data $x_i,y_i)$ where the inputs x are numbers, and the output y are yes/no (encoded as 1 or 0).

Metrics

Once you've trained a model you'll make predictions $xi↦y^ix_i \mapsto \hat{y}_i$ . Depending on the pair $(y^i,yi)(\hat{y}_i,y_i)$ you might have: true positive, true negative, false positive, false negative.

Accuracy

Accuracy measures how many we got right over how many samples there are. Let N = TP + TN + FP + FN be the total number of samples we are evaluating. Then accuracy is

Accuracy=TP+TNN\text{Accuracy} = \frac{\text{TP}+\text{TN}}{N}

This metric is terrible when the data is strongly imbalanced. For example, let's say we are training a search engine with a lots of different documents. So x is a pair (search query, result) and y is the outcome good/bad. It's not unreasonable to expect our data to mostly be (query,result) pairs labeled "bad". So we could just have a model always assign $\mapsto 0$ and achieve super high accuracy.

Precision and Recall

High precision means few false positives.

Precision=TPTP+FP\text{Precision} = \frac{\text{TP}}{\text{TP} + \text{FP}}

High recall means few false negatives.

Recall=TPTP+FN\text{Recall} = \frac{\text{TP}}{\text{TP} + \text{FN}}

For example in a two-stage search engine, the first stage should have high recall (to make sure all the relevant documents are there, at the cost of throwing in some irrelevant ones), the second stage should have high precision.

F1

Ideally we want high F1, which combines both precision and recall.

F1=Precision⋅RecallPrecision+Recall\text{F1} = \frac{ \text{Precision} \cdot \text{Recall} } { \text{Precision} + \text{Recall} }

the threshold

Another issue is that typically our model $f$ doesn't really have a binary output, but rather a "probability" (or score) $f(xi)∈[0,1]f(x_i) \in [0,1]$ . So then it's up to us to decide a cutoff: if $f(x_i) > t$ then it's a 0, otherwise it's a 1. How to decide a cutoff? And is there a cutoff-independent way of evaluating our model?

Cutoff can be decided whether you favor precision or recall most.
Models could be evaluated by the ROC-AUC, or by looking at the precision-recall curve.

Logistic Regression

Possibly the second most basic binary classifier, after nearest neighbors. You have data $xi∈Rd,yi∈0,1x_i \in \mathbb R^d , y_i \in {0,1}$ . You apply a linear map to x to produce a scalar, ie you take the dot product with some other vector $\cdot x$ . We then hit this with a sigmoid, to get a number between 0 and 1. The sigmoid is

σ(t)=et1+et\sigma(t) = \frac{e^t}{1 + e^t}

so that

y^=σ(f(x,w))∈[0,1].\hat y = \sigma(f(x,w)) \in [0,1].

What loss function is appropriate here? We should interpret $y^\hat y$ as being a probability of being 1, in some sense.
More formally, if we treat our inputs and outputs as random variables, the idea is that $σ(f(X,w))=E[Y∣X]\sigma(f(X,w)) = E[Y|X]$ . Since Y can only take 0,1 values it must be a Bernoulli random variable, whose likelihood is

p^Y (1-p)^{1-Y}

where $p = E [Y ∣ X]$ . Following the maximum likelihood principle, given our data $x_i,y_i$ the best $w$ is the one maximizing the likelihood, which is (assuming as is customary that our samples are iid)

max⁡w∏iyi^yi(1−yi^)1−yiw^* = \argmax_w \prod_i \hat{y_i}^{y_i} (1 - \hat{y_i})^{1-y_i}

and since log is monotone, this is equivalent to

min⁡w∑i−yilog⁡(yi^)−(1−yi)log⁡(1−yi^)w^* = \argmin_w \sum_i - y_i \log(\hat{y_i}) - (1-y_i) \log(1-\hat{y_i})

which is the so-called binary cross-entropy loss.

Leetcode 282: Expression Add Operators

John Calabrese — Fri, 13 Aug 2021 23:04:04 +0000

This one threw me off. The solution was conceptually kinda clear, but implementing it was a bit tricky.

So the input consists of a string num and an integer target. The string consists of digits, and the goal is to find all the ways to insert +,-,* operators to reach the target.

How to solve this is kinda clear. There isn't a way to be smart about things, so we'll just stick in the operators in all possible ways and see what we get. But how to actually code it? Here's a first attempt.

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        """
        scan num
        at each index in num you can either stick in an operator, or not
        exhaust all possibilities

        we will use recursion
        """
        def helper(prev: str, i: int):
            # it's often easier to have a helper function to perform the recursion
            # at the very least it should have the position i as an argument
            # and also whatever the previous string was cooked up (ie with inclusion of operators)
            if i == len(num):
                # check if prev is as solution
                if is_sol(prev):
                    ans.append(prev)

            else:
                # if we haven't reached the end, keep building the string
                for c in ['+','-','*','']:
                    helper(prev+c+num[i],i)

        ans = []
        helper('',0)
        return ans

This was actually pretty simple, but we still haven't implemented the is_sol function. How to do that? I think the easiest way is to use possibly the worst coding practice out there: eval. This is bad for two reasons: it's slow, and in a real system it would be an immense vulnerability. But this is leetcode, so we don't care. We'll just replace is_sol(prev) with eval(prev) == target.

However, we are not done. If you try to run that code, at least two issues may come up. The first is that we may be forming numbers from strings like 007, ie with leading zeros. The second is that we may be concatenating operators together, such as ** or +*. This is bad. We need to fix this. We just need to include some boring checks at the beginning.

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        """
        at each index in num you can either add in an operator or not
        the goal is to exhaust all possibilities

        can recurse over it
        """
        def helper(prev,i):
            # check if we can add num[i] to prev
            if len(prev) == 0:
                add_num = True
            elif prev[-1] in operators:
                add_num = True
            elif len(prev) == 1:
                if prev[-1] == '0':
                    add_num = False
                else:
                    add_num = True
            elif prev[-1] == '0' and prev[-2] in operators:
                add_num = False
            else:
                add_num = True
            # check if we can add operators and num[i] to prev
            if len(prev) == 0:
                add_ops = False
            elif prev[-1] in operators:
                add_ops = False
            else:
                add_ops = True

            if i == len(num):
                if eval(prev) == target:
                    ans.append(prev)
            else:
                if add_num:
                    helper(prev+num[i],i+1)
                if add_ops:
                    for c in operators:
                        helper(prev+c+num[i],i+1)

        operators = ['+','-','*'] 
        ans = []
        helper('',0)
        return ans

This was not pretty.

From DFS to Topological Sort

John Calabrese — Thu, 08 Jul 2021 18:15:12 +0000

Recently I revisited this leetcode question https://leetcode.com/problems/alien-dictionary/solution/. I first learned about it a year and a half ago when I was a data science fellow at Insight, in New York. It's a fun problem, though a terrible interview question. I think it would be much better if you could at least assume the alien dictionary has no inconsistencies (ie that an order can always be extracted).

DFS

Depth-first search is a standard method to explore a graph. For example, let's say we want to print the value of all the nodes in a graph. Here is a(n incorrect) recursive implementation.

def dfs(node):
    print(node.val)
    for child in node.children:
        dfs(child)

There are two big issues with this code. The first is that it might get stuck in a loop. For the graph 1->2->3->1, calling dfs(node_1) will loop forever. Let's fix this by keeping track of which nodes have already been visited by the DFS.

def dfs(node):
    if node in visited:
        return None
    print(node.val)
    visited.add(node)
    for child in node.children:
        dfs(child)

visited = set()

The second issue is that it has no awareness of the whole graph. For the graph 1 -> 2 -> 3, calling dfs(2) will miss node 1. So let's assume we have a dictionary edges, where edges[node] lists all the children of node.

def print_nodes(edges):
    def dfs(node):
        if node in visited:
            return None
        print(node.val)
        visited.add(node)
        for child in edges[node]:
            dfs(child)

    visited = set()
    for node in edges.keys():
        dfs(node)

For the graph

(where I assume the edges are all pointing down) the function above will print the nodes in the order 1,2,3,4 (assuming 3 comes before 4 in edges[node_2]). This would be a "pre-order" way of printing the graph. The "post-order" way would be

def print_nodes_post(edges):
    def dfs(node):
        if node in visited:
            return None
        visited.add(node)
        for child in edges[node]:
            dfs(child)
        print(node)

    visited = set()
    for node in edges.keys():
        dfs(node)

yielding 3,4,2,1.

Obviously printing out the nodes in a graph is a silly task (we could just directly use edges.keys()). The point is that DFS allows us to explore a whole graph, and we can perform tasks as we move along.

def dfs(node):
    visited.add(node)
    do_some_work_pre_children(node)
    for child in edges[node]:
        dfs(child)
    do_some_work_post_children(node)

Detecting cycles

Given a graph, let's write a function to detect if it has any cycles. Here is an (incorrect) approach.

def is_acyclic(edges):
    def dfs(node):
        if node in visited:
            # cycle detected?
            return False

        visited.add(node)
        for child in edges[node]:
            if dfs(child) is False:
                return False
        return True

    visited = set()
    for node in edges.keys():
        if node not in visited:
            if dfs(node) is False:
                return False
    return True

The main thought process here is that if upon calling dfs the node is already in visited then a cycle must be present. However this is deeply flawed. For example with the graph

(where again all the edges are pointing downwards) if we start DFS from 0 everything is fine. But if we instead started from node 2 (or 3, or 4) the function will return False, ie that the graph contains a cycle.

To fix this, we add an additional visited set, which is specific to the recursion.

def is_acyclic(edges):
    def dfs(node):
        if node in visited:
            return True

        visited.add(node)
        visited_dfs.add(node)
        for child in edges[node]:
            if child in visited_dfs:
                return False
            if dfs(child) is False:
                return False

        # after we explored node and all its children
        # we can remove the temporary marker
        # if we don't we'll run into the same issue
        # as in the naive approach
        visited_dfs.remove(node)
        return True

    visited = set()
    visited_dfs = set()
    for node in edges.keys():
        if dfs(node) is False:
            return False
    return True

Topological Sort

Let's say you have a graph which represents certain tasks to be executed (eg ETL tasks for an orchestrator like airflow or prefect, or a computation graph for a neural network). Edges in this graph represent a dependency between two tasks. Because of these dependencies, we can't just execute these tasks in a random order. It would be nice if we could extract a total order of the tasks, compatible with the edges, ie if you can go from node a to node b, we should have a < b in the order.

We can't do this for all graphs. Whatever order we choose for the nodes of 1->2->3->1 it will be incompatible with the graph structure. However if we have a DAG (directed acyclic graph), ie a graph without cycles, then we can. One way to come up with such an order is via DFS. For the graph

[0,1,2,3,4,5], [0,1,3,2,4,5], [0,5,1,2,3,4] are all acceptable orders. The idea is to explore the graph using DFS and to add nodes to the list in post-order. For example let's start by exploring the graph above from the node 2. This will yield the list [4,2]. Continuing from node 1, we will have [4,2,3,1]. Continue with node 5 to get [4,2,3,1,5], and finally add 0 to get [4,2,3,1,5,0]. Reversing this list we get [0,5,1,3,2,4], which is a valid total order.

def topological_sort(edges):
    """Assumes graph is acyclic."""
    def dfs(node):
        if node in visited:
            return None
        visited.add(node)
        for child in edges[node]:
                dfs(child)
        order.append(node)

    order = []
    visited = set()
    for node in edges.keys():
        dfs(node)

    order.reverse()
    return order

Combining the two

Of course, if your graph is not guaranteed to be acyclic, we can combine the two operations at once.

def topological_sort_if_acyclic(edges):
    """Return an order if acyclic, else return []"""
    def dfs(node):
        if node in visited:
            return True

        visited.add(node)
        visited_dfs.add(node)

        for child in edges[node]:
            if child in visited_dfs:
                return False
            if dfs(child) is False:
                return False
        visited_dfs.remove(node)
        order.append(node)
        return True

    order = []
    visited = set()
    visited_dfs = set()
    for node in edges.keys():
        if dfs(node) is False:
            return []

    order.reverse()
    return order

LeetCode 124. Binary Tree Maximum Path Sum

John Calabrese — Tue, 06 Jul 2021 05:56:39 +0000

I normally do not enjoy the leetcode grind, but I had fun understanding the solution to this problem, as it had an enlightening gotcha.
Here is the link to it: https://leetcode.com/problems/binary-tree-maximum-path-sum

In short, the problem asks the following. In a binary tree, a path is a (non-repeating) sequence of adjacent nodes. For each path, take the sum of the values of each node. What's the highest value you can get?

For the tree

  1
 / \
2   -3

the following are all the paths: [1], [2], [-3], [1,2], [1,-3], but also [2,1,-3]. (I am considering the paths [2,1] and [1,2] as being the same) So two things to notice: the paths do not need to contain the root, paths can travel upwards.

I thought about how to solve it for bit, and then looked up the solution. The idea is pretty simple, once you realize that in doing DFS by recursion you should be looking at the tree from the bottom up.

Taking the tree above again, let's start from node 2. It has no children, so the best thing we can do is the path [2] for a max of 2. Same goes for -3. Once DFS moves up a level, we land in node 1. Here we have several options.

stand still, ie the path [1] for a max of 1
consider 1 as part of a path going left, ie [1,2] with a max of 3
consider 1 as part of a path going right, ie [1,-3] with a max of 2
consider 1 as part of a path going from left to right, ie [2,1,-3] for max of 0

At this point I thought I had understood the solution, so I went and wrote this up.

def max_path(root: Node) -> int:
    # initialize the best value to be the lowest number
    # (the tree could contain all negative values,
    # so we can't just initialize as 0)
    # I'm using an array as a cheap way to bind a global variable
    # perhaps the better way is to use python's global / nonlocal
    best_global = [float('-inf')]

    def helper(node: Node) -> int:
        # node is None, return 0
        if not node:
            return 0

        # compute the possible scenarios
        stand = node.val
        go_left = stand + helper(node.left)
        go_right = stand + helper(node.right)
        bridge = go_left + go_right - stand
        # the value of bridge (ie a path that goes left and right) is
        # helper(node.left) + stand + helper(node.right)
        # = go_left - stand + stand + go_right - stand
        # = go_left + go_right - stand

        local_best = max(stand, go_left, go_right, bridge)
        best = best_global.pop()
        best = max(best, local_best)
        best_global.append(best)

        # return local_best to continue the recursion
        return local_best

    helper(root)
    best = best_global.pop()
    return best

I was confident about this code, as it's pretty intuitive. However, it contains a serious error. Can you spot it?

Here is a tree where it breaks down.

What's the best path sum we can do here? Well there's [5,4,1] for a total of 10, and there's [5,4,2] for a total of 11. However the code above will return 12. Why?
The mistake is in the recursion step, viz in the return value of the helper function. At node 4, local_best is 7, which is the value of bridge, corresponding to the path [1,4,2]. Hence, at node 5 the helper function will happily return 5 + 7 = 12. But this would correspond to the "path" [5,4,1,2], which is not allowed!

Thankfully the fix is simple.

def max_path(root: Node) -> int:
    best_global = [float('-inf')]

    def helper(node: Node) -> int:
        if not node:
            return 0

        stand = node.val
        go_left = stand + helper(node.left)
        go_right = stand + helper(node.right)
        bridge = go_left + go_right - stand

        # for recursion to be correct it should
        # exclude bridge from the returned max value
        recursion_best = max(stand, go_left, go_right)
        local_best = max(recursion_best, bridge)
        best = best_global.pop()
        best = max(best, local_best)
        best_global.append(best)

        # return recursion_best to continue the recursion
        return recursion_best

    helper(root)
    best = best_global.pop()
    return best

So, in a nutshell, the latter is the solution to the "max_path" problem, while the former is the solution to the "max_subtree" problem.

All right, back to the grind.