QTreeView display of graph (multiple parents of item)

[iraytrace]

I'd like to use a QTreeView to display/edit a directed acyclic graph (a tree where a node may have more than one parent). For example, the following tree has node2 used in 2 different places:

Root
  parentA
    node1
    node2
  parentB
    node2
    node3

Root
  parentA
    node1
    node2
  parentB
    node2
    node3

To copy to clipboard, switch view to plain text mode 

The only challenge is implementing the "parent()" method. At the moment there is no way to know the path that was taken to get to a node so that the proper parent can be returned based upon how the node was reached. At the moment, I am thinking of sub-classing QModelIndex (ugh) to extend it with the full path to the object.

Has anyone else done anything like this? How did you do it?

[wysota]

Have a regular Qt model that will work on a separate structure where you store the graph. Don't try to store the graph in the model, it won't work - subclassing QModelIndex or trying to implement parent() to return more than one index will not do you any good.

[fleebness]

I have the same need.

I don't think wysota understood the nature of the problem, and I suppose iraytrace gave up (or at least didn't follow up on any found solutions), so I'll rephrase the question.

A graph is a representation of data that doesn't precisely fit into the notion of a tree (with parents and children), but can sometimes be represented this way none-the-less. For example, in geneology, a child has two parents, who themselves may have multiple children.

I want to provide a tree-like model using the QAbstractItemModel class, so the graph may be displayed in a QTreeView.

Using the geneology example I mentioned earlier, I want a tree node to represent a person, and when you 'expand' the tree node, you get that person's parents (as in, father and mother), and when you expand the father or mother's tree node, you get the father or mother's parents (again, father or mother), etc.

Sounds easy, but the QAbstractItemModel requires you to provide a parent function that takes a QModelIndex with no sense of where you are in the QTreeView (just a row, a column, and possibly a pointer to the actual graph vertex). So, given my graph, I do not know if my parent-node is the mother's first, second, or third child (from her womb). So, I don't know what to return for this function.

Even if I wanted to show this graph upside-down (with the tree node expanding to show a mother's children instead of a child's mother/father), I would run into a the aforementioned problem.

To further clarify, I already have the graph objects separate from the model object... in fact, I want to construct my model object with the graph object as a parameter for the constructor. This design worked really well for iterating over all the vertexes in a graph for a simple QListView (using QAbstractListModel). I just want to figure out a way to represent the graph in this tree-like fashion, and the model format seemed like the best way to go, except for the multiple-parent problem.

Is there another model one should use instead? Do we have to actually build a widget completely from scratch to represent graph-like data like this? Or do we have to use a QTreeWidget and rebuild the widget manually any time there are modifications to the graph? Or perhaps some other solution I haven't considered?

[Santosh Reddy]

It is possible to view graphs like data / nodes using QTreeView. In simple terms it is possible to show the same node under two or more different parent nodes simultaneously. You need to sub-class QAbstractItemModel, and implement the basic interface calls (i guess you should be knowing them).

Now If I understand you question correctly you have problem implementing parent() call. Relook at the createIndex() call, there you can provide an Id / Pointer for the index being created (and returned to view), this Id / Pointer should be the key to access the node from graph container (may be inside model / from some other source). Also you need to add some more intelligence into the Id / pointer using which you can figure out for which parent this index was created.

I can give you an example which I generally follow in my model/view classes, when I create index of an item (node) I encode the parent's row and item specific id into the internalId of the index. At any point later when i get index from view as a request for parent() or data() or setData(), I decode the parent id and item specific id from the index's internalId (index->internalId()) and find out for which parent this index was created.

[iraytrace]

Santosh Reddy:
I would love to see your example code. You have hit the nail on the head: implementing parent() is a problem. I had thought of encoding the path from root into the QModelIndex, but subclassing QModelIndex didn't work out so well.

What I have had to do is implement a "mirror" of the data model for the QTreeView. This kind of defeats the point of QTreeView and as a result I am looking at dropping back to QTreeWidget. I'd still appreciate anything anyone can suggest to keep it to one data model.

To give an idea, the data model I'm wrapping (OpenSceneGraph) looks roughly like this:

