python-graph

A library for working with graphs in Python

--------------------------------------------------------------------------------

CHANGELOG

Release 1.6.3 [??? ??, 2009]

Release 1.6.2 [Sep 30, 2009]

Important API Changes:

Adding an arrow to an non existing node on a digraph now fails sanely (Issue 35);

Adding an already added node to a graph or digraph now raises an exception (AdditionError);

Adding an already added edge to a graph or digraph now raises an exception (AdditionError);

pygraph.classes.Classname.classname classes were renamed to pygraph.classes.classname.classname;

pygraph.algorithms.filters.Filtername.filtername filters were renamed to pygraph.algorithms.filters.filtername.filtername;

pygraph.algorithms.heuristics.Heuristicname.heuristicname heuristics were renamed to pygraph.algorithms.heuristics.heuristicname.heuristicname;

hypergraph's read() and write() methods were removed.

Release 1.6.1 [Jul 04, 2009]

Enhancements:

Added reverse method to the digraph class.

Important API Changes:

Removed methods calling algorithms from graph and digraph classes;

pygraph.algorithms.cycles.find_cycle does not take argument directed anymore;

Removed methods read, write and generate from graph and digraph classes;

Functions for writing and reading graphs now in pygraph.readwrite.

Release 1.6.0 [Jun 06, 2009]

Important API Changes:

Module name was renamed to pygraph;

python_graph_exception was renamed to GraphError;

Exception unreachable was renamed to NodeUnreachable;

get_edge_weight was renamed to edge_weight;

get_edge_label was renamed to edge_label;

get_edge_attributes was renamed to edge_attributes;

get_node_attributes was renamed to node_attributes;

degree was renamed to node_degree;

order was renamed to node_order.

Release 1.5.0 [May 03, 2009]

Enhancements:

Assymptotically faster Mutual Accessibility (now using Tarjan's algorithm);

DOT-Language importing;

Transitive edge detection;

Critical path algorithm.

Fixes:

Cycle detection algorithm was reporting wrong results on some digraphs;

Removed Minimal Spanning Tree from Digraphs as Prim's algorithm does not work on them (Issue 28).

Deletion of A--A edge raised an exception;

Deletion of an node with an A--A edge raised an exception.

Important API Changes:

Removed minimal_spanning_tree() method from the digraph class.

Release 1.4.2 [Feb 22, 2009]

Fixes:

find_cycle() trapped itself in infinite recursion in some digraphs (Issue 22).

Release 1.4.1 [Feb 09, 2009]

Fixes:

graph.algorithms.filters was not being installed (Issue 20).

Release 1.4.0 [Feb 07, 2009]

Enhancements:

Added Asearch algorithm (as heuristic_search);

Added Chow's and Euclidean heuristics for A*;

Added filtered depth-first and breadth-first search;

Added 'find' search filter (stops the search after reaching a target node);

Added 'radius' search filter (radial limit for searching);

Moved to setuptools.

Fixes:

Breadth first search was omitting the first node in level ordering when no root was specified.

Release 1.3.1 [Oct 27, 2008]

Fixes:

Graph and digraph inverse was not working;

Node removal in digraphs was not deleting all relevant edges (Issue 13).

Important API Changes:

Deprecated methods were removed.

Release 1.3.0 [Sep 28, 2008]

Enhancements:

Tree traversals (preorder and postorder).

Fixes:

Node insertion is much faster now (Issue 11).

Hypernode/hyperedge insertion also much faster.

Important API Changes:

get_nodes() is now nodes();

get_edges() is now edges();

get_neighbors() is now neighbors();

get_incidents() is now incidents();

get_order() is now order();

get_degree() is now degree().

(Former method names are deprecated and will be removed in the next release.)

Release 1.2.0 [Sep 09, 2008]

Enhancements:

Moved to new class style;

Graphs and digraphs are separated classes now;

Added level-based ordering to breadth first search;

Graph object is now iterable;

Graph object is now a container and graphobj[nodeid] iterates too;

Support for node and edge attributes (Issue 5);

Node deletion.

Fixes:

Install now works with a prefix (Issue 10);

Shortest path spanning trees did not had an explicit root.

Important API Changes:

breadth_first_search() now returns a tuple;

Arrow methods are gone. Use class digraph + edge methods for directed graphs now.

Release 1.1.1 [Sep 04, 2008]

Enhancements:

Improved install script.

Fixes:

DOT Language output now works for nodes/edges labelled with spaces.

Important API Changes:

get_neighbours() is now get_neighbors() (Issue 9).

Release 1.1.0 [Aug 31, 2008]

Enhancements:

Hypergraph support (Issue 4);

Complete and complement graph generation;

Weights in random generated graphs (Issue 8).

Fixes:

Fixed bug in cut-node identification;

Fixed bug causing wrong results for graphs with nodes labelled with values that evaluate to False (Issue 7).

Important API Changes:

get_edges() now return all edges in the graph;

get_neighbours() has the former behaviour of get_edges().

Release 1.0.0 [Aug 01, 2008]

Adds some operations;

Random graph generation;

Cut-vertex/cut-edge identification.

Release 0.85 [Jul 27, 2008]

Adds DOT-Language output (Issue 1);

Install script included (Issue 3).

Release 0.75 [Jul 06, 2008]

Added XML import/export;

Docs are bundled now.

Release 0.65 [Jun 25, 2008]

DFS, BFS and MST can be generated for given roots;

Added Dijkstra's shortest path algorithm (Issue 2).

Release 0.50 [May 13, 2008]

Some API changes;

Nodes can now be arbitrary names/objects.

Release 0.45 [May 12, 2008]

Adds Prim's minimal spanning tree.

Release 0.40 [Mar 09, 2008]

Adds topological sorting;

Support for weighted graphs.

Release 0.30 [Aug 30, 2007]

Adds algorithms for accessibility and mutual accessibility.

Release 0.20 [Jul 16, 2007]

Adds breadth-first search;

API documentation.

Release 0.10 [Jul 10, 2007]

First release;

Feat. basic operations and depth-first searching.