Source code for computing a 'Visibility Graph' in java

It really sounds like a homework task, isn't it?

I would suggest that you read the material provided with the assignment properly, and look the theory up in your text book.
Create a plan to solve the problems in the assignment. Split the assignemnt into small tasks, to make the assignment manageable.
Solve each small task.
Put all the solutions together to solve the assignment.
Once you've written some code and have problems, we'll be happy to help you out.

No its not actually, but if you guys cant handle it, there is not much chance of me being able to do it.

The points are there for the taking.

brian

I shall post the code I currently have and you shall see I am no further on that I was previously.

This is very important for my business.

Regards
Brian

Ok, we'll be awaiting the code and be eager to help. Thanks.

There are 6 classes and I cannot exactly paste them all here, so below are the classes I think are necessary.

There are only 2 errors:
 
 
1. Dijkstra.java [20:1] cannot access Map
bad class file: C:\Documents and Settings\Craig\My Documents\newdijkstra-30.3.04\Map.class
class file contains wrong class: structure.Map
Please remove or make sure it appears in the correct subdirectory of the classpath.
    public static Map dijkstra(Graph g, Object start)
 
 
2. GraphListUndirected.java [62:1] cannot access GraphList
bad class file: C:\Documents and Settings\Craig\My Documents\honours documentation\newdijkstra-30.3.04\GraphList.class
class file contains wrong class: structure.GraphList
Please remove or make sure it appears in the correct subdirectory of the classpath.
public class GraphListUndirected extends GraphList

 
These files are in the same location as the others so the errors have me stumped.

import structure.*;
import java.io.*;
import java.util.Iterator;



public class Dijkstra {


    public static Map dijkstra(Graph g, Object start)
    // pre: g is a graph; start is source vertex
    // post: returns a dictionary of vertex-based results
    //       value is association (total-distance,prior-edge)
    {

        Graph g;
        // keep a priority queue of distances from source
      PriorityQueue q = new SkewHeap();
      Map result = new Table(); // results, sorted by vertex
      Object v = start;      // last vertex added
      // result is a (total-distance,previous-edge) pair
      ComparableAssociation possible =
          new ComparableAssociation(new Integer(0),null);
      // as long as we add a new vertex...
      while (v != null)
      {
          if (!result.containsKey(v))
          {
            // visit node v - record incoming edge
            result.put(v,possible);
            // vDist is shortest distance to v
            int vDist = ((Integer)possible.getKey()).intValue();

            // compute and consider distance to each neighbor
            Iterator ai = g.neighbors(v);
            while (ai.hasNext())
            {
                // get edge to neighbor
                Edge e = g.getEdge(v,ai.next());
                // construct (distance,edge) pair for possible result
                possible = new ComparableAssociation(
                  new Integer(vDist+((Integer)e.label()).intValue()),
                  e);
                q.add(possible);      // add to priority queue
            }
          }
          // now, get closest (possibly unvisited) vertex
          if (!q.isEmpty())
          {
            possible = (ComparableAssociation)q.remove();
            // get destination vertex (take care w/undirected graphs)
            v = ((Edge)possible.getValue()).there();
            if (result.containsKey(v))
                v = ((Edge)possible.getValue()).here();
          } else {
            // no new vertex (algorithm stops)
            v = null;
          }
      }
      return result;
    }

    static public void main(String[] args) {
      Graph g = new GraphMatrixDirected(300);

      // towns and their names
      String hereName, thereName;// two generic towns
      String startName, finishName; // the specific query

      // a road to be added or manipulated
      Integer length;
      ReadStream input = new ReadStream();

      // read in all roads, add two copies <-> bidirectional
      for (hereName = input.readString();
           !hereName.equals("end");
           hereName = input.readString()) {

          thereName = input.readString();
          input.readString();
          length = new Integer(input.readInt());

          g.add(hereName);
          g.add(thereName);
          // for getting from hereTown to thereTown
          g.addEdge(hereName, thereName, length);
          // for getting from thereTown to hereTown
          g.addEdge(thereName, hereName, length);
      }

      // read in the source town
      startName = input.readString();

      Map results = dijkstra(g,startName);
      Iterator ki = results.keySet().iterator();
      Iterator vi = results.values().iterator();
      while (ki.hasNext())
      {
          String dest = (String)ki.next();
          Association a = (Association)vi.next();
          if (dest.equals(startName)) continue;
          String source = (String)((Edge)a.getValue()).here();
          if (source.equals(dest))
            source = (String)((Edge)a.getValue()).there();
          int len = ((Integer)a.getKey()).intValue();
          System.out.println(dest+" is "+len+" miles from "+startName+" (via
"+source+")");
      }
    }
}

