Expand|Select|Wrap|Line Numbers

- class Graph {
- protected int numvertices;
- protected int numedges;
- protected boolean directed;
- protected EdgeList adjlist [];
- // Constructors
- public Graph() {};
- //Below constructor you specify the number of edges,
- //it assumes that the graph is undirected
- public Graph(int n) {
- numvertices = n;
- directed=false;
- adjlist = new EdgeList [n];
- }
- //Below constructor you specify the number of edges and whether it is directed or not
- public Graph(int n, boolean isdirected) {
- numvertices = n;
- directed=isdirected;
- adjlist = new EdgeList [n];
- }
- //SimpleInp class is a short version of BufferedReader
- public void read(SimpleInp d) throws IOException {
- String line, first, second;
- int x, y, split;
- while (true) {
- // get next line of input -- containts two ints split by a " "
- line = d.readLine();
- if (line == null) {break; } // Exit here
- // find where the split is
- split = line.indexOf(" ");
- // extract out the numbers and convert to integer
- first = line.substring(0,split);
- second= line.substring(split+1);
- x = Integer.parseInt(first);
- y = Integer.parseInt(second);
- addEdge(x,y); //It then adds that edge
- }
- }
- //Checks whether the gives edges are adjacent
- public boolean isedge(int x, int y) {
- EdgeList curr;
- curr = adjlist[x];
- while (curr != null) {
- if (curr.y == y) return true;
- curr = curr.next;
- }
- return false;
- }
- //Adds an edge to the graph
- public void addEdge(int x, int y) {
- EdgeList curr = new EdgeList(x,y);
- curr.next = adjlist[x];
- adjlist[x] = curr;
- if (!directed)
- {
- curr = new EdgeList(y, x);
- curr.next = adjlist[y];
- adjlist[y] = curr;
- }
- }
- //Removes a certain edge between x and y
- private void cutEdge(int x, int y) {
- EdgeList prev, curr;
- prev = null;
- curr = adjlist[x];
- while (curr != null) {
- if (curr.y == y) {
- if (curr == adjlist [x] ) {
- adjlist[x] = curr.next;
- } else {
- prev.next = curr.next;
- }
- break;
- }
- prev = curr;
- curr = curr.next;
- }
- }
- //Deletes an edge from a given graph
- public void deleteEdge (int x, int y) {
- cutEdge(x,y);
- if (!directed) {cutEdge(y,x);};
- }
- public int getNumVertices() { return numvertices; }
- public int getNumEdges()
- { return numedges; }
- /*
- public int getMaxDegVertex(int v) {
- }
- */
- private void show_edges(int v) {
- for (EdgeList i:adjlist){
- if(i.x == v)
- System.out.println(i.y);
- }
- }
- public void print() {
- System.out.println("Graph has "+numvertices+" vertices");
- System.out.println("Graph is " + (directed ? "directed" : "not directed"));
- for (int i=0; i<numvertices; i++) { show_edges(i); }
- }
- }

The above were written by Mr S. Hazelhurst