This week's book giveaway is in the Spring forum.
We're giving away four copies of Spring in Action (5th edition) and have Craig Walls on-line!
See this thread for details.
Win a copy of Spring in Action (5th edition) this week in the Spring forum!
  • 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
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

Doubts about the implementation of the visits of a graph implemented with adjacency lists  RSS feed

 
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone. I have to create a class that allows me to create and edit graph using adjacency lists. The graph should be oriented.
The specifications of the professor require that:

Create a Graph interface which defines the abstract data type graph. The graph must be defined on the nodes of a generic type V.

So I created the Graph interface, the SparseGraph class and the Edge class:








All methods have been tested and work properly.

Then the specifications of the professor ask me to do this:

You create an interface GraphSearch that declares the method void search(Graph<V> graph, V source, VertexAnalyser<V> analyser);. VertexAnalyser is an interface that declares the method void analyse(V vertex);.
The search method iterates over all vertices of the graph from vertex source and calls analyser.analyse(...) on each of them.
Realizing the BreadthFirstSearch and DepthFirstSearch class that implement algorithms breadth and depth.
Both classes must implement the interface GraphSearch.


So I created this class:









I understand how the breadth and depth visit works.
The classes are written right?
I do not understand what are all these interfaces. What should the method analyze()?

I thought about using this pseudo-code for breadth-first search:


I would put this code in the search method of the class BreadthFirstSearch.
But I do not understand what is the third parameter (VertexAnalyser<V> analyser). How should I use it?
I have the ideas a little confused...

Thank you very much.
 
Sheriff
Posts: 5448
147
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm not sure what the analyser method is. It may be something your prof is going to have to implement later.

Your pseudo-code looks good. Go ahead and implement it and post what you did.

Why all the interfaces? I suspect your prof is teaching you to code your classes to interfaces. Technically, you don't need an interface to implement a class. But if you get in the habit of coding to an interface, it can payoff later.
 
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Alcia,

long time no see

This professor of yours is not exactly making life easy.

This 'VertexAnalyser<V> analyser' will be a class that simply will do anything that
you want it to do. The only thing is that is has a given entrypoint (the method 'analyse'),
and from there you could do whatever analysis you want to do. It could be a simple
counter, that counts how many times it is called, and when it has a method that
returns this counter, then you know, for instance, how long a path is, given the
Vertex v that is a parameter in the 'seach' method. Or it could count the number of paths,
or it could detect loops in your Graph, whatever.

Now, the 'analyse' method has only one parameter,
a Vertex v, so the question is: does the implementing 'analyzer' class need access to the Graph to which
the parameter v belongs? Well, that is up to the one that implements the 'analyzer' interface.
If in doubt, just make a class that implements this interface, and simply does nothing
in the method 'analyse'.

My impression is that this whole collection of interfaces is rather vague. If you implement all of this,
then you have to invent a lot of other behaviour. I think your professor should give you some more clues.

Lastly, looking at the pseude code of the BFS, I have two remarks.

1) I wouldtn't put this code in the 'search' method. If you look at the specification of that method,
you see that it has a Vertex v as a parameter. So you should only do a BFS for this vertex, in stead
of looping through all you vertices in the graph. Of course, you could loop through all these vertices,
but then I would call 'seach' for each vertex in the graph, given that it has not yet been visited.

2) where in your pseudo code do you call the method 'analyze' of the analyzer class?

Greetz,
Piet
 
Alicia Perry
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello, sorry for the delay.
I wrote to the professor about the usefulness of the method analyze().
His answer was:

The method analyse() is the method that analyze nodes reached during the visit. What it means to 'analyze' is deliberately under-specified because it depends on the application that will use this method. For example, the method could be used to print to video nodes as that you meet them, or to calculate a statistic on an attribute of the nodes of the graph (for example, the average length of a string contained therein).
In this case I advice to use it for the test methods of the visit. By implementing analyze in a way that fits into an array nodes as they are visited then you can simply compare the array constructed in this way with the array containing the nodes in the expected order and verify that the two arrays are equal.


Mmm, ok, I didn't understand 100% what he mean.
Given the pseudocode written above, how should I call the method analyze()?

Thanks!
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Alicia Perry wrote:Given the pseudocode written above, how should I call the method analyze()?


Bad question, because it assumes that the pseudocode you (or someone else) wrote is correct. Take the preamble out, or add a condition to that effect, and it's fine.

