Hash Table & Graph

Kay Chan · #1 05-Oct-2004, 09:12

I'm doing an assignment about hash table and graph by using Dijkstra. But I don't know how to use the hash table to store the graph. It is the logic showing as below, can anyone give me hints ? As I know that the graph contains 100 nodes, so how about the size of the table ? If port[i].IDName is one of the node, how to store in the table ?

Initilaization:
First create a hashtable.
Create an array of GraphVertex ports[]. Each element of ports[] is a GraphVertex structure
Repeat:
Read in a line of the form: Portfrom Portto Portdistance
Check if Portfrom exists in hashtable or not:
if exist, ignore it.
if not, form a GraphVertex V and add it to ports[i], and add pointer of V to hashtable.
Check if Portto exists in hashtable or not:
if exist, ignore it.
if not, form a GraphVertex w and add it to ports[i], and add pointer of w to hashtable.
Form adjvertex structure A with pointer of w as vertex, and Portdistance as NeighbourDist.
Add A to adj list of V.

davekw7x · #2 05-Oct-2004, 13:48

Quote:

Originally Posted by Kay Chan

I'm doing an assignment about hash table and graph by using Dijkstra. But I don't know how to use the hash table to store the graph. It is the logic showing as below, can anyone give me hints ? As I know that the graph contains 100 nodes, so how about the size of the table ? If port[i].IDName is one of the node, how to store in the table ?

Initilaization:
First create a hashtable.
Create an array of GraphVertex ports[]. Each element of ports[] is a GraphVertex structure
Repeat:
Read in a line of the form: Portfrom Portto Portdistance
Check if Portfrom exists in hashtable or not:
if exist, ignore it.
if not, form a GraphVertex V and add it to ports[i], and add pointer of V to hashtable.
Check if Portto exists in hashtable or not:
if exist, ignore it.
if not, form a GraphVertex w and add it to ports[i], and add pointer of w to hashtable.
Form adjvertex structure A with pointer of w as vertex, and Portdistance as NeighbourDist.
Add A to adj list of V.

Well, the hash table, obviously, must be larger than the number of nodes. You and your instructor and Dijkstra can decide how much larger. It depends on the hashing algorithm, the nature of the data base, etc.

The table will be an array of structs. Each struct is a table entry, and will contain, among other things a name associated with that entry.

Now, suppose your table contains, say 500 entries.

When you allocate storage for the table, there are 500 structs, each has a field that allows you to enter a name.

If you know that all names are, say, less than 9 characters long, then the memory for the struct field IDName can be allocated at the time that the table is declared. The definition of the table entry structs can be something like the following.

In C, using C-style strings

CPP / C++ / C Code:

typedef struct H_table_entry {
..
..
..
  char IDName[10];
...
...

To make an entry in the table, you would see something like

CPP / C++ / C Code:

  strcpy(table[i].IDName, current_name_entry);

If you hadn't previously verified that the name was 9 characters or less, you should use strncpy(), but I would have verified the length as part of the input process.

Now, to make better use of memory, and to make it possible to have longer or shorter names, most people would only allocate memory for each name when the entry is made in the table. So the definition would be :

CPP / C++ / C Code:

typedef struct H_table_entry{
...
...
...
  char *IDName;
...
...

Then, when an entry is made in the table, you would see something like

CPP / C++ / C Code:

...
   if ((table[i].IDName = malloc(strlen(current_name_entry) + 1)) == NULL) {
    printf("error.....);

    //.... some code to bail out with the error condition

   }
   else {
      strcpy(table[i].IDName, current_name_entry);
  }

That is, it is necessary to allocate memory for the string then copy the string into the table entry. Remember, in C there is no such data type as "string". Strings are handled as null-terminated arrays of char.

In the wonderful world of C++ strings, you can simply have

CPP / C++ / C Code:

  typedef struct H_Table_entry {
   ...
   ...
   string IDName;
   ...

Now you can have something like this to make the table entry:

CPP / C++ / C Code:

  table[i].IDName = current_name_value;

And the C++ string is automatically expanded to whatever length it needs to be, and the string is copied into the C++ string by the assignment statement.

(That's why even some old-fashioned bare-bones, rubber-meets-the-road C programmers sometimes sneak in and use C++ from time to time.)

Does this help?

Regards,

Dave

Kay Chan · #3 05-Oct-2004, 20:46

Actually, there is a program to calculate the shortest path from place A to place X(weight graph). I need to store the node(starting port), vertex(destination port), neighbour distance(distance from A to B) in a hash table.

As I have mention b4. There is an struct array call GraphVertex ports[i] from hold above items. The problem is how to make a table to hold all the item. Hence, ports[i].IDName is linked with adj -> vertex and adj ->NeighbourDist. Do I only copy the posts[i].IDName to the table as u mention b4 or do I need to do sth extra ? If it isn't clear enough, I can send what I have done to u.

CPP / C++ / C Code:

struct GraphVertex {
    char IDName[4];
    List *adj;
    int  MinDistance;
    GraphVertex * path;
};

struct AdjVertex {
    GraphVertex * vertex;
    int  NeighbourDist;
};

Regards,
Kay

Quote:

Originally Posted by davekw7x

Well, the hash table, obviously, must be larger than the number of nodes. You and your instructor and Dijkstra can decide how much larger. It depends on the hashing algorithm, the nature of the data base, etc.

The table will be an array of structs. Each struct is a table entry, and will contain, among other things a name associated with that entry.

Now, suppose your table contains, say 500 entries.

When you allocate storage for the table, there are 500 structs, each has a field that allows you to enter a name.

If you know that all names are, say, less than 9 characters long, then the memory for the struct field IDName can be allocated at the time that the table is declared. The definition of the table entry structs can be something like the following.

In C, using C-style strings

CPP / C++ / C Code:

typedef struct H_table_entry {
..
..
..
  char IDName[10];
...
...

To make an entry in the table, you would see something like

CPP / C++ / C Code:

  strcpy(table[i].IDName, current_name_entry);

If you hadn't previously verified that the name was 9 characters or less, you should use strncpy(), but I would have verified the length as part of the input process.

Now, to make better use of memory, and to make it possible to have longer or shorter names, most people would only allocate memory for each name when the entry is made in the table. So the definition would be :

CPP / C++ / C Code:

typedef struct H_table_entry{
...
...
...
  char *IDName;
...
...

Then, when an entry is made in the table, you would see something like

CPP / C++ / C Code:

...
   if ((table[i].IDName = malloc(strlen(current_name_entry) + 1)) == NULL) {
    printf("error.....);

    //.... some code to bail out with the error condition

   }
   else {
      strcpy(table[i].IDName, current_name_entry);
  }

That is, it is necessary to allocate memory for the string then copy the string into the table entry. Remember, in C there is no such data type as "string". Strings are handled as null-terminated arrays of char.

In the wonderful world of C++ strings, you can simply have

CPP / C++ / C Code:

  typedef struct H_Table_entry {
   ...
   ...
   string IDName;
   ...

Now you can have something like this to make the table entry:

CPP / C++ / C Code:

  table[i].IDName = current_name_value;

And the C++ string is automatically expanded to whatever length it needs to be, and the string is copied into the C++ string by the assignment statement.

(That's why even some old-fashioned bare-bones, rubber-meets-the-road C programmers sometimes sneak in and use C++ from time to time.)

Does this help?

Regards,

Dave

davekw7x · #4 06-Oct-2004, 07:41

Quote:

Originally Posted by Kay Chan

Actually, there is a program to calculate the shortest path from place A to place X(weight graph). I need to store the node(starting port), vertex(destination port), neighbour distance(distance from A to B) in a hash table.

As I have mention b4. There is an struct array call GraphVertex ports[i] from hold above items. The problem is how to make a table to hold all the item. Hence, ports[i].IDName is linked with adj -> vertex and adj ->NeighbourDist. Do I only copy the posts[i].IDName to the table as u mention b4 or do I need to do sth extra ? If it isn't clear enough, I can send what I have done to u.

CPP / C++ / C Code:

struct GraphVertex {
    char IDName[4];
    List *adj;
    int  MinDistance;
    GraphVertex * path;
};

struct AdjVertex {
    GraphVertex * vertex;
    int  NeighbourDist;
};

Regards,
Kay

Here's what I think you can use to go forward.

You have defined two structs. (I'm not sure what the List is in the first struct; I assume it has been defined at this point.)

In your main() function, if you want the size of the table to be, say, 500, then declare an array of GraphVertex structs. Something like

CPP / C++ / C Code:

int main()
{
  struct GraphVertex ports[500];
  ...
  ...
}

Now, as you read something in, and decide that it should be the ith entry in the table, you could have something like

CPP / C++ / C Code:

  strcpy(ports[i].IDName, new_name_value);
  ports[i].MinDistance = calc_min_distance(whatever_you_need_to_calculate_it);

...

Note that your names can only be three chars long, since the string "xyz", for example, occupies four memory locations: 'x', 'y', 'z', 0

Regards,

Dave

Kay Chan · #5 06-Oct-2004, 21:58

If I need to make a hash table to store sth like this struct

CPP / C++ / C Code:

struct GraphVertex {
    char IDName[4];
    List *adj;
    int  MinDistance;
    GraphVertex * path;
};

struct AdjVertex {
    GraphVertex * vertex;
    int  NeighbourDist;
};

just make one more struct for the hash table ?
for example, this is the GraphVertex ports[i].IDName
i make another struct for the hash table sth like

CPP / C++ / C Code:

struct hast {
    char Name[4];
};

strcpy(hash[i].Name, ports[i].IDName)

Regards,
Kay

Quote:

Originally Posted by davekw7x

Here's what I think you can use to go forward.

You have defined two structs. (I'm not sure what the List is in the first struct; I assume it has been defined at this point.)

In your main() function, if you want the size of the table to be, say, 500, then declare an array of GraphVertex structs. Something like

CPP / C++ / C Code:

int main()
{
  struct GraphVertex ports[500];
  ...
  ...
}

Now, as you read something in, and decide that it should be the ith entry in the table, you could have something like

CPP / C++ / C Code:

  strcpy(ports[i].IDName, new_name_value);
  ports[i].MinDistance = calc_min_distance(whatever_you_need_to_calculate_it);

...

Note that your names can only be three chars long, since the string "xyz", for example, occupies four memory locations: 'x', 'y', 'z', 0

Regards,

Dave

davekw7x · #6 07-Oct-2004, 08:01

Quote:

Originally Posted by Kay Chan

If I need to make a hash table to store sth like this struct

CPP / C++ / C Code:

struct GraphVertex {
    char IDName[4];
    List *adj;
    int  MinDistance;
    GraphVertex * path;
};

struct AdjVertex {
    GraphVertex * vertex;
    int  NeighbourDist;
};

just make one more struct for the hash table ?
for example, this is the GraphVertex ports[i].IDName
i make another struct for the hash table sth like

CPP / C++ / C Code:

struct hast {
    char Name[4];
};

strcpy(hash[i].Name, ports[i].IDName)

Regards,
Kay

These statements do not create any variables (they do not allocate storage), they just tell the compiler what do do if you use "struct GraphVertex", "struct "AdjVertex, etc.

These declarations can be at the top of the file, or in a header file, or anywhere else in your program, but they must be some place before you actually use them. If you are going to use them in more than one function, the declarations must be outside of any function. (That's why they typically are in header files.

Now once the declaration has been made specific instances (definitions that actually allocate storage) can be created anywhere you need them

So, see if this code makes sense in your context:

CPP / C++ / C Code:

#include <stdio.h>
#include <string.h>


struct GraphVertex {
    char IDName[4];
    int  MinDistance;
    struct GraphVertex * path;
};

struct AdjVertex {
    struct GraphVertex *vertex;
    int  NeighbourDist;
};

int main()
{
  int ReadElement(struct GraphVertex *); /* declares a function */

  struct GraphVertex MyGraph[100]; /* this declares an array of structs */
  struct AdjVertex *A; /* this declares a pointer to a struct */
  

  int hashvalue;

  printf("sizeof(struct GraphVertex) = %d\n", sizeof(struct GraphVertex));
  printf("sizeof(MyGraph)            = %d\n", sizeof(MyGraph));
  printf("sizeof(struct AdjVertex)   = %d\n\n", sizeof(struct AdjVertex));


  /* Typically, we would have a loop such as */
  /*do(){  ... } while (hashvalue > 0);     */

  /* This would be the beginning of the loop */
  
  /* do {                                    */
    hashvalue = ReadElement(MyGraph);
    if (hashvalue <= 0) {
      printf("ReadElement Returned non-positive value \n");
    }
    else {
      printf("ReadElement succeeded, execution continues\n\n");
      printf("MyGraph[%d].IDName: <%s>\n", hashvalue, MyGraph[hashvalue].IDName);
      /* Do more stuff here */
    }
  /* This would be the end of the do{}while loop */

  /* while (hashvalue > 0) */
  return 0;
}

int ReadElement(struct GraphVertex *Graph)
{
  /* do whatever ReadElement needs to do */
  /* typically, read something in and make assignments to some */
  /* elements of the structure                                 */

  /* for test purposes I just do something trivial             */
  int i;

  i = 20;


  strcpy((Graph+i)->IDName, "ABC") ; /* copy to the ith element */

  return i;
}

Regards,

Dave

Kay Chan · #7 07-Oct-2004, 20:26

This is the program that they are provided. They suggest to use hash table to store the GraphVertex, so How to do this ?

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include "list.h"
#include "heap.h"

struct GraphVertex {
    char IDName[4];
    List *adj;
    int  MinDistance;
    GraphVertex * path;
};

struct AdjVertex {
    GraphVertex * vertex;
    int  NeighbourDist;
};


int const MAXVERTEX = 3;
GraphVertex ports[MAXVERTEX];

void RunDijkstra (GraphVertex *);
void Dijkstra(GraphVertex *); 
int  CompareVertexDistances(const void *, const void *);
void DeleteAdj(const void *);
void PrintAdj(const void *);
void PrintPath(GraphVertex *);

int main() {
    AdjVertex *adj;
    int i;

    /* 
    This is similar to using sectorS.txt with 4 entries:
    ABC BCD 20
    ABC CDE 100  
    BCD CDE 70
    CDE ABC 100
    */
  
    strcpy(ports[0].IDName, "ABC");        <--------
    strcpy(ports[1].IDName, "BCD");        <--------
    strcpy(ports[2].IDName, "CDE");        <--------

    ports[0].adj = ListConstruct();
    ports[1].adj = ListConstruct();
    ports[2].adj = ListConstruct();

    adj = (AdjVertex *)malloc(sizeof(AdjVertex));
    adj->vertex = &ports[1];
    adj->NeighbourDist = 20;
    ListInsert(ports[0].adj, ListLast(ports[0].adj), adj);

    adj = (AdjVertex *)malloc(sizeof(AdjVertex));
    adj->vertex = &ports[2];
    adj->NeighbourDist = 100;
    ListInsert(ports[0].adj, ListLast(ports[0].adj), adj);
                                
    adj = (AdjVertex *)malloc(sizeof(AdjVertex));
    adj->vertex = &ports[2];
    adj->NeighbourDist = 70;
    ListInsert(ports[1].adj, ListLast(ports[1].adj), adj);

    adj = (AdjVertex *)malloc(sizeof(AdjVertex));
    adj->vertex = &ports[0];
    adj->NeighbourDist = 100;
    ListInsert(ports[2].adj, ListLast(ports[2].adj), adj);

    // Output what we have!
    printf ("Before running Dijkstra:\n");
    for (i = 0; i < MAXVERTEX; i++) {
        printf("%s: %d\n", ports[i].IDName, ports[i].MinDistance);
    }

    RunDijkstra (&ports[0]);
    RunDijkstra (&ports[1]);
    RunDijkstra (&ports[2]);
                        
    for (i = 0; i < MAXVERTEX; i++) {
        ListTraverse(ports[i].adj, DeleteAdj, true);
        ListDestroy(ports[i].adj);
    }
    system("PAUSE");
    return 0;
}

Regards,
Kay

Quote:

Originally Posted by davekw7x

These statements do not create any variables (they do not allocate storage), they just tell the compiler what do do if you use "struct GraphVertex", "struct "AdjVertex, etc.

These declarations can be at the top of the file, or in a header file, or anywhere else in your program, but they must be some place before you actually use them. If you are going to use them in more than one function, the declarations must be outside of any function. (That's why they typically are in header files.

Now once the declaration has been made specific instances (definitions that actually allocate storage) can be created anywhere you need them

So, see if this code makes sense in your context:

CPP / C++ / C Code:

#include <stdio.h>
#include <string.h>


struct GraphVertex {
    char IDName[4];
    int  MinDistance;
    struct GraphVertex * path;
};

struct AdjVertex {
    struct GraphVertex *vertex;
    int  NeighbourDist;
};

int main()
{
  int ReadElement(struct GraphVertex *); /* declares a function */

  struct GraphVertex MyGraph[100]; /* this declares an array of structs */
  struct AdjVertex *A; /* this declares a pointer to a struct */
  

  int hashvalue;

  printf("sizeof(struct GraphVertex) = %d\n", sizeof(struct GraphVertex));
  printf("sizeof(MyGraph)            = %d\n", sizeof(MyGraph));
  printf("sizeof(struct AdjVertex)   = %d\n\n", sizeof(struct AdjVertex));


  /* Typically, we would have a loop such as */
  /*do(){  ... } while (hashvalue > 0);     */

  /* This would be the beginning of the loop */
  
  /* do {                                    */
    hashvalue = ReadElement(MyGraph);
    if (hashvalue <= 0) {
      printf("ReadElement Returned non-positive value \n");
    }
    else {
      printf("ReadElement succeeded, execution continues\n\n");
      printf("MyGraph[%d].IDName: <%s>\n", hashvalue, MyGraph[hashvalue].IDName);
      /* Do more stuff here */
    }
  /* This would be the end of the do{}while loop */

  /* while (hashvalue > 0) */
  return 0;
}

int ReadElement(struct GraphVertex *Graph)
{
  /* do whatever ReadElement needs to do */
  /* typically, read something in and make assignments to some */
  /* elements of the structure                                 */

  /* for test purposes I just do something trivial             */
  int i;

  i = 20;


  strcpy((Graph+i)->IDName, "ABC") ; /* copy to the ith element */

  return i;
}

Regards,

Dave

davekw7x · #8 08-Oct-2004, 07:44

Quote:

Originally Posted by Kay Chan

This is the program that they are provided. They suggest to use hash table to store the GraphVertex, so How to do this ?

Regards,
Kay

Kay: please use code tags so that your code has a better chance of being readable:

put [ c ] before the first line of code, and [ /c ] after the last line, but don't leave any spaces between the brackets and the "c"

"left squarebracket"c"right square bracket"

#include <stdio.h>

int main() {

}

"left square bracket"/c"right square bracket"

Code:


  CPP / C++ / C Code:
  
// Your Program Stuff Here

Not clear? Read this http://www.gidforums.com/t-689.html

Now as far as trying to help you with your code, I can't do much with this specific example without the files "list.h" and "heap.h". I can't see how anyone can help you know how to use Dijkstra(), RunDijkstra(), CompareVertexDistances(), etc. without having them.

If you have specific questions about code, error messages, etc. I would like to help you in any way that I can (within reason).

Regards,

Dave

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
customizing preprocessor and hash table	incognito54	C Programming Language	2	21-Apr-2004 18:25
form in a table cell	Kurtanator	Web Design Forum	2	18-Feb-2004 04:52
form in a table cell	blelisa	Web Design Forum	1	19-Aug-2003 09:14
[Tutorial] MySQL Basics	nniehoff	MySQL / PHP Forum	15	23-Mar-2003 19:42
using a button to change table contents.	demtro	MySQL / PHP Forum	20	02-Mar-2003 15:07

Hash Table & Graph

Hash table