Results 1 to 4 of 4
  1. #1
    Join Date
    Dec 2009
    Posts
    1
    Rep Power
    0

    Default Implementing an Adjacency List for a Flight Map

    I have to implement a flight map's adjacency list for a airline service and I'm having a lot of trouble understanding how to implement this. I have the readFlightMap method already. Which reads in the data and then calls upon the method below in my 2nd for loop which handles the adjacency list file:

    Java Code:
    // Inserts information into the flight map to record the fact that the
    // adjCity is adjacent to aCity.
    // Precondition: aCity and adjCity are valid cities that are served
    // by the airline.
    // Postcondition: The map will have changed to record the given information
    
    public void insertAdjacent(City aCity, City adjCity)
    {
    
    }
    My instructor told me to implement a array of linked lists to solve this problem, but this is the picture he showed us in class:

    An Array of LinkedLists:

    In the | |, the original city positions, then followed by their Adj list.

    | Q | -> X
    | X | -> No Adj
    | R | -> X
    | P | ->R ->W
    | W | ->S
    | S | ->T
    | T | ->W
    | Y | ->R ->Z
    | Z | ->No Adj

    I've searched all over google about how to implement this, but I have not discovered anything that helps. He gave us a ADTList based class, but it only has simple things like add, remove, size, etc and it does not handle the implementation that he suggested to us.

    This what I came up with so far, but it does nothing:

    Java Code:
    ListArrayBased cityAdjList;
    	public void insertAdjacent(City aCity, City adjCity)
    	{
    		//cityAdjList = new ListArrayBased();
    		cityAdjList.add(cityAdjList.size(),aCity);
    		cityAdjList.add(cityAdjList.size()+1,adjCity);
    	}
    I'm lost. :confused:
    Last edited by javaRancher2009; 12-07-2009 at 05:18 AM.

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,361
    Blog Entries
    7
    Rep Power
    20

    Default

    Why not use a Map? The key is a City and the associated value is a List of cities (the adjacent cities). Basically it'll look like this:

    Java Code:
    Map<City, List<City>> adj= new HashMap<City, List<City>>();
    ...
    // add a connection from -> to
    public boolean add(City from, City to) {
       List<City> tos= adj.get(from);
       if (tos == null) // from is not in the map
          return false;
       tos.add(to); // add a new to 
       return true;
    }
    // add a single airport
    public boolean add(City airport) {
       List<City> tos= adj.get(airport);
       if (tos != null) // already in the list
          return false;
       tos= new ArrayList<City>();
       adj.put(airport, tos); // add airport and a new empty adj. list
       return true;
    }
    kind regards,

    Jos

  3. #3
    sky
    sky is offline Member
    Join Date
    Nov 2009
    Posts
    96
    Rep Power
    0

  4. #4
    wtd_nielsen is offline Member
    Join Date
    Dec 2009
    Posts
    24
    Rep Power
    0

    Default

    I would use 2 ArrayLists, and all the Vertexs would have a list with incident Edges..
    Java Code:
    private List<Vertex<E1>> vertices; 
    private List<Edge<E2>> edges;
    
    public Edge<E2> insertEdge(Vertex<E1> v, Vertex<E1> w, E2 o)
    {
    	Edge<E2> e = new AdjacencyListEdge(o, v, w);
    	edges.add(e);
    	((AdjacencyListVertex) v).addEdge(e);
    	((AdjacencyListVertex) w).addEdge(e);
    	return e;
    }
    
    public Vertex<E1> insertVertex(E1 o)
    {
    	Vertex<E1> v = new AdjacencyListVertex(o);
    	vertices.add(v);
    	return v;
    }

Similar Threads

  1. Replies: 2
    Last Post: 11-22-2009, 05:24 PM
  2. Replies: 3
    Last Post: 11-21-2009, 05:48 PM
  3. how to create list of list in java ???
    By ilayaraja in forum Advanced Java
    Replies: 1
    Last Post: 10-26-2009, 04:30 PM
  4. problem with implementing list
    By timkd127 in forum New To Java
    Replies: 3
    Last Post: 04-13-2009, 03:54 AM
  5. How to access ArrayList in List of List?
    By alvations in forum New To Java
    Replies: 5
    Last Post: 10-08-2008, 12:23 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •