Graphs, Adjacency Table/List Examples?

Ok well i chose to start implementing the graph as a linked list.
Here are some general questions I have:

1) is this correct for the linked list implementation? any tips?
2) what would be the difference with an adjacency list?


Basically in the end im wanting three implementations:
1. adjacency table
2. linked vertex list with linked adjacency lists (this is just a basic adjacency list right?)
3. a contiguous vertex list of linked adjacency lists (linked list correct?)

Current Code: http://www.geocities.com/bjohnson045/program/

Any tips helpful.

(1) How you store the vertex list with an adjacency list is really immaterial so using a linked list of vertices is as good as a vector of vertices or even an array of vertices.

(2) What are you going to DO with your graphs? Saying you will have three implementations of graphs is all fine and well but it is similar to saying I will have three implementations of cars. Without knowing what the cars will be used for it is hard to decide between a gas-guzzling monster truck or a pressboard Traubant.

I will try to take a look at your code tomorrow morning (EST; in about 13 hours). I don't really have any words of wisdom other than: Make a good, easy to use graph interface. Make sure it hides the implementation so that changing the implementation is easy.

Good luck, -bcl

To tell you the truth this is an assignment im working on.
The three implementations are a requirement.  To tell you the truth I dont know why we need to do all three.

As listed above they are:
1. adjacency table
2. linked vertex list with linked adjacency lists
3. a contiguous vertex list of linked adjacency lists

I'm guessing that if I can get one implementation the others will be easier correct?  As you said make a easy to use graph interface and the implementation changes should be easy.

(1) Interface is the key. Make sure that your Graph class does not expose any "private" information. You don' t want the internal representation of vertices and edges to be visible outside the class; use functions like addNode() and addEdge() that take "outside" information as parameters.

What I mean is, think about a graph being used to represent airplane routes. The nodes are named cities and edges connect cities with direct connecting flights and are labeled with their weight, the cost of a ticket between the two cities. I want to be able to use it as in the following:

Graph G;

G.addNode("Los Angeles");
G.addNode("Pittsburgh");
G.addNode("Frankfurt");
G.addNode("Cairo");

G.addEdge("Los Angeles", "Cairo", 1100);
G.addEdge("Frankfurt", "Cairo", 1000);
G.addEdge("Pittsburgh", "Frankfurt", 900);

cout << G << endl;

Note that each node is known by its name OUTSIDE the graph class. Each edge is represented by two node names and the weight.

The underlying graph could be a digraph (in which case this grpah is not connected) or an undirected graph (in which case this graph IS connected).

Think carefully about how you will name nodes and edges across the interface.

-bcl

I have it setup as you mentioned.

Did you get a chance to check out my code thats up there?
Just wanting to see what you think.

I downloaded it when I got to work and then I started into doing stuff and forgot to look at it. It looks pretty good. I am not sure why Edge and Vertex are classes outside of Graph (you have a find function that returns a pointer at a Vertex inside the graph. That is very, very dangerous because I can do bad things to the internal pointers of that vertex, things that bork your graph; once you return copies of the data or some such there is no need to have Edge or Vertex appear outside of Graph so you can move them into the private section of the structure).

I tend to put two end pointers on an edge, both the head and the tail vertices. I also tend to have Graph keep track of all edges in it as well as all vertices (permits certain types of checks on the number of edges versus the number of edges there could be in a complete graph and stuff like that).

It looks pretty good if I am just making simple design suggestions.

-bcl

I guess im pretty confused at this point.  So I should only have one class?  I'm wanting to get this as simple as i can, so obviously i can understand it a little better.  Right now im lost.  The three classes...

class Vertex, lass Edge, class Graph were examples in the text.

Only difference in my suggestion is that class Vertex and class Edge ARE INSIDE class Graph:

class Graph {
private:
  class Vertex {
    // ... as you have it now
  };
 
  class Edge {
    // ... as you have it now
  };

  Vertex * allTheVerticesList;
 
public:
  Graph();
  // ... as you have it now
};

Change in .cpp file is that the names of Vertex and Edge are now Graph::Vertex and Graph::Edge

Hope this makes it clearer.

-bcl

Ive been working a bit on the adjacency table implementation but it looks pretty bad.
Am I headed in any direction at all?

#ifndef _TABLEGRAPH_H
#define _TABLEGRAPH_H

template <int max_size>
class Digraph {
 public:
  void read();
  void write(max_size);
 private:
  int count;
  bool adj[maxe_size][max_size];
};

#endif


Graph::Graph()
{
  count = 0;
}

void Graph::read()
{
  "Entr connections:";
  int i, j;
  while(cin >>i  >> j)  // read a connection and set the edges
    {
      adj[i][j] =1;
      adj[j][i] = 1;
    }
}


int main()
{
  int verts;
  cout <<"Enter the number of vertices:";
  cin >> verts;

  Digraph <verts> mygraph;
  mygraph.read();
  mygraph.write();

  return 0;
}

Stop!

The signature of your graph classes should be the same. I mean exactly the same. You should be able to use one main.cpp and only change the header included and, possibly, the other file linked to use any one of the three graph implementations.

You might argue about that since you want to use an integer template parameter for compile time size determination but if you use dynamic memory allocation AND hack the constructor in every graph to take the maximum number of nodes (only enforced in the table version) you can use the same code across the board.

<Note: I wrote my dissertation on graph-based algorithms and graph-based data storage and I came to it from a hypertext rather than a graph-theoretic direction. That means I call them nodes and not vertices. Also means I sometimes call edges links. Read your favorite name everywhere below as I may well switch back and forth. My apologies in advance for any confusion this may cause.>

Having said that, how would you write addVertex for this graph implementation? Well, since you need to associate a name with a row/column in the table you need some mechanism to match the two, say an array of node data and a getNodeIndesFromName and  getNodeNameFromIndex functions (implementation functions so they are NOT in the interface for Graph). Thus addNode updates the relationship between names and indices.

