Graphviz Issue Tracker
Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0001168graphvizDotpublic2006-08-16 11:132011-04-28 04:03
ReporterWillem Kokke 
Assigned Togviz 
PlatformOS*-*-*OS Version
Summary0001168: memory leak if directional graph contains cycles

If a graph has cycles, graphviz tries to break the cycles by reversing the edge. The code to do this seems to cause a memory leak.

This can be easily demostrated by replacing the create_test_graph function in dot.c with
static graph_t *create_test_graph(void)
    Agnode_t *node[3];
    Agraph_t *g;

    g = agopen("new_graph", AGDIGRAPH);

    node[0] = agnode(g, "0");
    node[1] = agnode(g, "1");
    node[2] = agnode(g, "2");

    agedge(g, node[0], node[1]);
    agedge(g, node[1], node[2]);
    agedge(g, node[2], node[0]);

    return g;

and then running it with the -m flag to observe the memory increase.
With the original create_test_graph, the memory foot print did not increase

I've compiled graphviz and dot with visual studio 2003 and 2005, both exhibit the same behaviour.
I've first detected it with my own modified version of graphviz, but later verified it with the stock development snapshot
Steps To Reproduce

digraph example{
    a -> b -> c -> a
Additional Information

With the help of various tools, I've found out where this leak occurs exactly

it seems for each cycle in the graph it leaks 168 bytes per layout step
The exact location of the memory leak and call stack at that time is as follows:

---------- Block 336 at 0x007DAFA0: 168 bytes ----------
  Call Stack:
    d:\work\graphviz-bug\graphviz-win-devel\lib\common\memory.c (52): gmalloc
    d:\work\graphviz-bug\graphviz-win-devel\lib\common\memory.c (30): zmalloc
    d:\work\graphviz-bug\graphviz-win-devel\lib\dotgen\fastgr.c (169): new_virtual_edge
    d:\work\graphviz-bug\graphviz-win-devel\lib\dotgen\fastgr.c (199): virtual_edge
    d:\work\graphviz-bug\graphviz-win-devel\lib\dotgen\acyclic.c (32): reverse_edge
    d:\work\graphviz-bug\graphviz-win-devel\lib\dotgen\acyclic.c (49): dfs
    d:\work\graphviz-bug\graphviz-win-devel\lib\dotgen\acyclic.c (53): dfs
    d:\work\graphviz-bug\graphviz-win-devel\lib\dotgen\acyclic.c (53): dfs
    d:\work\graphviz-bug\graphviz-win-devel\lib\dotgen\acyclic.c (70): acyclic
    d:\work\graphviz-bug\graphviz-win-devel\lib\dotgen\rank.c (473): dot_rank
    d:\work\graphviz-bug\graphviz-win-devel\lib\dotgen\dotinit.c (226): dot_layout
    d:\work\graphviz-bug\graphviz-win-devel\lib\gvc\gvlayout.c (68): gvLayoutJobs
    d:\work\graphviz-bug\graphviz-win-devel\cmd\dot\dot.c (155): main
TagsNo tags attached.
VERSION     2.9
Attached Files

- Relationships

-  Notes
There are no notes attached to this issue.

- Issue History
Date Modified Username Field Change
2011-04-28 04:03 user1 New Issue
2011-04-28 04:03 user1 Assigned To => user1

MantisBT 1.2.5[^]
Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker