Digraph With Adjacency List

Inspired by Digraph (Algorithms 4/e) – Algorithms, 4th Edition

Digraph.java

//Digraph implementation with adjacency list
public class Digraph<V>{

    private Map<V,List<DirectedEdge<V>>> vertexes;

    private int eCount;

    public Digraph(){
        this.vertexes = new HashMap<>();
    }

    public int V(){
        return vertexes.size();
    }

    public int E(){
        return eCount;
    }

    public List<DirectedEdge<V>> adj(V vertex){
        return vertexes.get(vertex);
    }

    public void addEdge(DirectedEdge<V> de){
        if (de == null){
            return;
        }
        if (!vertexes.containsKey(de.from())){
            vertexes.put(de.from(), new ArrayList<>());
        }
        if (!vertexes.containsKey(de.to())){
            vertexes.put(de.to(), new ArrayList<>());
        }
        vertexes.get(de.from()).add(de);
        ++eCount;
    }

    //O(V+E)
    public List<DirectedEdge<V>> getEdges(){
        List<DirectedEdge<V>> res = new ArrayList<DirectedEdge<V>>(eCount);
        for (V v : vertexes.keySet()){
            res.addAll(vertexes.get(v));
        }
        return res;
    }

    public Set<V> getVertexes(){
        return vertexes.keySet();
    }
}

DirectedEdge.java

public class DirectedEdge<V>{

    private V from;
    private V to;

    public DirectedEdge(V from, V to){
        this.from = from;
        this.to = to;
    }

    public V from(){
        return from;
    }

    public V to(){
        return to;
    }

    @Override
    public String toString(){
        return from.toString() + "-->" + to.toString();
    }

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s