What does addEdge need to do in this representation? Well it looks up a couple of indices and if the named nodes exist it adds an edge...wonder what that actually entails.

Finally, how would you print this implementation out? Probably as the matrix.

Hope this helps, -bcl

Well you dont have to say anything about the stupid mistakes.  I see those already but mostly im wondering about the following.

1) why cant you use a variable for the template?? (verts)
2) I'm wanting a read function that takes in from the terminal the number of vertices.  Should this be taken into count?  I'm confused on what determines how big the overall matrix is?  Isnt its size the number of vertices? I dunno im confused here.

Oh i didnt see your most recent post, let me look it over.

You can't use a template if you expect the user to provide the number of vertices in the graph at RUNTIME. You basically have to use dynamic memory yourself or use an STL container that does dynamic memory allocation for you under the hood.

-bcl

Well ok, I should have mentioned this.  I'm wanting to make all of this a bit more simple.  So I am basically starting over with the adjacency table and am going to re-do my linked list version.  All I really want is a read function that takes in the number of vertices (nodes) from the terminal, and then takes in the connections (edges/links) from the terminal.  I also want a write function that writes graph info to the terminal.

Well specifying the number of vertices is confusing to me, considering I'm using part of the code from the text.  It gives us...

template <int max_size>
class Digraph {
  int count;
  bool adj[max_size][max_size]
};

But the problem statement is to have number of vertices determined from user input from the terminal.

The only thing i could think of is that it wants use to determine the max size of the matrix, but then only part of it is used?

Okay. That is fine. So the interface has changed to read and write:

class Graph {
public:
  void read();
  void write();
private:
  // The devil is in the details
};

Okay, what does read do? I would guess that it is something like this (based on your code with a little bit more abstraction):

void Graph::read() {
  int i, j, n;
  cout << "Number of nodes: ";
  cin >> n;
  if (0 < n) {
    setNumberOfNodes(n);
    while (cin >> i >> j) {
      addEdge(i, j);
    }
  }
}

And write? How about ALWAYS printing it out like it is an adjacency table (so you can compare your implementations for correctness):

void Graph::write() {
  for (int i = 0; i < numberOfNodes; ++i) {
    for (int j = 0; j < numberOfNodes; ++j)
      if (isEdge(i, j))
        cout << "1 ";
      else
         cout << "0 ";
    cout << endl;
  }
}

Then you just write addEdge(int, int) (easy in this case, just the two lines from inside your loop) and isEdge(int, int) (how would you implement this?).

