Implementazione grafica dell'elenco di adiacenza generico

Question

Implementazione grafica dell'elenco di adiacenza generico

#1 da (1 voti)
#2 da (0 voti)

2

Sto provando a realizzare un'importante implementazione del grafico Adjacency List in modo da poter iniziare a lavorare con tutti i tipi di problemi grafici e algoritmi come venditore ambulante e altri problemi ... Ma non riesco a trovare un implementazione decente. Questo è probabilmente perché sto cercando di rispolverare le ragnatele dalla mia classe di strutture dati.

Ma quello che ho finora ... e questo è implementato in Java ... è fondamentalmente una classe edgeNode che ha un tipo generico e un peso, nel caso in cui il grafico sia effettivamente ponderato.

public class edgeNode<E> {
    private E y;
    private int weight;

    //... getters and setters as well as constructors...
}

Ho una classe di grafici che ha un elenco di bordi un valore per il numero di Vertici e un valore int per gli spigoli nonché un valore booleano per indicare se è diretto o meno. La mia prima domanda, se il grafico è effettivamente diretto, non dovrebbe avere un valore nella mia classe edgeNode? O dovrei semplicemente aggiungere altri vertici alla mia LinkedList? Ciò implicherebbe che un grafico diretto è 2 volte più grande di un grafo non orientato, vero?

public class graph {
    private List<edgeNode<?>> edges;    
    private int nVertices;
    private int nEdges;
    private boolean directed;

    //... getters and setters as well as constructors...
}

Finalmente qualcuno ha un modo standard per inizializzare il grafico? Stavo pensando di leggere in un file delimitato da pipe, ma è così il 1997.

