Create Directed Acyclic Graph (DAG) from XML-Tree

Question

I've written a program that creates the (minimal unique) directed acyclic graph from the tree structure of an XML-document. The program prints a Bplex-Grammar to cout. I'm interested in all kinds of remarks, and especially performance optimization.

#include <iostream>
#include <sstream>
#include <boost/foreach.hpp>
#include <boost/functional/hash.hpp>
#include <libxml++/libxml++.h>
#include <string>
#include <stack>
#include <vector>
#include <tr1/unordered_map>
#include <tr1/unordered_set>
#include <list>

// compile with:     g++ -Wall -g -Wno-deprecated `pkg-config --cflags libxml++-2.6` -o Dag dag.cpp `pkg-config --libs libxml++-2.6`


using namespace std;
using namespace tr1;
class TreeNode;
class TreeNodeHasher;
class TreeNodeEqualityTester;

typedef list<unsigned int> childrenList;
typedef unordered_map<unsigned int, unsigned int> GRAMMAR_MAP; 
typedef unordered_map<TreeNode*, unsigned int, TreeNodeHasher, TreeNodeEqualityTester> TREE_HASH_MAP;
typedef unordered_map<unsigned int, TreeNode*> RULES_MAP; 

class TreeNodeHasher
    : unary_function<TreeNode*, size_t>{
public:
    size_t operator()(TreeNode * pNode) const;
};

class TreeNodeEqualityTester
    : std::binary_function<TreeNode*, TreeNode*, bool>{
public:
    bool operator()(TreeNode *pNode1, TreeNode *pNode2) const;
};

class TreeNode{
    friend class TreeNodeHasher;
    friend class TreeNodeEqualityTester;

public:
    TreeNode(){;}
    TreeNode(string namePar, childrenList childrenListPar); 
    ~TreeNode(){;}

    string getName(){return this->name;}
    unsigned int getNumberOfChildren(){return this->numberOfChildren;}
    childrenList getKidsList(){return this->kidsList;}
    void incrementRefCount(){refCount++;}
    unsigned int getRefCount(){return refCount;}

private:
    string name;
    childrenList kidsList;
    unsigned int numberOfChildren;
    unsigned int refCount;
};


class MySaxParser : public xmlpp::SaxParser
{

public:
    MySaxParser(char * pFilePath, bool printProductionsPar);
    ~MySaxParser(void);
    void printProduction(TreeNode *pNode, unsigned int lhs, bool start);

protected:
  //overrides:
    virtual void on_end_document();
    virtual void on_start_element(const Glib::ustring& name,const AttributeList& properties);
    virtual void on_end_element(const Glib::ustring& name);

private:
    unsigned int leftHandSides;
    /**
      * For print use only.
      */
    unsigned int printedLeftHandSides;
    /**
      * The childrenStack is needed for parsing only.
      */
    stack< childrenList*> childrenStack;
    /**
      * The hash map of all trees encountered till now. TreeNode->unsigned int
      */
    TREE_HASH_MAP treeHashMap;
    /**
      * Only if a rule is the start production or encountered at least twice is it added to grammarMap.
      * It maps to the id of the TreeNode that has been found at least twice.
      */
    GRAMMAR_MAP grammarMap;
    /**
      * All unsigned int -> TreeNode are placed here. We need this for printing.
      */
    RULES_MAP rulesMap;

    /**
      * If true, we print the productions.
      */
    bool printProductions;

};

bool isNumber(string s){
    if(atoi(s.c_str()) > 0)
        return true;
    else
        return false;
}

string toString(unsigned int number){
   stringstream ss;//create a stringstream
   ss << number;//add number to the stream
   return ss.str();//return a string with the contents of the stream
}

TreeNode::TreeNode(string namePar, childrenList childrenListPar):
    name(namePar), kidsList(childrenListPar), refCount(1){
    numberOfChildren = kidsList.size();
}

size_t TreeNodeHasher::operator()(TreeNode *pNode) const {
    size_t hash_value = 0;
    hash_value =  tr1::hash<string>()(pNode->name);
    boost::hash_combine(hash_value, pNode->kidsList);

    return hash_value;

}

bool TreeNodeEqualityTester::operator()(TreeNode *pNode1, TreeNode *pNode2) const{
    if(pNode1->name != pNode2->name){
        return false;
    }
    if(pNode1->numberOfChildren != pNode2->numberOfChildren){
        return false;
    }
    if(pNode1->kidsList != pNode2->kidsList){
        return false;
    }

    return true;
}

MySaxParser::MySaxParser(char * pFilePath, bool printProductionsPar) :
    xmlpp::SaxParser::SaxParser(), leftHandSides(2), printedLeftHandSides(2), printProductions(printProductionsPar){

    this->set_substitute_entities(true); //
    this->parse_file(pFilePath);

}

MySaxParser::~MySaxParser(void){
    BOOST_FOREACH(TREE_HASH_MAP::value_type i, treeHashMap){
        delete i.first;
    }
}

void MySaxParser::on_start_element(const Glib::ustring& name,const AttributeList& attributes){
    childrenList * chList = new childrenList();
    childrenStack.push(chList);
}

