hash table chaining

[chris896]

Hi, i have a project where i should read an input.txt that contains a x node, the neighboor y and the weight w of the connecting line in the graph... so i should insert(with a function INSERT_LINK(int x,int y,int w) ) all the x in a hash table and connect them with their y neighboors with chains (in order). Also i should creat a function DELETE_LINK(int x,int y) and use the prim algorithm to find the mintree. But the user can't give the orders, i should creat a command.txt where i will write the commands... can anyone help me ?? It's a very important project for me, i need your help !!

[Duthomhas]

I'm not sure why you need a hash table. Do your nodes have names attached to them?

What "orders" do you need to process other than "this is the input tree's edges"?

Can you provide more information about what exactly you are trying to accomplish?

[chris896]

Sorry if you didn't understand, i must admit that i can't explain my project in english also i am a beginner in c++... but i have a picture that may give you a idea for what i am trying to accomplish. The input that i mentioned contains the edges of the graph and the weight of the connecting lines...


x->y
|_|
|3|->|1|->|2|->|4|
|_|
|_|
|4|->|1|->|2|->|3|
|_|
|_|


there is the hash table with chains

[Duthomhas]

I understand hash tables.

A hash table is used to store some small collection of values where each value may be relatively large, such as the following list: { 1, 19, 72, 312 }. In other words, the value itself cannot be used as an index into the list of values, because it would be too big. (312 cannot be an index into 20 items.)

A graph has sequentially numbered nodes, like { 0, 1, 2, 3, ... }, so you will always need exactly as many elements as there are nodes in the graph. With the convenient 1:1 ratio, this suggests an array lookup. A graph array should then be:

x->y
|0|
|1|
|2|
|3|->|1|->|2|->|4|
|4|->|1|->|2|->|3|


That said, you are telling me that you are required to hash the node number given you from the input file. That's fine. I have no problem with that. But you still haven't answered my other two questions:

What "orders" do you need to process other than "this is the input tree's edges"?

Can you provide more information about what exactly you are trying to accomplish?

Can you give an example of your input files? And your desired output from using them?


In terms of the table itself, you only need a hash function to place your u nodes in the table, and the table should just be pointers to your data (u,v)=w.

struct node
{
  int v;
  int w;
  node* next;

  node( int v, int w, node* next = nullptr ): v(v), w(w), next(next) { }
};

node* table[ 100 ] = { nullptr };

To find a u in the table, just use your hash function:

int i = hash( u );
for (node* p = table[ i ]; p; p = p->next)
{
  cout << "(" << u << "," << p->v << ")=" << p->w << "\n";
}

Your assignment is to be able to INSERT and DELETE nodes from a link chain. (This is a linked list, where the HEAD pointers are the elements of the TABLE.)


Is this where you are stuck?

[chris896]

Yes i understood what you are saying about the graph, the elements of the the table will be only the nodes of the graph (1,2,3,4,...). The assignment ask us to make a input.txt, i suppose it will be something like that :
x y w

1 2 10
1 3 4
3 1 6 ....

The orders will be readen from a commands.txt ( i can't imagine how i will accomplish that).

The assignment asks :

Creat the table, use a hash function and hashing by open adress to find the edge. The neighboors will be stored in a linked list. The size of the table is 2*N (N= number of edges).

The functions that i should accomplish are :
1) Find the minimum tree by using the prim algorithm (MST order)
2)Find the number of the same neighboors from two different edges (NCN order)
all these orders should be readen from the commands.txt:
[ READ_DATA input.txt
INSERT_LINK x y w
DELETE_LINK x y
MST NCN x y ]

In the output.txt only MST and NCT will write. When we find the MST order, we write the cost of the minimun tree and the time it took to find the tree, when we find the NCN we write the number of the same neighboors(as i said before).

This is exactly the assignment, i tried to translate it... as i mentioned i am a very beginner and i find too difficult this project but i can't pass the exams without it so i am trying very hard. I really appreciate your help !!

[Duthomhas]

This is by no means a beginner's homework. ¿Hablas español? Do you have a link to the actual assignment that I could look at? (Even if it is a language other than English or Spanish.)

Handling the commands.txt file looks really simple: just use cin >> s to get the next word of input and then some if else statements to look for one of the command names. When found, cin the correct values and call a function to do it. Put it all in a loop and quit when cin fails for any reason.

Sorry this isn't a quick and simple answer. Don't give up!

[chris896]

It is greek... can you give me a code for reading all edges from the input ? I should read the orders from the commands and use the functions, how i could do that ? I would be pleased if i managed to do at least this part of the project !


