Results 1 to 13 of 13

Thread: QTreeView display of graph (multiple parents of item)

  1. #1
    Join Date
    Oct 2009
    Location
    Maryland
    Posts
    16
    Thanks
    3
    Thanked 3 Times in 2 Posts
    Qt products
    Qt4
    Platforms
    MacOS X Unix/X11 Windows

    Default QTreeView display of graph (multiple parents of item)

    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:
    Qt Code:
    1. Root
    2. parentA
    3. node1
    4. node2
    5. parentB
    6. node2
    7. 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?

  2. #2
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,364
    Thanks
    3
    Thanked 5,013 Times in 4,791 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: QTreeView display of graph (multiple parents of item)

    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.
    Your biological and technological distinctiveness will be added to our own. Resistance is futile.

    Please ask Qt related questions on the forum and not using private messages or visitor messages.


  3. #3
    Join Date
    Nov 2011
    Location
    Maryland, USA
    Posts
    2
    Thanks
    3
    Qt products
    Qt4
    Platforms
    Windows

    Default Re: QTreeView display of graph (multiple parents of item)

    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?
    Last edited by fleebness; 6th November 2011 at 23:16.

  4. #4
    Join Date
    Mar 2011
    Location
    Hyderabad, India
    Posts
    1,882
    Thanks
    3
    Thanked 452 Times in 435 Posts
    Qt products
    Qt4 Qt5
    Platforms
    MacOS X Unix/X11 Windows
    Wiki edits
    15

    Default Re: QTreeView display of graph (multiple parents of item)

    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.
    Last edited by Santosh Reddy; 7th November 2011 at 03:49.

  5. #5
    Join Date
    Oct 2009
    Location
    Maryland
    Posts
    16
    Thanks
    3
    Thanked 3 Times in 2 Posts
    Qt products
    Qt4
    Platforms
    MacOS X Unix/X11 Windows

    Default Re: QTreeView display of graph (multiple parents of item)

    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:

    Qt Code:
    1. class Node
    2. {
    3. std::vector<Node *> parents;
    4. std::string name;
    5. public:
    6. void setName(const std::string &name);
    7. const std::string &getName();
    8. Node *parent(unsigned i);
    9. };
    10.  
    11. class Group : public Node
    12. {
    13. std::vector<Node *>children;
    14. public:
    15. Node *childAt(unsigned i);
    16. void addChild(Node *newChild);
    17. };
    To copy to clipboard, switch view to plain text mode 

  6. The following user says thank you to iraytrace for this useful post:

    fleebness (15th November 2011)

  7. #6
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,364
    Thanks
    3
    Thanked 5,013 Times in 4,791 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: QTreeView display of graph (multiple parents of item)

    Usually one implements the following structure:

    Qt Code:
    1. struct Item {
    2. Item *parent;
    3. QList<Item*> children;
    4. };
    To copy to clipboard, switch view to plain text mode 

    and then parent() becomes something like:
    Qt Code:
    1. QModelIndex Model::parent(const QModelIndex &index) const {
    2. if(!index.isValid()) return QModelIndex();
    3. Item *item = static_cast<Item*>(index.internalPointer());
    4. Item *parent = item->parent;
    5. if(parent == m_rootItem ) { return QModelIndex(); } // I'm top level
    6. Item *grandParent = parent->parent;
    7. int row = grandParent->children.indexOf(parent); // find out the row number of the parent
    8. return createIndex(row, 0, parent);
    9. };
    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.
    Your biological and technological distinctiveness will be added to our own. Resistance is futile.

    Please ask Qt related questions on the forum and not using private messages or visitor messages.


  8. #7
    Join Date
    Mar 2011
    Location
    Hyderabad, India
    Posts
    1,882
    Thanks
    3
    Thanked 452 Times in 435 Posts
    Qt products
    Qt4 Qt5
    Platforms
    MacOS X Unix/X11 Windows
    Wiki edits
    15

    Default Re: QTreeView display of graph (multiple parents of item)

    IMO OP is trying to have QTreeView for a item which has multiple parents, then the structure should look like
    Qt Code:
    1. struct Item {
    2. QList<Item*> parents;
    3. QList<Item*> children;
    4. };
    To copy to clipboard, switch view to plain text mode 

  9. #8
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,364
    Thanks
    3
    Thanked 5,013 Times in 4,791 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: QTreeView display of graph (multiple parents of item)

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

    Qt Code:
    1. struct Item {
    2. Item *parent;
    3. QList<Item*> otherParents;
    4. QList<Item*> children;
    5. };
    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.
    Your biological and technological distinctiveness will be added to our own. Resistance is futile.

    Please ask Qt related questions on the forum and not using private messages or visitor messages.


  10. #9
    Join Date
    Mar 2011
    Location
    Hyderabad, India
    Posts
    1,882
    Thanks
    3
    Thanked 452 Times in 435 Posts
    Qt products
    Qt4 Qt5
    Platforms
    MacOS X Unix/X11 Windows
    Wiki edits
    15

    Default Re: QTreeView display of graph (multiple parents of item)

    Quote Originally Posted by wysota
    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?

    Quote Originally Posted by iraytrace
    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.

  11. The following user says thank you to Santosh Reddy for this useful post:

    fleebness (15th November 2011)

  12. #10
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,364
    Thanks
    3
    Thanked 5,013 Times in 4,791 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: QTreeView display of graph (multiple parents of item)

    Quote Originally Posted by Santosh Reddy View Post
    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.
    Your biological and technological distinctiveness will be added to our own. Resistance is futile.

    Please ask Qt related questions on the forum and not using private messages or visitor messages.


  13. The following user says thank you to wysota for this useful post:

    fleebness (15th November 2011)

  14. #11
    Join Date
    Nov 2011
    Location
    Maryland, USA
    Posts
    2
    Thanks
    3
    Qt products
    Qt4
    Platforms
    Windows

    Default Re: QTreeView display of graph (multiple parents of item)

    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.

  15. #12
    Join Date
    May 2014
    Posts
    1
    Thanked 1 Time in 1 Post
    Qt products
    Qt5
    Platforms
    MacOS X Unix/X11 Windows

    Default Re: QTreeView display of graph (multiple parents of item)

    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:
    Qt Code:
    1. struct IndexData{
    2. IndexData *parentIndex;
    3. Entity *parent;
    4. Entity *item;
    5. int row;
    6. };
    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):
    Qt Code:
    1. #include "entitymodel.h"
    2. #include <QDebug>
    3.  
    4. EntityModel::EntityModel(Entity *root, QObject *parent) :
    5. {
    6. m_root = root;
    7. m_rootIndexData = new IndexData;
    8. m_rootIndexData->parent = 0;
    9. m_rootIndexData->parentIndex = 0;
    10. m_rootIndexData->row = 0;
    11. m_rootIndexData->item = root;
    12. }
    13.  
    14. QModelIndex EntityModel::index(int row, int column, const QModelIndex &parent) const
    15. {
    16. if (!hasIndex(row, column, parent)) {
    17. return QModelIndex();
    18. }
    19.  
    20. IndexData *parentData = indexData(parent);
    21. Entity *child = parentData->item->child(row);
    22.  
    23. if (child)
    24. return createIndex(row, column, createIndexData(parentData, child, row));
    25.  
    26. return QModelIndex();
    27. }
    28.  
    29. QModelIndex EntityModel::parent(const QModelIndex &child) const
    30. {
    31. if (!child.isValid())
    32. return QModelIndex();
    33.  
    34. IndexData *data = indexData(child);
    35. if (data->parent == m_root) {
    36. return QModelIndex();
    37. }
    38.  
    39. if (data->parentIndex == 0)
    40. return QModelIndex();
    41.  
    42. return createIndex(data->parentIndex->row, 0, data->parentIndex);
    43. }
    44.  
    45. int EntityModel::rowCount(const QModelIndex &parent) const
    46. {
    47. IndexData *data = indexData(parent);
    48. return data->item->childrenCount();
    49. }
    50.  
    51. int EntityModel::columnCount(const QModelIndex &parent) const
    52. {
    53. return 2;
    54. }
    55.  
    56. QVariant EntityModel::data(const QModelIndex &index, int role) const
    57. {
    58. if (!index.isValid())
    59. return QVariant();
    60.  
    61. if (role != Qt::DisplayRole)
    62. return QVariant();
    63.  
    64. Entity *item = indexData(index)->item;
    65.  
    66. if (index.column() == 0) {
    67. return item->name();
    68. } else if (index.column() == 1) {
    69. return "Entity";
    70. } else {
    71. qCritical() << "Invalid column";
    72. return "";
    73. }
    74. }
    75.  
    76. EntityModel::IndexData *EntityModel::indexData(const QModelIndex &index) const
    77. {
    78. if (index.isValid()) {
    79. IndexData *data = static_cast<IndexData*>(index.internalPointer());
    80. if (data)
    81. return data;
    82. }
    83.  
    84. return m_rootIndexData;
    85. }
    86.  
    87. EntityModel::IndexData *EntityModel::createIndexData(IndexData *parent, Entity *item, int row) const
    88. {
    89. if (!m_indexData.contains(quintptr(parent->item))) {
    90. QHash<quintptr, IndexData*>* hash = new QHash<quintptr, IndexData*>();
    91. m_indexData.insert(quintptr(parent->item), hash);
    92. }
    93.  
    94. if (!m_indexData[quintptr(parent->item)]->contains(quintptr(item))) {
    95. IndexData *data = new IndexData;
    96. data->parent = parent->item;
    97. data->item = item;
    98. data->parentIndex = parent;
    99. data->row = row;
    100. m_indexData[quintptr(parent->item)]->insert(quintptr(item), data);
    101. }
    102.  
    103. return m_indexData[quintptr(parent->item)]->value(quintptr(item));
    104. }
    To copy to clipboard, switch view to plain text mode 

  16. The following user says thank you to Petro Svintsitskyi for this useful post:

    d_stranz (16th May 2014)

  17. #13
    Join Date
    Jan 2008
    Location
    Alameda, CA, USA
    Posts
    4,776
    Thanks
    262
    Thanked 773 Times in 763 Posts
    Qt products
    Qt5
    Platforms
    Windows Android

    Default Re: QTreeView display of graph (multiple parents of item)

    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.

Similar Threads

  1. QTreeWidget item with multiple parents
    By di_zou in forum Newbie
    Replies: 0
    Last Post: 16th November 2009, 16:32
  2. Can't change the text display of a QTreeview item.
    By johnny_sparx in forum Qt Programming
    Replies: 3
    Last Post: 2nd June 2006, 02:03

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.