Need some advice for my graph implementation with java

Question

I want to implement some graph algorithms that's why I am creating a kind of graph framework. Up to now I implemented directed graphs very easily with the following classes;

class Vertex {
    String id;
    String name;
}


class Edge {
    String id;
    Vertex source;
    Vertex destination;
    int weight;
}

class Graph {
     List<Vertex> vertexes;
     List<Edge> edges; }

When testing it I create:

Edge edge = new Edge(id, source_node, destination_node, weight)

This is perfectly fine in directed graphs. However in undirected graphs; I have to write like this; Let's say we have 2 nodes which are A, B and the weight between them is say 10. So because of the structure of undirected graphs I have to put two edges;

Edge e1 = new Edge(id1, A, B, 10)
Edge e2 = new Edge(id2, B, A, 10)

This type of edge creation is both inefficient and exhaustive.

Therefore how can I modify my code so that I don't have to put two edges between two nodes for undirected graphs. What is best way to integrate undirected graph type to my code as well?

Thanks for your time.

Answer 1

There is an interesting Java API I recently came across called Blueprints by Tinkerpop that you can use, or look at to get some ideas of how to implement your own graph framework.

I'm developing a graph framework that utilizes JSON. This is due to the mutable nature of graphs. Algorithms in graph theory tend to add data to a graph that other algorithms use. Ergo, attempting to describe a graph concretely is inherently flawed.

Answer 2

The natural solution is to make the direction of the edge be an attribute. Create an enum:

public enum EdgeType {
     Undirected,
     From1to2,
     From2to1,
     Cyclic
}

Then add an attribute to your Edge class:

public EdgeType enumEdgeType;

When doing traversals and other operations you can use a switch statement to handle the 4 different cases. My experience has been that this approach is the simplest and most efficient.

Answer 3

I'm going to disagree with the existing answers...

Usually, when representing graphs in code, you don't want to store your edges as one big list, or even as objects at all, for efficiency reasons. You will usually want to use an adjacency matrix (for relatively dense graphs) or adjacency lists (for relatively sparse graphs). This allows you to look up neighbors of vertices easily, which is mostly what you use in graph algorithms. Hence often in implementation all you need are an indexed array or set or list of Vertex objects.

In an undirected graph, you would add the edge (i,j) as well as (j,i) to the data structure. In a directed graph, you would just add one of them.

Answer 4

Depending on the graph algorithm you want to implement you will need different graph representation, so you will have to be able to use several of these. Most of the algorithms use neighbourhood lists, while in your code you use an edge list.

You really should not worry about the edge creation. Most of the time it will be negligible with comparison with the actual algorithm. Now depending on what you try to do it might be the case you only need only one of the edges, but most of the time, having both edges is perfectly fine and sane.

Answer 5

I will have to disagree with the answer concerning blueprint. There is a lot hype around this library and except the nice feature of graph implementation abstraction, there is absolutely nothing implemented in the graph algorithm (furnace) package, rendering the complicated stack totally useless.

When I mean nothing is implemented, that is really nothing (take a look here), and the repo hasn't been updated since a while, so you can consider it dead. If you want to use a

My 2 cents, use a seasoned graph framework : Jgrapht. I use it for several research projects, there are 20 standards (and some non trivials) graph algorithms implemented. So you don't need to reinvent the wheel. It also supports a heavy load of graph types.

Avoid hype, go for working solutions.