Arraylists of arraylist as a representation of relationships

[Kovacs Akos]

I have several values, like this: (Elements in a row are in relationship.)

x1 26 y1 287 x2 154 y2 303
x1 22 y1 114 x2 115 y2 185
x1 26 y1 287 x2 375 y2 338
x1 26 y1 287 x2 260 y2 393
x1 115 y1 185 x2 121 y2 7
x1 200 y1 101 x2 392 y2 238
x1 99 y1 394 x2 375 y2 338
x1 99 y1 394 x2 121 y2 7
x1 274 y1 28 x2 22 y2 114
x1 296 y1 185 x2 200 y2 101
x1 115 y1 185 x2 154 y2 303

I should find all the values which are in relationship and put them into a list, like this: [26,287 154,303 375,338 260,393] I have tried to use this code:

   for(int i=0; i<vertexnum; i++){
        adjLists.add(new ArrayList<Integer>());
    }

    for(int j=0; j<vertexnum; j++) {
        for (Point p : nodes) {
            for (Edge e : edges) {
                    adjLists.get(j).add(e.p1.x);
                    adjLists.get(j).add(e.p1.y);
                    adjLists.get(j).add(0);

                    adjLists.get(j).add(e.p2.x);
                    adjLists.get(j).add(e.p2.y);
                    adjLists.get(j).add(0);
                for (Point p1 : nodes) {
                    for (Edge e1 : edges) {
                        if (e1.p1.x == e.p1.x && e1.p1.y == e.p1.y && !adjLists.get(j).contains(e1.p2.x) && !adjLists.get(j).contains(e1.p2.y)) {
                            adjLists.get(j).add(e1.p2.x);
                            adjLists.get(j).add(e1.p2.y);
                            adjLists.get(j).add(0);

                        } else if(e1.p2.x == e.p1.x && e1.p2.y == e.p1.y && !adjLists.contains(e1.p1.x) && !adjLists.contains(e1.p1.y)){
                            adjLists.get(j).add(e1.p1.x);
                            adjLists.get(j).add(e1.p1.y);
                            adjLists.get(j).add(0);
                        }
                    }
                }

            }
        }
    }

It creates only one arraylist, it gives all elements in a row intead of separating. I have tried debugging, but I can not see what causes this.

[Junilu Lacar]

Forgive my honesty but the code you give here is a mess. Reading it is like watching somebody run around randomly and waving their arms without a clear purpose. All I can make out is that you have some points and you have some edges and a point has an x and y attribute and an edge has a p1 and p2 attribute. The code hides its true intent with all these loops (running around) and gets, adds, and contains (random waving of arms).

Can you tell us with a simple statement, one that doesn't mention loops and gets and whatever else programming mechanism you are thinking of using, what you are really trying to accomplish? Something like: "I have these points and edges and I need to... (do what?)"

[Kovacs Akos]

This code is to make adjacency lists for each vertices with use of given coordinates.
This should be the arraylist of the first vertex:

[26,287 154,303 375,338 260,393]

So it should it search for each row's first element in the lists and collect them in another list, that you can see above.

[Junilu Lacar]

So do you need to have a list of integers or a list of points? Your representation looks like you're trying to get a list of points:
list: [ point(26, 287), point(154, 303), point(375, 338), point(260, 393), ... ]
To just have a list of integers doesn't make a whole lot of sense to me. Also, a list won't really organize its elements the way you seem to want them to be organized.

[Junilu Lacar]

Can you explain to us why those first two points, (26, 287) and (154, 303), which appear to be the endpoints of the first edge, are supposed to be related to the points (375, 338) and (260, 393), which are the end points of the third and fourth edges, respectively?

[Kovacs Akos]

It should be an adjacency list, so it store all the other points, those are connected with the first point.

If it possible I would like to create a list of points(and flags, after all x and y values should be an integer), but a list of integers is also good, but a bit harder to refer to elements.

[Piet Souris]

hi Kovacs,

a HashMap<Point, ArrayList<Point>> is pretty standard for an adjacency table.
Is there a compelling reason why you want an ArrayList of ArrayLists?

Greetz,
Piet

