标签: graph-traversal

我有一个由用户创建的有向无环图，其中图的每个节点（顶点）代表对某些数据执行的操作。节点的输出取决于其输入（显然），并且该输入由其父节点提供。然后输出将传递给其子级。保证不存在循环，因此可以忽略。

该图的工作原理与Blender 中的着色器编辑器相同。每个节点对其输入执行一些操作，并且该操作的成本可能任意高。因此，我只想在严格要求时评估这些操作。

当通过用户输入或其他方式更新节点时，我需要重新评估每个节点，这取决于更新节点的输出。但是，鉴于我无法证明多次评估同一节点的合理性，我需要一种方法来确定更新节点的正确顺序。基本的广度优先遍历并不能解决问题。要了解原因，请考虑此图：

传统的广度优先遍历将导致D在 之前进行评估B，尽管D依赖于B。

我尝试过反向进行广度优先遍历（即从O1和O2节点开始，向上遍历图形），但我似乎遇到了同样的问题。反向广度优先遍历将访问Dbefore B，因此I2before A，导致I2被排序在 after A，尽管A取决于I2。

我确信我在这里遗漏了一些相对简单的东西，而且我觉得反向遍历似乎是关键，但我似乎无法全神贯注并让所有部分都适合。我认为一个潜在的解决方案是按预期使用反向遍历，但不是避免多次访问每个节点，而是在每次出现时访问每个节点，确保它具有绝对正确的顺序。但是多次访问每个节点以及随之而来的指数扩展是一个非常没有吸引力的解决方案。

对于此类问题是否有众所周知的有效算法？

假设我有来自各个农场的苹果。所以树结苹果，农场有树。我想要一份苹果列表，其中还包含对它们来自的农场的引用。

g = new TinkerGraph();

// apples
a1 = g.addVertex("a1");
a1.setProperty("type", "apple");

a2 = g.addVertex("a2");
a2.setProperty("type", "apple");

a3 = g.addVertex("a3");
a3.setProperty("type", "apple");


// trees
t1 = g.addVertex("t1");
t1.setProperty("type", "tree");

t2 = g.addVertex("t2");
t2.setProperty("type", "tree");


// farms
f1 = g.addVertex("f1");
f1.setProperty("type", "farm");
f1.setProperty("uid", "f1");

f2 = g.addVertex("f2");
f2.setProperty("type", "farm");
f2.setProperty("uid", "f2");

g.addEdge(t1, a1, "bears");
g.addEdge(t1, a2, "bears");
g.addEdge(t2, a3, "bears");

g.addEdge(f1, t1, "has");
g.addEdge(f2, t2, "has");

我想遍历图表来报告每个苹果，并在其中包含农场 ID。我尝试过这样的事情：

g.V.has("type", "apple").copySplit(_().in("bears").in("has").map("uid"),
                                  _().map()).fairMerge

我得到的输出是：

==>{uid=f1}
==>{type=apple}
==>{uid=f1}
==>{type=apple}
==>{uid=f2}
==>{type=apple}

我想要的是：

==>{uid=f1, type=apple} …

我已经死了泰坦新手,当我开始研究它时,我感到很困惑,因为它有很多新东西,如Gremlin,tinkerpop和rexter等.

我想要的是java中的一个例子,它使用Titan和Cassandra作为后端.我想创建一个图形,存储在cassandra中,检索它并遍历它.一个非常简单的也会很有帮助.

我在java中运行了一个基本的例子.

    BaseConfiguration baseConfiguration = new BaseConfiguration();
    baseConfiguration.setProperty("storage.backend", "cassandra");
    baseConfiguration.setProperty("storage.hostname", "192.168.3.82");

    TitanGraph titanGraph = TitanFactory.open(baseConfiguration);

     Vertex rash = titanGraph.addVertex(null);
        rash.setProperty("userId", 1);
        rash.setProperty("username", "rash");
        rash.setProperty("firstName", "Rahul");
        rash.setProperty("lastName", "Chaudhary");
        rash.setProperty("birthday", 101);

        Vertex honey = titanGraph.addVertex(null);
        honey.setProperty("userId", 2);
        honey.setProperty("username", "honey");
        honey.setProperty("firstName", "Honey");
        honey.setProperty("lastName", "Anant");
        honey.setProperty("birthday", 201);

        Edge frnd = titanGraph.addEdge(null, rash, honey, "FRIEND");
        frnd.setProperty("since", 2011);

        titanGraph.shutdown();

所以当我运行它时,我观察了cassandra日志并创建了一个名为titan的键空间和下表:

• titan_ids
• edgestore
• graphindex
• 系统属性
• systemlog
• txlog
• edgestore_lock_
• graphindex_lock_
• system_properties_lock_

我不知道这些表的用途以及它们如何存储数据.

运行程序后,会创建一个包含2个顶点和它们之间边缘的图形.我查询了表格,并在每个表格中找到了一些十六进制值.

我有以下问题:

1. 如何将图存储在cassandra中？

2. 现在我有这个图表说'x'存储在cassandra中.假设我创建了另一个图形'y'并存储它.如何检索和遍历任何特定图表？因为在正常的cql查询中,您知道要查询的表和列.我将如何分别识别'x'和'y'.

3. 任何人都可以帮助在java中发布示例代码,以使用一些示例csv数据创建图形.存储在Cassandra和一些相同图形的遍历示例.会有很多帮助,因为没有可用的例子是可以理解的.

我有两个收藏。sources：

[
  {
    "_id": "0001",
    "name": "John Doe"
  },
  {
    "_id": "0002",
    "address": "123 Some Place"
  },
  {
    "_id": "0003",
    "phone": "5555555555"
  }
]

和connections：

[
  {
    "_id": "0001.0002",
    "_from": "0001",
    "_to": "0002",
    "probability": 0.8
  },
  {
    "_id": "0002.0003",
    "_from": "0002",
    "_to": "0003",
    "probability": 0.6
  }
]

我正在尝试进行图遍历$graphLookup以获取所有源连接的列表。这是我的代码：

[
  {
    "_id": "0001",
    "name": "John Doe"
  },
  {
    "_id": "0002",
    "address": "123 Some Place"
  },
  {
    "_id": "0003",
    "phone": "5555555555"
  }
]

这将返回destinations为空的数组。我希望它包含两个记录（0002和0003）。 …