Given an XML which contains a representation of a graph, how to apply it DFS algorithm? [on hold]

Posted by winston smith on Programmers See other posts from Programmers or by winston smith
Published on 2013-11-10T17:54:41Z Indexed on 2013/11/10 22:21 UTC
Read the original article Hit count: 381

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?

© Programmers or respective owner

Related posts about java

Related posts about algorithms