Intro to Graphs

 You may have heard of a “graph” as a pie chart (a budget?), a line graph (change of something over time?), a histogram (into which buckets do values fall?), or another type. In computer science and related fields of math (this time, not statistics), a “graph” doesn’t mean those tools for representing data, but instead means, roughly, “a set of dots connected by lines.”

A “dot” is called a node or a vertex, and a “line” is called an “edge.” The following is a very simple graph, with 3 nodes and 3 edges.


And this is another graph with 5 nodes and 10 edges.

These are both “connected” graphs, because they don’t have any parts floating around in empty space, without any edges connecting the stray vertices to the rest. More formally, there is only one “component” in each of these graphs, a region of the graph connected by vertices and edges.

So much of computer science revolves around abstract objects like these graphs, so let’s look at a few special graphs.

K-graphs are called “complete” and identified by their number of vertices. You’ve already seen K5 and K3. Complete graphs have some number of vertices, and every possible edge between them. The binomial coefficient, using as inputs n and 2, gives the number of possible pairs of nodes to be connected by edges, which is the number of edges in a K.

Cycles are graphs that form a closed loop. Like K-graphs, C-graphs (be careful: complete is K, and cycle is C) are identified by the number of vertices they have, which is also the number of edges. Think about what C7, or C32678 would look like.

So far, all the graphs we’ve seen have been undirected—that is, there is no restriction on which way you move through a graph like there would be in a road network with some one-way streets, allowing movement only in that direction.

Every graph so far—every K and every C—has, deliberately or not, been cyclic. That is, each one had contained a cycle. Take a minute to draw out, on a whiteboard or on paper, a graph that does not have any cycles.

There is another category of graph called a bipartite graph. These graphs (from “bipartite” = “two parts”) are defined with two numbers, not just one. There is some group of vertices on the left, and another group on the right. A complete bipartite graph, known as K(L,R), connects all the left vertices with all the right ones, but has no left-left or right-right connections. The classic example, K(3,3) is often framed as the following:

• Alice has a house
• She needs water
• She needs heat
• She needs electricity
• Bob has a house
• He needs water
• He needs gas
• He needs electricity
• Charlie has a house
• He needs water
• He needs gas
• He needs electricity

Alice, Bob, and Charlie all need to connect to the water supply, get natural gas, and hook up to the meter. But Alice won’t take Charlie’s gas, just like Bob won’t take Alice’s water, and so on.

 

K(3,3) looks like this:

 

People sometimes call a graph where there’s one central node and all other nodes connect to it, and only to it, a “star(fish)” graph.

In many problems, the “degree” of a vertex, and, in directed graphs, this usually split by direction, in versus out. The “degree” of a vertex is the number of edges that come in, go out, or both (depending on if you want to know “degree,” “in-degree,” or “out-degree).

There are two common problems which we’ll cover in future articles, but I’ll introduce them now, and then, in the future, link to the articles working through a solution:

• Does a graph have an Eulerian cycle (or equivalently, “Is the graph Eulerian?”)—does there exist a cycle through the graph using every edge exactly once
• Does the graph have a Hamiltonian path (or equivalently, “Is the graph Hamiltonian?”)—does there exist a path through the graph that consumes every vertex exactly once?

Try to answer these two questions, but be warned—start with very small graphs, no bigger than any of the ones I’ve given as examples here. For now, suffice it to say in plain English that these problems are known to be “very hard.” In future articles coming up very soon, we’ll put some mathematical rigor into how we can classify problems and solutions.

Finally, let’s single out a particular class of graph: one which has no cycles or directed edges (and thus has exactly one path between any pair of nodes; try to prove this yourself), and exists in only a single component. They are called “trees” (they actually look like trees’ root systems, rather than what you see above ground), and they’re some of the most important graphs in computer science. We will devote many future articles to trees.

Exceptions

 Things go wrong in Java all the time, especially in more complex systems, or when user input is required: data is entered incorrectly, or a file is sent in the wrong format, or you keep looping beyond where there is no more material to consume—the list of potential bugs is endless.

Exception handling is a fundamental concept in Java that allows you to manage errors gracefully and keep your program running even when unexpected issues occur. The basic structure involves three main keywords: try, catch, and finally. The try block contains code that might throw an exception—essentially, code that could go wrong at runtime. For example, if you try to divide a number by zero inside a try block, Java will throw an ArithmeticException. When an exception occurs, the normal flow of the program is interrupted, and control jumps to the catch block, which is designed to handle specific types of exceptions. In the case of dividing by zero, the catch block can print an error message or take corrective action, ensuring the program doesn’t crash abruptly. Perhaps, after the printing of the error message, the user can be invited to try to input a number again, this time trying consciously to avoid whatever the exception was.

