Some assistance with directed graphs

[beerdog]

Hello,

I am new to the board. I was wondering if anyone would be generous enough to take a look at my code for a directed graph, more specifically, why I keep getting a segmentation fault on the first run of the 'compSearch' function. My suspicion is one of a few dynamic / pointer variables.

#include <iostream>
#include <list>
#include <queue>
#include <fstream>
using namespace std;

class DirectedGraph{

private:
int num;
int edgeNum;
int compNum;
list<int> * adjacent;
bool * visited;

public:
//Constructor
DirectedGraph(int num){
this->num = num;
adjacent = new list<int> [num];
compNum = 0;
edgeNum = 0;
}
//Function to add new vertex
void newEdge(int i, int j){
adjacent[i].push_back(j);
edgeNum++;
}

//Displays information about this graph
void statList(){

cout << "There are " << num << " vertices." << endl;
cout << "There are " << edgeNum << " edges." << endl;

visited = new bool[num + 1];
for(int i = 1; i < num + 2; i++)
visited[i] = false;

for(int i = 1; i < num + 1; i++){
cout << i << endl;
compSearch(i);
}

cout << "There are " << compNum << " components." << endl;
}

//Component search using queues//First iteration of this function causes the crash//
void compSearch(int search){

//Marks all as not visited
//visited = new bool[num];
//for(int i = 0; i < num; i++)
// visited[i] = false;

int temp = search;

if(visited[search] == false){
visited[search] = true;
compNum++;

queue<int> next;
next.push(temp);

//Iterator used for traversing the graph
list<int>::iterator adj;

//While loop to display nodes reachable by item 'search'
while(!next.empty()){
//Dequeues and displays result
cout << next.front() << " ";
temp = next.front();
next.pop();

//Finds adjacent nodes to item 'search'
if(!adjacent[temp].empty()){
for(adj = adjacent[temp].begin(); adj != adjacent[temp].end(); adj++) {
//crash here usually
if(visited[*adj] == false){
visited[*adj] = true;
next.push(*adj);
}
}
}

}//while end

cout << endl;

}//if end

}//compSearch end

};

int main(){
int n, i, j;
ifstream input;
input.open("file.txt");
input >> n;

DirectedGraph graph(n);

while(input){
input >> i;
input >> j;
graph.newEdge(i, j);
}

graph.statList();

return 0;
}

[Chervil]

It's possible there are other errors, (use of new without a corresponding delete stands out).

But I'd start with the file access in main(). There is a logic error - the file status isn't checked until after the data has already been used.

The while loop here:

while(input){
    input >> i;
    input >> j;
    graph.newEdge(i, j);
}

will loop one time too many, the last pair of i, j will be processed twice.

Try something like this - it only uses data after a successful read:

int main()
{
    int n, i, j;
    ifstream input("file.txt");
    
    if (input >> n)
    {
        DirectedGraph graph(n);

        while (input >> i >> j)
            graph.newEdge(i, j);
    
        graph.statList();
    }
}

[48T7M4Gy]

I suspect there is something wrong with your data because your program compiles and runs as follows.

There are 0 vertices.
There are 0 edges.
There are 0 components.
Program ended with exit code: 0

Please give us a sample of your data.

[beerdog]

yeah of course, a file would first read in the number of vertices and then some points of connection.


5
1 5
2 3
3 4

this should output

There are 5 vertices.
There are 4 edges.
1 5
2 3 4
There are 2 components.

[lastchance]

For your digraph, see below. Everything Chervil said is highly relevant (particularly new w/o delete and the input routine). The other big problem was indexing. Arrays start from 0, whereas your nodes start from 1. You partially addressed this, but I don't think you were consistent.

Note that I have internally stored from array index 0, which is why I have had to add two blatant WARNING lines below where I have had to match it up with the node numbers. Since digraphs can have letters, names, etc. for nodes, not just numbers, I wouldn't be inclined to change this.

Your use of a queue was quite neat.

#include <iostream>
#include <list>
#include <queue>
#include <fstream>
using namespace std;


class DirectedGraph
{
private:
   int num;
   int edgeNum;
   int compNum;
   list<int> *adjacent;
   bool *visited;

public:
   // Constructor
   DirectedGraph( int num )
   {
      this->num = num;
      visited = new bool[num];
      adjacent = new list<int> [num];
      compNum = 0;
      edgeNum = 0;
   }

   //Function to add new vertex
   void newEdge( int i, int j )
   {
      adjacent[i].push_back( j );
      edgeNum++;
   }


   //Displays information about this graph
   void statList()
   {
      cout << "There are " << num     << " vertices." << endl;
      cout << "There are " << edgeNum << " edges."    << endl;

      // Find separate unconnected sets
      for( int i = 0; i < num; i++ ) visited[i] = false;
      for( int i = 0; i < num; i++ ) compSearch(i);
      cout << "There are " << compNum << " components." << endl;
   }


   // Component search using queues
   // Searches for everything connected directly or indirectly to 'search'
   void compSearch( int search )
   {
      int temp;
      list<int>::iterator adj;
      queue<int> next;
      
      if ( !visited[search] )          // only if not previously connected to anything
      {
         compNum++;                    // increment number of separate components
         visited[search] = true;       // mark as visited
         next.push(search);            // start queue with this value
      

         //Find everything reachable from current front of queue
         while( !next.empty() )
         {
            // store the current loose end, output it and remove it from the queue
            temp = next.front();   next.pop();
            cout << temp + 1 << " ";             // **** WARNING ( INDEXING ) ****
         
            // Check whether nodes connected to this loose end have been visited
            if ( !adjacent[temp].empty() )
            {
               for ( adj = adjacent[temp].begin(); adj != adjacent[temp].end(); adj++ )
               {
                  if ( visited[*adj] == false )
                  {
                     visited[*adj] = true;
                     next.push(*adj);  // add a new unvisited node to the queue
                  }
               }
            }
         }
         cout << endl;      // complete this set of connected nodes
      }
   }
};



int main()
{
   int n, i, j;
   ifstream input;

   input.open( "file.txt" );
   input >> n;

   DirectedGraph graph(n);

   while( input )
   {
      input >> i >> j;
      if ( input ) graph.newEdge( i - 1, j - 1 );         // **** WARNING ( INDEXING )****
    }

    graph.statList();

    return 0;
}

From the data
5
1 5
2 3
3 4
it produces

There are 5 vertices.
There are 3 edges.
1 5 
2 3 4 
There are 2 components.

I believe this to be correct - there are 3 edges in your data, not 4.
The code correctly divides them into two disconnected components.

[beerdog]

I see, I wouldn't have guessed a big part of the problem would be in main and that is obviously the place i wouldn't have been looking. I knew about the arrays starting from 1, mostly wanted them to correspond with the data (since there wouldn't be any 0s) but I can definitely see how that played against me.

I appreciate the help, thank you very much :)