Changelog

python-graph
A library for working with graphs in Python
--------------------------------------------------------------------------------

CHANGELOG


Release 1.8.2 [July 14, 2012]

Fixes:
	The find_cycle function now accepts instances of any subtype of graph and digraph.


Release 1.8.1	[Jan 08, 2012]

Enhancements:
	Shortest-path now executes in O(n*log(n)) instead of O(n^2).

Fixes:
	Shortest-path raises KeyError when the source node is not on the graph;
	Bellman-Ford algorithm now works for unconnected graphs (Issue 87);
	Linking, unlinking and relinking a hypernode to hyperedge now works as expected (Issue 86);
	Graph comparison does not raise exceptions anymore (Issue 88);
	Fixed undesired sharing of attribute lists (Issue 92);
	Fixed reading of XML-stored graphs with edge attributes;
	Fixed calculation of minimal spanning trees of graphs with negative-weighted edges (Issue 102).


Release 1.8.0	[Oct 01, 2010]

Enhancements:
	Added Pagerank algorithm;
	Added Gomory-Hu cut-tree algorithm.

Fixes:
	Edges from one node to itself are no longer duplicated (Issue 75).


Release 1.7.0	[Mar 20, 2010]

Enhancements:
	Added equality test for graphs, digraphs and hypergraphs;
	Added has_edge() and has_hyperedge() methods to hypergraph objects;
	Accepting subtypes of graph, digraph and hypergraph in dot-language output (Issue 64);
	Added Bellman-Ford algorithm;
	Added Edmonds-Karp Maximum-Flow algorithm.

Fixes:
	Adding an edge with a label to a digraph now works again;
	Deleting an edge of a hypergraph now deletes its attributes;
	Node attributes on hypergraphs work now;
	Checking for node equality correctly in find_cycle;
	Avoiding errors caused by deep recursion on many algorithms (Issue 66).


Release 1.6.3	[Dec 13, 2009]

Enhancements:
	Added Python3 support (support for Python 2.5 and lower was dropped).

Fixes:
	Adding a graph to a digraph now works (Issue 39);
	Fixed the reading of graphs and digraphs stored in XML.

Important API Changes:
	Edges are now passed around as generic objects. In the case of graph / digraph this is a tuple;
	Removed traversal() method from graph and digraph classes;
	Removed accessibility, connected_components, cut_nodes and cut_hyperedges from hypergraph class;
	Functions for reading a hypergraph doesn't take an empty hypergraph as argument anymore.


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.