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.