It might also be worth mentioning that your prof's explanation of the analyse() method is a classic case of WhatNotHow (←click).
He (or she) knows WHAT it's supposed to do (and probably WHY it will be called), but leaves the implementation up to someone who knows HOW it needs to be done.

Code is nasty stuff; which is why we old farts leave it up to you young bods. It's generally verbose, brittle, difficult to change, and error-prone (unless you're good). A specification (or an interface), on the other hand...
Maybe that's why s/he is trying to get you into the habit of defining interfaces.

However, none of this addresses your basic question. Give me a while to look at your code (I arrived late to this thread), and I'll get back to you.

Winston
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:However, none of this addresses your basic question. Give me a while to look at your code (I arrived late to this thread), and I'll get back to you.


OK, I've had a chance to look it over quickly, and here's a few things:
1. I don't see a class that defines either a breadth() or depth() method, which would seem to be prerequisites for what you want to do.
2. Don't use names like 'bfs' (which, I assume, means "breadth-first search"), because they don't mean anything to the poor soul that has to read your code.
3. You seem to have piled all the stuff for (1) into your search() method - which might work, but it's a very "procedural" solution. Java is an object-oriented language, which means that we get objects (or classes) to do the work for us; NOT code.

Don't you think life would be a lot simpler if you could just provide your search() method with Graph objects that DO define breadth() and depth() methods? (if you're allowed to change the class)
And if you're not, why not define a Tree class that does? All you'd need to do is supply it with a Graph, and then do the required calculations. These are called "wrapper" (or sometimes 'Decorator') classes, since they "wrap" another class to provide functionality that it doesn't.

HIH, and good luck; and this is only an "initial look". If I see anything else, I'll post again.

Winston
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Winston
hmmm... you make it sound easy, that is if I understand you, and I'm not sure.
Are you referring to some generic class that enables you to do a BFS?
Well, I just remembered I wrote a generic BFS solver last year, just looked it up,
and I see this signature:

The idea was that you had vertices and edges in the form: T vertex, List<T> adjescents.
And although it worked, I would realy need some thorough rewriting to make it work
with Graphs, especially since edges are represented as separate objects. But then again,
I may misunderstand you completely.

@Alicia
what the professor told you about the analyzer, is what I expected, and I gave some
examples in my reply.
My idea is that it is fine to put the BFS algortihm in your search method.
The first part of your pseudocode is unneccessary:

Why would you iterate over all vertices of the Graph? The interface, and the
description, only says that this BFS needs to be done for some Vertex V, given as a
parameter of the search method.

The second part of your pseudocode look fine:


And if you implement the interface Analyzer, then do as the prof says: have a List<V> in that class,
and let the analyze method just add the vertex to the list. By looking at the list, you see exactly
what vertices you sent and in what sequence.
And in general, you don't need to worry about the analyzer interface. If someone wants to use
this framework, then that person has to come up with an implementation of that interface.

Greetz,
Piet
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Alicia
I've been thinking about my remark that it is unneccessary to iterate over all
vertices in the Graph. One goal to do it nevertheless could be to set up some
visited(v) structure for all possible v's.
What I was thinking was: can't you use, say, a LinkedHashSet for that purpose?
The advantages are that you do not need to create a visited(v) for all possible
v's, just for the encountered ones, and secondly, that you then also have a
structure that gives the exact sequence, by using its Iterator.
Just a thought.

@Winston
I think we could be in for a very interesting discussion here. However, I don't
want to flood Alicia's topic, so my question is: if you are interested, can you set up
a new topic, copying some of the replies to start with? I've been doing some thinking
abut why my beautiful generic BFS_solver is unsuitable for a Graph, and what
could be done to remedy this (well, big word).

Greetz,
Piet
 
Alicia Perry
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, I tried to implement the search method for the breadth-first search as recommended by Piet.



The compiler generates errors on assignments such as:
visited[v] = false;
parent[v] = null;


It's right that give these errors because it needs an int, not an object.
But how can I go back to the whole right?

I also created a class (VertexAnalyserImp) that implements the interface VertexAnalyser.


The method analyze is called in the search method but I don't think it is the right place.
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
<Grandpa Piet>
Promise to be always stubborn. If you say "A", and someone else says "O no, B",
then don't say "oh sorry, sorry, yes, B". Be critical, and if you think it is still A, just say (or
think) "Yeah, right, A it shall be". Of course, you may be wrong, but at least
it is YOUR mistake, and not somebody elses.
</Grandpa Piet>

hi Alicia,

I must say, I don't like your implementation. I have this to say:

1)
I quote from the specs you gave in your opening post:

"The search method iterates over all vertices of the graph from vertex source (...)"

Yet you iterate over all vertices nevertheless. You do not use the parameter "V source" at all.

Now, I don't like an interface method, where it is explicitly told what it should do, but that is
another story.

So, my conclusion would be that if someone is using this framework, and wants to iterate over all
vertices, in a BFS manner, then that one has to come up with a class in which this iteration
is taking place, calling, if desired, for every vertex v: BreadthFirstSearch.search(graph, v, analyzer).

2)
you have, as your first parameter in the search method, 'SparseGraph<V> graph'.
Now, SparseGraph is your implementation of Graph, but you must use the interface
'Graph' instead.

3)
can you explain what this 'parent' thing is? What is your intention for this?

4)

looks strange. Why can't you simply say:


5)
yes, boolean[] visited doesn't work

My idea was to use a LinkedHashSet<V> instead of some visited array.
Name that set something like "LinkedHashSet<V> visited'.
Every time you want to put a vertex v in your Queue, just check

and if it does, well, you know you already had that v.
And, if you're done, then the Iterator will give you the exact input
sequence back (as it were, ready to be compared to the list in
your Analyzer class )

So far my comments on your implementation. Think about it, and feel free
to disagree.

A final remark:

you end your reply with the sentence:

The method analyze is called in the search method but I don't think it is the right place.


I agree. I would call the analyze(v) method as soon as I pulled this v from the
Queue, so say at line 22 and a half.

Greetz,
Piet
 
Alicia Perry
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Piet, you're always very kind and patient.
Now it's too late to fix everything, I see tomorrow calmly..
Thank you
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:hmmm... you make it sound easy, that is if I understand you, and I'm not sure.
Are you referring to some generic class that enables you to do a BFS?


You're absolutely right.

@Alicia, my apologies. I was totally out to lunch on this one. That'll teach me to read a bit more next time.
I still say. however, that bfs() is not a great name for a method.

Winston
 
Marshal
Posts: 61753
193
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Moving as too difficult for the “beginning” forum.
 
Alicia Perry
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:however, that bfs() is not a great name for a method.


You're absolutely right! I used that name because it's the first one that came to my mind, but of course is not the best.

@Piet

1) You're right. Is the same thing that I thought. So I didn't understand how the search method must be used.
What sense does it iterate over the nodes of the graph from a node in particular?
(I think I did a very stupid question)

2) You're right about this too. Initially I used the Graph as a parameter (that is, as the specifications require that it be done the way) but the compiler generated an error that I honestly don't know how to solve if not putting SparseGraph.

3) I thought it was useful, whenever I reach a node, store as parent node the immediate parent of origin node. I don't need this thing?

4) I used parent = (V[]) new Object[graph.vertices.size()]; instead of parent = new V[graph.vertices.size()] because the compiler generates an error if I use the second statement. The error is: Error: Generic array creation.

5) Then, using LinkedHashSet<V>, instead of using a statement such as visited[v] = true should I use if(visited.contains(v))...?

I hope I have correctly understood your advice. Now I look better how the class LinkedHashSet<E> works.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Alicia Perry wrote:Now I look better how the class LinkedHashSet<E> works.


Good idea, but just very quickly: it's a HashSet that retains elements in the order they were added, which I suspect makes it ideal for your purposes, because contains() works in O(1) time, and you can also "pop" items out with its Iterator (also in O(1) time).

One thing I've noticed: You don't appear to have a Vertex class, which seems like a fairly major omission. Your current implementation appears to assume that values are the same thing as vertices, which would suggest that you can't add duplicate values to a Graph. Now that might be a reasonable assumption, but the fact is that vertices are not the same thing as values, even though they might contain them.
A Vertex is part of the structure of a Graph; a value isn't.

Adding a Vertex class may also let you add options to it that streamline some of your Graph processes. It also makes an Edge a pair of vertices (which accords with its definition), rather than a pair of values, which allows you to use a declaration like:

