C++图形构建问题

Question

你好，我希望能够构建一个连接句子的图表。例如，我的文件包含以下几行。

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;

}

- Avinash

---

你的意思是图应该是有向的吗？ - Grigor Gevorgyan

明天我会写答案（现在已经太晚了，凌晨4:18）。但是顺便问一下，你是否使用任何图形库？ - Ramadheer Singh

Answer 1

我可以建议使用这个小型、非面向对象的实现方式。对于您的问题来说很有效：

#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。

- Grigor Gevorgyan

Answer 2

你是否考虑过使用卓越的Boost库之一？

点击这里了解更多信息。

- spraff