Then the only hard part is the constructor and the setNubmerOfNodes routines. Constructor is easy (does nothing; don't know size until setNumberOfNoces) and setNumberOfNodes allocates a dynamic two dimensional array.

Hope this helps some. If I am pushing you where you don't want to go, let me know and I will help with what you need help on. I think a single, unified design will help make the rest of the coding task easier.

-bcl

I appreciate any direction you help to move me in.  The help is greatly appreciated.
Well here is kinda what I came up with.  I beleive my private section of the class is not right.

class Digraph {
 public:
  void read( );
  void write( );
 private:
   int numberOfNodes;
   Graph( );
   setNumberOfNodes( );
};

void Graph::read( ) {
  int i, j, n;
  cout << "Number of nodes: ";
  cin >> n;
  if (0 < n) {
    setNumberOfNodes(n);
    while (cin >> i >> j) {
      addEdge(i, j);
    }
  }
}

void Graph::write( ) {
  for (int i = 0; i < numberOfNodes; ++i) {
    for (int j = 0; j < numberOfNodes; ++j)
      if (isEdge(i, j))
        cout << "1 ";
      else
         cout << "0 ";
    cout << endl;
  }
}


Graph::Graph( )
{}

void addEdge(int i, int j)
{
   adj[i][j] =1;
   adj[j][i] = 1;
}

bool isEdge(int i, int j)
{
   if(adj[i][j] == 1 && adj[j][i] == 1)
      { return 1; }
   else
      { return 0; }
}

Graph::setNumberOfNodes(int n)
{
   int numberOfNodes = n;
   bool adj[n][n];
}

(1) Graph's constructor is public.

(2) Let's look at what is happening inside of setNumberOfNodes:

Graph::setNumberOfNodes(int n)
{
   int numberOfNodes = n;
   bool adj[n][n];
}

Well, from the point of view of the Graph object, NOTHING is happening inside here (it also won't compile but that is not the point right now). Note that two local variables are declared inside of setNumberOfNodes and both local variables go away at the end of the function. The object-level variable numberOfNodes is NOT changed by this function (inside this function numberOfNodes is a local variable that hides this->numberOfNodes).

So, step 1 is to remove the declaration of a new integer.

Step 2 is to remove the local declaration of adj (it, too, should be an object-level variable). The problem is that the declaration you use doesn't compile. There are two solutions:
(a) Pick a maximum number of nodes in the graph and only use part of the adjacency matrix.
(b) Dynamically allocate the space for the array.

(a) is easier so we'll use the maxNodes variable for this purpose:

private:
  const static int maxNodes = 100;
  bool adj[maxNodes][maxNodes];

(code not tested with compiler; I am pretty sure a const static can be used in this fashion).

Almost the same as the template parameter from the text's version.

So all the setNumberOfNodes function is doing is setting numberOfNodes = n ??

Sure.

Told you (a) was easier than (b)

Sooner or later im going to do a depth and breadth first search function, doesnt it need to be a directed graph to do this?

(1) No, depth, breadth, and order first (like finding the shortest path) are all well defined on digraphs AND undirected graphs. Assuming the code you have posted works you have an undirected graph that is one line away from being a digraph (hint: it is removing one line).

Oh ok, gotcha.  Well ok ill keep you posted on how im coming along. (im sure more problems will arise).  I feel I have a long way to go to where I want to get, but hopefully it wont be too hard with this code as a starter.  I plan on implemented all three implementations (adj table, linked vertex list w/ linked list, linked list) along with depth/breadth for each, and Prim's, Kruskals, and Dijkstra's algorithms for each.  

Meant to say contigous vertex list of linked adjacency lists for the second implementation.

Another quick question, if the graph is undirected, won't the vertices need some type of weight or name to determine how the breadth and depth work?

Depth-first and breadth-first searches don't depend on edge weights; the other algorithms you mention do (Dijkstra's is an in-order search; it is possible to write one routine that does depth, breadth, and Dijkstra's simply by changing one data structre from a stack to a queue to a priority queue). Notice that the weights are traditionally on the edges and not on the nodes themselves.
-bcl

So basically im going to have to make edges into something like a struct, giving it a weight?

Yep but when you have a class representing an edge (as you had in early code) then you can just add weight. What to do in the adjacecny matrix...

Wait a minute, if all you need is a weight and a weight is a number and you have a matrix of numbers indexed by the nodes in the graph...insiight like the preceding leads to the use of a weight matrix in place of an adjacency matrix. Need to work on isEdge and decide what value to use for element [i][i] and non-edges but it is fairly easy to accomodate weights.

Take a look at the text and I'll bet they show how to do weights using an adjacency list.

-bcl

Ah so basically instead of using a bool (1 or 0) matrix the number will represent the weight of the edge?

Roger that.

Ok sounds good.  Well im working on getting this to compile.  However im stuck.  Doesnt isEdge and addEdge need to be a part of graph since they are using the matrix?  It also is giving me an error concerning the constant for adj[ ][ ].  Along with numberOfNodes, being out of scope (another reason i thought isEdge and addEdge needed to be a part of graph.  Well here is the code if you want to take a look.

#ifndef _TABLEGRAPH_H
#define _TABLEGRAPH_H

#include "tablegraph.cpp"

class Graph {  
 public:
  Graph();
  ~Graph();
  void read();
  void write();  
 private:
  int numberOfNodes;
  const static int maxVertices;
  bool adj[maxVertices][maxVertices];
  void addEdge(i, j);
  bool isEdge(i, j);
};

#endif

#include <iostream>

Graph::Graph()
{}

void Graph::read()
{
  int i, j, n;

  cout << "Number of vertices: ";
  cin >> n;
  if(0 < n){
    setNumberOfNodes(n);
    while(cin >> i >> j){
      addEdge(i, j);
    }
  }
}

void Graph::write()
{
  for(int i=0; i < numberOfNodes; i++){
      for(int j=0; j < numberOfNodes; j++){
        if(isEdge(i, j))
          cout << "1 ";
        else
          cout << "0 ";
      }
      cout << endl;
  }
}

void Graph::setNumberOfNodes(int n)
{
  numberOfNodes = n;
}

void Graph::addEdge(int i, int j)
{
  adj[i][j]=1;
  adj[j][i]=1;
}

bool Graph::isEdge(int i, int j)
{
  if(adj[i][j]==1 && adj[j][i]==1)
    return 1;
  else
    return 0;
}

#include <iostream>
#include "tablegraph.h"
using namespace std;

int main()
{
  Graph mygraph;
  mygraph.read();
  mygraph.write();

  return 0;
}

 

How about including tablegraph.h in tablegraph.cpp?

I think that is missing

Okay, I misread what you were doing:

Don't include the .cpp in the .h UNLESS you are implementing a template. If you are implementing a template then include the .cpp at the very END of the .h

Give maxVertices a value INSIDE the class definition:

  const static int maxVertices = 100;

This  makes no sense to the compiler:

  void addEdge(i, j);

THIS does:

  void addEdge(int i, int j);

Still should include tablegraph.h in tablegraph.cpp

Need using namespace std in tablegraph.cpp (or qalify cout and cin and all of that).

Hope this helps, -bcl

Ok well that works.  Thanks for the tips.  On to dfs and bfs.  I started on bfs.  The stl queue can be used correct?  Here is what I have so far, but im a little confused near the end.  Any critiquing?

void Graph::bfs(??)
{
  Queue q;
  bool visited[maxVertices];
  for(int i=0; i<maxVertices; i++)
    visited[i]=false;
  for(int i=0; i<maxVertives; i++){
    if(!visited[i]){
      q.append(i);
      while(!q.empty()){
        q.retrieve(w);
        if(!visited[w]){
          visited[w]=true;
          for(all vertices adj to w) // ??
            q.append(x);
        }
        q.serve();
      }
    }
  }
}

(1) A breadth first search starts from somewhere. Thus the parameter to the function is a vertex. The driving loop is then whether or not there are nodes to be visited (whether the queue is empty or not), NOT a count controlled loop on the number of vertices. Why? Because you don't know, a priiori, whether or not the graph is connected.

The basic algorithm is:

bfs(v)
  q.enqueue(v);
   while !q.empty
      x = q.front
      visit x
       for each child of x
          if !visited child
             q.enqueue(child)


So that strips off your outer loop (you are doing that so that you end up visiting all nodes even if the graph is not connected?).

How would you find all the children (nodes adjacent to) a given node w (or x)? You would have to go across a row of the adjacency/weight matrix OR use isEdge...using isEdge means that you can write the bfs in an implementation neutral manner (no need to rewrite it for other implementations).

    for (int child = 0; child < numberOfNodes; ++child) {
        if (!isEdge(w, child)) continue;
        // do the real work here

Question: Why not use a vector<char> for your vistited array? (You don't want to use vector<bool> for a lot of technical reasons and one not so technical reason: it is BROKEN in the standard.) The vector means you don't have to set aside space with a constant (you can use numberOfNodes). Makes it easier to be implementation neutral.

-bcl

So you're saying that the nodes that are not connected should not be visited?  The BFS i wrote a post back I wrote basing it on the psuedo code in the book, so they had it going to every node?

The Dictionary of Algorithms and Data Strucutres defines it in terms of nodes connected to a single starting node (http://www.nist.gov/dads/HTML/breadthfirst.html) and some other on-line notes work from a single node (http://www.ics.uci.edu/~eppstein/161/960215.html) and I have always seen it done that way. This is particularly important if you plan to compare depth-first, breadth-first, and best-first algorithms since Dijkstra's algorithm will find no path to nodes outside the connected component of the starting node.

Thus with appeal to authority I shall carry the argument.

Actually, with some consideration, I guess you could expand depth and bread first definitions to deal with non-connected graphs (in some way other than just visiting nodes in one connected component). I think you should ask your instructor what form they want it to take. If you write the single connected component version you can have it return the number of nodes it visited (or, better yet, a vector of the nodes in the order visited). Then, if you need to do the "all" case you can put a wrapper function around the single connected component one that finds an unvisited node and calls the connected component version.

The more I think about it the less I AM convinced that visiting all of the connected components makes any sense. What do I know, though. What text book are you using? Sedgewick? He is sometimes less than clear for algorithms you've never seen before.

In any case, I would ask but I think you start at a given root.

-bcl

Im using the Druse and Ryba text, Data Structures and Program Design in C++.  Our professor is a little unclear and what she wants, and even when asked is sometimes unsure.  It is her first year teaching.  Her study is based in graphic design, and it just seems she lacks experience in teaching this subject.  The reason i included each node to be visited is simply because the text had the basic algorithm coded that way.  I agree that it should start at a single vertex and if nodes are not connected they should not be visited.  

Couple questions:
1) Why in the code below do you have !isEdge, if there is not a edge nothing happens.  Shouldnt it simple be isEdge, and then if true, push child onto the queue?

    for (int child = 0; child < numberOfNodes; ++child) {
        if (!isEdge(w, child)) continue;
        // do the real work here

2) Im confused on why visited[] should not be bool?  Isnt it simply going to be true or false, always? not sure what you mean by "it is BROKEN in the standard."

(1) Sure, the positive if statement is clearer and correct. Don't know what I was thinking.

(2) If you use vector<T> (the STL vector class), T should not be bool. Templates support explicit specialization which means that you can write a special version of the template for a particular template parameter (so you could have a template that did one thing if instantiated with char and another if instantiated with string, for example). The exact syntax is unimportant to the story. vector<bool> has a specialization (it was hoped during the standardization process that vector<bool> could be implemented as a collection of bits with set and clear operations); that specialization was not well described during the standards process and it should never have been included (many on the standards committee now agree). So, I was warning you that if you switch to vector (which I think you should) you would have to change the element type of the container.

-bcl

Ok but you would still use 1 and 0 for visited and not visited correct? Even if the type is string, char, int it will still work the same.  Well ok here is what i get from all of that :)

template <class T>
void Graph::bfs(v)
{
  Queue q;
  vector<T> visited;
  for(int i=0; i<numberOfNodes; i++){
    visited[i]=0;
  }  
  q.push(v);
  while(!q.empty()){
    w = q.front();
    if(visited[w]==0){
      visited[w]=1;
      for(int child = 0; child < numberOfNodes; ++child){
        if(isEdge(w, child)){
          q.push(child);
        }
      }
    }
  }
}

No need for bfs to be templated. visited is a vector of char/bytes and yes, I would use 0/1 for true/false (as C++ will treat them that way).

void Graph::bfs(NodeNdx v) // where NodeNdx is probably really int but it is the index of the starting node
{
  Queue q; // Did you mean this to be the STL queue? If so, queue is a templated type
  vector<unsigned char> visited; // signed/unsigned is really unimportant; vector of char IS important

  // Initialize contents of visited; remember that it is currently empty:
  for (int i = 0; i < numberOfNodes; ++i)
    visited.push_back(false); // Note that C++ translates this to a char (value of '\0') for you


The rest looks right: push ALL of the children and worry about visitedness (not really a word) when they come off the queue.

-bcl

Oh yeah that was another question, where in here do they come off the queue, I would say when they are visited correct?

Your code for setting visted[w] looks like it is in the right place. If you want to do more (as in visit the node), do it right before you set visited[w] to 1.

-bcl

Well doesnt the element have to come off of the queue somewhere? or else q.front( ) is always going to be the same thing?

void Graph::bfs(int v)
{
  queue<int> q;
  vector<unsigned char> visited;
  for(int i=0; i<numberOfNodes; i++){
    visited.push_back(false);
  }
  q.push(v);
  while(!q.empty()){
    int w = q.front();
    if(visited[w]==0){
      visited[w]=1;
      q.pop();
      for(int child = 0; child < numberOfNodes; ++child){
        if(isEdge(w, child)){
          q.push(child);
        }
      }
    }
  }
}

Sorry; I don't think in STL terms. Basically right after q.front() you want q.pop(); I read front as taking off and returning the front value.

-bcl

Does this work as a recursive algorithm for dfs? Or would it be smart to stick with using a stack?  This actually isnt working, for some reason its not breaking, but just wanting to see if this is one way I can go about dfs.

void Graph::dfs(int v)
{
  vector<unsigned char> visited;
  for(int i=0; i<numberOfNodes; i++){
    visited.push_back(false);
  }
  visited[v]=1;
  cout << v << " ";
  for(int child = 0; child < numberOfNodes; ++child){
    if(isEdge(v, child)){
      if(!visited[child]){
        dfs(child);
      }
      else
        break;
    }
  }
}

(1) Use a stack; it is just like bfs with a stack for a queue. Really.

(2) Note that visited is initialized each time the recursive function is called. If you want to do this recursively all the calls need to share a single instance of the visited vector.

-bcl

Ok cool.  I had a couple questions concerning the other implementations I plan on doing.
I'm a bit confused on what this is actually trying to say.

1) A linked vertex list with linked adjacency lists.  Is that going to be something like this?  Or is it going to be entirely linked lists?

Vertex        Adj. Vertices
 ___       ______________
|___|---|__|__|__|__|__|
|___|
   |
   |
 _V_      ______________
|___|---|__|__|__|__|__|
|___|


2) A contiguous vertex list of linked adjacency lists. Something like this?
 ___        ______________
|___|-->|__|__|__|__|__|
|___|-->|__|__|__|__|__|
|___|-->|__|__|__|__|__|
|___|-->|__|__|__|__|__|

I honestly don't recognize the difference between linked and contiguous in this instance (I know what the word means and I think your drawing makes sense) but haven't used that distinction before.

Since the nubmer of adjacent vertices is unknown, that is typically some dynamically allocated structure (say a linked list or a vector<>).

Note also that if you are using weights in the vertex list you need to have pairs in the lists associated with any given vertex.

Ok so for the contiguous basically use a vertex or array or even a list for the vertexes and then have linked nodes for the adjaceny list.

Something like:

struct Node{
  int v;
  Node* next;
};

class Graph{
 public:
  void read();
  void write();
 private:
  const static int maxVertices=50;
  Node* adj[maxVertices];
  Graph();
};

Sure BUT what you are calling a Node in this case is REALLY an edge. So if you want to extend this model with edge weights THAT is where you need to look.

-bcl

Am I doing the addEdge right here?  I'm a bit confused on how I would check to see if there is a edge??

#ifndef _TABLEGRAPH_H
#define _TABLEGRAPH_H

class Graph{
 public:
  Graph();
  void read();
  void write();
  void bfs(int v);
  void dfs(int v);
 private:
  int numberOfNodes;
  const static int maxVertices=50;
  bool adj[maxVertices][maxVertices];
  void addEdge(int i, int j);
  bool isEdge(int i, int j);
  void setNumberOfNodes(int n);
};

#endif


#include <iostream>
#include "adjlist.h"
using namespace std;

Graph::Graph()
{
  for(int i=0; i<maxVertices; i++){
    adj[i]=0;
  }
}

void Graph::read()
{
  int i, j, n;
  cout << "Number of vertices: ";
  cin >> n;
  if(0 < n){
    setNumberOfNodes(n);
    while(cin >> i >> j){
      cout << "Adding Edge between " << i << " and " << j << "." << endl;
      addEdge(i, j)
        }
  }
  cout << endl;
}

void Graph::write()
{}

void Graph::setNumberOfNodes(int n)
{
  numberOfNodes=n;
}

void Graph::addEdge(int i, int j)
{
  adj[j] = new Node(i, adj[j]);
  adj[i] = new Node(j, adj[i]);
}

bool Graph::isEdge(int i, int j)
{
  if(edge between i and j)
    return 1;
  else
    return 0;
}

Oops, put the wrong header file up there.

#ifndef _ADJLIST_H
#define _ADJLIST_H

struct Node{
  int num;
  Node* next;
  Node():num(0),next(0)
  {}
  Node(int x, Node* t){
    num=x;
    next=t;
  }
};

class Graph{
 public:
  Graph();
  void read();
  void write();
 private:
  int numberOfNodes;
  const static int maxVertices=50;
  Node* adj[maxVertices];
  addEdge(int i, int j);
  isEdge(int i, int j);
  void setNumberOfNodes(int n);
};

#endif

I figured maybe something like this for isEdge??

void Graph::isEdge(int i, int j)
for(Node* t = adj[i]; t!=0; t=t->next){
   if(t == j)
      return 1;
   else
      break;
}
return 0;
}

Ok well i got it working somewhat.  It finds basically half of the adjacent nodes.  Do I have it coded somehow that this is a directed graph or something?  I'm using the code above with one revision:

for isEdge, if(t->num == j)

Not sure whats causing this, if u need me to pose the entire code again let me know, but if you get a chance do u see anything im missing??

The bug is in your isEdge routine:

1: void Graph::isEdge(int i, int j) {
2: for(Node* t = adj[i]; t!=0; t=t->next){
3:    if(t->num == j)
4:       return 1;
5:    else
6:       break;
7: }
8: return 0;
9: }

What happens when we have the following graph:

Graph G;
G.addEdge(0,1);
G.addEdge(0,2);
G.addEdge(1,2);

and now we call G.isEdge(0,2)? The answer SHOULD be 1, right? It IS 0. Why?

The linked list off of adj[0] is {1, 2} (they are nodes with next pointers but that is the list, in order).
At line 2 t is initialize to point at the node containing 1. Line 3 1 is compared to 2 (the number sought) and doesn't match. The else clause (line 6) is executed, the loop terminated, line 8 returns 0.

The question becomes what is the logic of having a break in loop?

Hope this helps, -bcl

Ah ok i see where that was messing up.  Well cool seems I got those two implementations working.  However the linked list version is giving me trouble.  I should only have to change the addEdge, isEdge, and constructor right?

Ah ok i see where that was messing up.  Well cool seems I got those two implementations working.  However the linked list version is giving me trouble.  I should only have to change the addEdge, isEdge, and constructor right?

That is, basically, the point of having a good interface.

-bcl

Well where should the vertices/nodes be created?  Am I going to need a addVertex method also?

Yes; way back at the top of this thread we worked on an interface that consisted of addNode, addEdge, isEdge, constructor and destructor. You will want those interface functions in all of your versions so the graphs are interchangeable. It may be that addNode just increments a counter (in the first implementation) or pushes something back on a vecotor of pointers (second implementation) or allocates a new node from the heap (third implementation); the client program and functions like bfs don't need to know anything about that.

-bcl

Ok, thats what i figured, i didnt end up putting addVertex in the others, but now i see its needed.

Ok i kinda have an idea of what im trying to do here, am i going about the addVertex, addEdge methods correctly?  The isEdge i really am not sure of yet, so no code yet.

http://www.geocities.com/bjohnson045/linkedlist.txt

For the adjacency matrix the nodes were created by:
  const static int maxVertices=50;
  bool adj[maxVertices][maxVertices];

  setNumberOfNodes simply created a boundry on this determined by the user

For the adjacency list the nodes were created here:
  const static int maxVertices=50;
  Node* adj[maxVertices];

  set nodes does the same thing here

I dont understand where u are saying a counter is incremented or a vector?

I tend to write my adjacency matrix versions to increment the number of nodes each time addNode is called. This is because I usually don't refer to nodes by nubmer but rather by some sort of name. Thus the addNode funciton I was thinking of looks like this:

bool addNode(const &string nodeName) {
  nameVector.push_back(nodeName);
  ++numberOfNodes;
  return true; // should check for too many nodes and return true or false
}

That way I can write the addEdge function to take node names:

bool addEdge(const &string source, const &string target) {
  int sourceNdx = getNdx(source);
  int targetNdx = getNdx(target);
  if ((sourceNdx < 0) || (targetNdx < 0))
    return false;
  adj[sourceNdx][targetNdx] = 1; // only one; this is a digraph
}

In the other instance I mentally used a vector to hold the list of nodes, a vector of pair<string, Edge *> (where string is the name of the node as above and Edge * points at the list of adjacent nodes).

So your addNode routines can be NOP (do nothing) routines in those cases or you can avoid setNumberOfNodes and just add them one at a time. With your implementations it would mean to add one to numberOfNodes each time a new vertex is added.

I won't have a chance to look at your code until tomorrow morning. Hope this helped clear up what I was talking about.

-bcl

(1) Make a constructor for Edge and a constructor for Vertex so that you make sure your pointer fields are all initialized properly.

(2) Why does first_vertex get pointed to a new Vertex in Graph::Graph? Are you using a dummy head node on your linked list? That is, is an "empty" list one with a single, not really used, element in it? If not, why set first_vertex. If so I still say you should have a constructor for Vertex that does all of the work you're doing here.

(3) In addEdge, the following declaration doesn't do what you think it does:
    Vertex *first_position, second_position;
You have declared a pointer at a Vertex (first_position) and a Vertex (second_position); the "*" only modifies the very next variable. Three ways to fix it (in increasing desireability):
  (a) Vertex *first_position, *second_position; // fixed but hard to maintain
  (b) Vertex *first_position;
       Vertex *second_position; // one delcaration per line reminds you to add the star
  (c) // earlier in the program:
       typedef Vertex * PVertex; // create a new type pointing at a Vertex
       
       // in addVertex
       VertexP first_position, second_position; // one type applies across whole line

(4) I don't understand addEdgeat all (sorry, but I am pretty sure you don't, either). Without paying too much attention to detail, what does the function need to do in this implementation?
    first_position = find_vertex(i) // find_vertex returns a pointer at the given vertex or NULL if there isn't one
    second_position = find_vertex(j);

    if ((first_position != NULL) && (second_position != NULL)) {
        // Create a new edge
        // new edge's end point is second_position
        // insert new edge in the list of edges pointed to by first_position->first_edge
    }
 
Yes, you have to write a private member funciton find_vertex(int k); you have the guts of it in the beginning of addEdges but by making it a function you will make what you are doing in the function clearer and you will not get the two loops confused (which I believe you have).

Also: NEVER have a parameter and a local variable with the same name! I think the compiler would catch this one but don't use i as a parameter and as a local count control variable.

(5) addVertex should create a new vertex and insert it into the list. It is just a tail insert into a linked list. You seem to be confused by having multiple types of pointers. Make sure you work with one set of pointers (next_vertex or next_edge) in any given loop.

Hope this helps

Yeah you are right im having a hard time with this.  Well does this look any better??

void Graph::find_vertex(int n)
{
  Vertex *temp;
  temp = first_vertex;

  while(temp->next_vertex != NULL){
    if(temp->value == n){
      return temp;
    }
    else{
      temp=temp->next_vertex;
    }
  }
  return NULL;
}

void Graph::addEdge(int v1, int v2)
{
  Vertex *first_position, *second_position;
  first_position = find_vertex(v1);
  second_position = find_vertex(v2);

  if((first_position != NULL) && (second_position != NULL)){
    Edge* temp;
    temp = first_position->first_edge;
    temp->end_point = second_position;
    // not sure about insert new edge
}

find_vertex does not check the value in the last entry in the linked list. Look at the logic inside the loop.

 if((first_position != NULL) && (second_position != NULL)){
    Edge* temp;
    temp = first_position->first_edge;
    temp->end_point = second_position;
    // not sure about insert new edge
}

Okay, temp is the first edge in the out edges of *first_position. I will call *first_position "firstVertex" since it is a vertex and is pointed to by first_position; similarly with secondVertex.

So, again, temp points at the first edge OUT of firstVertex. You then point the edge at secondVertex. There are two obvious problems here: You are changing an edge that already points somewhere to point at secondVertex (means you lose whatever information was in the edge before) and you never check whether or not temp actually points at anything. Thus temp->end_point could, easily, be dereferencing a NULL pointer and dereferencing a NULL pointer is very, very bad (program crashes and dies bad).

So, have you written code to insert something into a linked list? If so pack it up into a function or, better yet, a linked-list class and just insert a new edge into the linked list. In anycase inserting a new edge means MAKING a new edge (means dynamically allocating it) AND inserting it into the list of outgoing edges in firstVertex. You must ADD the new edge to the list, not replace other edges in the list. You COULD check for a duplicate edge (standard graph theory does not permit duplicate edges in a digraph; the extended structure with multiple edges and self edges is called a multigraph though that term has several incompatible definitions).

Hope this helps, -bcl

I dont understand how this isnt what you meant?

// new edge's end point is second_position
temp->end_point = second_position;

The question is WHAT IS temp POINTING AT?

You do the right thing to the wrong pointer.

-bcl

Its point at the first_positions's first edge right?

Yes, it is. But is that WHERE it should be pointing. Consider again the following sequence of calls:

Graph G;

G.addNode(0);
G.addNode(1);
G.addNode(2);

G.addEdge(0, 1);
G.addEdge(0, 2);

First, the program as written will crash because

    temp = first_position->first_edge;

sets temp to NULL and then

    temp->end_point = second_position;

is equivalent to

    NULL->end_point = ...

and we all know that NULL-> or *NULL is BAD, BAD, BAD.

Okay. Now let us say you insert a new node into first_position->first_edge and then run your code for the second addEdge. What happens?

Well, after the assignment of temp we have:

    temp->end_point->data == 1 (the first edge inserted pointed from 0 to 1).
    temp->next_edge == NULL

now we run

    temp->end_point = second_position;

but second_position points at a DIFFERENT node than it did the last time this was run so NOW

    temp->end_point->data == 2
    temp->next_edge == NULL

There is only one edge out of node 0 and it points at 2.

Hope this helps,
-bcl

Ok im really confused now... i dont know what you meant by the second half of your last post.  I can't seem to follow what you are saying.

Where did data come from?

Basically I have never written a program using linked list, which is obviously a problem because now that im faced with sometime like this i certainly don't have a slight clue about a lot of what im doing.

.data is the number of the node. Since we have a linked list of nodes there is no obvious "index" of the node so I have added  a "data" field to keep track of what number the node has (so they can be found by the value in data).

If you want to ignore that, try the following (from the line "Well, after the assignment of temp we have:" above):

========================================================================

    temp->end_point == find_vertex(1) // the vertex numbered 1
    temp->next_edge == NULL

now we run

    temp->end_point = second_position;

but second_position points at a DIFFERENT node than it did the last time this was run so NOW

    temp->end_point == find_vertex(2) // the vertex numbered 2
    temp->next_edge == NULL

There is only one edge out of node 0 and it points at 2.

========================================================================

Hopefully that clears that up.

Question: Do you have to write your own linked list implementation for this? If the answer is yes I urge you to write a simple templated linked list that you can use to keep track of edges and nodes (where each type is appropriate). I can help you with that.

If the answer is "what other choice do I have?" then think about std::list. This is a STL container with performance characteristics that mean that every implementation I know of is a doubly-linked list under the hood.

Just a thought.

-bcl

Like ive said before im not sure sure what we are required to do, it is never made clear.  But i will ask.

Ok the code you list above in between the === signs.  Is this giving me an example of how my previous code will not work?

Yes.

The problem is that you don't add a new edge to the list of outgoing edges from the node. Instead you point a pointer at the first element in such a list and change the values stored in it.

Again, consider the code I gave a couple of posts back. How many edges should there be out of each of the nodes 0, 1, and 2? The answer is 2 edges out of 0 (one going to 1, the other to 2) and none out of 1 or 2 (assumption is that this is a digraph). That is, after the insertion the adjacency matrix would look like this:

0 1 1
0 0 0
0 0 0

Your code would leave at most one edge out of 0 and that would be the last one added:

0 0 1
0 0 0
0 0 0

This is why the code has problems.

-bcl

I guess we are able to use std::list, havent used it before, but im assuming this will make it a lot easier.

Lots easier. Use lists of pointers (most likely).

Good luck and ask any questions you have.

-bcl

So this is the same thing as the STL list??  If so how would you go about having the double lists?

The STL std::list is implemented as a doubly linked list. You don't need to do anything to have a doubly linked list. You just declare an approriate variable just as you would a vector:

#include <list>
using namespace std;

...

list<Node *> allNodes;

bool addNode(int nodeNumber) {
  allNodes.push_back(new Node(nodeNumber));
}

bool addEdge(int source, int target) {
   Node * s = findNode(source);
   Node * t = findNode(target);

   s->edges.push_back(new Edge(target));
}

You can use almost everything you know about vectors with std::list. The big differences are that list has no operator[] (you can't treat it like an array) and list has a push_front() operator.

-bcl

Does list have a find feature?  I'm looking at some documentation on it but not sure what it is saying, use an iterator? or does find( ) work?  on addEdge, do you have to declare edges somewhere?  I'm looking at how to do is edge,  is there a easy way to see if there is a edge between two vertices?

Given one vertex you can iterate down the list of outgoing edges to see if one "points" to the other node. Something like this:

bool isEdge(int i, int j) {
  Node * iN = findNode(i);

  for (list<Edge *>::iterator it = iN->edges.begin(); it != iN->edges.end(); ++it) {
    if ((*it)->end_point == j)
      return true;
  }
  return false;
}

This assumes that edges is of type list<Edge *> and that an Edge has a field called end_point that is the index of a Node. It also assumes that findNode returns a pointer to a Node.

Note that there is, in fact, a find algorithm in the <algorithm> header file but it is not really suited to finding an element in a container by a field in the class.

-bcl

So you still have to define the node and edge?

Oh yes. std::list is JUST LIKE std::vector in that it is a templated container. You have to decide what gets stored inside it and Node and Edge are the best candidates in your system.

At a minimum, Node contains a list of edges. Edge may only have one or two fields in it (say end_point and, perhaps, weight). Neither has any pointers to other Nodes or Edges; std::list hides the whole linked list thing from you. That is a good thing.

-bcl

So is findNode going to work the same as we last worked on it, or can you use the iterator for the list, and traverse the node list using that until its found, and then return it?

Iterate the list is probably the easiest. You can use push_back to add elements to the two lists in addEdge and addNode.

-bcl

Don't the nodes/vertices need some type of value to distinguish themselves from the others??, i know when i had them there is a vertex number but where does this go??

void Graph::findVertex(int n)
{
  for(list<Vertex *>::iterator it = allVerts.begin(); it != allVerts.end(); ++it){
    if(what iterator points to's value == n)
       return true
   }
return false;
}

Vertex should have a node number data member. Then you can look it up easily with iterators.

That make addVertex something like this:

void Graph::addVertex(int v) {
  Node * n = new Node(v); // now n->vertex_number == n
  allVerts.push_back(n);
}

-bcl

ok one question, when u say Node(v), is this getting set through the constructor?
Also does list require it to be Node or can it be named vertex if i choose?

Sorry. My Node/Vertex problem emerged again. You can have a list of anything that has a copy constructor and an assignment operator (int, pointer, char, class, struct, ...) (I am pretty sure the only requirements are those two things; don't feel like looking it up in the standard right now but I am pretty sure that is correct).

My assumption was that the Vertex constructor would set the vertex_number field in the newly created Vertex object (there, I used Vertex everywhere I could in that sentence).

-bcl

Well ok i got some code together but getting several errors referring to the allVerts and edges not being declared right?

Code is here if you want to take a look:
http://www.geocities.com/bjohnson045/program/

(1) You need to have list defined inside your graph.h file. Just inside the #ifndef stuff put

#include <list>


and then refer to list as std::list inside the header file. It is considered bad form to have using lines inside of header files. Since you only use it a couple of times you can just put in the qualification.

(2) Vertex has no constructor (in the class declaration inside of graph.h). It needs one.

(3) When it has a constructor, the name of the constructor OUTSIDE the class is
    Graph::Vertex::Vertex(/* parameters go here */)

You are missing one of the ::Vertex parts

(4) findVertex needs to return a value.

That is as far as I got in working on compiler errors; there are a lot more.

Hope this helps
-bcl

What does "void value not ignored as it ought to be" usually mean?
Doesnt findVertex need to return a pointer or null?  So would it return a Vertex*.

Note: it will not let me increment points past 500, ill make a seperate points post afterwards.

(1) Whatever with points.

(2) Yes, findVertex should return a pointer or NULL if there is no such vertex. Can you show me the routine where you're getting the error message? I don't recognize the error.

-bcl

Basically these are the errors im getting.  Ill post the up to date code here
www.geocities.com/bjohnson045/program

bash-2.05$ g++ -o test graph.cpp main.cpp
graph.cpp: In method `void Graph::addEdge (int, int)':
graph.cpp:87: void value not ignored as it ought to be
graph.cpp:88: void value not ignored as it ought to be
graph.cpp: In method `bool Graph::isEdge (int, int)':
graph.cpp:95: void value not ignored as it ought to be
graph.cpp: At top level:
graph.cpp:104: syntax error before `*'
graph.cpp:106: syntax error before `!='

graph.h:32 you declare findVertex to return void:
  void findVertex(int n);

Bet it should return Vertex *.

Also: Outside of the Graph class the name of the class is Graph::Vertex (in graph.cpp, for example).

Also, findVertex is flawed. It will only find the matching vertex if it is the very first one in the list. The problem is with the logic of you if statement.

-bcl

>> "Outside of the Graph class the name of the class is Graph::Vertex (in graph.cpp, for example)."
I don't see where your saying i dont have this??

Why do i get syntax errors here:

Vertex* Graph::findVertex(int n)  // get syntax here before *
{
  for(list<Vertex *>::iterator it = allVerts.begin(); it != allVerts.end(); ++it){ // get syntax before !=
    if((*it)->number == n)
      return *it;
  }
  return NULL;
}

The return type of that function is NOT Vertex *. If Vertex is defined INSIDE of the class Graph then the name of the return type is Graph::Vertex *.

There is a new extended lookup in the C++ standard (new as in 3 years old) and I think it handles the local variables inside of the functions (it permits context sensitive lookup). If you are not having any problems with compiling then don't worry about it. I had a problem with the return type name.

-bcl

Ok when I make that change then it tells me that allVerts, Vertex* are all undeclared.  I am guessing I dont have the header file setup correctly but don't see what i need to change.

I have the code you posted compiling. Only changed the header to have findVertex return Vertex * and the return type in graph.cpp is changed to Graph::Vertex *. Other than that I have made no changes (okay, I changed the file names but that is immaterial). As poste, graph.h:32 and graph.cpp:104, respectively.

-bcl

Im getting errors in findVertex with everything not being declared.... i posted my new code.

bash-2.05$ g++ -o test graph.cpp main.cpp
graph.cpp: In function `Graph::Vertex *findVertex (int)':
graph.cpp:106: `Vertex' undeclared (first use this function)
graph.cpp:106: (Each undeclared identifier is reported only once for
each function it appears in.)
graph.cpp:106: parse error before `>'
graph.cpp:106: `it' undeclared (first use this function)
graph.cpp:106: `allVerts' undeclared (first use this function)

It appears the g++ is not using context sensitive lookup OR that it doesn't apply inside of template parameters (I thought it did but my copy of the standard isn't on this computer so I can't look it up). The fix is to use the fully  qualified name for Vertex inside of the name of the type for the loop control variable:

list<Graph::Vertex *>::iterator it /* and so on */

-bcl

Its still not recognizing allVerts?

I am sorry but I don't have the error and don't recognize the error. Try this->allVerts  (should not be necessary but ...).

Hope this helps, -bcl

I just looked at your most recently posted code. The name of the function is Graph::findVertex. I don't know if I added that or if it was somehow removed during your modifications. That would explain why it could not recognize allVerts.

-bcl

No big deal but you might want to close this question (I am assuming from the lack of chatter that you have finished your work).

Hope all went well for you.

-bcl

No comment has been added lately, so it's time to clean up this TA.
I will leave a recommendation in the Cleanup topic area that this question is:

Accept bcladd's comment as answer.

Please leave any comments here within the next four days.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

migoEX
EE Cleanup Volunteer