Generic Adjacency List Graph implementation

Question

I am trying to come up with a decent Adjacency List graph implementation so I can start tooling around with all kinds of graph problems and algorithms like traveling salesman and other problems... But I can't seem to come up with a decent implementation. This is probably because I am trying to dust the cobwebs off my data structures class.

But what I have so far... and this is implemented in Java... is basically an edgeNode class that has a generic type and a weight-in the event the graph is indeed weighted.

public class edgeNode<E> {
    private E y;
    private int weight;

    //... getters and setters as well as constructors...
}

I have a graph class that has a list of edges a value for the number of Vertices and and an int value for edges as well as a boolean value for whether or not it is directed. The brings up my first question, if the graph is indeed directed, shouldn't I have a value in my edgeNode class? Or would I just need to add another vertices to my LinkedList? That would imply that a directed graph is 2X as big as an undirected graph wouldn't it?

public class graph {
    private List<edgeNode<?>> edges;    
    private int nVertices;
    private int nEdges;
    private boolean directed;

    //... getters and setters as well as constructors...
}

Finally does anybody have a standard way of initializing there graph? I was thinking of reading in a pipe-delimited file but that is so 1997.

public graph GenereateGraph(boolean directed, String file){
        List<edgeNode<?>> edges;
        graph g;
        try{
            int count = 0;
            String line;
            FileReader input = new FileReader("C:\\Users\\derekww\\Documents\\JavaEE Projects\\graphFile");
            BufferedReader bufRead = new BufferedReader(input);
            line = bufRead.readLine();
            count++;
            edges = new ArrayList<edgeNode<?>>();
            while(line != null){
                line = bufRead.readLine();
                Object edgeInfo = line.split("|")[0];
                int weight = Integer.parseInt(line.split("|")[1]);
                edgeNode<String> e = new edgeNode<String>((String)
                edges.add(e);
            }           
            return g;
        }
        catch(Exception e){
            return null;
        }
    }

I guess when I am adding edges if boolean is true I would be adding a second edge. So far, this all depends on the file I write. So if I wrote a file with the following Vertices and weights...

Buffalo | 18  br Pittsburgh | 20 br New York | 15 br D.C | 45 br

I would obviously load them into my list of edges, but how can I represent one vertices connected to the other... so on... I would need the opposite vertices? Say I was representing Highways connected to each city weighted and un-directed (each edge is bi-directional with weights in some fictional distance unit)... Would my implementation be the best way to do that?

I found this tutorial online Graph Tutorial that has a connector object. This appears to me be a collection of vertices pointing to each other. So you would have A and B each with there weights and so on, and you would add this to a list and this list of connectors to your graph... That strikes me as somewhat cumbersome and a little dismissive of the adjacency list concept? Am I wrong and that is a novel solution?

This is all inspired by steve skiena's Algorithm Design Manual. Which I have to say is pretty good so far. Thanks for any help you can provide.

msdn.microsoft.com/en-us/library/aa289152(v=vs.71).aspx should get you going. — Steven Evers
– Steven Evers, Commented Sep 26, 2012 at 15:37

gnat · Accepted Answer · 2012-10-26 15:43:40Z

Here's an implementation that I dug up from when I was dealing with graphs. Although it's in C#, with a few minor adjustments it could compile in Java.

To make it directed you would have to copy v.Adjacents.Add(new Edge(w, cost)); and reverse the direction, thereby taking up double the space.

I don't think it's any better than what you have though.

class Edge
{
    public Vertex Destination { get; set; }
    public double Cost { get; set; }

    public Edge(Vertex destination, double cost)
    {
        Destination = destination;
        Cost = cost;
    }

}

class Vertex
{
    public string Name { get; set; }
    public List<Edge> Adjacents { get; set; }
    public double Distance { get; set; }

    public Vertex(string name)
    {
        Name = name;
        Adjacents = new List<Edge>();
        Distance = double.MaxValue;
    }
}

class Graf
{
    private readonly Dictionary<string, Vertex> vertexmap = new Dictionary<string, Vertex>();

    public void AddEdge(string source, string dest, double cost)
    {
        var v = GetVertex(source);
        var w = GetVertex(dest);
        v.Adjacents.Add(new Edge(w, cost));
    }

    private Vertex GetVertex(string vertexname)
    {
        Vertex v;
        vertexmap.TryGetValue(vertexname, out v);
        if (v == null)
        {
            v = new Vertex(vertexname);
            vertexmap.Add(vertexname, v);
        }
        return v;
    }
}

SoftwareSavant · Accepted Answer · 2012-09-26 13:44:11Z

Here is something I dug up. If anyone has a better implementation I will mark his remark as the answer...

public interface AdjList {
    int beg();
    int nxt();
    boolean end();
}

public class Edge {
    int v, w;
    //E value;
    Edge(int v, int w){
        this.v = v; 
        this.w=w;
    }
}

public class GraphAdjList implements IGraph{
    private int vertCount, EdgeCount;

    private boolean directedGrph;

    private class Node{
        int v; Node next;
        Node(int x, Node t){
            v = x; 
            next = t;
        }       
    }
    private class AdjListPrvtImpl implements AdjList{
        private int vertex;
        private Node node;

        AdjListPrvtImpl(int v){
            this.vertex = v;
            node = null;
        }

        @Override
        public int beg() {
            // TODO Auto-generated method stub
            node = adj[vertex];

            return node == null ? -1 : node.v;
        }

        @Override
        public int nxt() {
            //
            if (node != null) node = node.next; 
            return node == null ? -1 : node.v;
        }

        @Override
        public boolean end() {
            // TODO Auto-generated method stub
            return node == null;
        }       
    }

    private Node[] adj;

    GraphAdjList(int V, boolean flag){
        vertCount = V;
        directedGrph = flag;
    }

    public int getVertCount() {
        return vertCount;
    }

    public int getEdgeCount() {
        return EdgeCount;
    }

    public boolean isDirectedGrph() {
        return directedGrph;
    }

    public AdjList getAdjList(int vertices){
        return new AdjListPrvtImpl(vertices);
    }

    @Override
    public void Graph(int vertCnt, boolean dir) {
        // TODO Auto-generated method stub
        vertCount = vertCnt;
        directedGrph = dir;
    }

    @Override
    public int V() {
        // TODO Auto-generated method stub
        return vertCount;
    }

    @Override
    public int E() {
        // TODO Auto-generated method stub
        return EdgeCount;
    }

    @Override
    public boolean directed() {
        // TODO Auto-generated method stub
        return directedGrph;
    }

    @Override
    public int insert(Edge e) {
        // TODO Auto-generated method stub
        return 0;
    }

    @Override
    public void remove(Edge e) {
        // TODO Auto-generated method stub

    }
    }

Most of the stuff with edges has to deal with Adjacency Matrix operations. So I left it unimplemented.

Stack Exchange Network

Generic Adjacency List Graph implementation

2 Answers 2

Hot Network Questions

Generic Adjacency List Graph implementation

2 Answers 2

Related

Hot Network Questions