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.
<code>public class edgeNode<E> {
private E y;
private int weight;
//... getters and setters as well as constructors...
}
</code>
<code>public class edgeNode<E> {
private E y;
private int weight;
//... getters and setters as well as constructors...
}
</code>
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?
<code>public class graph {
private List<edgeNode<?>> edges;
private int nVertices;
private int nEdges;
private boolean directed;
//... getters and setters as well as constructors...
}
</code>
<code>public class graph {
private List<edgeNode<?>> edges;
private int nVertices;
private int nEdges;
private boolean directed;
//... getters and setters as well as constructors...
}
</code>
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.
<code>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;
}
}
</code>
<code>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;
}
}
</code>
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…
<code>Buffalo | 18 br Pittsburgh | 20 br New York | 15 br D.C | 45 br
</code>
<code>Buffalo | 18 br Pittsburgh | 20 br New York | 15 br D.C | 45 br
</code>
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.
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.
<code>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;
}
}
</code>
<code>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;
}
}
</code>
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;
}
}
Here is something I dug up. If anyone has a better implementation I will mark his remark as the answer…
<code>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
}
}
</code>
<code>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
}
}
</code>
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.