public class Edge<V extends Vertex<?>> { ...

HIH

Winston
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

Alicia Perry wrote:Now I look better how the class LinkedHashSet<E> works.


Good idea, but just very quickly: it's a HashSet that retains elements in the order they were added, which I suspect makes it ideal for your purposes, because contains() works in O(1) time, and you can also "pop" items out with its Iterator (also in O(1) time).


Exactly!

Winston Gutkowski wrote:One thing I've noticed: You don't appear to have a Vertex class, which seems like a fairly major omission. (...)


The type parameter <V> is the Vertex. It is left completely unspecified, so whatever class V you throw at it, it should work.
The terminology used is that of a Graph, therefore the names 'Vertex' and 'Edge'. But if you want to form a 'Graph' where
V = HashMap<String, LinkedHashSet<Boolean>>, no problem!

But indeed, I think a requirement for V is that it has proper 'equals' and 'hashCode' methods. Otherwise
the use of a HashSet is very dubious. But that should be put in the documentation of this framework.

And also, whether Edge(v1, v2) is equal to Edge(v2, v1), or even if Edge(v1, v1) is allowed, that is up to the
implementation of the interface 'Graph<V>'.

Many moons have passed since I followed a course on Graph theory, and I forgot all of it since,
I have the idea that I find this subject more interesting now, than I did then. Never too old to learn, I guess

Greetz,
Piet
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Alicia Perry wrote:

Winston Gutkowski wrote:however, that bfs() is not a great name for a method.


You're absolutely right! I used that name because it's the first one that came to my mind, but of course is not the best.

@Piet

1) You're right. Is the same thing that I thought. So I didn't understand how the search method must be used.
What sense does it iterate over the nodes of the graph from a node in particular?
(I think I did a very stupid question)



hi Alicia,

the two distinguishing adages of this site are:

- this is a friendly site
- there are no stupid questions, only stupid answers.

Suppose you have three vertices in your Graph, v1, v2 and v3, and the Edges (v1, v2) and (v1, v3).

Now, if you call 'search(v1), then the neighbours are v2 and v3, and so you iterate over the complete
set of vertices.
If you call 'search(v2)' on the other hand, then you will only iterate over the vertices v1 and v2. And that
is only when Edge(v1, v2) is equal to Edge(v2, v1).

Now, whether that is the case, depends on the implementation of 'Graph<V>'. See my previous reply to Winstonn.


2) You're right about this too. Initially I used the Graph as a parameter (that is, as the specifications require that it be done the way) but the compiler generated an error that I honestly don't know how to solve if not putting SparseGraph.


Without knowing what it is that you did, and what the error was, I can only guess what is causing this error. So, can you provide some details
what it is that you did and what error you got?

However, it gets a bit complicated. Let me repeat the specifications you supplied in your opening post:



Now, you see that your BFS class must implement the method 'void search(Graph<V> graph, V source, VertexAnalyser<V> analyser);'.
That means that it does not have to implement the interfaces 'Graph<V>' and VertexAnalyzer<V>'. You must only implement
the BFS and the DFS algortihms, and while doing so, you use the methods of the interfaces to get the neighbours and to call
'analyze(v)'.

Now, suppose that someone is going to use the BFS class. He/she then has to use the following invocation:

BFS.search(graph, v, analyzer)

where 'graph' is a comcrete implementation of the interface 'Graph<V>, for instance your class 'SparseGraph',
and analyzer is a concrete implementation of the VertexAnalyzer interface, like the one you supplied earlier.

So you see, you only give implementations of 'Graph' and 'VertexAnalyzer' at the very latest moment possible,

But I must admint, it really gets complicated, with all these interfaces!

And again, my interpretation could be completely wrong, so please think about it and let me know what you think.

Meanwhile, I'll be taking a short break, and I will come back a bit later.

Greetz,
Piet
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:The type parameter <V> is the Vertex. It is left completely unspecified, so whatever class V you throw at it, it should work.


Hmmm. That suggests to me then that it's a value, whereas most of the diagrams and texts that I've (now ) read suggest that a vertex is a node - ie, it's a structural component of a Graph.

Linked lists are also made up of nodes, and you define them as:
public class LinkedList<V> ...
but the 'V' there refers to the values held by its nodes, not the nodes themselves (TBH, Java's one actually uses 'E').

If there's really nothing useful you can add to a Vertex class, then maybe you could leave it out; but I suspect there might well be. It also enforces the terminology that anyone familiar with graphs is likely to use.

Winston
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Alicia Perry wrote:
3) I thought it was useful, whenever I reach a node, store as parent node the immediate parent of origin node. I don't need this thing?