Περιγραφή
Στο δεύτερο μέρος της εργασίας, που αποτελεί επέκταση του πρώτου, θα ασχοληθούμε με ουρές
προτεραιότητας, κατακερματισμό και γραφήματα. Και πάλι θα πρέπει να μπορείτε να διαβάζετε ένα αρχείο
input.txt που περιέχει τις συνδέσεις μεταξύ κόμβων όπως και στην πρώτη εργασία. Βασική διαφορά είναι ότι
τώρα το γράφημα θεωρούμε ότι είναι μή κατευθυνόμενο και ότι σε κάθε ακμή υπάρχει και ένα βάρος που
δηλώνει το κόστος της ακμής. Έτσι, το αρχείο input.txt περιέχει τριάδες ακεραίων αριθμών της μορφής x y w,
όπου x και y τα IDs των κορυφών και w το βάρος της ακμής. Υποθέστε ότι δε θα υπάρχουν πάνω από 50.000
κορυφές στο αρχείο input.txt.
Η οργάνωση του πίνακα δε θα γίνει με ταξινομημένο array αλλά με πίνακα κατακερματισμού. Άρα, για να
βρούμε τους γείτονες μίας κορυφής, θα πρέπει να εφαρμόσουμε τη συνάρτηση κατακερματισμού και στη
συνέχεια να αναζητούμε την κορυφή σύμφωνα με τη λειτουργία του κατακερματισμού ανοικτής διεύθυνσης. Οι
γείτονες της κάθε κορυφής θα είναι αποθηκευμένοι σε μία απλά συνδεδεμένη λίστα ταξινομημένη σε αύξουσα
διάταξη ως προς τα IDs των γειτόνων. Για καλούς χρόνους αναζήτησης στον πίνακα κατακερματισμού αν
ξέρετε ότι θα αποθηκευτούν Ν κορυφές, χρησιμοποιήστε μέγεθος πίνακα 2*Ν, έτσι ώστε ο παράγοντας
φόρτωσης να είναι στο 0.5.

Οι λειτουργίες που πρέπει να υποστηρίξετε είναι δύο: 1) η εύρεση του ελάχιστου δένδρου σύμφωνα με τον
αλγόριθμο του Prim (εντολή MST) και 2) η εύρεση του πλήθους των κοινών γειτόνων δύο κορυφών (εντολή
NCN). Οι λειτουργίες θα διαβάζονται από το αρχείο commands.txt, όπου θα υπάρχουν οι εξής εντολές:
READ_DATA input.txt // ανάγνωση του αρχείου input.txt
INSERT_LINK x y w // εισαγωγή ακμής μεταξύ κορυφών x και y με βάρος w
DELETE_LINK x y // διαγραφή ακμήςMST // υπολογισμός του ελαχίστου δένδρου
NCN x y // υπολογισμός πλήθους κοινών γειτόνων

Στο αρχείο output.txt γράφουν μόνο οι εντολές MST και NCN. Κάθε φορά που στο αρχείο input.txt συναντούμε
μία εντολή MST, στο output.txt γράφουμε το κόστος του ελάχιστου δένδρου καθώς επίσης και το χρόνο
εκτέλεσης της εύρεσης του δένδρου (π.χ. σε seconds) και κάθε φορά που συναντούμε εντολή NCN γράφουμε το
πλήθος των κοινών γειτόνων. Σημειώνεται ότι οι εντολές που βρίσκονται στο αρχείο commands.txt μπορεί να
είναι με τυχαία σειρά ενώ δεν υπάρχει όριο σχετικά με το πλήθος τους. Ο μόνος περιορισμός είναι ότι η πρώτη
εντολή του commands.txt είναι η εντολή READ_DATA.

Σημείωση: η απόδοση του αλγορίθμου Prim εξαρτάται από τις βοηθητικές δομές δεδομένων που χρησιμοποιεί.
Χρησιμοποιώντας σωρό ελαχίστων θα μειωθεί σημαντικά η πολυπλοκότητα και ο χρόνος επεξεργασίας σε σχέση
με τη χρήση ενός απλού array. Ο χρόνος επεξεργασίας θα έχει αντίκτυπο στο βαθμό της εργασίας.

[Duthomhas]

Well, you did a pretty good job explaining it to begin with, it seems.

Alas, this is not a beginner's assignment. Your professor expects you to have a pretty good idea of how to handle data structure and then to be able to apply algorithms to your structures.

I am still not sure I understand some of the imposed restrictions on your graph structure: the requirement to use a hash table and the requirement to sort your linked lists in ascending order. Still, that isn't too much.

Your assignment requires you to:

1) Implement a hash function. You can create your own or use one provided by the std::hash object (in <functional>).

2) Have a linked list of nodes. Again, you can do it on your own (as I gave two posts above) or use the std::list container. You will have to either find a proper insertion point or just sort the list to maintain the requirement to maintain the list in ascending vertex number order every time you add a node.

(Remember, a node in your list has two pieces of information: the destination vertex number and the weight.)

3) Create a function to add a weighted edge to the graph. Remember that the graph is undirected, so you need to update both a→b and b→a in your data structures.

(Remember, an edge is given by source vertex, destination vertex, and weight.)

4) Create a function to remove an edge from the graph.

5) Create a function to read the graph from a named file. (void read_graph( const std::string& filename; node* table[100] ) or something similar.) Use the function in 3 to build the graph.

6) Use a loop to cin the commands.txt file instructions. Make sure you have all the stuff in place, even if it just prints "να κάνω" or something. That way you can verify that the graph is read and created correctly.

-) It might be worth your time to add a command to your requirements: one which prints the hash table from memory. That way you can verify that you have correctly read the graph and see how things are modified when you do the other things.

7) Create a priority queue structure. (Or use the std::priority_queue container adaptor.)

8) Create a function that duplicates your graph. (So that you have the original graph and an additional graph that you can trim to an MST, using the function in 4.)

9) Create a function that applies Prim's algorithm to a graph using 7 and 8.
Use the std::clock to time how long it takes to calculate the MST (as per your requirements).

10) Create a function that finds the number of common neighbors (NCN) given two nodes. That is, given the node numbers a and b in an undirected graph, you only need to find all v such that a→v→b.

11) Make sure to test everything you think your professor will do to you.

This is a lot of work, but if you break it down you can get through it. Good luck!

[Duthomhas]

Also, you may want to check with your professor that I ("you") have understood the hash table correctly.

[chris896]

Ok i will follow your advices, thank you very much, i really appreciate your help !!