Let’s look at a simple try-catch:

public class TryCatchExample {

    public static void main(String[] args) {

        try {

            int result = 10 / 0; // This will throw ArithmeticException

            System.out.println("Result: " + result);

        } catch (ArithmeticException e) {

            System.out.println("Error: Cannot divide by zero!");

        }

        System.out.println("Program continues after the try-catch block.");

    }

}

We enter the try-block, and attempt to assign 10/0 into an integer. Just as in math, in Java, you cannot divide by 0 without causing problems. (I don’t know if Java is actually trying to “divide” by zero somehow, the process is running away, and it’s throwing in the towel, or if Java has simply been written in a way such that “if someone tries to divide by 0, don’t even entertain that—just throw an error ASAP.”) In any case, dividing by zero throws an error, which, if not handled properly (by a catch-block, for example), will crash the program.

The finally block is optional but highly useful. Code inside finally will always execute, regardless of whether an exception was thrown or caught. This makes it ideal for cleanup actions, such as closing files or releasing resources. For instance, even if an exception occurs while reading a file or dividing numbers, the finally block can still close the file or print a message, guaranteeing that essential cleanup steps are performed. 

public class TryCatchFinallyExample {

    public static void main(String[] args) {

        try {

            int result = 10 / 0; // This will throw ArithmeticException

            System.out.println("Result: " + result);

        } catch (ArithmeticException e) {

            System.out.println("Error: Cannot divide by zero!");

        } finally {

            System.out.println("This is the finally block. It always runs.");

        }

        System.out.println("Program continues after the try-catch-finally block.");

    }

}

Consider this simple example: inside the try block, you attempt to divide by zero (exactly like the previous example above); the catch block prints out the exception message (again, exactly the same), and the band-new finally block prints “This is the finally block” regardless of what happened in try or catch.

A few years ago, I went to an Atlanta Java Users Group meeting at which Venkat Subramanian talked about good practices in exception handling. One thing stuck out at that talk more than probably any other talk I’ve ever been to: if you’re going to have something fail with an exception, make sure the failure is as soon, as loud, and as clear as possible. That is, fail early, make it obvious that something failed, and, in the statement that something failed, be as detailed as you can. For example, you could always just use a RuntimeException, passing in no message to handle a problem, like our old friend division by zero. That technically works, but it would be much better if

• The exception was triggered as early as possible, rather than delaying acknowledging the problem, or passing it down endlessly
• You used a more descriptive exception, like an ArithmeticException, or perhaps even your own custom-written CannotDivideByZeroException
• You passed a message into your exception to explain where, how, why, or all three, the code failed

Nesting Classes

We’ve seen this once or twice before already, but I wanted to create an article about it because it’s such an important concept: You can have a class inside a class in Java. Now that we’ve been exposed to this idea, with, let’s say, a Song class inside Playlist, which represents a List<Song>—let’s dive more deeply into it.

When you define a class inside another class in Java, you’re using what’s called a nested class or inner class. This approach is especially useful for grouping related classes together, which can make your code more organized, readable, and maintainable. For example, if you have a Song class inside a Playlist class, it signals that Song is only relevant within the context of Playlist, and it helps encapsulate the logic that belongs together. Inner classes can access the fields and methods of their outer class, including private ones, which allows for tight integration between the two.

There are several types of inner classes in Java. The most common is the non-static inner class, which is tied to an instance of the outer class. To use it, you first create an instance of the outer class, then use it to create an instance of the inner class. There are also static nested classes, which behave like regular classes but are nested for logical grouping; they can only access static members of the outer class and don’t require an instance of the outer class to be instantiated. Additionally, Java supports local inner classes (defined within methods) and anonymous inner classes (used for concise, one-off implementations, often for event handling or callbacks).

Using inner classes not only improves encapsulation but also keeps the code for closely related classes together, making it easier to manage and understand. For instance, in a Playlist class, having a Song inner class makes it clear that Song objects are meant to be managed by Playlist, and it hides the Song implementation from the rest of the application if you make it private or protected. This design strategy is particularly powerful in large projects, where logical grouping and encapsulation are key to maintainability and clarity.

 

Sorting objects with Comparable or Comparator

 Some things—primitives—are really easy to sort. 1 comes before 2 comes before 3; z comes before q comes before c comes before a (if we’re going in reverse); and so on. But not everything we want to sort is so easy. Suppose, for example, we wanted to sort Students. Students have many properties—names, IDs, years, GPAs, majors, and so on. How do we determine who comes first? What criteria matter? Does a senior with a low GPA come before a junior with a high GPA? Does a zoology major early in the alphabet come before or after an African-American Studies major late in the alphabet?  

