Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Lattice , Planar graphs and GraphViz

by spx2 (Deacon)
on Oct 15, 2009 at 09:55 UTC ( #801323=perlquestion: print w/replies, xml ) Need Help??

spx2 has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

I need a module(preferably from CPAN) that will render a graph planar(if possible) or if not reduce to a minimum the edge crossings that occur.

The purpose of this is to make a graph more readable which otherwise(because it has lots of edges) would not be so.

Also, is there any way I could use GraphViz so that I get a lattice(nodes lie on multiple horizontal layers which in turn are stacked on top of one another and on top and bottom layers there is just one node) ?

GraphViz seems to not have support for planar graphs(however,I can drop GraphViz and go for something else if it supports planarity).

Best regards,
Stefan

Replies are listed 'Best First'.
Re: Lattice , Planar graphs and GraphViz
by grizzley (Chaplain) on Oct 15, 2009 at 13:06 UTC
    Doesn't GraphViz do it by default? It always tries to reduce crossings. You can probably help by grouping edges into subgraphs if you can "manually" decide which nodes should be together in the neighbourhood.

      after I group nodes into subgraphs can I still plot the subgraphs as one big graph ?

      I guess you mean to cluster the nodes, no ?

        Yes, cluster nodes. And yes, subgraphs will be part of one graph. And it will probably do what you want (connecting nodes). I wanted the opposite - connect borders of subgraphs and it was very tricky. If you work on Windows then you will have many graphviz examples in directory C:\Program Files\Graphviz2.22\share\graphviz\graphs, e.g. C:\Program Files\Graphviz2.22\share\graphviz\graphs\directed\clust2.gv which show well how graphviz (well, actually dot, not graphviz: dot.exe -Tpng clust2.gv > clust2.gv.png) renders it.
Re: Lattice , Planar graphs and GraphViz
by blokhead (Monsignor) on Oct 15, 2009 at 15:27 UTC
    Yes, in Graphviz you can connect up many subgraphs.

    Keep in mind that computing the minimum crossing number of a graph is NP-hard (although checking for planarity can be done efficiently). So it is a pretty tough thing to ask of a graph layout engine. Graphviz (and probably any other layout engine) uses only heuristics in its layout.

    You may want to check out the Boost graph library. It does appear to have Perl bindings, though I can't speak from any personal experience. It is not clear whether the Perl bindings can do everything the C++ bindings can do. But it is clear that Boost is more of a graph theory library than Graphviz, and it seems able to do some really nice things, including drawing a planar embedding (see this example). If you give it a try, I'd be interested in hearing how it works.

    blokhead

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://801323]
Approved by GrandFather
Front-paged by tye
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (6)
As of 2020-07-14 10:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?