Given an XML which contains a representation of a graph, how to apply it DFS algorithm? [on hold]
- by winston smith
Given the followin XML which is a directed graph:
<?xml version="1.0" encoding="iso-8859-1" ?>
<!DOCTYPE graph PUBLIC "-//FC//DTD red//EN" "../dtd/graph.dtd">
<graph direct="1">
<vertex label="V0"/>
<vertex label="V1"/>
<vertex label="V2"/>
<vertex label="V3"/>
<vertex label="V4"/>
<vertex label="V5"/>
<edge source="V0" target="V1" weight="1"/>
<edge source="V0" target="V4" weight="1"/>
<edge source="V5" target="V2" weight="1"/>
<edge source="V5" target="V4" weight="1"/>
<edge source="V1" target="V2" weight="1"/>
<edge source="V1" target="V3" weight="1"/>
<edge source="V1" target="V4" weight="1"/>
<edge source="V2" target="V3" weight="1"/>
</graph>
With this classes i parsed the graph and give it an adjacency list representation:
import java.io.IOException;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Collection;
import java.util.Iterator;
import java.util.logging.Level;
import java.util.logging.Logger;
import practica3.util.Disc;
public class ParsingXML {
public static void main(String[] args) {
try {
// TODO code application logic here
Collection<Vertex> sources = new HashSet<Vertex>();
LinkedList<String> lines = Disc.readFile("xml/directed.xml");
for (String lin : lines) {
int i = Disc.find(lin, "source=\"");
String data = "";
if (i > 0 && i < lin.length()) {
while (lin.charAt(i + 1) != '"') {
data += lin.charAt(i + 1);
i++;
}
Vertex v = new Vertex();
v.setName(data);
v.setAdy(new HashSet<Vertex>());
sources.add(v);
}
}
Iterator it = sources.iterator();
while (it.hasNext()) {
Vertex ver = (Vertex) it.next();
Collection<Vertex> adyacencias = ver.getAdy();
LinkedList<String> ls = Disc.readFile("xml/graphs.xml");
for (String lin : ls) {
int i = Disc.find(lin, "target=\"");
String data = "";
if (lin.contains("source=\""+ver.getName())) {
Vertex v = new Vertex();
if (i > 0 && i < lin.length()) {
while (lin.charAt(i + 1) != '"') {
data += lin.charAt(i + 1);
i++;
}
v.setName(data);
}
i = Disc.find(lin, "weight=\"");
data = "";
if (i > 0 && i < lin.length()) {
while (lin.charAt(i + 1) != '"') {
data += lin.charAt(i + 1);
i++;
}
v.setWeight(Integer.parseInt(data));
}
if (v.getName() != null) {
adyacencias.add(v);
}
}
}
}
for (Vertex vert : sources) {
System.out.println(vert);
System.out.println("adyacencias: " + vert.getAdy());
}
} catch (IOException ex) {
Logger.getLogger(ParsingXML.class.getName()).log(Level.SEVERE, null, ex);
}
}
}
This is another class:
import java.util.Collection;
import java.util.Objects;
public class Vertex {
private String name;
private int weight;
private Collection ady;
public Collection getAdy() {
return ady;
}
public void setAdy(Collection adyacencias) {
this.ady = adyacencias;
}
public String getName() {
return name;
}
public void setName(String nombre) {
this.name = nombre;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
@Override
public int hashCode() {
int hash = 7;
hash = 43 * hash + Objects.hashCode(this.name);
hash = 43 * hash + this.weight;
return hash;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Vertex other = (Vertex) obj;
if (!Objects.equals(this.name, other.name)) {
return false;
}
if (this.weight != other.weight) {
return false;
}
return true;
}
@Override
public String toString() {
return "Vertice{" + "name=" + name + ", weight=" + weight + '}';
}
}
And finally:
/**
*
* @author user
*/
/* -*-jde-*- */
/* <Disc.java> Contains the main argument*/
import java.io.*;
import java.util.LinkedList;
/**
* Lectura y escritura de archivos en listas de cadenas
* Ideal para el uso de las clases para gráficas.
*
* @author Peralta Santa Anna Victor Miguel
* @since Julio 2011
*/
public class Disc {
/**
* Metodo para lectura de un archivo
*
* @param fileName archivo que se va a leer
* @return El archivo en representacion de lista de cadenas
*/
public static LinkedList<String> readFile(String fileName) throws IOException {
BufferedReader file = new BufferedReader(new FileReader(fileName));
LinkedList<String> textlist = new LinkedList<String>();
while (file.ready()) {
textlist.add(file.readLine().trim());
}
file.close();
/*
for(String linea:textlist){
if(linea.contains("source")){
//String generado = linea.replaceAll("<\\w+\\s+\"", "");
//System.out.println(generado);
}
}*/
return textlist;
}//readFile
public static int find(String linea,String palabra){
int i,j;
boolean found = false;
for(i=0,j=0;i<linea.length();i++){
if(linea.charAt(i)==palabra.charAt(j)){
j++;
if(j==palabra.length()){
found = true;
return i;
}
}else{
continue;
}
}
if(!found){
i= -1;
}
return i;
}
/**
* Metodo para la escritura de un archivo
*
* @param fileName archivo que se va a escribir
* @param tofile la lista de cadenas que quedaran en el archivo
* @param append el bit que dira si se anexa el contenido o se empieza de cero
*/
public static void writeFile(String fileName, LinkedList<String> tofile, boolean append) throws IOException {
FileWriter file = new FileWriter(fileName, append);
for (int i = 0; i < tofile.size(); i++) {
file.write(tofile.get(i) + "\n");
}
file.close();
}//writeFile
/**
* Metodo para escritura de un archivo
* @param msg archivo que se va a escribir
* @param tofile la cadena que quedaran en el archivo
* @param append el bit que dira si se anexa el contenido o se empieza de cero
*/
public static void writeFile(String msg, String tofile, boolean append) throws IOException {
FileWriter file = new FileWriter(msg, append);
file.write(tofile);
file.close();
}//writeFile
}//
I'm stuck on what can be the best way to given an adjacency list representation of the graph how to apply it Depth-first search algorithm. Any idea of how to aproach to complete the task?