public graph GenereateGraph(boolean directed, String file){
        List<edgeNode<?>> edges;
        graph g;
        try{
            int count = 0;
            String line;
            FileReader input = new FileReader("C:\Users\derekww\Documents\JavaEE Projects\graphFile");
            BufferedReader bufRead = new BufferedReader(input);
            line = bufRead.readLine();
            count++;
            edges = new ArrayList<edgeNode<?>>();
            while(line != null){
                line = bufRead.readLine();
                Object edgeInfo = line.split("|")[0];
                int weight = Integer.parseInt(line.split("|")[1]);
                edgeNode<String> e = new edgeNode<String>((String)
                edges.add(e);
            }           
            return g;
        }
        catch(Exception e){
            return null;
        }
    }

Credo che quando aggiungo i bordi se boolean è vero, aggiungerei un secondo edge. Finora, tutto dipende dal file che scrivo. Quindi se ho scritto un file con i seguenti Vertices e pesi ...

Buffalo | 18  br Pittsburgh | 20 br New York | 15 br D.C | 45 br

Ovviamente li caricherò nella mia lista di spigoli, ma come posso rappresentare un vertice collegato all'altro ... così via ... Avrei bisogno dei vertici opposti? Diciamo che stavo rappresentando le autostrade collegate a ogni città ponderate e non dirette (ogni spigolo è bidirezionale con pesi in qualche unità fittizia a distanza) ... La mia implementazione sarebbe il modo migliore per farlo?

Ho trovato questo tutorial online Tutorial grafico che ha un oggetto connettore. Questa mi sembra una raccolta di vertici che si indicano l'un l'altro. Quindi avresti A e B ciascuno con i pesi e così via, e lo aggiungerei ad una lista e questo elenco di connettori al tuo grafico ... Mi sembra un po 'macchinoso e un po' sprezzante del concetto di lista di adiacenza? Ho sbagliato e questa è una nuova soluzione?

Questo è tutto ispirato al Manuale di progettazione dell'algoritmo di steve skiena. Quello che devo dire è abbastanza buono finora. Grazie per l'aiuto che puoi fornire.

data-structures algorithms

posta SoftwareSavant 26.09.2012 - 01:11

fonte

2 risposte

Leggi altre domande sui tag data-structures algorithms

Lettura dei dati da file e const Una pagina che utilizza querystring o molte cartelle e pagine?

score 1 · Answer 1

Ecco un'implementazione che ho risolto quando avevo a che fare con i grafici. Sebbene sia in C #, con alcune modifiche minori potrebbe essere compilato in Java.

Per renderlo diretto dovresti copiare v.Adjacents.Add(new Edge(w, cost)); e invertire la direzione, quindi occupare il doppio dello spazio.

Non penso che sia meglio di quello che hai però.

class Edge
{
    public Vertex Destination { get; set; }
    public double Cost { get; set; }

    public Edge(Vertex destination, double cost)
    {
        Destination = destination;
        Cost = cost;
    }

}

class Vertex
{
    public string Name { get; set; }
    public List<Edge> Adjacents { get; set; }
    public double Distance { get; set; }

    public Vertex(string name)
    {
        Name = name;
        Adjacents = new List<Edge>();
        Distance = double.MaxValue;
    }
}

class Graf
{
    private readonly Dictionary<string, Vertex> vertexmap = new Dictionary<string, Vertex>();

    public void AddEdge(string source, string dest, double cost)
    {
        var v = GetVertex(source);
        var w = GetVertex(dest);
        v.Adjacents.Add(new Edge(w, cost));
    }

    private Vertex GetVertex(string vertexname)
    {
        Vertex v;
        vertexmap.TryGetValue(vertexname, out v);
        if (v == null)
        {
            v = new Vertex(vertexname);
            vertexmap.Add(vertexname, v);
        }
        return v;
    }
}

score 0 · Answer 2

Ecco qualcosa che ho scavato. Se qualcuno ha una migliore implementazione segnerò la sua osservazione come risposta ...

public interface AdjList {
    int beg();
    int nxt();
    boolean end();
}

public class Edge {
    int v, w;
    //E value;
    Edge(int v, int w){
        this.v = v; 
        this.w=w;
    }
}

public class GraphAdjList implements IGraph{
    private int vertCount, EdgeCount;

    private boolean directedGrph;

    private class Node{
        int v; Node next;
        Node(int x, Node t){
            v = x; 
            next = t;
        }       
    }
    private class AdjListPrvtImpl implements AdjList{
        private int vertex;
        private Node node;

        AdjListPrvtImpl(int v){
            this.vertex = v;
            node = null;
        }

        @Override
        public int beg() {
            // TODO Auto-generated method stub
            node = adj[vertex];

            return node == null ? -1 : node.v;
        }

        @Override
        public int nxt() {
            //
            if (node != null) node = node.next; 
            return node == null ? -1 : node.v;
        }

        @Override
        public boolean end() {
            // TODO Auto-generated method stub
            return node == null;
        }       
    }

    private Node[] adj;

    GraphAdjList(int V, boolean flag){
        vertCount = V;
        directedGrph = flag;
    }

    public int getVertCount() {
        return vertCount;
    }

    public int getEdgeCount() {
        return EdgeCount;
    }

    public boolean isDirectedGrph() {
        return directedGrph;
    }

    public AdjList getAdjList(int vertices){
        return new AdjListPrvtImpl(vertices);
    }

    @Override
    public void Graph(int vertCnt, boolean dir) {
        // TODO Auto-generated method stub
        vertCount = vertCnt;
        directedGrph = dir;
    }

    @Override
    public int V() {
        // TODO Auto-generated method stub
        return vertCount;
    }

    @Override
    public int E() {
        // TODO Auto-generated method stub
        return EdgeCount;
    }

    @Override
    public boolean directed() {
        // TODO Auto-generated method stub
        return directedGrph;
    }

    @Override
    public int insert(Edge e) {
        // TODO Auto-generated method stub
        return 0;
    }

    @Override
    public void remove(Edge e) {
        // TODO Auto-generated method stub

    }
    }

La maggior parte delle cose con bordi ha a che fare con le operazioni di Adjacency Matrix. Quindi l'ho lasciato non implementato.