Dijkstra algorithm in php?
Posted: Fri Aug 11, 2006 8:55 am
anyone has this algorithm implemented in php?
searched google, and this forums but no real answer.
Thanks
searched google, and this forums but no real answer.
Thanks
A community of PHP developers offering assistance, advice, discussion, and friendship.
http://forums.devnetwork.net/
Code: Select all
0..* INS
0...* OUTS which will be used as INS by other sources(nodes).Code: Select all
source A
IN(s) - customer_id
OUT(s) - phone_number, server_name
source B
IN(s) - server_name
OUT(s) - network_id
source C
IN(s) - networ_id
OUT(s) - ipsCode: Select all
IN (using customer_id)-> SourceA -> (using server_name) -> source B -> (using network_id) ->source C-> ips OUTole wrote:OK yeah I definately need to know why you have this fantasic nodes arrangement and also how they are stored.
Code: Select all
<?php
class node {
private static $_instanceCount = 0;
private $connections = array();
private $_nodeID = 0;
public $ins = array();
public $outs = array();
public function connect(node $node) {
$this->connections[] = $node;
}
public function __construct($ins, $outs) {
$this->_nodeID = ++self::$_instanceCount;
$this->ins = $ins;
$this->outs = $outs;
}
public function __toString() {
return 'Node #' . $this->_nodeID;
}
public function showConnected() {
$ret = array();
foreach($this->connections as $nextNode) {
$ret[] = (string) $nextNode;
}
return $ret;
}
}
function indexIns($listOfNodes) {
$ret = array();
foreach($listOfNodes as $node) {
foreach($node->ins as $in) {
if(!isset($ret[$in]) || !is_array($ret[$in]))
$ret[$in] = array();
$ret[$in][] = $node;
}
}
return $ret;
}
function dumpIndex($index) {
foreach($index as $in => $nodeList) {
echo $in . ' => ' .
join(', ', array_map(
create_function('$q', 'return $q->__toString();'),
$nodeList
)
) . PHP_EOL;
}
}
function interconnectNodes($nodes, $index) {
foreach($nodes as $node) {
foreach($node->outs as $out) {
if(!isset($index[$out]) || !is_array($index[$out])) // free out
continue;
foreach($index[$out] as $nextNode) {
$node->connect($nextNode);
}
}
}
}
function dumpConnections($nodes) {
foreach($nodes as $node) {
echo $node, ' is connected to ' . implode(', ', $node->showConnected()) . PHP_EOL;
}
}
$nodes = array();
$nodes[] = new Node($ins = array('network_id'), $outs = array('ip'));
$nodes[] = new Node($ins = array('customer_id'), $outs = array('phone_number', 'server_name'));
$nodes[] = new Node($ins = array('customer_id','server_name'), $outs = array('network_id'));
$index = indexIns($nodes);
dumpIndex($index);
interconnectNodes($nodes, $index);
dumpConnections($nodes);
?>
just wanted to say thanks. gave me a quick start on this one.Weirdan wrote:here is simple framework to experiment on (if you haven't implemented yours already):things that you can optimise:Code: Select all
<?php class node { private static $_instanceCount = 0; private $connections = array(); private $_nodeID = 0; public $ins = array(); public $outs = array(); public function connect(node $node) { $this->connections[] = $node; } public function __construct($ins, $outs) { $this->_nodeID = ++self::$_instanceCount; $this->ins = $ins; $this->outs = $outs; } public function __toString() { return 'Node #' . $this->_nodeID; } public function showConnected() { $ret = array(); foreach($this->connections as $nextNode) { $ret[] = (string) $nextNode; } return $ret; } } function indexIns($listOfNodes) { $ret = array(); foreach($listOfNodes as $node) { foreach($node->ins as $in) { if(!isset($ret[$in]) || !is_array($ret[$in])) $ret[$in] = array(); $ret[$in][] = $node; } } return $ret; } function dumpIndex($index) { foreach($index as $in => $nodeList) { echo $in . ' => ' . join(', ', array_map( create_function('$q', 'return $q->__toString();'), $nodeList ) ) . PHP_EOL; } } function interconnectNodes($nodes, $index) { foreach($nodes as $node) { foreach($node->outs as $out) { if(!isset($index[$out]) || !is_array($index[$out])) // free out continue; foreach($index[$out] as $nextNode) { $node->connect($nextNode); } } } } function dumpConnections($nodes) { foreach($nodes as $node) { echo $node, ' is connected to ' . implode(', ', $node->showConnected()) . PHP_EOL; } } $nodes = array(); $nodes[] = new Node($ins = array('network_id'), $outs = array('ip')); $nodes[] = new Node($ins = array('customer_id'), $outs = array('phone_number', 'server_name')); $nodes[] = new Node($ins = array('customer_id','server_name'), $outs = array('network_id')); $index = indexIns($nodes); dumpIndex($index); interconnectNodes($nodes, $index); dumpConnections($nodes); ?>
- index node on its creation
- make your algorithm work on index instead of working with actual graph
So, how is it going?just wanted to say thanks. gave me a quick start on this one.
we'll see todayWeirdan wrote:So, how is it going?just wanted to say thanks. gave me a quick start on this one.