aiz-lab7.pdf

CustomGraph.java

import java.util.ArrayList;
import java.util.List;

public class CustomGraph extends LGraph {

	@Override
	public void writeList() {
		for (int i = 0; i < this.iloscWierzcholkow; i++) {
			System.out.print(i + "=>" + this.listaSasiedztwa.get(i) + "\n");
		}
	}

	@Override
	public int addVertex() {
		this.listaSasiedztwa.add(new ArrayList<Integer>());
		return this.iloscWierzcholkow++;
	}

	@Override
	public void addEdge(int source, int target) throws IllegalArgumentException {
		if (source > this.iloscWierzcholkow || target > this.iloscWierzcholkow
				|| source < 0 || target < 0) {
			throw new IllegalArgumentException();
		}
		this.listaSasiedztwa.get(source).add(target);
	}

	@Override
	public List<Integer> sasiedzi(int v) throws IllegalArgumentException {
		if (v > this.iloscWierzcholkow || v < 0) {
			throw new IllegalArgumentException();
		}
		return this.listaSasiedztwa.get(v);
	}

	@Override
	public boolean check(int i, int j) throws IllegalArgumentException {
		if (i > this.iloscWierzcholkow || j > this.iloscWierzcholkow || i < 0
				|| j < 0) {
			throw new IllegalArgumentException();
		}
		return this.listaSasiedztwa.get(i).contains(j);
	}

	@Override
	public void dfs() {
		// TODO Auto-generated method stub

	}

	@Override
	protected void odwiedzaj(int wierzcholek) {
		// TODO Auto-generated method stub

	}

	@Override
	public LGraph transpose() {
		// TODO Auto-generated method stub
		return null;
	}

	public static void main(String[] args) {
		CustomGraph g = new CustomGraph();
		g.addVertex();
		g.addVertex();
		g.addVertex();
		g.addVertex();
		g.addEdge(0, 1);
		g.addEdge(0, 2);
		g.addEdge(2, 1);
		g.writeList();
		g.writeMatrix();
	}

	@Override
	public void writeMatrix() {
		// TODO Auto-generated method stub

	}
}

IterativeGraph.java

import java.util.Stack;

public class IterativeGraph extends CustomGraph {
	public void dfs() {
		int sourceVertex = 0;
		Stack<Integer> Q = new Stack<Integer>();
		boolean[] visited = new boolean[this.iloscWierzcholkow];
		visited[sourceVertex] = true;
		Q.push(sourceVertex);
		while (!Q.isEmpty()) {
			int v = Q.pop();
			System.out.print(v);
			for (int w = 0; w < this.iloscWierzcholkow; w++) {
				if (!this.check(v, w)) {
					continue;
				}
				;
				if (!visited[w]) {
					visited[w] = true;
					Q.push(w);
				}
			}
		}
	}

	public static void main(String[] args) {
		IterativeGraph g = new IterativeGraph();
		g.addVertex();
		g.addVertex();
		g.addVertex();
		g.addVertex();
		g.addVertex();
		g.addEdge(0, 1);
		g.addEdge(0, 2);
		g.addEdge(2, 1);
		g.addEdge(2, 3);
		g.addEdge(2, g.addVertex());
		g.addEdge(2, g.addVertex());
		g.addEdge(3, g.addVertex());
		g.addEdge(2, g.addVertex());
		g.addEdge(4, g.addVertex());
		g.writeList();
		g.writeMatrix();
		g.dfs();
	}
}

LGraph.java

/**
 * Listowa reprezentacja grafu.
 */
import java.util.ArrayList;
import java.util.List;

public abstract class LGraph {

	/**
	 * aktualna liczba wierzcholkow w grafie
	 */
	protected int iloscWierzcholkow = 0;
	/**
	 * Lista list sasiadow wszystkich wiercholkow
	 */
	protected ArrayList<List<Integer>> listaSasiedztwa;

	public LGraph() {
		listaSasiedztwa = new ArrayList<List<Integer>>();
	}

	/**
	 * Wypisuje graf w postaci listowej.
	 */
	public abstract void writeList();