class Node 
{
    std::vector<Node *> parents;
    std::string name;
public:
    void setName(const std::string &name);
    const std::string &getName();
    Node *parent(unsigned i);
};
 
class Group : public Node
{
    std::vector<Node *>children;
public:
    Node *childAt(unsigned i);
    void addChild(Node *newChild);
};

class Node 
{
    std::vector<Node *> parents;
    std::string name;
public:
    void setName(const std::string &name);
    const std::string &getName();
    Node *parent(unsigned i);
};

class Group : public Node
{
    std::vector<Node *>children;
public:
    Node *childAt(unsigned i);
    void addChild(Node *newChild);
};

To copy to clipboard, switch view to plain text mode 

[wysota]

Usually one implements the following structure:

struct Item {
    Item *parent;
    QList<Item*> children;
};

struct Item {
    Item *parent;
    QList<Item*> children;
};

To copy to clipboard, switch view to plain text mode 

and then parent() becomes something like:

QModelIndex Model::parent(const QModelIndex &index) const {
  if(!index.isValid()) return QModelIndex();
  Item *item = static_cast<Item*>(index.internalPointer());
  Item *parent = item->parent;
  if(parent == m_rootItem ) { return QModelIndex(); } // I'm top level
  Item *grandParent = parent->parent;
  int row = grandParent->children.indexOf(parent); // find out the row number of the parent
  return createIndex(row, 0, parent);
};

QModelIndex Model::parent(const QModelIndex &index) const {
  if(!index.isValid()) return QModelIndex();
  Item *item = static_cast<Item*>(index.internalPointer());
  Item *parent = item->parent;
  if(parent == m_rootItem ) { return QModelIndex(); } // I'm top level
  Item *grandParent = parent->parent;
  int row = grandParent->children.indexOf(parent); // find out the row number of the parent
  return createIndex(row, 0, parent);
};

To copy to clipboard, switch view to plain text mode 

This makes sense for trees while it doesn't have to make sense for arbitrary graphs (there is no concept of a root item). And I understood the OP's question correctly and I gave a good answer (to make the tree model a subset of an external graph representation) for it.

[Santosh Reddy]

IMO OP is trying to have QTreeView for a item which has multiple parents, then the structure should look like

struct Item {
    QList<Item*> parents;
    QList<Item*> children;
};

struct Item {
    QList<Item*> parents;
    QList<Item*> children;
};

To copy to clipboard, switch view to plain text mode 

[wysota]

Unfortunately this is impossible to express using QAbstractItemModel. One can assume the "first" parent is the "real" parent but then again the structure becomes:

struct Item {
    Item *parent;
    QList<Item*> otherParents;
    QList<Item*> children;
};

struct Item {
    Item *parent;
    QList<Item*> otherParents;
    QList<Item*> children;
};

To copy to clipboard, switch view to plain text mode 

The only way I see happening to represent a graph as a tree is to "snapshot" a subgraph that actually forms a tree and represent only this snapshot in the model. The data structure itself may contain other members (including pointers to items) however they are not relevant to the tree hierarchy of the model. You may look at it like on a genealogy tree. It is not really a tree but a graph but at a particular moment one is only looking only at its subgraph that is a regular tree.

[Santosh Reddy]

Unfortunately this is impossible to express using QAbstractItemModel.

Somehow I still believe that it is possible using QAbstractItemModel and QTreeView, but it not possible using the QModelIndex. As QTreeView uses QModelIndex to reference items in QAbstractItemModel, I would say it not possible using QModelIndex

If we manage to have a CustomModelIndex (enhances QModelIndex) with information required to reference items in the graph (both downlinks and uplinks) it should be possible. But Again the problem is how do we make QTreeView use CustomModelIndex

If somehow we are able to store two internalId / internalPointers in QModelIndex it should be possible. I would use the first internalPointer to store the item reference and the second internalPointer to store the item's parent (the parent under which the item is displayed in the QTreeView) reference.

So it boils down to one question. Is it possible to store two internalPointers in QModelIndex?

At the moment, I am thinking of sub-classing QModelIndex (ugh) to extend it with the full path to the object.

IMO OP tried to sub-class QModelIndex for same reason as above. Again here we have the same problem as above QTreeView is not able to understand sub-classed QModelIndex.

[wysota]

Somehow I still believe that it is possible using QAbstractItemModel and QTreeView, but it not possible using the QModelIndex.

Of course, if you reimplement the whole architecture to do something totally different then it will be possible. The same way as it will be possible to launch a rocket into space using QAbstractItemModel. However this will have little to do with the architecture of QAbstractItemModel.

As QTreeView uses QModelIndex to reference items in QAbstractItemModel, I would say it not possible using QModelIndex

It's not the fault of QTreeView. QAbstractItemModel has a parent() method that returns a SINGLE index. All views rely on that (if not for other things then at least for the root index of the view).

If we manage to have a CustomModelIndex (enhances QModelIndex) with information required to reference items in the graph (both downlinks and uplinks) it should be possible. But Again the problem is how do we make QTreeView use CustomModelIndex

You can put a custom pointer into the index but this will not teach QAbstractItemView to manipulate the graph.


A side note: it IS possible to express a graph in QAbstractItemModel because it is possible to express a graph using a plain two dimensional array. However you need a custom view for that and you lose almost all benefits of having a QAbstractItemModel. it will be much simpler to do without the burden of QAbstractItemModel.

[fleebness]

Thanks, everyone, for continuing the discussion.

I think wysota has it right, that it could be expressed, but it isn't practical. To do this, it seems you have to build a tree first, then model the tree. That negates the point of using a model, so I may as well use QTreeWidget instead of QTreeView, if I'm going to show this as a tree. The more I think about this, the more I see it as impossible, and probably impractical, to use the view, so I probably shouldn't bother.

Alternatively, I suppose, I could try creating a QGraphWidget and QGraphView (with associated QAbstractGraphModel, if I want to make this extensible, etc). That seems like an aggressive lot of code to write for someone new to Qt, though.

[Petro Svintsitskyi]

I know this thread is too old, but maybe my findings will be useful.

I also wanted to have multiple parents for my qtreeview entities (items) and came up with the following solution.

I have an IndexData structure that contains information about current item and it's parent:

struct IndexData{
        IndexData *parentIndex;
        Entity *parent;
        Entity *item;
        int row;
};

struct IndexData{
        IndexData *parentIndex;
        Entity *parent;
        Entity *item;
        int row;
};

To copy to clipboard, switch view to plain text mode 

When QAbstractItemModel::createIndex() function is called, I pass a pointer to IndexData structure as the third parameter.

Full item model class is the following (Please note that it is a quick and dirty solution with memory leaks that was not well tested):

#include "entitymodel.h"
#include <QDebug>
 
EntityModel::EntityModel(Entity *root, QObject *parent) :
    QAbstractItemModel(parent)
{
    m_root = root;
    m_rootIndexData = new IndexData;
    m_rootIndexData->parent = 0;
    m_rootIndexData->parentIndex = 0;
    m_rootIndexData->row = 0;
    m_rootIndexData->item = root;
}
 
QModelIndex EntityModel::index(int row, int column, const QModelIndex &parent) const
{
    if (!hasIndex(row, column, parent)) {
        return QModelIndex();
    }
 
    IndexData *parentData = indexData(parent);
    Entity *child = parentData->item->child(row);
 
    if (child)
        return createIndex(row, column, createIndexData(parentData, child, row));
 
    return QModelIndex();
}
 
QModelIndex EntityModel::parent(const QModelIndex &child) const
{
    if (!child.isValid())
        return QModelIndex();
 
    IndexData *data = indexData(child);
    if (data->parent == m_root) {
        return QModelIndex();
    }
 
    if (data->parentIndex == 0)
        return QModelIndex();
 
    return createIndex(data->parentIndex->row, 0, data->parentIndex);
}
 
int EntityModel::rowCount(const QModelIndex &parent) const
{
    IndexData *data = indexData(parent);
    return data->item->childrenCount();
}
 
int EntityModel::columnCount(const QModelIndex &parent) const
{
    return 2;
}
 
QVariant EntityModel::data(const QModelIndex &index, int role) const
{
    if (!index.isValid())
        return QVariant();
 
    if (role != Qt::DisplayRole)
        return QVariant();
 
    Entity *item = indexData(index)->item;
 
    if (index.column() == 0) {
        return item->name();
    } else if (index.column() == 1) {
        return "Entity";
    } else {
        qCritical() << "Invalid column";
        return "";
    }
}
 
