Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Bear Bibeault
  • Liutauras Vilda
  • Devaka Cooray
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • Henry Wong
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
  • Tim Holloway
Bartenders:
  • salvin francis
  • Frits Walraven
  • Piet Souris

How to implement a tree or hashmap for this particular case?

 
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi everyone!

My problem is I try to implement a data structure that will merge 3 Lists I have.

List<String> origins;        //10 elements
List<String> destinations;  //10 elements
List<String> distances;    //100 elements

Per each origin there are 10 destinations and for this combination there are 10 distances. For example:

1 origin -> 10 destinations -> (0,10) distances
2 origin -> 10 destinations -> (10,20)distances

and so on until 10 origins and 100 destinations.

What data structure would be good for this scenario? I have tried to put them in a HashMap but I get not what I want.
I thought a tree might be a solution for this.

Also, is it possible to have as root a List<String> origins?



tree.jpg
[Thumbnail for tree.jpg]
 
Saloon Keeper
Posts: 6921
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Before I could answer I'd need a tutorial on your data. Why is everything a String? Is "distance" really a String? What establishes the relationships between these lists? What's an example of an "origin"? Are "origins" and "destinations" swapable? Is a distance a measure between an "origin" and a "destination"? How would you know which origin/destination pair? etc. etc.
 
Marin Capranov
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah, right. So, some more details:

List<String> distances is a list of distances extracted from distance matrix API. They can be parsed to double, that is not a problem.

The relation between them is that they all are from a distance matrix API. Origins are a list of origin places. The destination is a list of destinations from the origin point. The distances are between each origin and destinations. One origin has ten options of destinations, therefore 10 different distances. All the distances are already ordered, hence all I need is to take the first ten and add to the first origin and ten destinations, after that I take the next ten distances, which belong to the second origin and ten destinations, and so on. The origin and destination list are identical and have the same order. I thought to make it as a matrix. However, as the matrix is quite verbose and long. I want a Hashmap or Tree to make it less complex.
download.png
[Thumbnail for download.png]
 
Carey Brown
Saloon Keeper
Posts: 6921
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Very good.

Seems like a matrix would be a dirt simple way to manage this, with perhaps the addition of a hash map to look up the source/destination name to give you the row/column.

Another possibility is a hash map using "<origin>|<destinationn>" as a key with the distance as a value.

It's hard to suggest alternatives to a matrix without understanding how you need to access the data. What question are you trying to answer with the data? What inputs are you given? What outputs are expected?
 
Marin Capranov
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Right, I should've been more simple and say it since the beginning that what I am looking for is a matrix, so I can access the rows and columns when needed. For example:

I need the distances for the genetic algorithm to find the shortest route but on the other hand, I need the origins and destination of each particular distances to be printed out for clarity, from where to where are that distances.

I have implemented a 2d matrix[][] but it is returning only distances and if I want to use its origins and destinations I simply cannot, because they are not linked to origins and destinations. That's why I tried to implement a HashMap, but for some reason, I thought it is more like a tree to me.

Regarding -

Another possibility is a hash map using "<origin>|<destinationn>" as a key with the distance as a value.



How would you do that?

I will show you my implementation, which is not complete but could you adjust it so it does the matrix thing as you suggested?



 
Marshal
Posts: 67939
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Marin Capranov wrote:. . . distances extracted from distance matrix API. They can be parsed to double,

In that case they are not Strings. If they are doubles, use them as doubles, or in this situation, probably as Doubles.

. . . . I thought to make it as a matrix. . . . .

It may look as if Carey and I were being very fussy, but we know it is necessary to have your ideas clear before you try any coding.
You might find thigns much easier with a Distance class. Or maybe call it Journey. I think you can get the information straight out of that matrix. Or maybe a matrix is the best data structure, so it might only need copying. It all depends what you are going to do with it. What you are going to do should determine how you do it.
 
Carey Brown
Saloon Keeper
Posts: 6921
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

I need the distances for the genetic algorithm to find the shortest route


This is the meat of your task. Everything must be geared towards solving this.

So, assuming for the moment that you are using a matrix, what would be the pseudo code for solving this?

You want to go from point A to point B, possibly passing other points in between, in the shortest possible distance.

So look up the distance between A and B in the matrix, that should be the worst case scenario. Anything longer than that should be discarded. Anything shorter, and you should keep track of the shortest route.

Only when you are done finding the shortest route do you need to look up the String names for the points when you go to print out the route.
 
Marin Capranov
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are correct!

Is exactly how you said, I need to print out only after finding the shortest route, which I can do at the moment.
But how I look up for names if I only have distances?

I will show you the code I use for now to extract only the distances in a matrix form and pass them to a Distance.class from where they get processed further for the GA purpose.



Basically, that is why I need another data structure, because I can't add row and columns names to a 2d array, right?
 
Carey Brown
Saloon Keeper
Posts: 6921
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would envision it something like this:

A route would be a list of "points" where a point is designated by an integer that is an index into the columns of the matrix which we will consider as the destination. At the next go around this destination become the origin so you don't need to keep track of it twice. So you end up with a List<Integer> where the first entry is the initial starting point and the last entry is the final destination.

Then you have a List<String> names; to hold the point names in same  order as columns (and rows).
 
Carey Brown
Saloon Keeper
Posts: 6921
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note that  in your nested loop you'd want to skip over case where i==j. I haven't looked to see if this is the correct approach overall though.
 
Carey Brown
Saloon Keeper
Posts: 6921
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Are you familiar with writing recursive algorithms? It is the cleanest way to write genetic search algorithms that search every path combination (aside from the ones it determines that it can prune).
 
Saloon Keeper
Posts: 21710
148
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That doesn't look like a tree, it looks like a network.

In fact, this sounds like one of the classic problems in Graph Theory (travelling saleman) or some variant thereof. Which is a problem with no easy solution.

Since you are mandated to use a genetic algorithm to solve the problem, that means basically running over the graph repeatedly and recording best scores.

The individual nodes can be linked in a many-to-many relationship, so probably the best way to represent them is as a Set of user-defined object types ("g" nodes), where the primary properties of each object are its ID and a Set of ID/distance pair values, one for each connected sibling object. Alternatively, you could also define a link object that contains distance and the IDs of the 2 pairs that are connected, and link the "g" nodes to the links and vice versa.
 
Hey cool! They got a blimp! But I have a tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!