and the graphlist class, where the second error comes from.

Basically, i want to compute the dijkstra algorithm, in order to do this, i need to use the other classes (skew heap, priority queue etc) so it will run

package structure;
import java.util.Iterator;

/**
* Implementation of graph using adjacency lists.
* Edges are stored in lists off of vertex structure.
* Class is abstract: you must use GraphListDirected or
* GraphListUndirected to construct particular instances of graphs.
*
* Typical usage:
* <pre>
*     Graph g = new GraphListDirected();
*     g.add("harry");
*     g.add("sally");
*     g.addEdge("harry","sally","friendly");
*     ...
* </pre>
*
* @version $Id: GraphList.java,v 4.0 2000/12/27 20:57:33 bailey Exp bailey $
* @author, 2001 duane a. bailey and kimberly tabtiang
* @see GraphListDirected
* @see GraphListUndirected
* @see GraphMatrix
*/
abstract public class GraphList extends AbstractStructure implements Graph
{
    /**
     * Map associating vertex labels with vertex structures.
     */
    protected Map dict;      // label to vertex dictionary
    /**
     * Whether or not graph is directed.
     */
    protected boolean directed;      // is graph directed?

    /**
     * Constructor of directed/undirected GraphList. Protected constructor.
     *
     * @param dir True if graph is to be directed.
     */
    protected GraphList(boolean dir)
    {
      dict = new Hashtable();
      directed = dir;
    }
    /**
     * Add a vertex to the graph.
     *
     * @pre label is a non-null label for vertex
     * @post a vertex with label is added to graph;
     *       if vertex with label is already in graph, no action
     *
     * @param label Label of the vertex; should be non-null.
     */
    public void add(Object label)
    {
        if (dict.containsKey(label)) return; // vertex exists
        GraphListVertex v = new GraphListVertex(label);
        dict.put(label,v);
    }

    /**
     * Add an edge between two vertices within the graph.  Edge is directed
     * iff graph is directed.  Duplicate edges are silently replaced.
     * Labels on edges may be null.
     *
     * @pre vtx1 and vtx2 are labels of existing vertices
     * @post an edge (possibly directed) is inserted between
     *       vtx1 and vtx2.
     *
     * @param vtx1 First (or source, if directed) vertex.
     * @param vtx2 Second (or destination, if directed) vertex.
     * @param label Label associated with the edge.
     */
    abstract public void addEdge(Object v1, Object v2, Object label);

    /**
     * Remove a vertex from the graph.  Associated edges are also
     * removed.  Non-vertices are silently ignored.
     *
     * @pre label is non-null vertex label
     * @post vertex with "equals" label is removed, if found
     *
     * @param label The label of the vertex within the graph.
     * @return The label associated with the vertex.
     */
    abstract public Object remove(Object label);

    /**
     * Remove possible edge between vertices labeled vLabel1 and vLabel2.
     * Directed edges consider vLabel1 to be the source.
     *
     * @pre vLabel1 and vLabel2 are labels of existing vertices
     * @post edge is removed, its label is returned
     *
     * @param vLabel1 First (or source, if directed) vertex.
     * @param vLabel2 Second (or destination, if directed) vertex.
     * @return The label associated with the edge removed.
     */
    abstract public Object removeEdge(Object vLabel1, Object vLabel2);

    /**
     * Get reference to actual label of vertex.  Vertex labels are matched
     * using their equals method, which may or may not test for actual
     * equivalence.  Result remains part of graph.
     *
     * @post returns actual label of indicated vertex
     *
     * @param label The label of the vertex sought.
     * @return The actual label, or null if none is found.
     */
    public Object get(Object label)
    {
      Assert.condition(dict.containsKey(label), "Vertex exists");
      return ((GraphListVertex)dict.get(label)).label();
    }

    /**
     * Get reference to actual edge.  Edge is identified by
     * the labels on associated vertices.  If edge is directed, the
     * label1 indicates source.
     *
     * @post returns actual edge between vertices
     *
     * @param label1 The first (or source, if directed) vertex.
     * @param label2 The second (or destination, if directed) vertex.
     * @return The edge, if found, or null.
     */
    public Edge getEdge(Object label1, Object label2)
    {
      Assert.condition(dict.containsKey(label1), "Vertex exists");
      Edge e = new Edge(get(label1),get(label2), null, directed);
      return ((GraphListVertex) dict.get(label1)).getEdge(e);
    }

    /**
     * Test for vertex membership.
     *
     * @post returns true iff vertex with "equals" label exists
     *
     * @param label The label of the vertex sought.
     * @return True iff vertex with matching label is found.
     */
    public boolean contains(Object label)
    {
      return dict.containsKey(label);
    }

    /**
     * Test for edge membership.  If edges are directed, vLabel1
     * indicates source.
     *
     * @post returns true iff edge with "equals" label exists
     *
     * @param vLabel1 First (or source, if directed) vertex.
     * @param vLabel2 Second (or destination, if directed) vertex.
     * @return True iff the edge exists within the graph.
     */
    public boolean containsEdge(Object vLabel1, Object vLabel2)
    {
      Assert.condition(dict.containsKey(vLabel1), "Vertex exists");
      Edge e = new Edge(vLabel1, vLabel2, null, directed);
      return ((GraphListVertex) dict.get(vLabel1)).containsEdge(e);
    }

    /**
     * Test and set visited flag of vertex.
     *
     * @post sets visited flag on vertex, returns previous value
     *
     * @param label Label of vertex to be visited.
     * @return Previous value of visited flag on vertex.
     */
    public boolean visit(Object label)
    {
      return ((GraphListVertex)dict.get(label)).visit();
    }

    /**
     * Test and set visited flag of edge.
     *
     * @pre sets visited flag on edge; returns previous value
     *
     * @param e Edge object that is part of graph.
     * @return Previous value of the Edge's visited flag.
     */
    public boolean visitEdge(Edge e)
    {
      return e.visit();
    }

    /**
     * Return visited flag of vertex.
     *
     * @post returns visited flag on labeled vertex
     *
     * @param label Label of vertex.
     * @return True if vertex has been visited.
     */
    public boolean isVisited(Object label)
    {
      return ((GraphListVertex)dict.get(label)).isVisited();
    }

    /**
     * Return visited flag of edge.
     *
     * @post returns visited flag on edge between vertices
     *
     * @param e Edge of graph to be considered.
     * @return True if the edge has been visited.
     */
    public boolean isVisitedEdge(Edge e)
    {
      return e.isVisited();
    }

    /**
     * Clear visited flags of edges and vertices.
     *
     * @post resets visited flags to false
     */
    public void reset()
    {
      // reset the vertices
      Iterator vi = dict.values().iterator();
      while (vi.hasNext())
      {
          Vertex vtx = (Vertex)vi.next();
          vtx.reset();
      }
      // reset the edges
      Iterator ei = edges();
      while (ei.hasNext())
      {
          Edge e = (Edge)ei.next();
          e.reset();
      }
    }

    /**
     * Determine number of vertices within graph.
     *
     * @post returns the number of vertices in graph
     *
     * @return The number of vertices within graph.
     */
    public int size()
    {
      return dict.size();
    }