Well, if you think it is useful, then a parent it shall be! But have you any idea what that 'parent' might be? The only relationship we have
in the Graph are the edges, and the vertices at the 'other' side of these edges will all be handled by the BFS and DFS.

Alicia Perry wrote:
4) I used parent = (V[]) new Object[graph.vertices.size()]; instead of parent = new V[graph.vertices.size()] because the compiler generates an error if I use the second statement. The error is: Error: Generic array creation.


Yes, you are right. I completely forgot about that rule on generic arrays... I guess I never encountered a situation
where I would need a generic array. A collection is far more natural.

But I still don't like the idea of using some fixed length array for that purpose. I much rather use some Collection or Map.
But let's figure that out when we know more about what this 'parent' is.

Alicia Perry wrote:
5) Then, using LinkedHashSet<V>, instead of using a statement such as visited[v] = true should I use if(visited.contains(v))...?


Yes. Of course, timing when to put a vertex v into that set is important, just as when to check for the presence of a vertex
in this Set. Think about where you would put this code.

Alicia Perry wrote:
I hope I have correctly understood your advice. Now I look better how the class LinkedHashSet<E> works.


Yes, it is very useful. Have you read the short description that Winston gave, especially why this data structure is very handy
in this situation?

Well, I think you can make a new version of the BFS. If I am correct, the code will be simpler than your first version.

So, enjoy!

Greetz,
Piet
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:(...) Linked lists are also made up of nodes, and you define them as:
public class LinkedList<V> ...
but the 'V' there refers to the values held by its nodes, not the nodes themselves (...)


Well, what is the importance of that? It's just an implementation aspect of the interface List.
Don't seek any particular meaniing behind the terms used. The only thing thaat matters is the
interface 'Graph'.

Do you want, in an implementation of Graph, something that looks like a Node of a LinkedList?
How about Node := Map<V, List<V>>? In this case, we do not need the 'Edge'. Two edges
like (v1, v2) and (v1, v3) are then represented as Map.Entry(v1, {v2, v3}).

Greetz,
Piet
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:Well, what is the importance of that? It's just an implementation aspect of the interface List.


Sure it is, but since most of this thread has been about implementation, it seems a reasonable point to make.

Suppose, instead of trying to represent a Graph as Lists of Edges and values, we actually include the "edges" in a Vertex? Viz:Now, as I say, it's been an awfully long time since I did any graph theory, so maybe it won't fly; but it sure seems like a reasonable alternative to me, and it's ONLY possible if you have a Vertex class.

And if it does fly, then maybe Edge becomes redundant (although I suspect not).

Hope I've made myself clearer.

Winston
 
Alicia Perry
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone

About the Vertex class... initially I wanted to create it but since that the specifications of professor says "The graph must be defined on the nodes of a generic type V" so I thought that the class Vertex was not necessary.
Honestly though, if I could create it, I would have created.. This is because not having a class Vertex, the nodes are identified only by their value so each node must have a different value. And I don't like it very much...

Piet Souris wrote:
Without knowing what it is that you did, and what the error was, I can only guess what is causing this error. So, can you provide some details
what it is that you did and what error you got?


I saw an error that the compiler does not actually generates. I apologize.
I have replaced the parameter SparseGraph with Graph.
SparseGraph is a class that implements Graph and provides some methods to create and edit graphs.
It was a required class so I created and tested. It seems to work.

Piet Souris wrote:
Yes, it is very useful. Have you read the short description that Winston gave, especially why this data structure is very handy
in this situation?


Yes, I will use that data structure.

Thanks Winston and thanks Piet!
 
Alicia Perry
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I rewrote the class in this way:



I then deleted the array visited and I created a LinkedHashSet.
However, the compiler generates this error:

error: cannot find symbol V s = graph.vertices.get(j);

symbol: variable vertices
location: variable graph of type Graph<V>
where V is a type-variable: V extends Object declared in class BreadthFirstSearch


I think it's due to the fact that the compiler search an object vertices in the Graph class but here there isn't.
If I remember correctly, in an interface can't be instantiated objects...
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Alicia,

yes, that looks very much better! And you see how much simplified the code is
compared to your previous version?

The error you get is caused by the fact that 'graph.vertices' does not exist.
If you look at the Graph interface, you see that it has the method 'Graph.vertices()',
returning an ArrayList of all the V's.
So, if you want to do this, you must use: (line 16)

But that would a waste of time: you already have your s!
See line 14:

