Sh@man
24.02.2004, 20:06
Я столкнулся с проблемой при реализации алгоритма Дейкстры (нахождения кратчайшего пути по графу) во Флеше. Проблема в построении самого графа.
Граф у меня задается во внешнем xml файле примерно так:
<root>
<uzel1>
<uzel2 n="2" l="1"/>
<uzel4 n="4" l="3"/>
<uzel8 n="8" l="4"/>
</uzel1>
<uzel2>
<uzel1 n="1" l="1"/>
<uzel3 n="3" l="2"/>
<uzel4 n="4" l="2"/>
<uzel5 n="5" l="6"/>
</uzel2>
<uzel3>
<uzel2 n="2" l="2"/>
<uzel5 n="5" l="3"/>
<uzel6 n="6" l="4"/>
</uzel3>
....
</root>
Где:
- количество дочерних узлов
(<uzel1 n="1" l="1"/><uzel3 n="3" l="2"/>...) - это количество вершин графа, с которыми связана данная (например <uzel3>)
- атрибут "n" каждого дочернего узла - это номер вершины, с которой связан родительский узел ,
- атрибут "l" - это вес, или, скажем , расстояние от родительского узла до дочернего с данным атрибутом.
Из этой xml я получаю матрицу весов и 3 массива для реализации алгоритма. И по этим массивам и матрице надо сделать визуальное представление графа, где размерность матрицы = количеству узлов, а => количеству дубликатов отдельного MovieClip'a - узла графа.
С дублированием проблем нет, но как соединить каждую вершину графа <uzel[i] > дугой с другими вершинами, связь с которыми определена для данной.
Я предполагаю, что нужна функция для построения линий (и она в принципе есть). Но в какой цикл загонять ее выполнение для каждого узла графа - вот это проблема.
Далее привожу кусок кода, в который я полагаю надо вставить реализацию функции соединения вершин графа.
Может кто поможет разобраться с этой проблемой?
function MatrixConstructor(sourcexml) {
trace("MATRIX CONSTRUCTOR STARTED >>");
var src_xml = new XML();
src_xml = sourcexml;
var razmernost = getNumOfChilds(src_xml.firstChild);
trace("Matrix razmernost="+razmernost);
_root.matrix = new Array(10);
for (i=0; i<razmernost; i++) {
_root.matrix[i] = new Array();
}
for (x=0; x<razmernost; x++){
for(y=0;y<razmernost;y++){
_root.matrix[x][y] = Number.POSITIVE_INFINITY;
}
}
for (rowIndex=0;rowIndex<razmernost;rowIndex++){
var numOfChlds =getNumOfChilds(src_xml.firstChild.childNodes[rowIndex]);
trace("numOfChlds="+numOfChlds);
duplicateMovieClip(_root.node_mc, "node_mc"+(rowIndex+1), 110+rowIndex);
_root["node_mc"+(rowIndex+1)]._x = Math.random()*400;
_root["node_mc"+(rowIndex+1)]._y = Math.random()*300;
_root["node_mc"+(rowIndex+1)].numtxt = rowIndex+1;
_root["node_mc"+(rowIndex+1)].onPress = function () {
startDrag(this,false,0,0,540,390);
}
_root["node_mc"+(rowIndex+1)].onRelease = function () {
this.stopDrag();
}
for(colIndex=0;colIndex<numOfChlds;colIndex++){
nValue=getAttributeN(src_xml.firstChild.childNodes[rowIndex].childNodes[colIndex]);
lValue = getAttributeL(src_xml.firstChild.childNodes[rowIndex].childNodes[colIndex]);
trace("lValue="+lValue+" "+ "nValue="+nValue);
_root.matrix[rowIndex][nValue-1] = lValue;
}
}
}
Граф у меня задается во внешнем xml файле примерно так:
<root>
<uzel1>
<uzel2 n="2" l="1"/>
<uzel4 n="4" l="3"/>
<uzel8 n="8" l="4"/>
</uzel1>
<uzel2>
<uzel1 n="1" l="1"/>
<uzel3 n="3" l="2"/>
<uzel4 n="4" l="2"/>
<uzel5 n="5" l="6"/>
</uzel2>
<uzel3>
<uzel2 n="2" l="2"/>
<uzel5 n="5" l="3"/>
<uzel6 n="6" l="4"/>
</uzel3>
....
</root>
Где:
- количество дочерних узлов
(<uzel1 n="1" l="1"/><uzel3 n="3" l="2"/>...) - это количество вершин графа, с которыми связана данная (например <uzel3>)
- атрибут "n" каждого дочернего узла - это номер вершины, с которой связан родительский узел ,
- атрибут "l" - это вес, или, скажем , расстояние от родительского узла до дочернего с данным атрибутом.
Из этой xml я получаю матрицу весов и 3 массива для реализации алгоритма. И по этим массивам и матрице надо сделать визуальное представление графа, где размерность матрицы = количеству узлов, а => количеству дубликатов отдельного MovieClip'a - узла графа.
С дублированием проблем нет, но как соединить каждую вершину графа <uzel[i] > дугой с другими вершинами, связь с которыми определена для данной.
Я предполагаю, что нужна функция для построения линий (и она в принципе есть). Но в какой цикл загонять ее выполнение для каждого узла графа - вот это проблема.
Далее привожу кусок кода, в который я полагаю надо вставить реализацию функции соединения вершин графа.
Может кто поможет разобраться с этой проблемой?
function MatrixConstructor(sourcexml) {
trace("MATRIX CONSTRUCTOR STARTED >>");
var src_xml = new XML();
src_xml = sourcexml;
var razmernost = getNumOfChilds(src_xml.firstChild);
trace("Matrix razmernost="+razmernost);
_root.matrix = new Array(10);
for (i=0; i<razmernost; i++) {
_root.matrix[i] = new Array();
}
for (x=0; x<razmernost; x++){
for(y=0;y<razmernost;y++){
_root.matrix[x][y] = Number.POSITIVE_INFINITY;
}
}
for (rowIndex=0;rowIndex<razmernost;rowIndex++){
var numOfChlds =getNumOfChilds(src_xml.firstChild.childNodes[rowIndex]);
trace("numOfChlds="+numOfChlds);
duplicateMovieClip(_root.node_mc, "node_mc"+(rowIndex+1), 110+rowIndex);
_root["node_mc"+(rowIndex+1)]._x = Math.random()*400;
_root["node_mc"+(rowIndex+1)]._y = Math.random()*300;
_root["node_mc"+(rowIndex+1)].numtxt = rowIndex+1;
_root["node_mc"+(rowIndex+1)].onPress = function () {
startDrag(this,false,0,0,540,390);
}
_root["node_mc"+(rowIndex+1)].onRelease = function () {
this.stopDrag();
}
for(colIndex=0;colIndex<numOfChlds;colIndex++){
nValue=getAttributeN(src_xml.firstChild.childNodes[rowIndex].childNodes[colIndex]);
lValue = getAttributeL(src_xml.firstChild.childNodes[rowIndex].childNodes[colIndex]);
trace("lValue="+lValue+" "+ "nValue="+nValue);
_root.matrix[rowIndex][nValue-1] = lValue;
}
}
}