英文:
Is there a way to modify the isdag matlab function in order for it to ignore cycles of length zero?
问题
最近,我被要求编写一个优化作业车间调度问题的算法,并且我正在采用一种使用有向图的方法。在这些有向图中,节点代表事件,边代表事件之间的时间先决条件,即时间不等式。例如,两个连续的节点A和B,它们之间有一个长度为2的有向边,从A到B,表示不等式tB-tA>=2。因此,等式将由两个方向相反的有向边表示,一个具有正长度,另一个具有负长度。因此,我们最终得到一个具有一些零长度循环的图。
Matlab有一个名为isdag的函数,如果有向图没有循环,则返回true,否则返回false;是否有办法修改此函数,使其忽略长度为零的循环?如果没有,是否有人有任何关于如何编写此功能的想法?提前感谢!
我也尝试了这个,但不起作用。我使用了邻接矩阵adjMatrix = [0, 10, 0; -9, 0, 5; 0, 0, 0],它应该返回true,因为它在节点1和2之间有一个长度为10+(-9)=1的循环,但它返回false。
英文:
recently I've been tasked with programming an algorithm that optimizes job-shop scheduling problems and I'm following an approach which uses directed graphs for this. In these directed graphs nodes represent events and edges represent time precedence constraints between events, i.e. time inequalities. So, for example, 2 consecutive nodes A & B separated by a directed edge of length 2 which goes from A to B would represent the inequality t<sub>B</sub>-t<sub>A</sub>>=2. It follows that equality would be represented by 2 directed edges of opposite directions, one with positive length and the other one with negative length. Thus, we end up with a graph which has some cycles of length zero.
Matlab has a function called isdag which returns true if a directed graph has no cycles and false otherwise; is there a way to modify this function in order for it to ignore the cycles of length zero? If not, has anyone got any idea on how to program this? Thanks in advance!!
I also tried this but it doesn't work. I've tried it with the adjacency matrix adjMatrix = [0, 10, 0; -9, 0, 5; 0, 0, 0] it should return true as it has a cycle between nodes 1 and 2 of length 10+(-9)=1, but it returns false,
function result = hasCycleWithPositiveWeight(adjMatrix)
n = size(adjMatrix,1);
visited = false(1,n);
path = zeros(1,n);
result = false;
for i = 1:n
pathStart = 1;
pathEnd = 1;
path(pathEnd) = i;
totalWeight = 0;
while pathStart <= pathEnd
node = path(pathStart);
visited(node) = true;
for j = 1:n
if adjMatrix(node,j) > 0
totalWeight = totalWeight + adjMatrix(node,j);
if visited(j)
if j == i && totalWeight > 0
result = true;
return;
end
else
pathEnd = pathEnd + 1;
path(pathEnd) = j;
end
end
end
pathStart = pathStart + 1;
totalWeight = totalWeight - adjMatrix(node, path(max(pathStart-1,1)));
visited(node) = false;
end
end
end
答案1
得分: 0
以下是翻译好的部分:
如果你想找到仅在两个连续节点之间的循环,请使用以下代码:
a = [0, 10, 0; -9, 0, 5; 0, 0, 0];
b = a.';
And = (a & b);
Add = (a + b);
result = any(And .* Add, 'all');
它返回 true
,如果存在长度不为 0
的循环。
解释:
在图中,如果节点 2
和 5
之间的距离是12,我们将邻接矩阵的元素 A(2, 5)
设置为 12
,如果节点 5
和 2
之间的距离是-8,我们将邻接矩阵的元素 A(5, 2)
设置为 8
。因此,节点关系之间存在对称性。矩阵的转置会将位置 (2, 5)
变为 (5, 2)
,以及 (5, 2)
变为 (2, 5)
。
如果我们对一个矩阵进行 And
运算和它的转置,结果矩阵显示如果存在两个节点之间的循环,则为 1
。
如果我们将一个矩阵与其转置进行 Add
运算,结果矩阵显示节点之间的两两距离之和。
如果我们逐元素相乘两个矩阵 Add
和 And
,结果矩阵显示节点之间的两两距离之和,但不形成循环的两个节点的距离之和设置为 0
。
现在可以使用 any
函数来测试矩阵是否存在长度不为 0
的循环。
英文:
If you want to find the cycle between just two consecutive nodes use this:
a = [0, 10, 0; -9, 0, 5; 0, 0, 0];
b = a.';
And = (a & b);
Add = (a + b);
result = any( And .* Add, 'all');
It returns true
if there is a cycle that its length isn't 0
.
Explanation:
In the graph if the length between node 2
and 5
is 12 we set the element A(2 , 5)
of the adjacency matrix to 12
and if the length between node 5
and 2
is -8 we set the element A(5, 2)
of the adjacency matrix to 8
. So there is a symmetry between nodes relationship. The matrix transpose changes the position of (2, 5)
to (5, 2)
and (5, 2)
to (2, 5)
.
If we And
a matrix with its transpose the result matrix shows that there is a cycle between two nodes if it is 1
.
If we Add
a matrix to its transpose the result matrix shows the sum of the pairwise lengths between nodes.
If we multiply
element-wise the two matrices Add
and And
the result matrix shows the sum of the pairwise lengths between nodes but the sum of lengths of two nodes that don't form a cycle is set to 0
.
Now the function any
can be used to test if the matrix has a cycle that its length isn't 0
.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论