| This PHP extension calculates short paths (i.e.sequences of edges) in directed graph.
It is based on unique author's algorithm. Limitations: a) no empty cycles;
b) bidirected edges may be passed twice in some paths. Limitations may be easily cancelled in customized developments.
The extension is still experimental. It is currently available only as a
Win32 dll. For installation issues, please refer to PHP manual at http://www.php.net/. For bug reports, please
contact :valstas@onlinehome.de . FUNCTIONS REFERENCE : array schain_short_paths(array graph, long vstart, long vfin, long len_limit); graph - array with the following format :
array(array($v2,$w2, $v5,$w5, ...), array(), ..., array($v0,$w0), array($v14,$w14)),
where $v0,$v1, ..., $vn - continued numbers of vertices in graph, $w0,$w1,... - weights of edges, i.e. edges are defined with pairs of vertices(pair - initial and end vertices). For example, graph with edges {0->1(weight 3), 0->2(2), 2->1(4)} looks like array(array(1,3,2,2), array(), array(1,4));
vstart - number of vertex to start search;
vfin - number of vertex to finish search;
len_limit - limitation of path length, if 0 - no limitation.
Returns set of paths with format :
array(array($length, $vi1, $vi2, ...$vin ),...), where $length - path length,
$vij - numbers of vertices to be passed (from $vi1=vstart to $vin=$vfin).
Calculates short paths (all minimal chains) in given graph.
Example: $graph = array(array(1,1,2,20),array(3,1,4,15,6,15),array(8,1,10,1),array(5,1,0,1),
array(6,1,0,1),array(7,15,2,1,0,1),array(9,1,0,1),array(9,1,2,1,0,1),array(7,1,3,1), array(8,1),array(12,1,11,1,1,1),array(13,1,5,1),array(14,1),array(12,1),array()); $pts = schain_short_paths($grr, 0,9,0);
foreach($pts as $k=>$v){
echo "<br> CHAIN N $k ";
$len = 'LENGTH'; $vert = 'VERTICES';
foreach($v as $vv){
echo " $len $vv $vert ";
$len = $vert = '';
}
echo "<br>";
}
Result:
CHAIN N 0 LENGTH 7 VERTICES 0 1 3 5 2 8 7 9 CHAIN N 1 LENGTH 17 VERTICES 0 1 6 9 CHAIN N 2 LENGTH 18 VERTICES 0 1 4 6 9 CHAIN N 3 LENGTH 19 VERTICES 0 1 3 5 7 9 CHAIN N 4 LENGTH 23 VERTICES 0 2 8 7 9 CHAIN N 5 LENGTH 23 VERTICES 0 1 3 5 2 10 11 5 7 9 CHAIN N 6 LENGTH 39 VERTICES 0 2 10 11 5 7 9 array schain_shortest(array graph, long vstart, long vfin); graph - array with the following format :
array(array($v2,$w2, $v5,$w5, ...), array(), ..., array($v0,$w0), array($v14,$w14)),
where $v0,$v1, ..., $vn - continued numbers of vertices in graph, $w0,$w1,... - weights of edges, i.e. edges are defined with pairs of vertices(pair - initial and end vertices). For example, graph with edges {0->1(weight 3), 0->2(2), 2->1(4)} looks like array(array(1,3,2,2), array(), array(1,4));
vstart - number of vertex to start search;
vfin - number of vertex to finish search.
Returns shortest path(or paths) with format :
array(array($length, $vi1, $vi2, ...$vin ),...), where $length - path length,
$vij - numbers of vertices to be passed (from $vi1=vstart to $vin=$vfin).
Calculates shortest path (chain) in given graph.
Example: $graph = array(array(1,1,2,20),array(3,1,4,15,6,15),array(8,1,10,1),array(5,1,0,1),
array(6,1,0,1),array(7,15,2,1,0,1),array(9,1,0,1),array(9,1,2,1,0,1),array(7,1,3,1), array(8,1),array(12,1,11,1,1,1),array(13,1,5,1),array(14,1),array(12,1),array()); $pts = schain_shortest($grr, 0,9);
foreach($pts as $k=>$v){
echo "<br> CHAIN N $k ";
$len = 'LENGTH'; $vert = 'VERTICES';
foreach($v as $vv){
echo " $len $vv $vert ";
$len = $vert = '';
}
echo "<br>";
}
Result:
CHAIN N 0 LENGTH 7 VERTICES 0 1 3 5 2 8 7 9 A few words about TREE PHP extension. The extension supports tree structures manipulations with php arrays like $tree = array($key0=>$root,$key1=>$node1,...,$keyN=>$nodeN).
Each key is a path from a node to a root, like '1', '1.2', '1.4.3.12.8'
...
Each node (root) is a structure-like array (<CODE>$kids</CODE>,
$content</CODE>), where $kids</CODE> is the number of child nodes in
this parent node, and $content is a container of any type including
long, double, string, array etc.
The extension is still experimental. It is currently available only as a
Win32 dll. For installation issues, please refer to PHP manual at
http://www.php.net . For bug reports, please contact the valstas@onlinehome.de .
Example:
$tree = array(
'1'=>array(2,'ROOT'),
'1.1'=>array(0),
'1.2'=>array(3,array(1,'CONT1',array(5,7),'Cont2')),
'1.2.1'=>array(0),
'1.2.2'=>array(0,'INFO'),
'1.2.3'=>array(0, array(5.3, 3.14))
);
Key values are supported to be continued, i.e. if node 2.1 has 5 kids, those
keys are from 2.1.1 to 2.1.5 .
All the arguments of functions are mandatory. The first argument must be a
variable, it always contains a tree before and after operations over nodes.
FUNCTIONS REFERENCE:</H3><B>string ctree_append_node(array& Tree, string
parent_Node, any_type new_Node_content)</B> <PRE> parent_Node - the node, which will contain a new child node
new_Node_content - the content of a new node (may be an empty string)
Inserts a new node under a parent node to the last position. Returns a
key (path to root) of a new node.
Example: $new_node = ctree_append_node($tree, '1', array('new content', 25));
string ctree_insert_node(array& Tree, string parent_Node, long
position, any_type new_Node_content) parent_Node - the node, which will contain new child node
position - assigned new node position
new_Node_content - content of a new node, may be an empty string
Inserts a new node into a parent node to a definite position. Returns
the key (path to root) of a new node.
Example: $new_node = ctree_insert_node($tree, '1.3', 2, 'insert content');
int ctree_delete_node(array& Tree, string delete_Node)</B> <PRE> delete_Node - a node to delete
Deletes a node with all of its descendants. Returns 0 if the delete is
successful, 1 if a node wasn't found, and 2 if you are trying do delete a root
node.
Example: $retcode = ctree_delete_node($tree, '1.3.4');
string ctree_change_pos(array& Tree, string what_node, string
after_node) what_node - node to be replaced
after_node - node, after which what_node is arranged
Changes a node's position in a parent node. The node becomes the next
node after <CODE>after_node node or a top one if after_node
is an empty string. Returns the key (path to root) of a changed
what_node position.
Example: $new_path = ctree_change_pos($tree, '1.3.2', '1.3.4');
int ctree_subordinate(array& Tree, string what_node, string
new_parent_node) what_node - node to be subordinated
new_parent_node - node, to which what_node is subordinated
Moves a node to another parent node with all descendants. Returns 0 if
successful, 1- if one or both of the nodes do not exist, 2- in case what_node is
the ancestor of a new_parent_node.
Example: $retcode = ctree_subordinate($tree, '1.3', '1.4');
string ctree_copy_node(array& Tree, string what_node, string
parent_node) what_node - node to be copied
new_parent_node - node, to which what_node is copied
Copies a node to the last position of a parent node without descendants.
Returns the key (path to root) of the what_node copy.
Example: $new_path = ctree_copy_node($tree, '1.3.1', '1.5');
int ctree_copy_subtree(array& Tree, string what_node, string
parent_node) what_node - subtree(what_node is root) to be copied
new_parent_node - node, to which what_node subtree is copied
Copies a node to the last position of a parent node with all of its
descendants. Returns 0 if successful, 1 if any of the nodes doesn't exist, 2 in
case the what_node is the ancestor of a
parent_node
Example: $new_path = ctree_copy_subtree($tree, '1.3', '1.5.5');
int ctree_get_subtree(array& Tree, string what_node, string
root_node) what_node - the root of subtree to get
root_node - new root of Tree, i.e. new key of what_node(may be the same)
Get a subtree. A tree becomes a subtree with the root_node as a new
root. Return 0 is successful , 1 if a what_node doesn't exist.
Example: $retcode = ctree_get_subtree($tree, '1.3', '2');
|
