graph
Class Graph<E>

java.lang.Object
  extended by graph.Graph<E>
All Implemented Interfaces:
java.lang.Iterable<Vertex<E>>, java.util.Collection<Vertex<E>>

public class Graph<E>
extends java.lang.Object
implements java.util.Collection<Vertex<E>>

A Graph is a group of vertices, with edges between vertices. This implementation places vertices in a HashMap with the key being a Location and the value for a given key being a Vertex. Each vertex has an array of Edge objects. Each Edge has two vertices.
Graph can read files given in the simple graph format. The simple graph format consists of three parts:

  • The number of vertices and edges
  • All the edges given as two vertex numbers
  • The locations of each vertex
  • For example, given a graph with 4 vertices and 3 edges between vertices 1 and 3, 2 and 3, and 2 and 4, the file would look like this:

    4 3
    1 3
    2 3
    2 4
    140 200
    210 120
    50 50
    60 80

    The first line is the number of vertices followed by the number of edges. The next three lines are all the edges each with one edge denoted by to vertex numbers. The following four lines are the locations of each of the vertices in order, in the form xLoc yLoc, (x,y).

    Since:
    1.6
    Version:
    1.0
    Author:
    Jonah Scheinerman

    Constructor Summary
    Graph()
              Creates a new empty graph.
     
    Method Summary
     boolean add(Vertex<E> v)
              Adds a vertex at its given location to this graph.
     boolean addAll(java.util.Collection<? extends Vertex<E>> arg0)
               
     void clear()
               
     void complete()
               
     boolean contains(java.lang.Object o)
               
     boolean containsAll(java.util.Collection<?> c)
               
    static
    <E> Graph<E>
    createInputGraph(java.io.File file)
              Creates a Graph object given a file in the Simple Graph Format.
     java.io.File createOutputFile(java.lang.String path)
              Creates an output file at the given location using the Simple Graph Format.
     void genMinSpanTree(Vertex<E> v)
               
     Vertex<E> get(Location loc)
              Returns the Vertex contained at Location loc.
     java.util.Set<Vertex<E>> getComponent(Vertex<E> v)
               
     java.util.Set<Location> getLocations()
              Retrieves the set of all vertex locations for this graph.
     Vertex<E> getVertexAt(Location l)
              Retrieves the vertex at a given location.
     java.util.Collection<Vertex<E>> getVertexCollection()
               
     java.util.HashMap<Location,Vertex<E>> getVertices()
              Returns the map of locations to vertices in this graph.
     double getWeight()
               
     boolean isEmpty()
               
     java.util.Iterator<Vertex<E>> iterator()
              Returns an iterator that iterates over the vertices in the graph.
     Vertex<E> remove(Location loc)
              Removes and returns the vertex at the given location.
     boolean remove(java.lang.Object arg0)
               
     boolean removeAll(java.util.Collection<?> arg0)
               
     boolean retainAll(java.util.Collection<?> arg0)
               
     int size()
               
     java.lang.Object[] toArray()
               
    <T> T[]
    toArray(T[] a)
               
     java.lang.String toString()
               
     
    Methods inherited from class java.lang.Object
    equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
     
    Methods inherited from interface java.util.Collection
    equals, hashCode
     

    Constructor Detail

    Graph

    public Graph()
    Creates a new empty graph.

    Method Detail

    add

    public boolean add(Vertex<E> v)
    Adds a vertex at its given location to this graph.

    Specified by:
    add in interface java.util.Collection<Vertex<E>>
    Parameters:
    v - - a vertex

    addAll

    public boolean addAll(java.util.Collection<? extends Vertex<E>> arg0)
    Specified by:
    addAll in interface java.util.Collection<Vertex<E>>

    clear

    public void clear()
    Specified by:
    clear in interface java.util.Collection<Vertex<E>>

    complete

    public void complete()

    createOutputFile

    public java.io.File createOutputFile(java.lang.String path)
                                  throws java.io.IOException
    Creates an output file at the given location using the Simple Graph Format.

    Parameters:
    path - - a path for the file.
    Returns:
    a file which has been instantiated and written with the graph data.
    Throws:
    java.io.IOException - - if the file cannot be read or created.

    createInputGraph

    public static <E> Graph<E> createInputGraph(java.io.File file)
                                     throws java.io.FileNotFoundException
    Creates a Graph object given a file in the Simple Graph Format.

    Parameters:
    file - - the file to be read
    Returns:
    a new graph created from the file data.
    Throws:
    java.io.FileNotFoundException - - if the file cannot be found.

    contains

    public boolean contains(java.lang.Object o)
    Specified by:
    contains in interface java.util.Collection<Vertex<E>>

    containsAll

    public boolean containsAll(java.util.Collection<?> c)
    Specified by:
    containsAll in interface java.util.Collection<Vertex<E>>

    getComponent

    public java.util.Set<Vertex<E>> getComponent(Vertex<E> v)

    getLocations

    public java.util.Set<Location> getLocations()
    Retrieves the set of all vertex locations for this graph.

    Returns:
    a set of locations.

    getVertexAt

    public Vertex<E> getVertexAt(Location l)
    Retrieves the vertex at a given location. This method guarantees that loc == getVertexAt(loc).getLocation() will always return true.

    Parameters:
    l - - a location
    Returns:
    the vertex at l.

    getVertexCollection

    public java.util.Collection<Vertex<E>> getVertexCollection()

    getVertices

    public java.util.HashMap<Location,Vertex<E>> getVertices()
    Returns the map of locations to vertices in this graph.

    Returns:
    - the HashMap

    getWeight

    public double getWeight()

    get

    public Vertex<E> get(Location loc)
    Returns the Vertex contained at Location loc. If no vertex exists at the given location, null will be returned.

    Parameters:
    loc - - a location
    Returns:
    the vertex at that location.

    isEmpty

    public boolean isEmpty()
    Specified by:
    isEmpty in interface java.util.Collection<Vertex<E>>

    genMinSpanTree

    public void genMinSpanTree(Vertex<E> v)

    remove

    public Vertex<E> remove(Location loc)
    Removes and returns the vertex at the given location. If this node has any edges connecting to other nodes, they will be removed from that vertex and its neighbors. If no node is at that location, null is returned.

    Parameters:
    loc - - a location
    Returns:
    the vertex at that location

    remove

    public boolean remove(java.lang.Object arg0)
    Specified by:
    remove in interface java.util.Collection<Vertex<E>>

    removeAll

    public boolean removeAll(java.util.Collection<?> arg0)
    Specified by:
    removeAll in interface java.util.Collection<Vertex<E>>

    retainAll

    public boolean retainAll(java.util.Collection<?> arg0)
    Specified by:
    retainAll in interface java.util.Collection<Vertex<E>>

    size

    public int size()
    Specified by:
    size in interface java.util.Collection<Vertex<E>>

    toArray

    public java.lang.Object[] toArray()
    Specified by:
    toArray in interface java.util.Collection<Vertex<E>>

    toArray

    public <T> T[] toArray(T[] a)
    Specified by:
    toArray in interface java.util.Collection<Vertex<E>>

    toString

    public java.lang.String toString()
    Overrides:
    toString in class java.lang.Object

    iterator

    public java.util.Iterator<Vertex<E>> iterator()
    Returns an iterator that iterates over the vertices in the graph.

    Specified by:
    iterator in interface java.lang.Iterable<Vertex<E>>
    Specified by:
    iterator in interface java.util.Collection<Vertex<E>>
    Returns:
    a vertex iterator.