I'm implementing some algorithms to teach myself about graphs and how to work with them. What would you recommend is the best way to do that in Java? I was thinking something like this:
public class Vertex {
private ArrayList<Vertex> outnodes; //Adjacency list. if I wanted to support edge weight, this would be a hash map.
//methods to manipulate outnodes
}
public class Graph {
private ArrayList<Vertex> nodes;
//algorithms on graphs
}
But I basically just made this up. Is there a better way?
Also, I want it to be able to support variations on vanilla graphs like digraphs, weighted edges, multigraphs, etc.
A simple representation written by 'Robert Sedgwick' and 'Kevin Wayne' is available at http://algs4.cs.princeton.edu/41graph/Graph.java.html
Explanation copied from the above page.
The Graph class represents an undirected graph of vertices named 0 through V - 1.
It supports the following two primary operations: add an edge to the graph, iterate over all of the vertices adjacent to a vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted. By convention, a self-loop v-v appears in the adjacency list of v twice and contributes two to the degree of v.
This implementation uses an adjacency-lists representation, which is a vertex-indexed array of Bag objects. All operations take constant time (in the worst case) except iterating over the vertices adjacent to a given vertex, which takes time proportional to the number of such vertices.
Even at the time of this question, over 3 years ago, Sage (which is completely free) existed and was pretty good at graph theory. But, in 2012 it is about the best graph theory tool there is. Thus, Sage already has a huge amount of graph theory material built in, including other free and open source stuff that is out there. So, simply messing around with various things to learn more is easy as no programming is required.
And, if you are interested in the programming part as well, first Sage is open source so you can see any code that already exists. And, second, you can re-program any function you want if you really want to practice, or you can be the first to program something that does not already exist. In the latter case, you can even submit that new functionality and make Sage better for all other users.
At this time, this answer may not be that useful to the OP (since it has been 3 years), but hopefully it is useful to any one else who sees this question in the future.
When learning algorithms, the programming language (Java) should not be considered in deciding the representation. Each problem could benefit from a unique representation, and moreover designing it can add a bit of learning. Solve the problem first without relying on a particular language, then the representation for any particular language will flow naturally.
Of course, general representations and libraries are useful in real-world applications. But some of them could benefit from some customization as well. Use the other answers to know the different techniques available, but consider customization when appropriate.
Adjacency List implementation of Graph is appropriate for solving most of the graph related problems.
Java implementation of the same is here on my blog.
class Graph<E> {
private List<Vertex<E>> vertices;
private static class Vertex<E> {
E elem;
List<Vertex<E>> neighbors;
}
}
Take a look at the http://jung.sourceforge.net/doc/index.html graph library. You can still practice implementing your own algorithms (maybe breadth-first or depth-first search to start), but you don't need to worry about creating the graph structure.
Time ago I had the same problem and did my own implementation. What I suggest you is to implement another class: Edge. Then, a Vertex will have a List of Edge.
public class Edge {
private Node a, b;
private directionEnum direction; // AB, BA or both
private int weight;
...
}
It worked for me. But maybe is so simple. There is this library that maybe can help you if you look into its code: http://jgrapht.sourceforge.net/
Why not keep things simple and use an adjacency matrix or an adjacency list?
I'd recommend graphviz highly when you get to the point where you want to render your graphs.
And its companions: take a look at Laszlo Szathmary's GraphViz class, along with notugly.xls.
Each node is named uniquely and knows who it is connected to. The List of connections allows for a Node to be connected to an arbitrary number of other nodes.
public class Node {
public String name;
public List<Edge> connections;
}
Each connection is directed, has a start and an end, and is weighted.
public class Edge {
public Node start;
public Node end;
public double weight;
}
A graph is just your collection of nodes. Instead of List<Node> consider Map<String, Node> for fast lookup by name.
public class Graph {
List<Node> nodes;
}
class Vertex {
private String name;
private int score; // for path algos
private boolean visited; // for path algos
List<Edge> connections;
}
class Edge {
private String vertex1Name; // same as Vertex.name
private String vertex2Name;
private int length;
}
class Graph {
private List<Edge> edges;
}
If you need weighted edges and multigraphs, you might want to add another class Edge.
I would also recommend using generics to allow specifying which sub-class of Vertex and Edge are currently used. For example:
public class Graph<V extends Vertex> {
List<V> vertices;
...
}
When it comes to implementing graph algorithms, you could also define interfaces for your graph classes on which the algorithms can operate, so that you can play around with different implementations of the actual graph representation. For example, simple graphs that are well-connected might be better implemented by an adjacency matrix, sparser graphs might be represented by adjacency lists - it all depends...
BTW Building such structures efficiently can be quite challenging, so maybe you could give us some more details on what kind of job you would want to use them for? For more complex tasks I would suggest you have a look at the various Java graph libraries, to get some inspiration.
Source: Stackoverflow.com