package AnalyzeSkeleton;
import java.util.ArrayList;import java.util.Stack;
public class Graph { private ArrayList<Edge> edges = null; private ArrayList<Vertex> vertices = null; private Vertex root = null;
public Graph() { this.edges = new ArrayList<>(); this.vertices = new ArrayList<>(); }
public boolean addEdge(Edge e) { if (this.edges.contains(e)) { return false; } else { e.getV1().setBranch(e); if (!e.getV1().equals(e.getV2())) { e.getV2().setBranch(e); }
this.edges.add(e); return true; } }
public boolean addVertex(Vertex v) { if (this.vertices.contains(v)) { return false; } else { this.vertices.add(v); return true; } }
public ArrayList<Vertex> getVertices() { return this.vertices; }
public ArrayList<Edge> getEdges() { return this.edges; }
void setRoot(Vertex v) { this.root = v; }
ArrayList<Edge> depthFirstSearch() { ArrayList<Edge> backEdges = new ArrayList<>(); Stack<Vertex> stack = new Stack<>();
for(Vertex v : this.vertices) { v.setVisited(false); }
stack.push(this.root); int visitOrder = 0;
while(!stack.empty()) { Vertex u = stack.pop(); if (!u.isVisited()) { if (u.getPredecessor() != null) { u.getPredecessor().setType(0); }
u.setVisited(true, visitOrder++);
for(Edge e : u.getBranches()) { if (e.getType() == -1) { Vertex ov = e.getOppositeVertex(u); if (!ov.isVisited()) { stack.push(ov); ov.setPredecessor(e); } else { e.setType(1); backEdges.add(e); } } } } }
return backEdges; }}
