Tuesday, April 12, 2011

A Gentle Introduction to Graph Theory

I thought it'd be nice to write about graph theory, because I love it so much. Here's a very gentle introduction to the concepts behind it.

What's Graph Theory?
Graph Theory is a powerful tool in computer science. It has nothing to do with "graphs" as the word is commonly used, but is rather a simple way of representing your data to allow you do a number of useful calculations.

The building blocks of Graph Theory are the vertex (also called a node) and the edge. Vertices (plural of vertex) tend to represent objects and edges typically represent the relationships between them.

Here is a sample (contrived) graph where the vertices are cities, and the edges are whether the city has an express flight between them.

As you can see, there is an express flight between Boston and New York and one between Atlanta and Miami, but there is not one between Boston and Atlanta. 

One often-seen configuration of graphs have weighted edges. This means that each edge connecting two vertices has some value attached to it. Here's the express flight graph again, but this time each edge has the price of the express flight it represents attached to it as its weight.


This begins to suggest some of the usefulness of graphs; if this were a more accurate graph, you might use it to plot the cheapest way to move between two cities via express flights. 

The two graphs we looked at so far have all had edges that were bidirectional. That is to say, the $49 edge between Chicago and New York meant that you could, for $49, fly from either Chicago to New York or from New York to Chicago. Of course, the world doesn't always work this way, and that's why we have directed graphs. 

In a Directed Graph, the edges have a direction to them -- that is, instead of merely going between two vertices, they go from one vertex to another. Following is an example of a family tree, which is a kind of directed graph. In this case, an edge from one vertex to another vertex represents that the first vertex is a parent of the second. 

Here you can see that George and Lucille Bluth are both parents to Michael Bluth, who is in turn a parent to George Michael Bluth.

Note that the lines representing the edges sometimes cross over each other -- that doesn't mean anything to the graph. Those intersections don't represent any actual connection and are just an inconvenience of trying to draw a graph on a 2-dimensional space. 

While graph theory is simple in the small scale, they are important enough to have filled a library's worth of books on the topic. A large number of famous and important algorithms are within the realm of graph theory, and it's a powerful tool in any developer's arsenal.

I'll dive into further details (both more theory as well as implementation options) in future posts; please post any requests in the comments.



Further Reading

  • Here! I intend to write more articles covering the basics of graph theory as well as interesting problems in it.
  • Wikipedia's article on the topic gives a good high-level overview of the history, meaning, and current state of Graph theory.
  • Introduction to Algorithms, Third Edition is a classic book covering all algorithms, but spends over 150 pages covering many of the most important graph theory algorithms.
  • Introduction to Graph Theory (2nd Edition) is a wonderful graph theory text, but I'd recommend it only for those who have a sturdy footing in discrete math. The definitions, explanations and proofs are extremely rigorous and thorough, (though this sometimes comes at the expense of clarity).

Monday, March 28, 2011

A Lightweight (pseudo)Random Directed Graph Generator

I recently needed to generate some random graphs for a project I'm working on at school. I wrote a quick java program that takes the number of vertices and the average outdegree as inputs, and outputs the graph as a CSV file representing each of the edges.

It is run as follows:

java RandomGraphGenerator NUMBER_OF_VERTICES AVERAGE_OUTDEGREE

When called like this, it assumes a graph with vertices numbered from 0 to (NUMBER_OF_VERTICES - 1). It then generates floor((NUMBER_OF_VERTICES * AVERAGE_OUTDEGREE)) random edges, by randomly selecting a source vertex, then a target vertex, and repeating that process if that given edge already exists in the graph.


Here's the source: RandomGraphGenerator.java
Please feel free to use this in any way you see fit.

An Introduction to Java Interfaces: What's an interface?

There are a lot of good resources on the net that explain what an interface is, but there really aren't so many resources in terms of why one would ever bother using one.

What is a java interface?

An interface is a definition of a type that describes the public methods that a given type will implement. Like the name suggests, it makes promises about the way other classes may interact with this type.

Here's an example:

public interface Pet {
     public String getName();
     public void play();
     public void speak();
}

You'll note that, unlike a standard function declaration in a class, there are no implementations for any of these functions. This is by necessity! Interfaces may not provide the implementation of the functions they define.

How does a class use an interface?
A class implements an interface by saying so! Let's say we have a Dog class that we think should adhere to the Pet interface. We would define it like so:

public class Dog implements Pet {
      //bla bla bla
}
Seems simple enough, but there's one twist: you need to actually define all of the functions that the interface describes. If you tried compiling the above code without doing so, you'd see an error message that looks like this:

Dog.java:1: Dog is not abstract and does not override abstract method speak() in Pet
public class Dog implements Pet {
^
1 error
You would fix this by actually implementing those methods! Here's an example:



public class Dog implements Pet {

private final String name;
private Ball favoriteBall;

     public Dog(String name, Ball favoriteBall) {
            this.name = name;
            this.favoriteBall = favoriteBall;
     }