	/**
	 * Wypisuje graf w postaci macierzy sasiedztwa.
	 */
	public abstract void writeMatrix();

	/**
	 * dodaje wierzcholek do grafu i zwraca jego numer. Metoda ma utworzyc pusta
	 * liste sasiedztwa dla nowo wstawionego wierzcholka oraz inkrementowac
	 * atrybut iloscWierzcholkow
	 */
	public abstract int addVertex();

	/**
	 * Dodaje krawedz do grafu.
	 */
	public abstract void addEdge(int source, int target)
			throws IllegalArgumentException;

	/**
	 * Zwraca liste sasiadow podanego wierzcholka.
	 */
	public abstract List<Integer> sasiedzi(int v)
			throws IllegalArgumentException;

	/**
	 * Sprawdza, czy istnieje krawedz pomiedzy wierzcholkiem i oraz j.
	 */
	public abstract boolean check(int i, int j) throws IllegalArgumentException;

	/**
	 * Przeszukuje graf w glab. Wypisuje wierzcholki w kolejnosci odwiedzania.
	 * Wykorzystuje metode odwiedzaj.
	 */
	public abstract void dfs();

	/**
	 * Metoda rekurencyjna odwiedzajaca wierzcholek i jego nastepniki.
	 */
	protected abstract void odwiedzaj(int wierzcholek);

	/**
	 * Wykonuje transpozycje grafu.
	 */
	public abstract LGraph transpose();
}

MatrixGraph.java

public class MatrixGraph extends CustomGraph {
	@Override
	public void writeMatrix() {
		for (int i = 0; i < this.iloscWierzcholkow; i++) {
			for (int j = 0; j < this.iloscWierzcholkow; j++) {
				System.out.print(this.check(i, j) ? "1" : "0");
			}
			;
			System.out.println();
		}
	}
}

RecursiveGraph.java

public class RecursiveGraph extends CustomGraph {
	final int BIALY = 0;
	final int SZARY = 1;
	final int CZARNY = 2;
	int[] kolor;
	int[] poczatek;
	int[] koniec;
	Integer[] rodzic;
	int czas;

	protected void odwiedzaj(int u) {
		System.out.print(u);
		this.kolor[u] = SZARY;
		this.czas += 1;
		this.poczatek[u] = czas;
		for (int v : this.sasiedzi(u)) {
			if (kolor[v] == BIALY) {
				this.rodzic[v] = u;
				this.odwiedzaj(v);
			}
		}
		this.kolor[u] = CZARNY;
		this.czas += 1;
		this.koniec[u] = czas;
	};

	@Override
	public void dfs() {
		this.kolor = new int[this.iloscWierzcholkow];
		this.poczatek = new int[iloscWierzcholkow];
		this.koniec = new int[iloscWierzcholkow];
		this.rodzic = new Integer[iloscWierzcholkow];
		this.czas = 0;
		for (int u = 0; u < this.iloscWierzcholkow; u++) {
			if (kolor[u] == BIALY) {
				this.odwiedzaj(u);
			}
		}

	}

	public static void main(String[] args) {
		RecursiveGraph g = new RecursiveGraph();
		g.addVertex();
		g.addVertex();
		g.addVertex();
		g.addVertex();
		g.addVertex();
		g.addEdge(0, 1);
		g.addEdge(0, 2);
		g.addEdge(2, 1);
		g.addEdge(2, 3);
		g.writeList();
		g.writeMatrix();
		g.dfs();
	}
}

TransposeGraph.java

public class TransposeGraph extends CustomGraph {
	@Override
	public LGraph transpose() {
		TransposeGraph tmp = new TransposeGraph();
		for (int i = 0; i < this.iloscWierzcholkow; i++) {
			tmp.addVertex();
		}
		;
		for (int i = 0; i < this.iloscWierzcholkow; i++) {
			for (int j = 0; j < this.iloscWierzcholkow; j++) {
				if (this.check(i, j)) {
					tmp.addEdge(j, i);
				}
			}
		}
		this.listaSasiedztwa = tmp.listaSasiedztwa;
		return this;
	};
}