This post defines API for fundamental graph operations for developing graph processing algorithms. The following is an API:
Graph(int V) creates a V-vertex graph with no-edge
Graph(String filePath) creates a graph from specified file
int V() number of vertices
int E() number of edges
void addEdge(int v, int w) add edge v-w to this graph
List<Integer> adjacentVertices(int v) vertices adjacent to vertex v
String toString() string representation
API for an undirected graph
This API contains two constructors, methods to return the number of vertices and edges, a method to add an edge, a method to get adjacent vertices and method to print Graph.
Let me present the implementation part of it.It is written in JAVA. The above API is taken from Chapter:4 Graphs, Algorithms, 4th Ed. I have implemented the above API as presented below. Feel free to use it for practicing some of the fundamental graph algorithms like BFS, DFS, Shortest path etc...
Graph.java
DemoGraph.java
====Output====
13 verticies, 13 edges
0: 5 1 2 6
1: 0
2: 0
3: 4 5
4: 3 6 5
5: 0 4 3
6: 4 0
7: 8
8: 7
9: 12 10 11
10: 9
11: 12 9
12: 9 11
Sample Input File: (tinyG.txt)
13
13
0 5
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3
This implementation of graph considered vertex-id to be only integers. It has used adjacency list as the graph representation. Feel free to let me know any bugs in the code.
public class Graph
Graph(int V) creates a V-vertex graph with no-edge
Graph(String filePath) creates a graph from specified file
int V() number of vertices
int E() number of edges
void addEdge(int v, int w) add edge v-w to this graph
List<Integer> adjacentVertices(int v) vertices adjacent to vertex v
String toString() string representation
API for an undirected graph
This API contains two constructors, methods to return the number of vertices and edges, a method to add an edge, a method to get adjacent vertices and method to print Graph.
Let me present the implementation part of it.It is written in JAVA. The above API is taken from Chapter:4 Graphs, Algorithms, 4th Ed. I have implemented the above API as presented below. Feel free to use it for practicing some of the fundamental graph algorithms like BFS, DFS, Shortest path etc...
Graph.java
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
public class Graph {
List<Integer>[] adjList;
/** This constructor build the graph of v vertices of no edges*/
public Graph(int v) {
createGraph(v);
}
/**
* Constructs the graph from a given file. The first two lines give the number of vertices and edges in the graph, respectively. From third line, edges are specified, as shown in example below.
1. Every line in the file should start with an integer. I, mean no space or empty chars at the start of each line.
2. <EOF> should be on the line of last edges specified in the file.
*/
public Graph(String filePath) {
BufferedReader reader;
try {
reader = new BufferedReader(new FileReader(new File(filePath)));
int v = Integer.valueOf(reader.readLine());
createGraph(v);
int e = Integer.valueOf(reader.readLine());
String line = reader.readLine();
while (line != null) {
int[] vertices = getVerticesForEdge(line);
addEdge(vertices[0], vertices[1]);
line = reader.readLine();
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
/** Retrieves the vertices from a given string. */
private int[] getVerticesForEdge(String line) {
int[] vertices = new int[2];
vertices[0] = Integer.valueOf(line.split(" ")[0]);
vertices[1] = Integer.valueOf(line.split(" ")[1]);
return vertices;
}
/** Creates a graph with v vertices without any edges.*/
private void createGraph(int v) {
adjList = (ArrayList<Integer>[]) new ArrayList[v];
for (int i = 0; i < v; i++)
adjList[i] = new ArrayList<Integer>();
}
/** Retievs the adjacent vertices for a given vertex.*/
public List<Integer> adjacentVertices(int v) {
return adjList[v];
}
/** Adds an edge: v-w to the current graph.*/
public void addEdge(int v, int w) {
adjList[v].add(w);
adjList[w].add(v);
}
/** Retrieves the number of vertices in this graph.*/
public int V() {
return adjList.length;
}
/** Retrieves the number of vertices in this graph.*/
public int E() {
int edges = 0;
for (int i = 0; i < adjList.length; i++)
edges += adjList[i].size();
return edges / 2;
}
/** Return the string version of the graph.*/
public String toString() {
int vertices = V();
int edges = E();
String s = vertices + " vertices, " + edges + " edges\n";
for (int v = 0; v < vertices; v++) {
s += v + ": ";
for (int w : this.adjacentVertices(v)) {
s += w + " ";
}
s += "\n";
}
return s;
}
}
DemoGraph.java
public class DemoGraph {
public static void main(String[] args) {
Graph g = new Graph("<File Specifying the graph>");
System.out.println(g.toString());
}
}
====Output====
13 verticies, 13 edges
0: 5 1 2 6
1: 0
2: 0
3: 4 5
4: 3 6 5
5: 0 4 3
6: 4 0
7: 8
8: 7
9: 12 10 11
10: 9
11: 12 9
12: 9 11
Sample Input File: (tinyG.txt)
13
13
0 5
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3
This implementation of graph considered vertex-id to be only integers. It has used adjacency list as the graph representation. Feel free to let me know any bugs in the code.
No comments:
Post a Comment