AiZLab7

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package aiz7;

/**
 *
 * @author MaxSylverWolf
 */
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

// GRAFY NIESKIEROWANE
class Graph {
// liczba krawedzi
private int e;
// liczba wierzcholkow
private int v;
// tablica list sasiedztwa danego wierzcholka
private List<Integer>[] adjacencyList;

@SuppressWarnings("unchecked")
public Graph(int v) {
this.v = v;
this.e = 0;
adjacencyList = (List<Integer>[]) new List[v];
for (int i = 0; i < v; i++) {
adjacencyList[i] = new ArrayList<Integer>();
}
}

public void addEdge(int v, int w) {
adjacencyList[v].add(w);
adjacencyList[w].add(v);
e++;
}

public int getNumberOfEdges() {
return e;
}

public int getNumberOfVertices() {
return v;
}

public Iterable<Integer> getAdjacencyList(int v) {
return adjacencyList[v];
}

public String toString() {
StringBuilder s = new StringBuilder();
String newLine = System.getProperty("line.separator");
s.append("wierzcholki: ").append(v).append("; krawedzie: ").append(e)
.append(newLine);
for (int i = 0; i < v; i++) {
s.append(i).append(": ");
for (int w : adjacencyList[i]) {
s.append(w).append(" ");
}
s.append(newLine);
}
return s.toString();
}
}

class DFSPaths {

private int[] edgeTo;
// tablica odwiedzonych wierzcholkow
private boolean[] marked;
// wierzcholek zrodlowy, z ktorego rozpoczynamy przeszukiwanie
private final int source;

public DFSPaths(Graph graph, int source) {
this.source = source;
edgeTo = new int[graph.getNumberOfVertices()];
marked = new boolean[graph.getNumberOfVertices()];
dfs(graph, source);
}

public boolean hasPathTo(int vertex) {
return marked[vertex];
}

public Iterable<Integer> getPathTo(int vertex) {
Deque<Integer> path = new ArrayDeque<Integer>();
// jesli nie istnieje sciezka zwroc pusta sciezke
if (!hasPathTo(vertex)) {
return path;
}
// dopoki istnieje wierzcholek dodawaj go do stosu
for (int w = vertex; w != source; w = edgeTo[w]) {
path.push(w);
}
// dodaj na koniec krawedz zrodlowa
path.push(source);
return path;
}

private void dfs(Graph graph, int vertex) {
//  wierzcholek jako odwiedzony
marked[vertex] = true;

for (int w : graph.getAdjacencyList(vertex)) {
if (!marked[w]) {
edgeTo[w] = vertex;
dfs(graph, w);
}
}
}
}

// GRAFY SKIEROWANE
class DirectedGraph {
// liczba krawedzi
private int e;
// liczba wierzcholkow
private int v;
// tablica list sasiedztwa danego wierzcholka
private List<Integer>[] adjacencyList;

@SuppressWarnings("unchecked")
public DirectedGraph(int v) {
this.v = v;
this.e = 0;
adjacencyList = (List<Integer>[]) new List[v];
for (int i = 0; i < v; i++) {
adjacencyList[i] = new ArrayList<Integer>();
}
}

public void addEdge(int v, int w) {
adjacencyList[v].add(w);
e++;
}

public int getNumberOfEdges() {
return e;
}

public int getNumberOfVertices() {
return v;
}

public Iterable<Integer> getAdjacencyList(int v) {
return adjacencyList[v];
}

public String toString() {
StringBuilder s = new StringBuilder();
String newLine = System.getProperty("line.separator");
s.append("wierzcholki: ").append(v).append("; krawedzie: ").append(e)
.append(newLine);
for (int i = 0; i < v; i++) {
s.append(i).append(": ");
for (int w : adjacencyList[i]) {
s.append(w).append(" ");
}
s.append(newLine);
}
return s.toString();
}
}

class DFSDirectedPaths {

private int[] edgeTo;
// tablica odwiedzonych wierzcholkow
private boolean[] marked;
// wierzcholek zrodlowy, z ktorego rozpoczynamy przeszukiwanie
private final int source;

public DFSDirectedPaths(DirectedGraph graph, int source) {
this.source = source;
edgeTo = new int[graph.getNumberOfVertices()];
marked = new boolean[graph.getNumberOfVertices()];
dfs(graph, source);
}


public boolean hasPathTo(int vertex) {
return marked[vertex];
}

public Iterable<Integer> getPathTo(int vertex) {
Deque<Integer> path = new ArrayDeque<Integer>();
// jesli nie istnieje sciezka zwroc pusta sciezke
if (!hasPathTo(vertex)) {
return path;
}
// dopoki istnieje wierzcholek dodawaj go do stosu
for (int w = vertex; w != source; w = edgeTo[w]) {
path.push(w);
}
// dodaj na koniec krawedz zrodlowa
path.push(source);
return path;
}

private void dfs(DirectedGraph graph, int vertex) {
// oznaczamy wierzcholek jako odwiedzony
marked[vertex] = true;
for (int w : graph.getAdjacencyList(vertex)) {
if (!marked[w]) {
edgeTo[w] = vertex;
dfs(graph, w);
}
}
}
}


class Paths {

public static void main(String[] args) {

Graph graph = new Graph(6);

graph.addEdge(0, 1);
graph.addEdge(0, 2);

graph.addEdge(1, 4);

graph.addEdge(2, 3);
graph.addEdge(2, 5);

graph.addEdge(3, 0);

graph.addEdge(4, 3);

System.out.println("Graf nieskierowany: " + graph);

System.out.println("\nPrzeszukiwanie grafu w głąb - sciezki nieskierowane");
// droga z 1 do 5
DFSPaths dfs1 = new DFSPaths(graph, 0);
for (int it : dfs1.getPathTo(4)) {
System.out.print(it + " ");
}
System.out.println("\n----------");

// droga z 5 do 1
DFSPaths dfs2 = new DFSPaths(graph, 4);
for (int it : dfs2.getPathTo(0)) {
System.out.print(it + " ");
}

// --------------------------------------------
// grafy skierowane
DirectedGraph digraph = new DirectedGraph(6);

digraph.addEdge(0, 1);
digraph.addEdge(0, 2);

digraph.addEdge(1, 4);

digraph.addEdge(2, 3);
digraph.addEdge(2, 5);

digraph.addEdge(3, 0);

digraph.addEdge(4, 3);

System.out.println("\n\nGraf skierowany: " + digraph);

System.out.println("\nPrzeszukiwanie grafu w głąb - sciezki skierowane");
// droga z 1 do 5
DFSDirectedPaths dfs3 = new DFSDirectedPaths(digraph, 0);
for (int it : dfs3.getPathTo(4)) {
System.out.print(it + " ");
}
System.out.println("\n----------");

// droga z 5 do 1
DFSDirectedPaths dfs4 = new DFSDirectedPaths(digraph, 4);
for (int it : dfs4.getPathTo(0)) {
System.out.print(it + " ");
}
}
}