你好，我想建立一个连接句子的图表。 例如我的文件有以下几行。

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

所以我希望每个节点都应该有一行，即 ab cd ef 应该是一个节点并且它应该连接到 ef gh ij 应该连接到 ij kl mn.

基本上一行的最后一个词应该连接到第一个词与最后一个词匹配的任何行。

这是我到目前为止的想法，但是当我添加 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;

}

最佳答案

我可以推荐这个微型的、非面向对象的实现。适用于您的问题:

#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;       
}

此外，正如@spraff 所说，如果您想使用设计良好的图形库，请查看 Boost。

关于C++图形构建问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6570667/