Dijkstra algorithm in php?
Moderator: General Moderators
Dijkstra algorithm in php?
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
hm...I am now not sure if this is the algorithm I need.
I found this written in pseudo code but the prerequisites does not quite match my situation.
http://www.devmaster.net/articles/pathfinding/
My case:
I have several sources of data (nodes) - DB, urls, XLS..whatever
- each source has:
- several sources (nodes) may have the same/overlaping INS/OUTS.
so this means:
1. From node to node I can have more than one edge (path between neighbour source).
2. I dont know the edges(paths between source) in advance.
Because of these two, I don't think I can impelment this algorithm (as stated in the link I gave).
Here is more specific exmaple of the problem:
Target is source C from source A to find ips basted on customer_id
Solution in this case is
so the problem is how to find such possible paths (because they can be more than one apperantly.)
Any ideas
I found this written in pseudo code but the prerequisites does not quite match my situation.
http://www.devmaster.net/articles/pathfinding/
My case:
I have several sources of data (nodes) - DB, urls, XLS..whatever
- each source has:
Code: Select all
0..* INS
0...* OUTS which will be used as INS by other sources(nodes).- several sources (nodes) may have the same/overlaping INS/OUTS.
so this means:
1. From node to node I can have more than one edge (path between neighbour source).
2. I dont know the edges(paths between source) in advance.
Because of these two, I don't think I can impelment this algorithm (as stated in the link I gave).
Here is more specific exmaple of the problem:
Target is source C from source A to find ips basted on customer_id
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 OUTAny ideas
- Ollie Saunders
- DevNet Master
- Posts: 3179
- Joined: Tue May 24, 2005 6:01 pm
- Location: UK
Whoa that looks really complicated. May I ask what you are making and why you need this?
Otherwise there seems to be Pseudocode in Wikipedia so you'll have to work from that yourself unless you can find anyone else who is prepaired to do. Remember if you have any specific difficulties you can always come back here for help.
Otherwise there seems to be Pseudocode in Wikipedia so you'll have to work from that yourself unless you can find anyone else who is prepaired to do. Remember if you have any specific difficulties you can always come back here for help.
- Ollie Saunders
- DevNet Master
- Posts: 3179
- Joined: Tue May 24, 2005 6:01 pm
- Location: UK
ole wrote:OK yeah I definately need to know why you have this fantasic nodes arrangement and also how they are stored.
here is the goal: you search in more than one source of data (different source have different output structure,input requirements and so on) for related information.
So once you describe what INs make sense for the source of data and what OUTs (results you can get from data...results like keys I mean...like to use as other INs) you can search for complex data within various sources of data...and come up with some useful information.
like in the example I gave.... you search for ips but you only have customer_id.
the source with the data that knows about ip have no idea what customer_id is...but it knows network_id....etc.
so different source are combinded dynamically and voalla.
of course, you have to make the assumption that customer_id in data source A means the exact same thing in source X
so you start searching by something....give the program from witch module or whatever you need data...and it looks either directly to get data or through other sources to make the relation.
When I am thinking these sources of data are actually nodes
To make this one step further...it is all about making search enginge within a company for example. all data, many systems...and when you need something specific you have to go through several interfaces to get what you need. this what problem this is supposed to solve (ultimately there will be ajax stuff...some boxes you group together or something to specify the data you need gathered.). If you need other sources...you just define what keys (INs) it can search by...and what data it can provide....and it will be automatically integrated to the global picture.
Maybe some more advanced methods are there...I am absolutely sure...but so far this is my approach to the problem
- Ollie Saunders
- DevNet Master
- Posts: 3179
- Joined: Tue May 24, 2005 6:01 pm
- Location: UK
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
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