Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
msdn.microsoft.com/en-us/library/aa289152(v=vs.71).aspx should get you going. –  Steve Evers Sep 26 '12 at 15:37
add comment

2 Answers 2

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;
    }
} 
share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.