2

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.

Improve this question
1

2 Answers 2

Reset to default
1

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; } }
Improve this answer
0

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.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.