|
-
Mar 21st, 2005, 03:36 PM
#1
Thread Starter
Stuck in the 80s
Problem converting Java to PHP
I've tried converting the following Java code to PHP, but each time I do, the code doesn't work. It executes without error, but doesn't produce the same results as it's Java counterpart. It's pretty basic code, nothing language specific in it. Just syntax differences.
Any know what might not be translating well? Here's the java code:
Code:
class DistPar {
public int distance;
public int parentVert;
public DistPar(int pv, int d) {
distance = d;
parentVert = pv;
}
}
class Vertex {
public char label;
public boolean isInTree;
public Vertex(char lab) {
label = lab;
isInTree = false;
}
}
class Graph {
private final int MAX_VERTS = 20;
private final int INFINITY = 1000000;
private Vertex vertexList[]; // list of vertices
private int adjMat[][]; // adjacency matrix
private int nVerts; // current number of vertices
private int nTree; // number of verts in tree
private DistPar sPath[]; // array for shortest-path data
private int currentVert; // current vertex
private int startToCurrent; // distance to currentVert
public Graph() {
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
nTree = 0;
for(int j=0; j<MAX_VERTS; j++)
for(int k=0; k<MAX_VERTS; k++)
adjMat[j][k] = INFINITY;
sPath = new DistPar[MAX_VERTS];
}
public void addVertex(char lab) {
vertexList[nVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end, int weight) {
adjMat[start][end] = weight;
}
public void path() {
int startTree = 0;
vertexList[startTree].isInTree = true;
nTree = 1;
for(int j=0; j<nVerts; j++) {
int tempDist = adjMat[startTree][j];
sPath[j] = new DistPar(startTree, tempDist);
}
while(nTree < nVerts) {
int indexMin = getMin(); // get minimum from sPath
int minDist = sPath[indexMin].distance;
if(minDist == INFINITY) {
System.out.println("There are unreachable vertices");
break;
} else {
currentVert = indexMin;
startToCurrent = sPath[indexMin].distance;
}
vertexList[currentVert].isInTree = true;
nTree++;
adjust_sPath();
}
displayPaths();
nTree = 0;
for(int j=0; j<nVerts; j++)
vertexList[j].isInTree = false;
}
public int getMin() {
int minDist = INFINITY;
int indexMin = 0;
for(int j=1; j<nVerts; j++) {
if( !vertexList[j].isInTree && sPath[j].distance < minDist ) {
minDist = sPath[j].distance;
indexMin = j;
}
}
return indexMin;
}
public void adjust_sPath() {
int column = 1; // skip starting vertex
while(column < nVerts) {
if( vertexList[column].isInTree ) {
column++;
continue;
}
int currentToFringe = adjMat[currentVert][column];
int startToFringe = startToCurrent + currentToFringe;
int sPathDist = sPath[column].distance;
if(startToFringe < sPathDist) {
sPath[column].parentVert = currentVert;
sPath[column].distance = startToFringe;
}
column++;
} // end while(column < nVerts)
}
public void displayPaths() {
for(int j=0; j<nVerts; j++) {
System.out.print(vertexList[j].label + "="); // B=
if(sPath[j].distance == INFINITY)
System.out.print("inf"); // inf
else
System.out.print(sPath[j].distance); // 50
char parent = vertexList[ sPath[j].parentVert ].label;
System.out.println("(" + parent + ") "); // (A)
}
System.out.println("");
}
}
class PathApp {
public static void main(String[] args)
{
Graph theGraph = new Graph();
theGraph.addVertex('A'); // 0 (start)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4
theGraph.addVertex('F'); // 5
theGraph.addVertex('G'); // 6
theGraph.addVertex('H'); // 7
theGraph.addVertex('I'); // 8
theGraph.addEdge(0, 2, 1);
theGraph.addEdge(0, 5, 1);
theGraph.addEdge(0, 7, 1);
theGraph.addEdge(1, 4, 1);
theGraph.addEdge(1, 5, 1);
theGraph.addEdge(1, 6, 1);
theGraph.addEdge(2, 3, 1);
theGraph.addEdge(2, 7, 1);
theGraph.addEdge(3, 4, 1);
theGraph.addEdge(3, 8, 1);
theGraph.addEdge(5, 6, 1);
theGraph.addEdge(5, 7, 1);
theGraph.addEdge(7, 8, 1);
System.out.println("Shortest paths");
theGraph.path(); // shortest paths
System.out.println();
} // end main()
} // end class PathApp
////////////////////////////////////////////////////////////////
-
Mar 21st, 2005, 05:10 PM
#2
Re: Problem converting Java to PHP
Can you post your converted PHP. Is it PHP 4 or PHP 5?
-
Mar 21st, 2005, 05:28 PM
#3
Thread Starter
Stuck in the 80s
Re: Problem converting Java to PHP
 Originally Posted by visualAd
Can you post your converted PHP. Is it PHP 4 or PHP 5?
Whoops. I meant too, but the post was too big, and I forgot to add it in a reply. Here it is:
PHP Code:
<?php
class DistPar {
var $distance;
var $parentVert;
function DistPar($pv, $d) {
$this->distance = $d;
$this->parentVert = $pv;
}
}
class Vertex {
var $label; // label (e.g. 'A')
var $isInTree;
function Vertex($lab) {
$this->label = $lab;
$this->isInTree = false;
}
} // end class Vertex
class Graph {
var $MAX_VERTS = 20;
var $INFINITY = 1000000;
var $vertexList; // = new Vertex(); // list of vertices
var $adjMat; // adjacency matrix
var $nVerts; // current number of vertices
var $nTree; // number of verts in tree
var $sPath; // = new DistPair(); // array for shortest-path data
var $currentVert; // current vertex
var $startToCurrent; // distance to currentVert
function Graph() {
//$this->vertexList = new Vertex[MAX_VERTS];
//$this->adjMat = new int[MAX_VERTS][MAX_VERTS];
$this->nVerts = 0;
$this->nTree = 0;
for($j = 0; $j < $this->MAX_VERTS; $j++) // set adjacency
for($k = 0; $k < $this->MAX_VERTS; $k++) // matrix
$this->adjMat[$j][$k] = $this->INFINITY; // to infinity
//$this->sPath = new DistPar[$this->MAX_VERTS]; // shortest paths
} // end constructor
function addVertex($lab) {
$this->vertexList[] = new Vertex($lab); $this->nVerts++;
}
function addEdge($start, $end, $weight) {
$this->adjMat[$start][$end] = $weight; // (directed)
}
function path() { // find all shortest paths
$startTree = 0; // start at vertex 0
$this->vertexList[$startTree]->isInTree = true;
$this->nTree = 1; // put it in tree
for($j = 0; $j < $this->nVerts; $j++) {
$tempDist = $this->adjMat[$startTree][$j];
$this->sPath[$j] = new DistPar($startTree, $tempDist);
}
while($this->nTree < $this->nVerts) {
$indexMin = $this->getMin(); // get minimum from sPath
$minDist = $this->sPath[$indexMin]->distance;
if($minDist == $this->INFINITY) { // if all infinite // or in tree,
echo "There are unreachable vertices<br />";
break; // sPath is complete
} else { // reset currentVert
$this->currentVert = $indexMin; // to closest vert
$this->startToCurrent = $this->sPath[$indexMin]->distance;
}
$this->vertexList[$this->currentVert]->isInTree = true;
$this->nTree++;
$this->adjust_sPath(); // update sPath[] array
} // end while(nTree<nVerts)
$this->displayPaths(); // display sPath[] contents
$this->nTree = 0; // clear tree
for($j = 0; $j < $this->nVerts; $j++)
$this->vertexList[$j]->isInTree = false;
} // end path()
function getMin() { // get entry from sPath // with minimum distance
$minDist = $this->INFINITY; // assume minimum
$indexMin = 0;
for($j = 1; $j < $this->nVerts; $j++) { // for each vertex // if it's in tree and
if(!$this->vertexList[$j]->isInTree && $this->sPath[$j]->distance < $minDist) {
$minDist = $this->sPath[$j]->distance;
$indexMin = $j; // update minimum
}
} // end for
return $indexMin; // return index of minimum
} // end getMin()
function adjust_sPath() {
$column = 1;
while($column < $this->nVerts) { // go across columns
if($this->vertexList[$column]->isInTree) {
$column++;
continue;
}
$currentToFringe = $this->adjMat[$currentVert][$column];
$startToFringe = ($this->startToCurrent + $currentToFringe);
$sPathDist = $this->sPath[$column]->distance;
if($startToFringe < $this->sPathDist) { // if shorter // update sPath
$this->sPath[$column]->parentVert = $currentVert;
$this->sPath[$column]->distance = $startToFringe;
}
$column++;
} // end while(column < nVerts)
} // end adjust_sPath()
function displayPaths() {
for($j = 0; $j < $this->nVerts; $j++) { // display contents of sPath[]
echo $this->vertexList[$j]->label . '='; // B=
if($this->sPath[$j]->distance == $this->INFINITY) {
// inf
echo '[inf]<br />';
} else {
// 50
echo '[' . $this->sPath[$j]->distance . ']<br />' ;
}
$parent = $this->vertexList[ $this->sPath[$j]->parentVert ]->label;
//echo '(' . $parent . ') '; // (A)
}
echo '<br />';
}
} // end class Graph
$theGraph = new Graph();
$theGraph->addVertex('A'); // 0 (start)
$theGraph->addVertex('B'); // 1
$theGraph->addVertex('C'); // 2
$theGraph->addVertex('D'); // 3
$theGraph->addVertex('E'); // 4
$theGraph->addVertex('F'); // 5
$theGraph->addVertex('G'); // 6
$theGraph->addVertex('H'); // 7
$theGraph->addVertex('I'); // 8
$theGraph->addEdge(0, 2, 1);
$theGraph->addEdge(0, 5, 1);
$theGraph->addEdge(0, 7, 1);
$theGraph->addEdge(1, 4, 1);
$theGraph->addEdge(1, 5, 1);
$theGraph->addEdge(1, 6, 1);
$theGraph->addEdge(2, 3, 1);
$theGraph->addEdge(2, 7, 1);
$theGraph->addEdge(3, 4, 1);
$theGraph->addEdge(3, 8, 1);
$theGraph->addEdge(5, 6, 1);
$theGraph->addEdge(5, 7, 1);
$theGraph->addEdge(7, 8, 1);
echo 'Shortest Paths<br />';
$theGraph->path();
?>
-
Mar 22nd, 2005, 12:37 AM
#4
Thread Starter
Stuck in the 80s
Re: Problem converting Java to PHP
Update: I don't need this code anymore, but am still curious as to what I did wrong, so if anyone figures it out, let me know.
-
Mar 22nd, 2005, 02:29 AM
#5
Re: Problem converting Java to PHP
The problem may heve been caused by thee way PHP handles objects. Whenether you create a new instance of an object, a copy is returned by default.
In the past when I have had a problem with objects changing all object assignments like $new_object = $old_object to $new_object = & $old_object and the creation of new objects to $object = & new $object has solved the problem.
What is it supposed to do and what doesn't work?
-
Mar 23rd, 2005, 03:40 PM
#6
Thread Starter
Stuck in the 80s
Re: Problem converting Java to PHP
The program is supposed to be a shortest paths algorithm for a graph. The PHP version of my code just doesn't return the same values as the Java version. It either returns 1 or infinity for all vertices.
But I wrote my own piece of code to do it, so I don't need to translate this one anymore. Was just curious what was screwing it up.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|
Reply With Quote