     private void fetchBall(Ball thrownBall) {
           //some implementation details
     }

     private void bark() {
           //some implementation details
     }

     public String getName() {
          return name;
     }

     public void speak() {
           for(int i = 0; i < 5; i++) {
                 bark();
           }
     }

     public void play() {
          fetchBall(favoriteBall);
     }

}


Note that the 3 interface functions are implemented, and match the interfaces declaration in name, return type, AND parameters. This is all necessary.

Now let's say we want to implement a Cat class too! Easy enough to do:

public class Cat implements Pet {

private final String name;


     public Cat(String name) {
           this.name = name;
     }

     private void stareAtYou() {
           //some implementation details
     }

     private void meow() {
           //some implementation details
     }

     public String getName() {
           return name;
     }

     public void speak() {
           meow();
     }

     public void play() {
           stareAtYou();
     }

}


Ok, so now you have a Cat and Dog class that both implement the pet interface. So what does that do for you?
You can now refer to either of those animals by a Pet object. Observe:

Pet yourPet = new Cat("Fluffy");


You now can access Fluffy the Cat object, but only via a Pet interface. So, you could call any of the functions on yourPet that are defined in the Pet interface, but NOT the functions that exist only in Cat.


yourPet.speak(); //legal
yourPet.play(); //legal
yourPet.meow(); //illegal, both because that function is private but also because it is not a member of the Pet interface.

//All of the following is valid

Pet[] thePets = new Pet[3]();
thePets[0] = new Cat("Fluffy");
thePets[1] = new Dog("Spraynard", new Ball());
thePets[2] = new Cat("Uncle Stupid");

for(int i = 0; i < 3; i++) {
     thePets[i].play(); //This is going to call play() on each of the Pet objects

                        //For the Dog, it means he's going to do fetchBall(),
                        //Whereas the Cats are just going to stareAtYou()
}


Why would I bother using an interface?
There are a lot of good reasons to use interfaces.

  • It separates the interface to a class from its implementation, which can be very helpful in keeping the separation between classes clean, and also makes it very easy to switch classes in and out. Imagine you are building a system that is going to need to save large strings of text. For now, you're just going to save the data in files on your local computer, but you may someday need to upgrade to a centralized database or some other storage system. In the interest of keeping things easy to swap, you define an interface for your storage solution. It might look like this:

    public interface StorageSolution {
          public String getData(long dataId);
          public void putData(long dataId, String data);
    }

    Now you can implement your File-based storage to implement that interface:

    public class FileStorageSolution implements StorageSolution{

         public String getData(long dataId) {
         //The code to retrieve the data from a file
         }

         public String putData(long dataId, String data) {
               //the code to put the data in a file
         }

    }

    You will then want to make sure that you only reference the specific implementation class through the interface, like here:

    StorageSolution ourDataStorage = new FileStorageSolution();
    String file1234 = ourDataStorage.getData((long)1234);

    Now, later on down the road, when you want to switch from storing files on disk to storing on a database, you just need to make a new DatabaseStorageSolution that implements StorageSolution, and you can replace FileStorageSolution with DatabaseStorageSolution with a minimum of effort, because you access the class only through interface. You would go from the above tidbit to:

    StorageSolution ourDataStorage = new DatabaseStorageSolution(); //Later on, this is the only part you'd need to change
    String file1234 = ourDataStorage.getData((long)1234);
  • Interfaces allow you to use a class you created with a class that's never heard of it specifically.
    For example, imagine you have a ToyStore system, and you have different objects for all kinds of different toys. Imagine you have new kinds of toys being developed all the time. Also imagine you have a ShoppingCart class that is supposed to help you check customers out. Imagine that you require that all objects made to represent toys implement the Toy interface:


    public interface Toy {
         public double getPrice();
         public String getName();
    }


    By doing so, we can guarantee that ShoppingCart can handle all new Toy objects that get created without having to update it! It might look a little like this:


    public class ShoppingCart{
    Toy[] allTheToys = new Toy[50];
    int numberOfToys = 0;

         public void addAToy(Toy newToy) {
               allTheToys[numberOfToys]=newToy;
               numberOfToys++;
         }

         public String makeAReceipt() {
               String receiptString = "Items purchased:\n";
               for(int i = 0; i < numberOfToys; i++) {
                     receiptString = receiptString + allTheToys[i].getName() + " " + allTheToys[i].getPrice() + "\n";
               }
               return receiptString;
         }

    }


    Now the ShoppingCart class can work with any new toy object you make as long as it implements the Toy interface.

Welcome

Welcome to my new blog.

I'm a Software Engineer in Boston, currently finishing up my Master's Degree at a local university. I thought it would be nice to capture my thoughts, learnings, ideas, and recommendations as I encounter them in work and school. I guess we'll all see whether that was correct or not.

I imagine that this will involve interesting things I encounter at work and in my studies, essayed-up versions of answers to programming queries encountered on stack overflow and reddit, as well as reviews of books and other resources.