[Kovacs Akos]

No, no reason, I have not found Java implementation for an adjacency. It looks not too easy to implement.

[Piet Souris]

If I look at the first file in your opening post, I see that each line
contains two points, being the vertices of an edge (correct me if I'm wrong).

So, if you read in a line, create the two points P1 and P2.
Now, if P1 is not already a key of the HashMap, then create an
ArrayList<Point> A, add P2 to it and put the pair (P1, A) into
the hashmap.

If P1 is already present as a key, then add P2 to the corresponding
arraylist. And if you have an undirected graph, don't forget
to put P2 as a key too, and P1 to its corresponding ArrayList.

It should now not be so difficult to create lists of all the paths that you
are interested in.

Greetz,
Piet

[Kovacs Akos]

What does HashMap mean?
How to implement, what is difference between my code and this? I have thought, that my code make the same thing, that you describe.

[Piet Souris]

To be frank, I'm with Junilu here. I do not understand your code.

The HashMap that I proposed, makes things very much easier. In short,
a HashMap is a list of Key, Value pairs. In this case, it would be a list
of <Point, ArrayList<Point>> pairs. Each point P has in this HashMap
a corresponding Value, being an ArrayList of Points.

A HashMap is just a standard Java class. If you want, you can read the
API, or read the Oracle tutorial on Collections

(https://docs.oracle.com/javase/tutorial/collections/interfaces/map.html)

It is possible that your code creates a similar structure. If you want us to help you
with that, then you must explain in much more detail what your code is doing, especially
the very nested for-part. Tell us also what you have tested so far, and
how you did that. What were your outcomes?

Greetz,
Piet

[Junilu Lacar]

Kovacs Akos wrote:It should be an adjacency list, so it store all the other points, those are connected with the first point.

If it possible I would like to create a list of points(and flags, after all x and y values should be an integer), but a list of integers is also good, but a bit harder to refer to elements.

The first sentence is actually a good start. In the second sentence, you go deep down to the unfathomable again, so we'll ignore that for now.

Ok, so you want to get an adjacency list. And you want that list to include points that are connected to the first point. For example, given an edge with points (26, 287) and (154, 303), you want to find other points that are adjacent to the first point of that edge, (26, 287). Is that right?

How do you determine whether or not other points are adjacent? And why specifically are you using the first point as the reference? How do come to conclude that points (275, 338) and (260, 393) are adjacent to (26, 287)?

The answers to these questions are hidden somewhere in all those for-loops that you wrote and it's not very clear how you are trying to arrive at the results that you are expecting. You need to clarify things first.

[Junilu Lacar]

Maybe this will give you an idea of what I'm trying to get from you:
Main Task: Building an Adjacency List 1. Given a set of points and edges 2. Get the first edge. 3. Get the first point on that edge. 4. Using this first point as the reference, find other edges that are adjacent (see subtask below). 5. Add the adjacent points you found to a list. This list will be the adjacency list for the point in #3. 6. ... ... and so on N. Now you have built your Adjacency List for all relevant points. --------- Sub-Task: Finding edges that are adjacent to a given reference point. 1. Given a reference point and a set of edges that may or may not be adjacent to it. 2. ... (now what do I do?) ... and so on N. Now you have found all the points adjacent to the reference point
This is just an example -- I don't know if this is what you actually need. But see how I don't talk about any kind of Java language construct, except maybe List but that's in a very general way. I do break down the procedure into small steps and they are very detailed. This is what you need to guide you in writing the program. Now give it a try and see if you can come up with a similar list of instructions for solving your problem.

[Kovacs Akos]

So, a full output:
Relationship table:

x1 357 y1 92 x2 150 y2 353
x1 150 y1 353 x2 289 y2 325
x1 357 y1 92 x2 306 y2 204
x1 306 y1 204 x2 80 y2 257
x1 289 y1 325 x2 180 y2 164
x1 180 y1 164 x2 289 y2 325
x1 180 y1 164 x2 357 y2 92
x1 390 y1 331 x2 289 y2 325
x1 180 y1 164 x2 306 y2 204
x1 306 y1 204 x2 180 y2 164

Output of my code:
[357, 92, 0, 150, 353, 0, 306, 204, 0, 180, 164, 0, 180, 164, 0, 180, 164, 0, 180, 164, 0, 180, 164, 0, 180, 164, 0, 180, 164, 0, 150, 353, 0, 289, 325, 0, 357, 92, 0, 357, 92, 0, 357, 92, 0, 357, 92, 0, 357, 92, 0, 357, 92, 0, 357, 92, 0, 180, 164, 0, 180, 164, 0, 180, 164, 0, 180, 164, 0, 180, 164, 0]

Bold section is a great output, this should be in an arraylist without the other numbers.
It should be done with some method all of the vertices in the given table. BUT all vertices and his neighbors in a separated arraylist.
I have tried to write out several variables with system.out, but I can't found the reason of this malfunction. I do not know how to code to close a list then start a new one with the first 2 elements of the second line.

[Piet Souris]

Hmm... time for a decision.

My strategy is to persuade Kovacs into the use of a HashMap, since whatever he
intends to do with his vertices and points, a HashMap will greatly simplify it.
Even if it means to do some study of Maps.
HashMaps are very common for adjacency tables, and for a good reason.

Junilu's strategy is getting Kovacs method correct, in a way that we have
come to know from him. As always, it'll be very interesting.

So I will step back now.

Greetz,
Piet

[Junilu Lacar]

I admit, Piet, that my way may be a much longer route. And it may not be a route that Kovacs is willing to follow right now. So let's just see where he goes. I get the feeling that he's leaning towards following your lead instead of mine. I will not be offended at all if Kovacs decides to go your way, which is fine. To each his own way of learning.

Edit: I will say this though (tongue firmly planted in cheek): I believe the answer is, of course, 42

[Piet Souris]

hi Junilu,

well. it is up to Kovacs of course, but I got the impression that he
likes to stick to his own code. And rightly so, me thinks. He has put
a lot of effort into it, and the biggest reward he can get is to get it up
and running. And to help him with that, I cannot think of anyone
better suited for the job than you.

So, please go ahead.

Greetz,
Piet

[Junilu Lacar]

Well then I must wax philosophical with you guys. It is almost always the wrong thing to do to not want to throw away code because you already spent a lot of time on it. That's like not wanting to throw out a dirty, soiled blanket because you've slept with it for most of your life. Or not wanting to throw an old car in the junkyard because you have driven it for past 27 years.

You have to become emotionally detached from your code. It's called software for a reason and the biggest, most important part of the software is not in the computer: it's in between your ears.

[Kovacs Akos]

When I have to throw away my code I can do this.
So I have started to work with Piet's method... I defined necessary variables to store values, but I've stucked at a point.
How to identify source and deatination. These depends on 2 values, x-y coordinates. Source is only one for each lists.

    private Map<Integer, List<Integer>> Adjacency_List;

    public GraphAdjacencyList(vertexnum)
    {
        Adjacency_List = new HashMap<Integer, List<Integer>>();
        for (int i = 1 ; i <= vertexnum ; i++)
        {
            Adjacency_List.put(i, new LinkedList<Integer>());
        }
    }


    public void setEdge(int source , int destination)
    {
        List<Integer> slist = Adjacency_List.get(source);
        slist.add(destination);
        List<Integer> dlist = Adjacency_List.get(destination);
        dlist.add(source);
    }

[Piet Souris]

hi Kovacs,

first of all: how would you describe your vertices? Are they simply integers, are they Points
with x and y coordinates? Or anything else?

If 'T' is the type of a vertex, then we will be using a Map<T, ArrayList<T>>.
From your opening post, I had the impression that a vertex was indeed a Point,
but specifying a vertex by a simple integer is of course good enough.

The idea is that we have a Map<T, ArrayList<T>> map, containing all the data that
we have about the graph. T being the type of a vertex. Let's assume that T is an Integer,
so we indicate the vertices simply by a sequential number.

Now, if we wnat to know if a certain integer I is in our graph, then all we have to do
is to call the method: graph.containsKey(I), and we get a boolean true or false, depending on
whether this I is in our graph or not.

If I is indeed a vertex, and we want to know the adjacent vertices, then all that is necessary
is to call the method: graph.get(I). We then have an ArrayList containing all the adjacent vertices.
And that is what makes a Map a fine structure for graphs.

Now, how do we create this graph in the first place?

You have a class 'GraphAdjacencyList', and you showed us the constructor. That looks fine.

Then, I see a method 'setEdge'. That looks fine too. We have two integers, the vertices of an edge,
and so we add the pair (source, destination) and (destination, source) into the map.
This means an undirected graph,

So far, so good, I would say.

How to identify source and deatination. These depends on 2 values, x-y coordinates. Source is only one for each lists.

And here I'm not sure what you mean. So far, I considered a vertex to be just an integer. But
you are talking about x-y coordinates. Do you mean that a vertex is indeed a Point?
It doesn't change much though, we need to define the map as Map<Point, List<Point>>, and we need to
adjust the constructor and the setEdge accordingly.

So, make your choice. After that, let's see how to fill the map with the available data.
If you already know how to do this, then go ahead.

Greetz,
Piet

[Kovacs Akos]

Maybe I partly get it! Yes, a vertex is a Point(given x-y coordinates).

    public Map<Point, List<Point>> Adjacency_List;


        for (int i = 1; i <= vertexnum; i++){
            Adjacency_List.put(e.p1.x, e1.p2.x, new LinkedList<Point>());
        }

        for (Edge e : edges) {
            if (e.p1.x > Adjacency_List.size() || e.p2.x > Adjacency_List.size()) {
                System.out.println("the vertex entered in not present ");

            }
            List<Point> slist = Adjacency_List.get(e.p1.x, e.p2.x);
            slist.add(e.p2.x);
            List<Integer> dlist = Adjacency_List.get(e.p2.x);
            dlist.add(e.p1.x);
        }

All the code is in a specified method now. BUT it gives always errors, because I think I should ude two values, the two coordinates of a point in every get() and add().

[Kovacs Akos]

Please provide some code snippets. It is only the base of this application and I am working with this problem since a week and have only plus 20 days to finish the whole. It is a really big problem for me. Thanks in advance!

[Piet Souris]

hi Kovacs,

if you are working with a HashMap, you do not need to worry about sizes. So these lines:

for (int i = 1; i <= vertexnum; i++){
        Adjacency_List.put(e.p1.x, e1.p2.x, new LinkedList<Point>());

are unnecessary!

Suppose we have the coordinates x1,y1 and x2,y2. We can then create two Points:

Point p1 = new Point(x1, y1);
Point p2 = new Point(x2, y2);

we also have your map:

private Map<Point, ArrayList<Point>> adjacencyList = new HashMap<>();
// I use a small letter as the first letter. This is Java-convention

Now. let's store the two points in this map. It goes like this:

ArrayList<Point> al = adjecencyList.get(p1); if (al == null) { // p1 is not present in the map; we create a new ArrayList al = new ArrayList<>(); // we put p2 in it al.add(p2); // and now, store the pair (p1, al) into the map adjacencyList.put(p1, al); } else { // well, if we are here, then al was not null. So, p1 was // already present. All we need to do is is to store p2 // in the arraylist al al.add(p2); } // and done! // Question is now: is adjacencyList an undirected graph? If so, // we also need to put the pair (p2, p1) into the map // That means we have to follow the same procedure as above, // only with p1 and p2 exchanged. Can you do that? // And if we have a directed graph, then of course we do not do // this at all. // // final note: the above procedure can be done a bit more handy // than I showed here, but that's another story.

Now, in your opening post, you show a list with many x1 y1 x2 and y2 values.
From each line, we can derive two points p1 and p2, and apply the above
procedure to the points p1 and p2.

If you want to have all adjecent points to point p1, then all that's needed is
a simple call:

ArrayList<Point> list = adjacencyList.get(p1);

See if you can fill the complete map now.

Greetz,
Piet

[Kovacs Akos]

Thanks a lot for your help Piet! I can continue work with your helpful, detailed post!

[Piet Souris]

You're welcome!