But even worse, it is incorrect. To see that, suppose j = 0. We are talking about the first
V of listAd, and you are asking for the very first V of the complete list of all V's! And the chance
that these two V's are indeed the same, is: ... (about zero?).

So use in line 15 an extended for-loop:

and we're nearly done!
The nearly being: what was that again with this VertexAnalyzer?

Greetz,
Piet
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:
Sure it is, but since most of this thread has been about implementation (...).


Well, yes and no. Indeed, there's a lot of implementation, but the second part (starting
with the GraphSearch interface) is all about programming to the interfaces, as Knute
indicated.

Winston Gutkowski wrote:Suppose, instead of trying to represent a Graph as Lists of Edges and values, we actually include the "edges" in a Vertex?
(...)
but it sure seems like a reasonable alternative to me


It is more than a reasonable alternative, it is a very fine alternative.

What I especially like is the method

in which you can set the direction.

This aspect (direction) is what I have my doubts about. In line 1 of the opening post,
you see that the Graph must be directed. However, nothing in the interface forces this,
so it leaves this aspect to the implementation. In Alicia's case, it could be done in the Edge class,
or it could be done in the Sparseraph class. In the last case, and in your class,
(V1, V2) = (V2, V1) IIF both edges exist, or V2 is endpoit of V1 AND V1 is endpoint of V2.

Winston Gutkowski wrote:, and it's ONLY possible if you have a Vertex class.


What is the 'it' in your statement?

Winston Gutkowski wrote:
And if it does fly, then maybe Edge becomes redundant (although I suspect not).


I suspect it does. If you want to know all the edges of a given vertex T, then you just return the endpoints
of T, and you have a method for that, You call them 'endpoints', Alicia calls them 'neighbors'.

And I do sincerely hope that I understood everything correctly!

Winston Gutkowski wrote:Hope I've made myself clearer.

Winston


You sure have. If I look at Alicia's 'Graph' interface, then it would be pretty easy
to implement a Graph with this class.

Greetz,
Piet
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:It is more than a reasonable alternative, it is a very fine alternative.


Thanks.

What I especially like is the method
public void connect(Vertex<T> endpoint, boolean directed)
in which you can set the direction.


I thought you might. I was quite pleased when it occurred to me too, because it allows you to create a directed link without enforcing it. That's the Graph's job, not a Vertex's.

This aspect (direction) is what I have my doubts about...


Which is why I suspect that an Edge is not necessarily redundant. You still have to "build up" a Graph somehow, by supplying a List of values (which get converted to Vertexes), and a list of connections between those values. I see no reason why you shouldn't just be able to supply those as Edges, using the class that Alicia has already written (with a couple of alterations).

Suppose that an Edge:
1. Has 'start' and 'end' values (as opposed to v1 and v2).
2. Has a "directed" field (as I think you suggested earlier).
3. Is "equal" to another Edge if it's 'start' and 'end' values are the same as another Edge's in any combination.
ie: Edge(a, b).equals(Edge(b, a)) returns 'true'.
For consistency, you would probably want to make the hashCode() for such an Edge == hash(a) + hash(b).

That would allow a Graph to disallow two specifications for the same endpoints by simply putting the supplied Edges in a Set, while at the same time allowing connections to be directed (1-way) or undirected (2-way). And if the Graph is "directed", then all Edges supplied to it have to be "directed". Whether or not you allow mixtures of directed and undirected Edges for a Graph that isn't would be up to you.

Furthermore, if you also store those Edges in a "multimap", ie:
Map<V, List<Edge<V>>> edgesByEndpoint ...     (where 'V' is the end-point of the Edge)
it should be a simple matter to get all startpoints for a given endpoint.

The main problem with Vertex is that it's a "navigation" class. It's easy to find the "neighbours", or the "tree" for a Vertex, but it's quite tough to find the list of vertices connected to it (specifically, directed connections).
Now I don't know if that is, in fact, a problem or not; but if you need it, a Map of Edges as described above would certainly make it possible.

The "contents" of your Graph then becomes something like:
private Map<V, Vertex<V>> vertices;
private Set<Edge<V>> edges;

and optionally:
private Map<V, List<Edge<V>>> edgesByEndpoint;

And I do sincerely hope that I understood everything correctly!


Looks like it. If not, I should have documented/explained it better.

Winston
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:What is the 'it' in your statement?


Missed that one. The 'it' basically refers to flexibility:

If you have a Vertex class, then you can use it to define the structure of your Graph. If you simply have values, then you're pretty much forced to do everything internal procedurally.

Now if it turns out that a Vertex is simply a container for a value and nothing else, then maybe you can remove it; but (as I've hopefully illustrated) I suspect that's not the case. Indeed, I suspect that your "breadth-first" and "depth-first" algorithms could simply be part of the Vertex class (although they certainly don't have to be).

It's basically a "level of indirection", which good old David Wheeler told us are generally good for solving problems.

Winston
 
Alicia Perry
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone, I changed again the search method and I have tested it.
Now it works. I must say that I'm learning a lot reading your comments. Thank you!
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Winston,

you're my favorite person I'd love to 'agree to disagree', but now I'd say: let's agree to agree.

Your Vertex class would be an excellent building block for a Graph. Most of the Graph's methods
could directly be forwarded to the relevant Vertex.

The really great thing about assignments like these is that it is an excellent opportunity
to put your phantasy at work, and also to implement the ideas any way you like. There's no
Company that sets you up with tons of "Business Requirements" and no wolfpacks
of "Reviewers" that demand of you to give the 'impact' of whatever decision you made and
depending on the shortcomings, stamp it as High Gap, Medium or Low

So one nice addition to class 'Vertex' would be the 'state' of a Vertex. For instance, an energy
distribution center just got burned down to the floor, taking it out for some time.
Now, what would that mean for the paths in your Graph? Do some vertices get isolated?
Of course the theory is well known (not by me), and there's expensive software
around that deals with every possible sort of Graph that can do whatever you
want it to do, but let that not marr our enjoy.

I like Alicia's implementation for its simplicity. I like yours for the fine 'Vertex' class,
and now I'm wondering what I would have done. Well, I'm not gonna tell,
for otherwise people could instantly tell I'm just an old guy who hasn't got a clue
what he's talking about. (I'm a lot older than you, 58).

Greetz,
Piet

 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Alicia Perry wrote:Hello everyone, I changed again the search method and I have tested it.
Now it works. I must say that I'm learning a lot reading your comments. Thank you!


Congratulations! And I'm glad all this "esoteric" stuff is helping.

Basically, what Piet and I have been going through is the business of WhatNotHow. My first post was basically out-to-lunch because I didn't understand what was required. Now that I've read (and re-remembered ) a bit, I think I'm probably on the right track.

And notice that I was able to say that you seemed to be lacking a Vertex class without any idea of how it was supposed to work, simply by reading the requirements for a Graph on Wiki. All of them mention "vertices", not values, or types, which I took to mean that a "vertex" was probably a fairly important component of a Graph.

The "how" part was part of my next post, and it was only a suggestion; I suspect there are many ways to implement it.

HIH

Winston
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Alicia Perry wrote:Hello everyone, I changed again the search method and I have tested it.
Now it works. I must say that I'm learning a lot reading your comments. Thank you!



hi Alicia,
love to hear this. Well done! Can you let us know what the professor thinks of it?

And, as you can infer from all the comments, we enjoyed it very much and learned a lot too!

Greetz,
Piet
 
Rancher
Posts: 1090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:
And, as you can infer from all the comments, we enjoyed it very much and learned a lot too!



Me too. I have loved reading every post in this thread. There was something to be learned from every post. Your last post too, Piet.

Thank you.

 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:you're my favorite person I'd love to 'agree to disagree', but now I'd say: let's agree to agree.


Hey, I think I've said it before, if everybody agreed with me, I'd have been out of this business long ago.
Good solutions usually come about by healthy discussion, not from one person's input.

Your Vertex class would be an excellent building block for a Graph. Most of the Graph's methods could directly be forwarded to the relevant Vertex.


And, as I said above, I got it from the description, not because I knew it would be useful. That came later.

The really great thing about assignments like these is that it is an excellent opportunity to put your phantasy at work, and also to implement the ideas any way you like. There's no Company that sets you up with tons of "Business Requirements" and no wolfpacks of "Reviewers" that demand of you to give the 'impact' of whatever decision you made and depending on the shortcomings, stamp it as High Gap, Medium or Low


Totally agree, and (@Alicia) I'd say that your prof's explanation of the analyse() method makes him a good egg. He's not spoon-feeding you, and he wants you to think about what you're doing and, when you've finally sorted that out, how to get it done in Java.

So one nice addition to class 'Vertex' would be the 'state' of a Vertex.


I think you'll have to explain that one to me in a bit more detail. A Vertex is simply a "node" that knows about its neighbours (ie, links that radiate "out" from it), and I've also assumed that they can't be removed.

You could, I suppose, expand it to include "incoming" links in a separate List (which would obviate the need for the optional Map), but it adds complexity without much benefit that I can see, beyond being able to determine if a Vertex is "isolated".

Now, if you need a modifiable Graph that allows you to remove edges and/or vertices, then it makes a lot of sense. Perhaps a ModifiableVertex subclass?

I like Alicia's implementation for its simplicity. I like yours for the fine 'Vertex' class, and now I'm wondering what I would have done. Well, I'm not gonna tell, for otherwise people could instantly tell I'm just an old guy who hasn't got a clue what he's talking about. (I'm a lot older than you, 58).


ONE year is a lot? And I think you're being overmodest: this thread has taught me a lot too.

Winston
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:You could, I suppose, expand it to include "incoming" links in a separate List (which would obviate the need for the optional Map), but it adds complexity without much benefit that I can see, beyond being able to determine if a Vertex is "isolated".


Actually, I take that all back. I think it might well be very useful, since a Graph may well be built by puny humans, who might supply an insufficient set of edges to connect every vertex.

So, for the benefit of Alicia: Piet is quite right (and not for the first time). And the update to my class would look something like this:and now you don't need the optional Map I suggested before.

Winston
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Chan Ag wrote:Me too. I have loved reading every post in this thread. There was something to be learned from every post. Your last post too, Piet.

Thank you.


Chan,

and thank you for this lovely reply. It really makes me blush.

Greetz,
Piet
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@ Winston,

well, it is not quite what I had in mind, but that is of no importance.
Far more important is that you see what I wrote about:
using your imagination, and coming up with new ideas and implementations: no one to stop you and it is great fun!

So you see what a fine Abstract Data Structure a Graph is. You would
never spend so much time on, say, the ArrayList.

Greetz,
Piet

 
Alicia Perry
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:
hi Alicia,
love to hear this. Well done! Can you let us know what the professor thinks of it?



Yes, of course!

@Winston Is absolutely true what is written in WhatNotHow. I hope I can improve from this point of view. I program since only a couple of years and the problem is that for learning to program well I need a lot of desire and a lot of time available.
Often lack the time (and unfortunately when you are tired it also lacks the desire).
Especially when professors assign homework shall be carried out in a short time, what happens is that you want to get the solution up and running quickly, without thinking of how it works and if it's powerful and elegant.
Then I don't like having too restrictive specifications to be respected because I don't think they're useful.

However, I'm realizing how important it is to think before you write the code: you will save much time and the generated code is more elegant and clean.

So, thank you very much for your help.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Alicia Perry wrote:@Winston Is absolutely true what is written in WhatNotHow. I hope I can improve from this point of view [...] professors assign homework shall be carried out in a short time, what happens is that you want to get the solution up and running quickly, without thinking of how it works and if it's powerful and elegant.
However, I'm realizing how important it is to think before you write the code: you will save much time and the generated code is more elegant and clean.
So, thank you very much for your help.


You're most welcome. And don't worry: learning - and more importantly, getting into the habit of thinking about - "what not how" is hard, especially when you're in an intense learning situation. You're being bombarded with new stuff all the time, and there's a tendency to want to see it in action in code.

We puny humans also tend to think procedurally ("OK, to get this problem solved, I need to do this, then this, then this...") and for simple stuff it works just fine. However, as I suspect you're realising, when you're given a task as complex (and, as Piet says, abstract) as a Graph, that approach tends to break down. In something like a BFS search you have several things that have to work together - at the very least, a set of vertices and a queue to store them in - and trying to plough through the logic sequentially can end up tying you in mental knots.

For example, I still find recursion tough, even after 35+ years; but what I'm better at now (mostly through experience) is understanding when it might be useful.

All I can say is: it will come, and as the problems you face get harder (and they will ) you'll find more and more benefit in thinking first. It may seem like it adds to the time, but in fact it probably doesn't, since the coding process simply becomes one of translating what you already know into Java; and that process is usually much quicker and less error-prone than when you starting coding immediately.

And I have no doubt that you'll be a fine programmer one of these days.

Winston
 
Campbell Ritchie
Marshal
Posts: 61753
193
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Are you trying to understand recursion? I gave up trying to understand it ages ago. It just seems to work!
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!