    /**
     * Determine out degree of vertex.
     *
     * @pre label labels an existing vertex
     * @post returns the number of vertices adjacent to vertex
     *
     * @param label Label associated with vertex.
     * @return The number of edges with this vertex as source.
     */
    public int degree(Object label)
    {
      Assert.condition(dict.containsKey(label), "Vertex exists.");
      return ((GraphListVertex) dict.get(label)).degree();
    }

    /**
     * Determine the number of edges in graph.
     *
     * @post returns the number of edges in graph
     *
     * @return Number of edges in graph.
     */
    abstract public int edgeCount();

    /**
     * Construct vertex iterator.  Vertices are not visited in
     * any guaranteed order.
     *
     * @post returns iterator across all vertices of graph
     *
     * @return AbstractIterator traversing vertices in graph.
     */
    public Iterator iterator()
    {
      return dict.keySet().iterator();
    }

    /**
     * Construct an adjacent vertex iterator.   Adjacent vertices
     * (those on destination of edge, if directed) are considered,
     * but not in any guaranteed order.
     *
     * @pre label is label of vertex in graph
     * @post returns iterator over vertices adj. to vertex
     *       each edge beginning at label visited exactly once
     *
     * @param label Label of the vertex.
     * @return Iterator traversing the adjacent vertices of labeled vertex.
     */
    public Iterator neighbors(Object label)
    {
      // return towns adjacent to vertex labeled label
      Assert.condition(dict.containsKey(label), "Vertex exists");
      return ((GraphListVertex) dict.get(label)).adjacentVertices();
    }

    /**
     * Construct an iterator over all edges.  Every directed/undirected
     * edge is considered exactly once.  Order is not guaranteed.
     *
     * @post returns iterator across edges of graph
     *       iterator returns edges; each edge visited once
     *
     * @return Iterator over edges.
     */
    public Iterator edges()
    {
      return new GraphListEIterator(dict);
    }

    /**
     * Remove all vertices (and thus, edges) of the graph.
     *
     * @post removes all vertices from graph
     */
    public void clear()
    {
        dict.clear();
    }

    /**
     * Determine if graph is empty.
     *
     * @post returns true if graph contains no vertices
     *
     * @return True iff there are no vertices in graph.
     */
    public boolean isEmpty()
    {
      return dict.isEmpty();
    }

    /**
     * Determine if graph is directed.
     *
     * @post returns true if edges of graph are directed
     *
     * @return True iff the graph is directed.
     */
    public boolean isDirected()
    {
      return directed;
    }

    public static void main(String[] argv){
      Graph theaters = new GraphListDirected();
      SkewHeap heap = new SkewHeap();

      //instantiate array of locations
      String[] locations = new String[]{"TCL 312", "Images Cinema",
                                "Movie Plex 3", "Cinema 1,2,&3",
                                "Cinema 7", "Berkshire Mall Cinemas"
                                ,"Hathaway's Drive Inn Theatre",
                                "Hollywood Drive-In Theatre"};

      //instantiate array of distances between <code>location[0]</code>
      //and movie theaters
      double[] distances =  new double[]{-1, 0.0, 12.6, 12.9, 12.9,
                                 14.7, 16.5, 18.0};

      //build graph
      for(int i=0; i < locations.length; i++) theaters.add(locations[i]);
      for(int i=1; i < distances.length; i++){
          theaters.addEdge(locations[0],locations[i],
                       new Double(distances[i]));
      }

      //place neighbors of lab in into priority queue
      for(Iterator i=theaters.neighbors(locations[0]); i.hasNext();){
          Object theater = i.next();
          Object distance = theaters.getEdge(locations[0], theater).label();
          heap.add(new ComparableAssociation((Comparable)distance,theater));
      }

      //print out theaters in order of distance
      while(!heap.isEmpty()){
          ComparableAssociation show = (ComparableAssociation)heap.remove();
          System.out.println(show.getValue()+" is "+show.getKey()+" miles
away.");
      }
    }
}

As you can see this is only two of six classes.... I am up to my eyeballs here.

Is there anything that can be done....

Dear Sir,
Am trying to use this code with mine. I have a list of triangles and I want to find visible vertices for a vertex lying in the same plane. Please reply ASAP