void MySaxParser::on_end_element(const Glib::ustring& name){
    unsigned int lhs = 0;
    string tmpname = name.raw();
    TreeNode * pTopNode = new TreeNode(tmpname, *childrenStack.top());
    delete childrenStack.top();
    childrenStack.pop();

    TREE_HASH_MAP::iterator it = treeHashMap.find(pTopNode);
    if(it == treeHashMap.end()){ // we've found the node for the first time
        if(childrenStack.size() == 0){ //root node
            treeHashMap[pTopNode] = 1;
            rulesMap[1] = pTopNode;
            grammarMap[1] = 1;
            if(printProductions){
                printProduction(pTopNode, 1, true); cout << endl;
            }
            return;
        }else{  //non-root node.
            treeHashMap[pTopNode] = leftHandSides;
            rulesMap[leftHandSides] = pTopNode;
        }
        lhs = leftHandSides;
        leftHandSides++;
    }
    else{
        delete pTopNode;
        lhs = it->second;
        it->first->incrementRefCount();
        if(it->first->getRefCount() == 2 && it->first->getNumberOfChildren() > 0 ){
            //we've found the rule twice, hence we add it to the grammarMap.
            grammarMap[lhs] = printedLeftHandSides;
            if(printProductions){
                printProduction(it->first, printedLeftHandSides, true); cout << endl;
            }
            printedLeftHandSides++;
        }
    }
    childrenList * chList = childrenStack.top();
    chList->push_back(lhs);
}


void MySaxParser::on_end_document(){
    cout << "size: " <<  treeHashMap.size() << endl;
}


void MySaxParser::printProduction(TreeNode *pNode, unsigned int lhs, bool start){

    if(start)
        cout << "A" << lhs << " -> ";
    cout << pNode->getName() ;
    if(pNode->getNumberOfChildren() > 0){
        unsigned int commaCounter = 1;
        TreeNode * pKidNode = 0;
        childrenList printList = pNode->getKidsList();
        childrenList::iterator chIt;
        GRAMMAR_MAP::iterator grIt;
        RULES_MAP::iterator ruIt;
        cout << "(" ;
        for(chIt = printList.begin(); chIt != printList.end(); chIt++){
            grIt = grammarMap.find(*chIt);
            if(grIt == grammarMap.end()){
                ruIt = rulesMap.find(*chIt);
                pKidNode = ruIt->second;
                printProduction(pKidNode, lhs, false);
            }
            else{
                cout << grIt->second;
            }
            if(commaCounter < pNode->getNumberOfChildren()){
                cout << ", ";
            }
            commaCounter++;
        }
        cout << ")" ;
    }
}

int main(int argc, char* args[]){

    if(argc < 2){
        cout << "Please add file. " << endl;
        return 0;
    }
    char * pFilePath = args[1];

    MySaxParser mySaxParser(pFilePath, true);

    return 0;

}

Answer 1

You don't need the semi-colon(';') here (it looks weird).

    TreeNode(){;}

The default destructor also does nothing.
If you are not doing anything use the one provided.

    ~TreeNode(){;}

You TreeNode methods are not const correct:
Mark methods that are non mutating as const. Return objects by reference to avoid a copy operation. If you don not want to give access to the underlying object then return a const reference to the object.

    string const&        getName()              const  {return this->name;}
    unsigned int         getNumberOfChildren()  const  {return this->numberOfChildren;}
    childrenList  const& getKidsList()          const  {return this->kidsList;}
    unsigned int         getRefCount()          const  {return refCount;}

Prefer pre-increment to post-increment.
For fundamental types there is no advantage for either. But for object types there is a difference as the default implementation requires an extra copy construction for post-increment. Even though you are using a fundamental type here that may not always be the case (future extensions may change things) in which case you have to go and change your post-increment to pre-increment to stay effecient. So it is a good habbit to get into.

    void                 incrementRefCount()           {refCount++;}

I am not convinced you is_Number() function works:

bool isNumber(string s){
    if(atoi(s.c_str()) > 0)
        return true;
    else
        return false;
}

What happens for isNumber("0")

Also pass the string parameter by const reference This allows remporaries to be passed to the function (otherwise the above call will not work as the compiler can not construct a temporary std::string object and pass it to isNumber()).

Other issues:

• atoi() is relatively expensive.
• "12.34" is a number and would return true (I think) is that what you intended?

Your convert to string method:

string toString(unsigned int number){
   stringstream ss;//create a stringstream
   ss << number;//add number to the stream
   return ss.str();//return a string with the contents of the stream
}

Find a standard one they have been done a million times before.

boost::lexical_cast<std::string>()  // should work for you.

If you must do it yourself at least templatise it so that it works for anything:

template<typename T>
string toString(T const& number)
{
   stringstream ss;    //create a stringstream
   ss << number;       //add object to the stream
   return ss.str();    //return a string with the contents of the stream
}

One operation per line please. That includes the initalizer list:

TreeNode::TreeNode(string namePar, childrenList childrenListPar):
    // 
    // This is hard to read.
    name(namePar), kidsList(childrenListPar), refCount(1){
    numberOfChildren = kidsList.size();
}

// I like:

TreeNode::TreeNode(string namePar, childrenList childrenListPar)
    : name(namePar)
    , kidsList(childrenListPar)
    , numberOfChildren(kidsList.size())
    , refCount(1)
{}

Dislkie the use of this argument to call methods with:

this->set_substitute_entities(true); //
this->parse_file(pFilePath);

Why not just use:

set_substitute_entities(true);
parse_file(pFilePath);