C++ Graph Building Question

Question

Hello I want to build a graph for connecting sentences. for example my files has following lines.

ab cd ef
ef gh ij
ij kl mn
xy ab cd

So I want each node should have one line i.e. ab cd ef should be one node and it should be connected to ef gh ij which should be connected to ij kl mn.

Basically last word of a line should be connect to any line whose first word matches with last word.

Here is what I have come up so far, but failing when I add Edges.

#include <map>
#include <string>
#include <deque>
#include <list>
#include <iostream>
#include <stack>
#include <fstream>
#include <vector>

class GraphNode {
public:
    GraphNode(std::string name) {
        std::vector<std::string> words;
        std::string::size_type lastPos = name.find_first_not_of(' ', 0);
        std::string::size_type pos     = name.find_first_of(' ', lastPos);
        while (std::string::npos != pos || std::string::npos != lastPos){
            words.push_back(name.substr(lastPos, pos - lastPos));
            lastPos = name.find_first_not_of(' ', pos);
            pos = name.find_first_of(' ', lastPos);
        }
        first = words[0];
        middle = " ";
        for ( int i = 1; i < (int)words.size() - 1; i++) {
            middle = words[i] + " ";
        }
        last = words[words.size() - 1 ];
    }
    ~GraphNode() {};

    std::string first;
    std::string middle;
    std::string last;
};

struct GraphNodeCompare {
   bool operator() (const GraphNode& lhs, const GraphNode& rhs) {
       return lhs.last < rhs.last;
   }
};

class Graph {
public:
    Graph() {}
    ~Graph() {}
    typedef std::map <GraphNode, std::list<GraphNode>, GraphNodeCompare > GraphType;
    void AddVertex  ( GraphNode vertexID );
    void AddEdge    ( GraphNode vertexLeft, GraphNode vertexRight);
    std::list<GraphNode> GetVertices(GraphNode vertexID);   
    friend std::ostream& operator << (std::ostream& os, const Graph& dt);

private:
    GraphType m_graph;
protected:
};
void Graph::AddVertex(GraphNode vertexID) {
    GraphType::const_iterator iter = m_graph.find(vertexID);
    if ( iter == m_graph.end()) {
        std::list<GraphNode> list;
        m_graph[vertexID] = list;
    }
}

void Graph::AddEdge( GraphNode vertexLeft, GraphNode vertexRight) {
    AddVertex(vertexLeft);
    AddVertex(vertexRight);
    m_graph[vertexLeft].push_back(vertexRight);
    m_graph[vertexRight].push_back(vertexLeft);
}
std::list<GraphNode> Graph::GetVertices(GraphNode vertexID) {
    GraphType::const_iterator iter = m_graph.find(vertexID);
    std::list<GraphNode> list;
    if ( iter != m_graph.end()){
        return m_graph[vertexID];
    }
    return list;
}
std::ostream& operator << (std::ostream& os, const Graph& graph) {
    std::cout << "---------------------------------------------" << std::endl;
    std::map<GraphNode, std::list<GraphNode>, GraphNodeCompare >::const_iterator iter;
    for ( iter = graph.m_graph.begin(); iter != graph.m_graph.end(); ++iter) {
        std::cout << iter->first.first << iter->first.middle << iter->first.last << " : " ;
        std::list<GraphNode> list = iter->second;
        std::list<GraphNode>::const_iterator iter1;
        for ( iter1 = list.begin(); iter1 != list.end(); ++iter1) {
            std::cout << iter1->first << iter1->middle << iter1->last << '\t' ;
        }
        std::cout << std::endl;
    }
    std::cout << "---------------------------------------------" << std::endl;
    return os;
}

int main( int argc, char **argv) {
    Graph *pGraph = new Graph();
    std::ifstream dataFile("D:\\personal\\data\\datas3.txt");
    if ( dataFile.peek() == EOF ) {
        return -1;
    }    
    if (dataFile.is_open()) {
        while (! dataFile.eof() ) {
            std::string line;
            std::getline (dataFile,line);
            GraphNode node(line);
            pGraph->AddVertex(node);
            std::list<GraphNode> vertices = pGraph->GetVertices(node);
            for ( std::list<GraphNode>::iterator itr = vertices.begin(); itr != vertices.end(); ++itr) {
                pGraph->AddEdge( node, *itr);
            }
            //std::cout << line << std::endl;
        }
    }
    dataFile.close();
    //std::cout << *pGraph;
    delete pGraph;

}

Answer 1

I can suggest this tiny, non object-oriented implementation. Works fine for you problem:

#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <string>

typedef std::vector< std::string > Node;
typedef std::pair< int, int > Edge;

// Node stuff
std::string firstWord ( const Node& node ) { return *node.begin(); }

std::string lastWord ( const Node& node ) { return *node.rbegin(); }

void addWord ( Node& node, std::string s ) { node.push_back( s ); }

bool isNotEmpty( const Node& node ) { return !node.empty(); }

bool precedes( const Node& a, const Node& b ) { return lastWord( a ) == firstWord( b ); }


struct Graph
{
    void addNode ( const Node& node ) { nodes.push_back( node ); }
    void addEdge ( const int& from, const int& to ) { edges.push_back( Edge( from, to ) ); }

    std::vector< Edge > edges;
    std::vector< Node > nodes;  
};

std::ostream& operator << ( std::ostream& out, const Graph& graph )
{
    int esize = graph.edges.size();
    for( int i = 0; i < esize; ++i )
    {
        int index1 = graph.edges[ i ].first, index2 = graph.edges[ i ].second;
        for( int j = 0; j < graph.nodes[ index1 ].size(); ++j )
            out << graph.nodes[ index1 ][ j ] << ' ';
        out << "----> ";
        for( int j = 0; j < graph.nodes[ index2 ].size(); ++j )
            out << graph.nodes[ index2 ][ j ] << ' ';
        out << std::endl;
    }
    return out;
}    


int main ()
{
    Graph graph;
    std::ifstream inputFile( "input.txt" );
    std::string s;  

    // reading from file and constructing graph vertices
    if( inputFile.is_open() )
        while( !inputFile.eof() )
        {
            std::getline( inputFile, s );
            std::stringstream ss( s );
            Node node;
            while( ss >> s )
                addWord( node, s );
            if( isNotEmpty( node ) )
                graph.addNode( node );      
        }
    inputFile.close();

    // constructing graph edges
    std::vector< Node > nodes ( graph.nodes );
    int sz = nodes.size();
    for( int i = 0; i < sz; ++i )
        for( int j = 0; j < sz; ++j )
            if( precedes( nodes[ i ], nodes[ j ] ) )
                graph.addEdge( i, j );

    // let's see what we got
    std::cout << graph;

    return 0;       
}

Also, as @spraff says, if you want to use a well-designed graph library, have a look at Boost.

Answer 2

Have you considered one of the excellent Boost libraries?