我有一个包含一个循环的图,但是我需要使用“拓扑排序”(当然,实际的拓扑排序不处理循环)对它进行排序。我在想怎么做呢?
例如:
A -> B
B -> C
C -> D
D -> A
可能的解决办法是:
A -> B -> C -> D
B -> C -> D -> A
C -> D -> A -> B
D -> A -> B -> C
我看到了作为,但是它对我的用例来说太复杂了。
在所有边都在错误方向上的图上,反转拓扑排序的结果是否会产生有效的拓扑顺序,就像边在排序之前被反转一样?
a -> b
a -> c
b -> d
c -> d
可以给出a b c d的拓扑结构。颠倒这个列表可以得到d c b a。在拓扑排序之前反转图形中的所有边也可以得到d c b a。这在一般情况下是真的吗?我猜没有,但我找不到一个失败的例子。
我把DAG存储为数组。如何以父节点获得最高优先级而所有叶节点获得最低优先级的方式为DAG分配优先级?
如果我有DAG,如下所示
A # A -> B,C # A
/ \ # B -> D -----> # B C //can be used in parallel
C B # C -> E # D
\ \ # D -> E
这里有生产者-消费者图。图的拓扑排序是T。我想在拓扑排序T中添加额外的节点,并改变T中的顺序。这里假设消费者关系比生产者关系具有更高的优先级。
我能想到的解决方案是:
For new node N:
check the last producer in the T for which N is consumer. Let it be T1
check the last consumer in T for which N is producer. Let it be I2.
If I1 < I2, add N after I1
If I1 > I2,
我现在正在为UE4开发我的Google Protobuf到C++的转换器。以下结构是由protobuf的消息构成的。假设在Messages.h文件中,它们按以下方式列出:
struct B
{
int i;
A b;
};
struct A
{
float f;
long l;
};
struct C
{
A a;
B b;
};
注意:我不能使用正向声明,也不能使用指针,它们应该是值。
正确的初始化顺序是:A, B, C (这意味着如果这些结构是在order A, B, C中定义的,那么一切都很好)。我有所有类型及其对其他类型的引用,在我的
给定具有N个单词和标准字典的k个起始字母的外星语言排序字典,任务是完成函数,该函数返回一个字符串,表示语言中字符的顺序。
Input: Dict[] = { "baa", "abcd", "abca", "cab", "cad" }, k = 4
Output: Function returns "bdac"
Here order of characters is 'b', 'd', 'a', 'c'
我已经用拓扑排序实现了一个问
如果有一组节点N和一组顶点V_1定义具有一定拓扑顺序的图G_1,那么如何检查来自N的节点子集和定义图G_2的新顶点V_2是否保持G_1的拓扑顺序?
例如:
G_1:
D -> E
B -> C
A -> C
G_1:[A, B, C, D, E]的拓扑序
G_2:
D -> B
B -> E
G_2:[D, B, E]的拓扑序
我在考虑某种蛮力方法,生成G_1的所有拓扑顺序,从这些命令中删除在G_2中找不到的节点,并检查是否有任何与G_2的第一个排序相匹配的方法。
我的潜在解决方案正确吗?你有更好的建议吗?
我正在尝试创建一个有序的类别分支列表,这样我就可以找到任何子类别并在开始时添加"-";还可以找到该类别可能具有的任何子类别并添加"--"等。
我的测试类属性如下所示:
public int Id { get; set; }
public int OrderInList { get; set; }
public int ParentId { get; set; }
public IList<TestCategories> Subcategories { get; set; }
示例:
Books
-Special Off
我想知道为什么所有有向无环图都有一个以上的拓扑排序顺序。 我在谷歌上搜索过,我说大多数都是轻而易举地通过了他们至少有一个topo排序的事实。但是我在思考如何实现一个单链表: A -> B -> C -> D 这可能意味着,从技术上讲,拓扑端口只有一种方式可以通过- D,C,B,A… 然而,可能的情况是,这不是一个有向无环图,但我不确定如何反驳这种情况,因为它是有向的(A到B等),无环图(没有环回到任何开始)图(从技术上讲它是一棵树)。 非常感谢您提供的任何澄清!
我使用库构建定向图,并按拓扑顺序检索其节点。由于一个图的拓扑序可能有很多种可能性,所以对于同样的等号图,我需要有拓扑序的确定性结果。
这个小应用程序突出了这个问题。
import scalax.collection.Graph
import scalax.collection.GraphEdge.DiEdge
import scalax.collection.GraphPredef._
object MainApp extends App {
// Creates new graph for every call
// val is not an option
def grap
我有一种直觉,原始图的拓扑排序与转置图的dfs相同(反转所有边)
A -> B -> C
D -> B
拓扑排序是D、A、B、C或A、D、B、C
如果我转置图形(反转所有的边)
C -> B -> A
B -> D
dfs还给出了D、A、B、C或A、D、B、C
求求你,我不能从数学上证明/反驳它。如果命题不正确,举一个反例会很有帮助。
我有几个陈述,比如
# exhibit 1
a = 0
b = 0
c = d + a
d = a + b
执行的顺序应该是正确的。
# exhibit 2
a = 0
b = 0
d = a + b # d before c
c = d + a
是否有办法找到证物1中陈述的正确执行顺序?
我尝试用有向图和语句来使用networkx,如
tree.add_edge(a, b)
tree.add_edge(b, d)
tree.add_edge(d, c)
tree.add_edge(a, c)
但我看不出如何穿越这棵树,所以必须要拿出展品2。
我不局限于网络。
做这项工作的任何工具对我来说都是
因此,假设我有以下字段对象的集合:
public class Field
{
public string Formula { get; set; }
public string Name { get; set; }
public double Value { get; set; }
}
每个字段都有一个唯一的名称。有些字段有公式。公式是一个数学表达式,用于计算字段的值,其中输入是集合中由其名称表示的其他字段。我给出的收藏品看起来可能是这样的:
名称:"A";公式:"";值: 0.0
名称:"B";公式:"&
我正在使用一个GTFS提要作为我正在开发的应用程序。我正试图列出所选路线的所有站位。目前,我正试图通过stop_sequence来订购列表,但这并不能正常工作,因为有些行程并不是每次行程都会进行,而且我收到的数据每次行程都会使stop_sequence增加一个。这一点的意义在于,stop_sequence不考虑其他可能有或多或少停留的旅行。
下面是一个例子:
这是路线的停车顺序(忽略了并非每一站都会停下来的事实)。
Stop A
Stop B
Stop C
Stop D
Stop E
下面是这条路线的一些旅行示例:
Trip 1: A, B, C, D
Trip 2: A, B, E
我的数据
我希望将多个项目列表合并到一个列表中,同时保留总体顺序要求。即:
1: A C E
2: D E
3: B A D
result: B A C D E
上面,从列表1开始,我们有ACE,然后我们知道D必须在E之前,从列表3,我们知道B必须在A之前,D必须在B和A之后。
如果存在冲突的排序,则应使用第一个排序。即
1: A C E
2: B D E
3: F D B
result: A C F B D E
%3与%2冲突(B _D与D_ B),因此将使用%2的要求。
如果排序要求意味着一个项目必须在另一个项目之前或之后,那么它是紧跟在列表之前还是之后,或者在列表的开始或结束,只要保持整体排
我有以下用于拓扑排序的伪代码
Repeat:
Find a vertex with no successor
Remove it from graph
Put It at beginning of list
Until graph is empty
我的问题是,它是否应该修改为“找到一个没有前导的顶点”?
问题描述
给定的顶点V,它可以被称为“命题”。
给定的权重:
data W
= Requires -- ^ Denotes that a "proposition" depends on another.
| Invalidates -- ^ Denotes that a "proposition" invalidates another.
在线性序中,如果A要求B,则B必须在A之前,反之,如果A使B无效,则B必须在A之后。
给出了一个加权有向多图(多重图),它最多有2条平行边.其中一个顶点只能要求包含另一个顶点一次,并且只
我的文本内容充满了这样的表达:
a = 1
d = b + c
b = a * c
c = 2 - a
...
此表达式可以按随机顺序编写。我可以提取每个表达式并对它们求值,但我需要找到最佳算法来避免循环求值,例如:
a = 1
d = ? (skip)
b = ? (skip)
c = 2 - a = 1
...
d = ? (skip)
b = a * c = 1
...
d = b + c = 2
...
有没有办法根据涉及的参数对方程进行“排序”,以避免额外的计算传递,如:
a = 1
c = 2 - a = 1
b = a * c = 1
d = b + c = 2
...
我的Java 8应用程序中有一个代码气味,我想通过重新设计来解决这个问题。
我声明了一个枚举DataType,它不仅包含枚举值,还包含基于某些逻辑的这些枚举值的有序列表。总而言之,每个枚举值都声明了一组对其他枚举值(相同类型)的依赖关系,该列表是这些枚举值的。每个枚举值也有一个与之关联的Calculator。
public Enum DataType
{
A(EnumSet.noneOf(DataType.class), new CalculatorA()),
B(EnumSet.of(A), new CalculatorB()),
C(EnumSet.noneOf(D
我只想给张量赋值一次,并且在以后的所有执行中保持不变。换句话说,我想实现如下内容:
x = tf.cond(tf.equal(x_ready, 0), ComputeX(), tf.no_op)
这当然行不通,因为tf.no_op不返回张量。那么,有没有什么简单的方法可以在Tensorflow中实现与以下C++代码等效的代码?
x_ready = false;
if (!x_ready) {
x = ComputeX();
x_ready = true;
} // and there is no "else" branch
请注意,我不希望通过以下方式实现它:
x =