EntityModel::IndexData *EntityModel::indexData(const QModelIndex &index) const
{
    if (index.isValid()) {
        IndexData *data = static_cast<IndexData*>(index.internalPointer());
        if (data)
            return data;
    }
 
    return m_rootIndexData;
}
 
EntityModel::IndexData *EntityModel::createIndexData(IndexData *parent, Entity *item, int row) const
{
    if (!m_indexData.contains(quintptr(parent->item))) {
        QHash<quintptr, IndexData*>* hash = new QHash<quintptr, IndexData*>();
        m_indexData.insert(quintptr(parent->item), hash);
    }
 
    if (!m_indexData[quintptr(parent->item)]->contains(quintptr(item))) {
        IndexData *data = new IndexData;
        data->parent = parent->item;
        data->item = item;
        data->parentIndex = parent;
        data->row = row;
        m_indexData[quintptr(parent->item)]->insert(quintptr(item), data);
    }
 
    return m_indexData[quintptr(parent->item)]->value(quintptr(item));
}

#include "entitymodel.h"
#include <QDebug>

EntityModel::EntityModel(Entity *root, QObject *parent) :
    QAbstractItemModel(parent)
{
    m_root = root;
    m_rootIndexData = new IndexData;
    m_rootIndexData->parent = 0;
    m_rootIndexData->parentIndex = 0;
    m_rootIndexData->row = 0;
    m_rootIndexData->item = root;
}

QModelIndex EntityModel::index(int row, int column, const QModelIndex &parent) const
{
    if (!hasIndex(row, column, parent)) {
        return QModelIndex();
    }

    IndexData *parentData = indexData(parent);
    Entity *child = parentData->item->child(row);

    if (child)
        return createIndex(row, column, createIndexData(parentData, child, row));

    return QModelIndex();
}

QModelIndex EntityModel::parent(const QModelIndex &child) const
{
    if (!child.isValid())
        return QModelIndex();

    IndexData *data = indexData(child);
    if (data->parent == m_root) {
        return QModelIndex();
    }

    if (data->parentIndex == 0)
        return QModelIndex();

    return createIndex(data->parentIndex->row, 0, data->parentIndex);
}

int EntityModel::rowCount(const QModelIndex &parent) const
{
    IndexData *data = indexData(parent);
    return data->item->childrenCount();
}

int EntityModel::columnCount(const QModelIndex &parent) const
{
    return 2;
}

QVariant EntityModel::data(const QModelIndex &index, int role) const
{
    if (!index.isValid())
        return QVariant();

    if (role != Qt::DisplayRole)
        return QVariant();

    Entity *item = indexData(index)->item;

    if (index.column() == 0) {
        return item->name();
    } else if (index.column() == 1) {
        return "Entity";
    } else {
        qCritical() << "Invalid column";
        return "";
    }
}

EntityModel::IndexData *EntityModel::indexData(const QModelIndex &index) const
{
    if (index.isValid()) {
        IndexData *data = static_cast<IndexData*>(index.internalPointer());
        if (data)
            return data;
    }

    return m_rootIndexData;
}

EntityModel::IndexData *EntityModel::createIndexData(IndexData *parent, Entity *item, int row) const
{
    if (!m_indexData.contains(quintptr(parent->item))) {
        QHash<quintptr, IndexData*>* hash = new QHash<quintptr, IndexData*>();
        m_indexData.insert(quintptr(parent->item), hash);
    }

    if (!m_indexData[quintptr(parent->item)]->contains(quintptr(item))) {
        IndexData *data = new IndexData;
        data->parent = parent->item;
        data->item = item;
        data->parentIndex = parent;
        data->row = row;
        m_indexData[quintptr(parent->item)]->insert(quintptr(item), data);
    }

    return m_indexData[quintptr(parent->item)]->value(quintptr(item));
}

To copy to clipboard, switch view to plain text mode 

[d_stranz]

Thanks for this. Now I need to figure out how to implement a model that will handle an undirected cyclic graph which may contain disjoint subgraphs :-) I might have to save that for another lifetime.