When it comes to sorting custom objects like Students in Java, you have two main tools at your disposal: the Comparable interface and the Comparator interface. Both serve to tell Java how your objects should be ordered, but they do so in different ways and are suited to different scenarios. If your class has a natural way of being ordered—say, students by their ID number or last name—you can implement the Comparable interface. This means you define a compareTo() method inside your Student class that tells Java how to compare one Student to another.

compareTo() returns one of three numbers—by convention, -1, 0, or 1. If x comes before y however you want to order it, then x.compareTo(y) returns -1; if x comes after y, then the same call returns 1; if they’re equivalent, then it returns 0.

For example, you might decide that students should be sorted alphabetically by last name. Now, whenever you call Collections.sort() on a list of Students, Java will use this method to determine the order. This is great when there is a single, obvious way to sort your objects.

However, if you want to sort Students by GPA one day, by year the next, and by major after that, the Comparator interface is the better choice. A Comparator is a separate object that defines a compare() method, allowing you to specify different sorting strategies without changing your Student class. For instance, to sort by GPA, you can create a Comparator that compares the GPA values of two students.

 Comparable requires you to implement the compareTo() method inside your class, establishing one default sorting behavior. Comparator, on the other hand, lets you define multiple external sorting strategies through separate objects or lambda expressions. By understanding and applying these two interfaces, you can efficiently sort even complex objects like Students in Java, tailoring the sorting logic to fit your specific needs.

Let’s look at both in action. First, Comparable:

import java.util.Arrays;

 

class Student implements Comparable<Student> {

    private String name;

    private int id;

 

    public Student(String name, int id) {

        this.name = name;

        this.id = id;

    }

 

    public String getName() {

        return name;

    }

 

    public int getId() {

        return id;

    }

 

    @Override

    public String toString() {

        return "Student [name=" + name + ", id=" + id + "]";

    }

 

    @Override

    public int compareTo(Student other) {

        if (this.id < other.id) {

            return -1;

        } else if (this.id > other.id) {

            return 1;

        } else {

            return 0;

        }

    }

}

 

public class ComparableExample {

    public static void main(String[] args) {

        Student[] students = {

            new Student("Alice", 103),

            new Student("Bob", 101),

            new Student("Charlie", 105),

            new Student("David", 102)

        };

 

        System.out.println("Students before sorting:");

        for (Student student : students) {

            System.out.println(student);

        }

 

        Arrays.sort(students);

 

        System.out.println("\nStudents after sorting by ID:");

        for (Student student : students) {

            System.out.println(student);

        }

    }

}

The fact that Student implements Comparable means that Students are comparable. Notice how in main(), the ordering by IDs is not the same as the “Alice, Bob, Charlie, David” ordering we’d get by names. The fact that we want to order by ID, not by name, is defined in the compareTo() method, a method that must be implemented if something is Comparable.

compareTo() rearranges the students in order by ID as we want them, based on the results of those comparisons returning -1, 0, or 1.

Now in this other example, a whole new class—a Comparator—is invoked to make the comparison, by way of Comparator’s compare() method. Note that this time, the method is just “compare,” not “compareTo” as with Comparable.

import java.util.Arrays;

import java.util.Comparator;

 

class Student {

    private String name;

    private int id;

 

    public Student(String name, int id) {

        this.name = name;

        this.id = id;

    }

 

    public String getName() {

        return name;

    }

 

    public int getId() {

        return id;

    }

 

    @Override

    public String toString() {

        return "Student [name=" + name + ", id=" + id + "]";

    }

}

 

public class ComparatorExample {

    public static void main(String[] args) {

        Student[] students = {

            new Student("Alice", 103),

            new Student("Bob", 101),

            new Student("Charlie", 105),

            new Student("David", 102)

        };

 

        System.out.println("Students before sorting:");

        for (Student student : students) {

            System.out.println(student);

        }

 

        // Define a Comparator to sort by name

        Comparator<Student> byName = new Comparator<Student>() {

            @Override

            public int compare(Student s1, Student s2) {

                return s1.getName().compareTo(s2.getName());

            }

        };

 

        Arrays.sort(students, byName);

 

        System.out.println("Students after sorting by name:");

        for (Student student : students) {

            System.out.println(student);

        }

    }

}

Here, the comparison strategy changes. Comparing strings is very easy to do with compareTo. (Strings are naturally Comparable.) Feeding two strings into compareTo() as we have done here will put them in A-Z alphabetical order. (As an exercise, think about how you could reverse this to Z-A order.) Therefore, the Comparator, calling Comparable, puts the Students in order by name, as opposed to ID in the previous example.

If you have an array that isn’t easily sorted (as in our case of the array of Students, since Students have more than one property), Java allows you, in Arrays.sort, to pass in a Comparator to tell sort on what criteria to perform the sort.