![]() ![]() | ![]() |
File: [local] / OpenXM_contrib / PHC / Ada / Schubert / pieri_root_counts.ads (download)
Revision 1.1.1.1 (vendor branch), Sun Oct 29 17:45:32 2000 UTC (23 years, 9 months ago) by maekawa
Import the second public release of PHCpack. OKed by Jan Verschelde. |
with text_io; use text_io; with Generic_Lists; with Pieri_Trees; use Pieri_Trees; package Pieri_Root_Counts is -- DESCRIPTION : -- This package executes the combinatorial root counting method based on -- the construction of Pieri trees and provides data structures to perform -- the Pieri deformations. These deformations start at the leaves that -- satisfy Pieri's condition for which a triple intersection of planes -- leads to a unique solution. They continue following the chains that -- end at those leaves. These chains are indexed by the pairs of leaves. -- So a list of paired nodes suffices to run the Pieri homotopy algorithm. -- For efficiency one wants to avoid the repeated generation of the same -- equations at every node. Therefore a tree of paired nodes is needed. -- In the creation of this tree, a chain is traversed in increasing order. -- DATA STRUCTURES : type Paired_Nodes is record left,right : Link_to_Pieri_Node; end record; package Lists_of_Paired_Nodes is new Generic_Lists(Paired_Nodes); type List_of_Paired_Nodes is new Lists_of_Paired_Nodes.List; type Paired_Chain is array ( integer range <> ) of Paired_Nodes; type Nodal_Pair; type Link_to_Nodal_Pair is access Nodal_Pair; type Nodal_Matrix is array (integer range <>,integer range <>) of Link_to_Nodal_Pair; type Nodal_Pair ( d : natural ) is record pnd : Paired_Nodes; sols : natural; -- #paths arriving at the node children : Nodal_Matrix(0..d,0..d); -- indices in children are jumps ancestor : Link_to_Nodal_Pair; end record; -- CREATORS : function Create ( n,d : natural; t1,t2 : Pieri_Tree ) return List_of_Paired_Nodes; -- DESCRIPTION : -- Creates a list of paired nodes that satisfy Pieri's condition. function Create ( pnd : Paired_Nodes ) return Paired_Chain; -- DESCRIPTION : -- Returns the chain of nodes that start at the first branch point down -- and end at the given pair of leaves pnd. -- This is an intermediate data structure in the Create operation below. function Create ( d : natural; lp : List_of_Paired_Nodes ) return Nodal_Pair; -- DESCRIPTION : -- Creates a tree of nodal pairs and returns its root. -- The tree structure allows repeated nodes. -- A node that occured already once has sols equal to zero. -- SELECTORS : function Height ( pnd : Paired_Nodes ) return natural; -- DESCRIPTION : -- Returns Max(pnd.left.h,pnd.right.h). function Equal ( pnd1,pnd2 : Paired_Nodes ) return boolean; -- DESCRIPTION : -- Returns true when both nodes are the same. function At_First_Branch_Point ( pnd : Paired_Nodes ) return boolean; -- DESCRIPTION : -- Returns true when the current pair of nodes is at the first -- branch point in the Pieri trees. function At_Leaves ( pnd : Paired_Nodes ) return boolean; -- DESCRIPTION : -- Returns true when the current pair of nodes consists of leaves. function Ancestor ( pnd : Paired_Nodes ) return Paired_Nodes; -- DESCRIPTION : -- Returns the pair of ancestor nodes to the given pair of nodes. function First_Branch_Point ( pnd : Paired_Nodes ) return Paired_Nodes; -- DESCRIPTION : -- Returns the pair of nodes down in the chains of pnd where the -- first branch point occurs. function Height ( np : Nodal_Pair ) return natural; -- DESCRIPTION : -- Returns the number of nodes above the current nodal pair. function Is_In ( root : Nodal_Pair; pnd : Paired_Nodes ) return boolean; -- DESCRIPTION : -- Returns true if the paired nodes occur somewhere in the tree of -- nodal pairs starting at the root. function Number_of_Paths ( root : Nodal_Pair ) return natural; -- DESCRIPTION : -- Returns the number of paths that need to be followed. -- FORMATTED OUTPUT : procedure Write ( file : in file_type; chn : in Paired_Chain ); -- DESCRIPTION : -- Writes the chain of paired nodes in a formatted way. procedure Write ( file : in file_type; root : in Nodal_Pair ); -- DESCRIPTION : -- Writes the tree of paired nodes on file in a formatted way. end Pieri_Root_Counts;