Use c++ to draw a figure of a graph(data structure)

{ Algorithm questions still belong to a language-independent forum,
but questions about using the Boost Graph Library can fit here. -mod }


Hi,all.

I need to draw a figure of a graph(data structure). C++ is used in my
code.
The moderators told me to go to a language-independent forum.
Considering *boost graphic library* may help,I think here is the best
place.


I can't get the whole graph all at once. Eachtime I get a pair of
points,they indicate an edge and two
vertexes of the graph.

It's easy to store the graph. But I don't know how to get a rational
layout of the graph,so that the figure looks symmetrical and
balanced.

Another difficult problem(to me) is how to reduce cross-lines.

Any suggestion will be highly appreciated. Thanks in advance!

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

"weii meng" <willgun.x@gmail.com> wrote in message
news:3317a2e2-7a34-42c0-a088-49f0194bd6e0@r24g2000prf.googlegroups.com...
>{ Algorithm questions still belong to a language-independent forum,
> but questions about using the Boost Graph Library can fit here. -mod }
>
>
> Hi,all.
>
> I need to draw a figure of a graph(data structure). C++ is used in my
> code.
> The moderators told me to go to a language-independent forum.
> Considering *boost graphic library* may help,I think here is the best
> place.

If you want to learn about how to use the Boost Graph Library, for your
problem, this group is definately more appropriate than a language
independant one, but less appropriate than a boost mailing list.

The BGL is rather complicated. If you want somebdoy to help you through an
example, of creating a graph using it, we would need to know if the graph is
director or not.

If vertices are identifed by a name or a number. If at the start you know
the number of vertices, or not. Etc.

Unfortunately for you, the implemented Graph layout algorithms may not be
what you want. They focus on placement of the vertices and symmetry, but pay
no attention to the number of times edges will cross. Minimizing that is
desireable, but is difficult, and few algorithms attempt it. Depending on
the structure of the graph, this might be acceptable, as for some structures
the implemented algorithms will tend to have few overlaps. For others though
things are not as nice.

As for finding other algorithms, the only one I have found that might be
suitable for your purpose is the algorithm used by Graphviz's dot. This
algorithm however is only good for directed graphs where it is desired that
edges tend to all face the same general direction. (I.e. edges or normally
from higher in the image to lower in the image, or from left to right).


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 13 Dec, 09:38, weii meng <willgu...@gmail.com> wrote:
> { Algorithm questions still belong to a language-independent forum,
> but questions about using the Boost Graph Library can fit here. -mod }
>
> Hi,all.
>
> I need to draw a figure of a graph(data structure). C++ is used in my
> code.
> The moderators told me to go to a language-independent forum.
> Considering *boost graphic library* may help,I think here is the best
> place.
>
> I can't get the whole graph all at once. Eachtime I get a pair of
> points,they indicate an edge and two
> vertexes of the graph.
>
> It's easy to store the graph. But I don't know how to get a rational
> layout of the graph,so that the figure looks symmetrical and
> balanced.

Well, this is the main problem. The boost graph library, like other
graph libraries, concentrates on the representation of the graph,
rather than how to draw it. Drawing involves graphics and there is no
std way to do graphics in C++ (yet). There are loads of libraries and
loads of approaches, but nothing std.

My approach would be to write an output file suitable as input to a
graph drawing program. Dot (aka graphviz) is quite popular. However,
dot does have a habit of drawing non-trivial graphs with many crossing
lines. A more sophisticated graph drawing program is uDraw (http://
http://www.informatik.uni-bremen.de/.../en/index.html), formerly known
as Da Vinci. This does a much better job but has a more complicated
file format.

Regards,

Andrew Marlow


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]