Menu

Visualise doubles associated to nodes

Help
2018-10-04
2018-10-10
  • Oliver Kullmann

    Oliver Kullmann - 2018-10-04

    Hello, I have the following generic problem: Given is a graph (actually it is typically a binary tree), and a natural number k, such that every node has a k-tuple of real numbers associated with it. Visualise this labelled graph.

    Via property-type double I can create such graphs, but how to visualise them? The easiest possibility which comes into my mind is a grey scale, for just one component of the k-tuple. In the application one can download, I couldn't find such an option? Of course, I would hope that there are lots of options for visualisation? Especially for visualising several components at the same time.

    Two related questions:
    1. It seems one can not specify properties just for nodes? In our application we never have properties of edges.
    2. Often indeed the real number is an integer, but since no range of the integer is specified, and indeed the integers can be very big (the problems are related to combinatorial mathematics), it seems double is more appropriate?

    Thanks for your help!

    Oliver

     
  • Oliver Kullmann

    Oliver Kullmann - 2018-10-04

    Searching the literature for visualisation of graphs, I can't find anything in the direction we needed (somewhat strange). Actually, the binary-tree-structure is rather central, so instead of a graph we should focus on binary trees here (rooted trees, where every node has at most two children, and the children are either "left" or "right" children). We also want to look at small trees, with just hundreds of nodes, but really interesting case should at least include millions of nodes, hopefully up to billions.

    It seems we have then to write an application ourselves, where we simply compute from the k-tuples of each node a colour of each node, in various ways as we specify it, and the application then shows the tree in this colour-scheme. We would then need the Rheingold-Tilford algorithm for the positioning of the vertices, and various colour-codings of real numbers. Are there already library-components for this in Tulip?

    Concerning the colours: it seems you are using the RGBA colour-model
    https://en.wikipedia.org/wiki/RGBA_color_space
    So for handling the k numerical attributes a simple model looks like this:
    1. For each component, determine min and max.
    2. Choose a colour for each component, and for each component, map the numerical values to different intensities of the respective colours, with the min-value corresponding to minimal intensity.
    3. Map the nodes with these colours and overlay these colour schemes.

    Just using one colour, one would hope that one could see the distribution of the values, in interaction with the topology of the tree.
    One would also hope that in this way one could handle at least two attributes at the same time, how they interact.

    The application needs to enable user-interaction, and this in a fast way. So that one could choose two attributes, get the tree, and then slide through the opacity-range, starting with one attribute visible only, and increasing the contribution of the second attribute, until at the end only the second attribute is visible. Possibly only through such dynamical visualisation more complicated patterns become visible.

     

    Last edit: Oliver Kullmann 2018-10-04
  • Oliver Kullmann

    Oliver Kullmann - 2018-10-04

    Through experimentation meanwhile I found out the following (seem to be speaking to myself, but who knows):
    1. There is the rendering-algorithm "Hierarchical Tree (R-T Extended)", which should be the Rheinhold-Tilford algorithm. Seems basically to work, except that the handling of the node-sizes, which is important here, can not be directly influenced.
    2. For the colour-scheme there is "Color Mapping", which computes the attribute viewColor.

    Concerning "alpha", there is "Alpha Mapping", by which the attribute viewColor can be modified, but I can't see how to apply this to different layers of the graph, given by various input-attributes. So let's ignore this for now.

    For viewing a single numerical property, we are coming closer to what we want, but there is the following problem: The numerical values are actually only meaningful for the inner nodes, the non-leaves. It seems one better defines already with the input-graph the boolean attribute "leaf". Now the colouring should only be applied to the inner nodes, those where attribute "leaf" is false -- how is this possible?

    And for the leaves there are two types of leaves, which are given by an input-attribute. There should be two clearly visible symbols for these two types of leaves of the tree -- how to do this?

    When considering the selection-facilities, then it seems there are no boolean-logic facilities available?? So that it is not enough to have the boolean attribute "leaf" in the input, since one can not select the value "false" here?? So one needs another attribute "nonleaf" for the input? Rather strange. One has certain possibilities to copy existing properties, and set nodes to true/false, perhaps one can achieve negation, but that is unclear, and arcance in any way.

     
    • Melançon Guy

      Melançon Guy - 2018-10-04

      Dear Oliver,

      you are not talking to yourself, I am listening carefully :-) Haven't you seen my answer to your first post?

      I just ran a test, and it seems the R-T algorithm does take node size into account (at least their width). Again, you won't find an already made plugin that will use your k-tuples, you probably have to write a proper script that will do what you exactly need.

      For instance, applying you color scheme to non leaves nodes can be dealt with by custumizing the colormap using a function my_map(node):
      for n in graph.getNodes():
      graph['viewColor'][n] = my_map(n)
      for instance ...
      On the boolean selection facilities, have a look at the search functionality at the bottom of the right panel ...

      I assure you there are lots of things out there to solve you problem.

       
      • Oliver Kullmann

        Oliver Kullmann - 2018-10-04

        Dear Melancon,
        you wrote "Haven't you seen my answer to your first post?"
        I indeed updated the Forum-page permanently, but your answers did show up only some time later ...
        If I can, I definitely want to avoid any scripting (never Python), and any programming (all of that Qt ... ). It's not just me, it's also the students --- they can waste endless time with that. And if that problem with colouring only a subclass of nodes is solved (which should be possible), then we are there!

        The selection of the nodes isn't the problem (we can hardcode this in the input file without problems), but just that we can colour only selected nodes.
        Oliver

         
  • Oliver Kullmann

    Oliver Kullmann - 2018-10-04

    I hoped that with "clusters" one could colour the inner nodes differently from the leaves. But unfortunately the colouring-algorithm has no effect, when a cluster is selected! The variable "input property" is reset when clicking on a different cluster/sub-graph, but that's it, no other effect (except of changing the "local variable" viewColor, which seems not usable).

    The whole usage seems rather unintuitive to me. It seems that at least the application is driven by intuitions coming from very special backgrounds, while as a generic mathematician/computer scientist one is not supported (or has to write such an application oneself :-(( ). The whole concept of these computations via "properties" (which act as variables) in the application seems very restricted, no general idea behind it, which would make it more powerful. You can't really work with these variables.

    Or if the Color-algorithm just had also a select-button, as some other algorithms have ...

    If one considers "Elements", and selects the cluster, then one gets shown the colours computed "locally" for these nodes --- but how to move these values to the global level? It seems at some point I managed to just have the colours for the cluster ... but I couldn't reproduce this.

     
    • Melançon Guy

      Melançon Guy - 2018-10-04

      Hi Oliver,

      you seem to be a very impatient person :-)

      I assure you the property-based approahc for grpahs is one of the most mathematically principled, general, multi-purpose and powerful approcah you can imagine. ï really hope you may believe me, I have been working in the area for quite some time. I could list tens of papers our tem has published in the area.

      The most reasonable thing to do is to stop looking for the right button to press. You need to sit down and write your own (python) script. You don't need to write an applicaiton, a script will do fine.

       
      • Oliver Kullmann

        Oliver Kullmann - 2018-10-04

        Hi Melancon,

        I think that property-business is more of a hack, and you can't get that implemented really efficiently. But that's not the problem, the Boost graph library takes a similar (but more generic) approach. One just needed to take, in that application, the properties serious! That is, allow for example assignments for them. Then we could just assign the local colouring to the global colouring, and problem solved!

        The scale of colouring-algorithms available in the application looks fine, and I am not aware of something similar elsewhere. After consultation with computer scientists working in visualisation, in our department and elsewhere, it seems the (general) application to trees I have in mind has never been done before, and so definitely a lot of playing around is needed. Except of that business with the local colouring, the application seems to provide all what we need.

        Oliver

         
        • Melançon Guy

          Melançon Guy - 2018-10-05

          Me again,

          you write "I think that property-business is more of a hack, and you can't get that implemented really efficiently."

          I am sorry Oliver, but you are totally wrong. This is not a hack, this is one of the core features of Tulip which allows it to deal with very, very large graphs, and more particularly allows it to efficiently deal with very large hierarchies of graphs. I know no other software with that capabilities, and I know quite a few others.

          I can expand my thought on this if you loike.

          Guy

           
          • brenoust

            brenoust - 2018-10-05

            Dear Oliver,

            Just throwing one idea here:
            I feel that some of your issues may be resolved with a quick hands-on demo
            with someone knowing Tulip.
            You are from Swansea University, aren't you? It happens that one excellent
            expert and contributor of Tulip is also a faculty in your university:
            Daniel Archambault.
            I am not sure Dan is still receiving the sourceforge emails and seeing this
            conversation, but he is the kindest of all, and I am sure he could show you
            some cool tricks should you ask him.

            Best wishes,

            Benjamin

            On Fri, 5 Oct 2018 at 14:15, "Melançon Guy" melancon@users.sourceforge.net
            wrote:

            Me again,

            you write "I think that property-business is more of a hack, and you can't
            get that implemented really efficiently."

            I am sorry Oliver, but you are totally wrong. This is not a hack, this is
            one of the core features of Tulip which allows it to deal with very, very
            large graphs, and more particularly allows it to efficiently deal with very
            large hierarchies of graphs. I know no other software with that
            capabilities, and I know quite a few others.

            I can expand my thought on this if you loike.

            Guy

            Visualise doubles associated to nodes
            https://sourceforge.net/p/auber/discussion/206283/thread/638b3490d1/?limit=25#32ac/353d/9b65/38f2


            Sent from sourceforge.net because you indicated interest in
            https://sourceforge.net/p/auber/discussion/206283/

            To unsubscribe from further messages, please visit
            https://sourceforge.net/auth/subscriptions/

             
            • Oliver Kullmann

              Oliver Kullmann - 2018-10-05

              Ha, that's fun -- Dan is just next door :-)
              So that should solve indeed the problem!
              Thanks Benjamin

              Concerning that hacking-business: As I said, I worked with properties, in a more generic (powerful) setting, in the Boost (C++) Graph library. From a complexity point of view it's a hack -- but that doesn't mean that it isn't useful! The whole Linux is kind of a hack, and it is useful. And perhaps that hack here is very hard to make better, in general. You might then not call it a "hack", but I didn't say that hacks are bad :-)

              Greetings

              Oliver

               
  • Melançon Guy

    Melançon Guy - 2018-10-04

    Dear Oliver,

    I need to make sure I understand the problem you are trying to solve. I believe Tulip can help you quite a bit. I would advise to have a real look at it before building your own app -- Tulip benefited (and still benefits) from a significant development effort over more than 10 years.

    So, I understand you need to visualize trees, small an

    d large. Tulip offers about 10 different tree layout algorithms adopting different geometrical patterns. Depending on the structure of the trees you consider, you may be able to comfortably visualize larger trees although at some point you may need to zoom and pan.

    Now, I see you have an issue with how you may deal with the k-tuples associated with each of your nodes. There are several options: associate the whole tuple at once or spread them over different properties (it makes sense since the tuples all have the same size and k may be fixed).
    I believe your problem is to propermy define a colormap so you don't need to inspect individual values but rather get an overview of how values distribute over nodes. Am I right?

    I hope you do see what I am suggesting. Tulip is property-based, that is anythign you know or compute on the graph is stored as a hasmap indexed by nodes and edges. Property may hold numerical values or string, colors, shapes, etc. Properties may also hold vectors of these values (tuples).

    When assigning (computing) a color to a node (you may also assign a color to the border of the node or to its label), you may used predefined functions (throught the menu). What I see is you may need to write a script (python) to compute colors out of the values in the k-tuples.

    Let me know whether all this makes sense. I'd be happy to help you with tulip-python (I am a great fan and enthusiastic user of this very unique Tulip's scripting functionality).

     
    • Oliver Kullmann

      Oliver Kullmann - 2018-10-04

      You write: "There are several options: associate the whole tuple at once or spread them over different properties (it makes sense since the tuples all have the same size and k may be fixed)." Yes, but that's just a technicality. Having it as single properties is perhaps better, since then you have proper names for it.

      You write: "I believe your problem is to propermy define a colormap so you don't need to inspect individual values but rather get an overview of how values distribute over nodes. Am I right?" Yes. I consider this problem already for quite some time, and the colourmaps in the application indeed cover all the possibilities. For a single property that is, and that's a good start.

      You write "What I see is you may need to write a script (python) to compute colors out of the values in the k-tuples." If at some point we have a good idea how to combine several node-properties, then it would seem more sensible to do this more generally at the level of the graph-generation, namely combining these several numbers into a single number, which then can be visualised as usual.

      You write: "Let me know whether all this makes sense. I'd be happy to help you with tulip-python (I am a great fan and enthusiastic user of this very unique Tulip's scripting functionality)." Thanks for the offer! But as I said, I hope we can figure out how to overcome the hurdle of colouring only some nodes, and then we can systematically experiment with all these colouring schemes, which seems absolutely needed. A few years ago a (good) student already implemented the Rheingold-Tilford algorithm (which seems by far best here) with a fixed colouring scheme (a few parameters) in Qt, and it became clear that to make something out of that, the colouring-question is absolutely non-trivial, and there doesn't seem to be anything in the literature in this direction.

      To give you a rough impression what our trees are: They come from the area of ATP, Automated Theorem Proving, and represent the search for a counterexample to the Theorem to be proven. Our biggest success yet is described in
      https://cacm.acm.org/magazines/2017/8/219606-the-science-of-brute-force/fulltext
      The Science of Brute Force
      The trees are computed in intricated and, though provably correct, but finally very "mysterious" ways, and they are the result of large computations. We want to understand (somewhat) what actually is going on. Thus at the nodes, which correspond to backtracking decisions, we observe many details of the reasoning-process and about the heuristics involved. Billions of nodes isn't very large for such a tree, and there are many aspects of the reasoning and the heuristics involved you can observe.
      The visualisation is just one of many approaches. Nobody did something like that before (as far as we know).

      Greetings and thanks again

      Oliver

       

      Last edit: Oliver Kullmann 2018-10-04
      • Melançon Guy

        Melançon Guy - 2018-10-05

        Hi Oliver,

        ok, let's see if I can help. As a first step, you'd like to color internal nodes of your trees and them only, is that right ?
        So a way to acheive this wold be to:
        select all internal nodes
        make a subgraph out of them
        color nodes of that subgraph
        bring that coloring back to the original tree
        Is that right? I can script this in a few minutes, I juts need to make sure I get things right. ANd probably also define what color non-colored nodes wojuld be (white with a simple black border?)

        Cheers
        Guy

         
        • Oliver Kullmann

          Oliver Kullmann - 2018-10-05

          Hi Guy,
          today I am fully busy with teaching and admin, so can continue properly only tomorrow.
          But just some quick remarks:
          1. We definitely need a lot of experimentation, and thus need much (all) of the functionality available in the Tulip 5.2 application. When you write "script", is this some form of plug-in to that application?
          2. What seems fully sufficient would be to add the field "selection" (as you have it for "To labels") to the algorithm "Color Mapping". Then we could compute the colouring piecewise.
          3. We can augment the input in any form (it comes out of our C++ program).
          4. If it is not possible to extend the Tulip-application with selection-fields, then we needed indeed to distinguish between three types of nodes (can come from the input-file, in any form): inner nodes, and two types of leaves.
          5. For the inner nodes we needed the full strength of colouring algorithms available, for experimentation.
          6. For the two types of leaf nodes, constant colours are fine, but it might be needed to change these colours (depending on the colouring of the inner nodes).
          7. It seems (another) bug of the Tulip-application to have the " Alpha Mapping" algorithm basically being useless: In principle one could achieve with it the piecewise computation of colouring, but it seems with every application of "Color Mapping" always all nodes are changed.
          8. One could create new properties, for the single computations, in the Tulip-application. But I don't see a possibility to combine these properties into another one --- there seems NOTHING what you can do with properties, except applying the predefined algorithms, or setting them to just constant values. This seems another bug of the application -- obviously you need some form of general operations on the properties.

          Thanks for your help!

          Oliver

           
    • Oliver Kullmann

      Oliver Kullmann - 2018-10-04
      Post awaiting moderation.
  • Oliver Kullmann

    Oliver Kullmann - 2018-10-04

    Under algorithms there exists an option "Always store results in an existing property of the graphs hierarchy", which sounds as if one could get lift the colouring-results for the subgraph to the whole graph, but it doesn't work. What's the point of these "local colours"??

     
    • Melançon Guy

      Melançon Guy - 2018-10-04

      Dear Groucho :-)

      you might have heard about inheritance in object oriented approaches: this is exactly how properties are dealt with in Tulip. That is, once a property has been defined for a grpah, it becomes available to all its subgraphs. Unless a subgraph (re)defines it (we call that property overridding in OO programming jargon).

      Now, assume you compute a property for a subgraph while a property with the same name exists at the (super) graph level: the canonical mechanism is that this property then becomes local and overrides inheritance.

      You may not want that to happen, and a possibilty is that you want the property to be imported at the (super) graph level. This is what the "Always store results ..." does.

      Hope this helps

       
      • Oliver Kullmann

        Oliver Kullmann - 2018-10-04

        Hello, thanks for your efforts!
        You write "You may not want that to happen, and a possibility is that you want the property to be imported at the (super) graph level. This is what the "Always store results ..." does."
        That would be good, but it doesn't work: One runs the colouring-algorithm on the subgraph, indeed it re-computes the colours only on the vertices of the subgraphs -- but the colours of the whole graphs are not changed, unfortunately.
        If this would work, then problem solved! Wouldn't need to do any programming, but could start experimenting right away -- and that's important, since the graph-visualisation isn't for us a goal in itself, but just a possible tool, and we need to experiment likely quite a bit to find out whether it can be helpful at all.

        Perhaps there is a problem with how to "activate" the subgraph? In that panel, which lists the graphs, one can click on it, it becomes blue in my application, while the synchronisation apparently makes it bold?

         
  • Oliver Kullmann

    Oliver Kullmann - 2018-10-10

    Hello, beginning of semester here, everything takes it s time.

    Currently it seems actually most useful to us if we compute the colouring of nodes (and edges) ourselves, putting that already into the tree given to the Tulip-application. We can easily compute anything we want and put into into the data given to Tulip. That seems indeed easier for us, and we have full control over that. Leaving then the display and all of that to Tulip.

    Our own program is C++. Now it would be great if there would be a nice little header-only library inside Tulip which we could just include, and having then the basic definitions of colour-classes and such stuff. The root file seems

    http://tulip.labri.fr/Documentation/current/doxygen/html/_color_8h_source.html

    which includes only Vector.h. Hm, perhaps finally it's easy enough, and teaches us how that works, writing such helper classes ourselves. We don't need all of that, but can start small.

    Greetings

    Oliver

     

Log in to post a comment.