Solved

Source code for computing a 'Visibility Graph' in java

Posted on 2004-04-01
11
1,334 Views
1 Endorsement
Last Modified: 2012-06-27
ok.  Its a basic (naive) visibility graph that i need that will use use a 'sweeping' method in a clockwise direction.  It should display all the vertices that can see each other joining them with a line.  The obstacles are polygons.  It will be used with the dijkstra algorithm to find the shortest path which will be a sequence of the lines created by the visibility graph.
1
Comment
Question by:Brian_Johnston
11 Comments
 
LVL 14

Expert Comment

by:StillUnAware
Comment Utility
It really sounds like a homework task, isn't it?
0
 
LVL 14

Expert Comment

by:Tommy Braas
Comment Utility
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.
0
 

Author Comment

by:Brian_Johnston
Comment Utility
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
0
 

Author Comment

by:Brian_Johnston
Comment Utility
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
0
 
LVL 14

Expert Comment

by:Tommy Braas
Comment Utility
Ok, we'll be awaiting the code and be eager to help. Thanks.
0
Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

 

Author Comment

by:Brian_Johnston
Comment Utility
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+")");
      }
    }
}
0
 

Author Comment

by:Brian_Johnston
Comment Utility
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.");
      }
    }
}
0
 

Author Comment

by:Brian_Johnston
Comment Utility
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....

0
 

Accepted Solution

by:
modulo earned 0 total points
Comment Utility
Closed, 500 points refunded.
modulo
Community Support Moderator
Experts Exchange
0
 

Expert Comment

by:chennavarri
Comment Utility
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
0

Featured Post

Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

Join & Write a Comment

Suggested Solutions

An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing insta…
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now