Graph-Easy
view release on metacpan or search on metacpan
trailing part, ever. Fixes also the regression from todos/hash.txt
no longer working. Adjust doc to reflect this change.
+ add more tests for trailing/leading empty parts.
* Layout.pm:
+ typo: {_chain} vs. {chain} (Thanx Jim Cromie)
+ don't use alarm when under the debugger (Thanx Jim Cromie)
2006-02-05 v0.41 Tels 1670 tests
* use Module::Install and bundle it in inc/
* add "point-style: invisible" for very small, invisible nodes - nodes with
"shape: invisible;" will still have a minimum size.
* add support for '\l', '\r' and '\c' as line breaks to align individual
label lines left, right or center
* as_ascii:
+ support proper alignment on edge labels
* as_graphviz():
+ fix invisible nodes to not show their label
+ add support for nodes with "shape: point;"
* t/graphviz.t: reduce the number of unnec. calls to as_graphviz()
* as_html():
+ use white-space: nowrap; (not "pre")
+ add support for \l, \r, \c and don't include text-align twice
* Node:
+ remove the unused and undocumented "noquote" param from as_html()
* Graph:
+ add: add_edge_once(): add an edge from A to B only once
(Thanx to Florian Lindner for the suggestion!)
2006-01-29 v0.40 Tels 1652 tests
* add attribute:
+ "invisible" as edge style
+ "minlen" - for edges (minimum distance in cells)
+ "align" - alignment for graph, group, edge and node labels
* General:
+ fix Makefile.PL to work with newer YAML
+ avoid duplicate code when dealing with labels and dimensions
+ empty attribute-parts on autosplit nodes work now:
[ A|B ] { class: |legend; }
will put B into class 'legend' and leave the class of A alone
[ A|B ] { class: legend|; }
will put A into class 'legend' and leave the class of B alone
[ A|B ] { class: legend; }
will put A *and* B into class 'legend'
+ _class_styles(): use correct indent instead of hard-coded ' '
* Edge:
* start_port()/end_port(): + remove spaces to normalize result
+ return list in list context
* Node:
+ add nodes_sharing_end(), is_anon()
+ remove place() from public API (is now _do_place())
+ allow spaces in set_attribute('size', '9 , 8')
* Node::Cell:
+ add a group() method to make things like $cell->group() easier
* Group:
+ is also a Graph::Easy, to inherit from it (for nesting)
+ find right-most cell for label if "align: right"
+ rename find_label_cell() to _find_label_cell() (is internal use only)
* Graph:
+ add use_class(), and use it instead of hard-coded class names
+ due to bad caching, one couldn't set the node size as class-attribute
+ weaken() is costly and O(N), so avoid it whenever possible.
Graph creation and destroy are now O(1) again. Creating a graph with
N nodes and N-1 edges takes (bench/stress.pl):
N 0.39 0.39 | 0.40 0.40
Create Destroy | Create Destroy
----------------------------|------------------------
4000 0.35 0.23 | 0.31 0.12
8000 0.77 0.68 | 0.61 0.21
16000 1.91 2.26 | 1.19 0.48
32000 9.32 8.02 | 2.32 0.78
* Parser:
+ add use_class() to use user-provided classes for generated objects
+ referencing an (empty) part of an autosplit node before the autosplit
node itself would create wrongly a stray node
+ simplify group code ($graph->add_group() does everything nec. already)
+ store labels for autosplit nodes not in the label attribute, but
separately. This fixes the problem that you couldn't put a node
(resulting from an autosplit) into a class and set a label on the
class - the node would always show the part name as label. In addition
that fixes the long-standing bug that as_txt() would output stray labels
for autosplit nodes.
+ parts in an autosplit node are relative to their preceding part, not
to the first part. This enables setting columns/rows/size on parts
and the other parts will flow/adjust properly.
+ set the basename property on the first part in an autosplit node,
enabling proper as_txt() output of it.
* Layouter:
+ implement the same spacing rules between nodes for end points as
0.39 did for start points: edges joining up to a node work now
+ only use 3 cells space when there are more than one node sharing
the same port (was "more than zero")
+ fix a problem when placing nodes without an edge object resulting in
a crash
+ repair edges outside of groups, as well as edges that end at a corner
+ multi-celled nodes in spliced layouts (e.g. with group fillers)
did not preserve their filler-cells correctly
* as_txt():
+ clean up nodes after output so that a following as_graphviz() does work
* as_graphviz():
+ fix links involving groups: lhead/ltail were swapped
+ generate shorter invisible node names ("A,south,0" vs "A,south,0,0")
+ do not create invisible joint-nodes when there is only one edge sharing
the start/end port
+ make "shape: rounded" work (needs "style=rounded,...")
+ support label alignments on groups
* as_ascii():
+ round corners for shape: rounded (using ' ', instead
of using unicode characters by accident)
+ support for aligned labels (left|right|center)
* as_boxart(): round corners for bold/wide/broad etc using spaces
* as_html():
+ make space below edges smaller, to create more compact layout
+ a color on a group was ignored, resulting always in black group labels
+ finally align the vertical arrows with the edge lines. In Opera 8.5
under Linux the "v" now gets cut off, but this seems a browser bug.
Sorry, some of the Opera users!
+ support label alignments (center|left|right)
+ when a class attribute specified the font-size, don't include it at
at the td (node|edge|caption etc) again
+ edge { arrow-style: none; } did not remove the arrows from edges
+ group cells need ' ' for IE to show the border - I hate IE bugs :-(
* as_html(): remap "fill" to "background" for classes (especially "graph")
* as_html(): caption gets graph's background as background
2005-09-04 v0.27 Tels 1058 tests - Offset, offset, offset, offset the position...
* remove Graph::Easy::Cluster, and overhaul relative-node position code
+ use "[ B ] { origin: A; offset: 2,0 }" to position A relative to B
(no cluster needed anymore)
+ can position C relative to B, which is relative to A, and so on
+ works correctly with multi-celled nodes
+ update doc for this feature
* remove "point-style: none" - "shape: invisible;" already does the same
* remove "point-style: ring" - is: "point-style: circle; fill: white;"
* add "point-style: diamond"
* add attribute arrow-style (open, closed, filled) for edges
* add attribute "fill" (color inside shape) and change notion of "background"
to the color outside the shape (important change for nodes)
* add attribute "label-color" for edges
* attribute "border-style" was accidentily allowed only as "border-shape"
* remove node styles: box, rectangle (were aliases for "rect"), plaintext
(was alias for "none")
* Save memory: Nodes use 638 (vs 770) bytes, Edges 631 (vs 683) Bytes, this
makes a big graph use about 10% less memory (and it is
generated in about 6% less time) (measured on 32 bit system)
* fix small nits in Graph::Easy::Attributes
* define possible values as lists in Graph::Easy::Attributes, removes double
definitions in both code and documentation that could get out of sync
* examples/common.pl was broken - thanx to Vagn Johansen for the report!
* disallow arguments to new(), leave only in:
* Node: "label" and "name"
* Edge: "label", "name" and "style"
* Parser: "debug"
* Node::Cell: "node"
* remove useless subroutine contains() in Node.pm
* build/gen_manual: generate doc for group attributes, too
* build/gen_manual: generate color table from definitions in code
* build/gen_manual: split attributes into 4 sub pages and add an index
* build/gen_manual: include sample graphs
* as_graphviz(): quote reserved words: /(strict|(sub)?graph|node|edge)/i
* as_graphviz(): quote attribute values with non \w chars
* as_graphviz(): support for all flow directions (left, right, top, bottom)
* as_graphviz(): fix colors because dot et. al have a different idea on what
color "grey" actually is. This is solved by making checks
on attributes on Nodes etc. strict (it converts "red" to
"#ff0000" on input) and then outputting the raw RGB colors
* as_graphviz(): support for bidirectional and arrow-less edges
* as_graphviz(): add support for different arrow styles (except filled with
different fill color)
* as_graphviz(): support anon nodes properly (rendered invisible)
* as_graphviz(): correctly handle link, linkbase and autolink attributes
* as_graphviz(): use graph ID to construct graph name (useful for imagemaps)
* as_html(): reimplement output for edges with 4x4 table cells, including
correct start/end points, label colors. Finally works in all
major browsers and looks better than ever :)
* as_html(): generate graph-table caption from label attribute
* as_html(): correctly handle multi-celled nodes
* as_html(): generated links have class 'l'
* as_ascii(): handle multi-lined labels on edges correctly
* as_ascii(): invisible nodes are 3x3, not 5x3 in minimum size
* don't unnec. load "Heap" and "Heap::Fibonacci"
* Graph: add as_txt_file() as alias for as_txt()
* add weaken() in Edge::Cell to trigger early DESTROY of graphs
* move the ASCII code to Graph::Easy::As_ascii and load it on demand
* Parser: report wrong attribute names/values better
* Parser: allow '$graph = Graph::Easy::Parser->from_text("...")'
* Parser: fix parsing of undirected edges with following nodes/attributes
* Parser: parse "[ A ]\n { ... }" and "[ A ] { ...\n...}" properly
* Parser/Layout: support undirected (arrowless) edges properly
* Layout: set proper flags for bidirectional edges (so they are rendered
correctly (Thanx to Scott Beuker)
* Layout: stop an endless loop in the chain-backtracking code
* Layout: set correctly edge label cells on found A* paths
* setting the attribute 'origin' and 'offset' on a node works now correctly
* attribute are now strictly checked on Nodes, Edges etc, too
* fix unitialized warning in Graph::Easy::Layout::Scout
* fix broken link to EXAMPLES in POD (Thanx Scott Beuker)
* border_attribute(): return no width if style eq 'double'
* remap_attributes(): fix handling of 'all' entries for attributes
* remap_attributes(): add handling of 'undef' to force attributes
2005-08-21 v0.26 Tels 1007 tests - Speed, speed, speed, speed up the code...
Fixed:
* as_ascii(): render node labels centered, instead on top-left corner
* as_ascii(): on clustered nodes, collapse borders
* as_ascii(): output edge labels on VER edge pieces, too
* as_ascii(): render end/start points on CROSS edge pieces
* as_ascii(): multi-celled nodes only worked when layout was not completed
* as_ascii(): crossing between different line styles are rendered better
than simple '#':
| | | | : H
===+=== ###+### ...!... ~~~+~~~ ---+--- ---H---
| | | | : H
* create shorter self-loops (block only 1 cell/1 port vs. 5 cells/2 ports)
* add_edge('A','A') works now, and creates only one node object
* make node attributes "size", "columns" and "rows" really work
* Node: make edges_to() work correctly with self-loops
* A*: only cross HOR/VER edges when they have no start/end points nor labels
* A*: use Heap::Binary (slightly faster) and inline $elem->fields() call
* Layouter: try to place nodes in chains first near their chain parent
* Layouter: better fallback strategy upon blocked paths
* edges with one bend now correctly have their label on HOR piece
* make attribute checks via Graph and Parser "strict", e.g. it will fail on
unknown attributes or invalid values
* fix parsing nodes after attributes like: "graph { color: red; } [ Bonn ]"
* we do not need to create filler cells unless there are groups, this makes
generating layouts w/o groups between 10 and 30% faster.
Added:
* color attributes are now stored as '#ff0000' and output as 'red' or
'#ff0000', depending on output format.
* Graph: option "strict", on by default, this makes set_attribute() check
all attributes and their values strict
* add option "flow" to graphs and nodes: general flow of edges
* near_places(): takes list of edge types
* A*: allow last edge piece to cross a horizontal/vertical edge
* build/gen-manual: generate manual page with attribute descriptions from
table in Graph::Easy::Attributes automatically
2005-08-12 v0.25 Tels 885 tests - Speed, speed, speed, speed up the code...
Added:
* $graph->add_edge('A','B') works now and is documented
* $graph->add_edge('A','B') in list context returns nodes and edge
* $graph->add_cluster('A') works and returns created cluster object
* Graph::Easy: timeout(): get/set timeout in seconds for layouter
* Layout: calculate chains-of-nodes, and lay out path along these chains
longest one first. This greatly detangles many layouts.
Fixed:
* as_ascii(): Drawing line crossings now works. Really! Believe me!
* as_ascii(): labels on horizontal edge pieces are now included
* rename "todo/" to "todos/" because case-insensitive OS have problems
with "TODO" and "todo/"...
* layout: move the alarm(0) to where it belongs and propagate
fatal errors to the outside
* Layout: calculating positions needs an int() to have nodes not fall
between the cell-grid
* Node: move the assignment to {id} into new(), so that subclasses
like Graph::Easy::Edge etc get a unique ID, too
* use Scalar::Util's weaken so that the Node's references back to their graph
do not prevent the graph from being freed
* Upon DESTROY, reset the appropriate fields in node/edge objects, so they
can be reused safely in other graphs
* A*: fixed an endless-loop in the path-backtracking code
* adding node clusters as well as managing them is now easier
* No longer uses Graph. We store nodes/edges in a hash in Graph::Easy object
as opposed to the Graph object. In addition we store per-node the edges
this node is involved in. This all results in less code, great speed and
memory improvements (see bench/no_graph.txt): v0.25 uses only about 50% of
the memory as 0.24!
Even the testsuite is much much faster, despite the new tests:
0.24: Files=23, Tests=820, 5 secs ( 4.37 cusr + 0.50 csys = 4.87 CPU)
0.25: Files=23, Tests=859, 4 secs ( 2.37 cusr + 0.31 csys = 2.68 CPU)
Loading Graph::Easy now takes less time & memory, too (output from top):
VIRT RES SHR
0.24: 8252 5712 1444
0.25: 5840 3376 1432
2005-08-07 v0.24 Tels 820 tests - Fix, fix, fix, fix the bugs...
Added:
* node attribute: "point-style" - set style for nodes with "shape: point"
* remappig of attributes can take code-ref for special handling
* A*: create crossings, and proper edge end/start pieces, fix bias
Fixed:
* Graph::Easy POD: add note to add_edge() about multi-edges
* correct POD in Graph::Easy::Node::Cell
* Graph::Easy::Edge->new( label => 'foo' ); did not work
* remap_attributes(): suppress empty attributes (fixes as_graphviz)
* as_graphviz: suppress "border-style" on edges and nodes
* as_graphviz: properly remap edge attribute "style"
* as_graphviz: do not include class as attribute in output
* as_graphviz: fix broken comment (graphviz uses //, not #)
* as_graphviz: default node settings are included in class "node"
* as_graphviz: escape '"' (double quoting char) to avoid issues with node
names like '2"'. Also avoid quoting plain node names when
possible.
* as_graphviz: output nodes with their name, not their label
* as_graphviz: multi-edged graphs work now correctly
* as_ascii: implement rendering of nodes with "shape: point"
* as_ascii: render edges with style 'bold'
* as_ascii: properly render edge pieces without gaps
* as_ascii: render edges seemless (".-.-.-.-" vs. ".-.--.-.-.-")
* as_ascii: render all combinations of edge pieces and start/end points
* as_svg_file: did not pass $self to _as_svg(), inducing a fatal failure
* Parser: drop support for parsing reversed edges ("<--"), this never
worked reliable and made parsing of normal edges with labels
much harder and error-prone due to ambigitous cases.
* Parser: fix parsing of bidirectional edges
* Parser: fix parsing of edges with labels containing "-", "[" etc
(edges labels can now contain any character unescaped except ">",
which must be escaped with "\" as "\>")
* Layouter: weed out positions for a node that are too close to a successor
2005-07-31 v0.23 Tels 765 tests - Fix, fix, fix, fix the bugs...
Fixed:
* update POD to reflect that the overall placement strategy is now better
* warn on broken Graph 0.66
* t/parser.t: sort edges on label to avoid hash key ordering tripping us up
* sorted_nodes(): use "name" as second field if a non-unique first field
sorting was requested (like sorted_nodes("layer"))
( run in 3.214 seconds using v1.01-cache-2.11-cpan-99c4e6809bf )