3

这是一个设计问题。我正在努力为我面临的问题创建一个概念模型。

我有许多对象（<1000）的图表。这些对象以多种方式连接在一起。这些对象中的每一个都有一些属性。

我需要能够通过它们的连接和属性访问这些对象。

例如，让我们假设以下对象 -

{name: A, attributes:{black, thin, invalid}, connections: {B,C}} 
{name: B, attributes:{white, thin, valid}, connections: {A}} 
{name: C, attributes:{black, thick, invalid}, connections: {A,B}}

现在我应该能够通过以下方式查询此图 - 使用属性 -

black - yields [A,C]
black.thick - yields C

使用连接 -

A.connections[0].connections[0] - yields A

使用它们的组合 -

black[0].connections[0] - yields B

我的主要语言是Java。但我不认为 Java 能够处理这些类型的野兽。因此，我试图用像 Python 这样的动态语言来实现它。我还考虑过使用像 OGNL 或图形数据库这样的表达式语言评估。但我很困惑。我对编码解决方案不感兴趣。但是，对此类问题进行建模的正确方法是什么？

4

4 回答 4

1

听起来您有一些想要以不同方式查询的对象模型。一种解决方案是使用 Java 创建模型，然后使用脚本语言支持以不同方式查询此模型。例如：Java + Groovy 是我的推荐。

您可以为模型使用以下 Java 类。

public class Node {

    private String name;
    private final Set<String> attributes = new HashSet<String>();
    private final List<Node> connections = new ArrayList<Node>();

    // getter / setter for all
}

然后，您应该使用正确填充的“连接”属性填充此类对象的列表。

要支持不同类型的脚本，您需要为脚本创建一个上下文，然后填充此上下文。上下文基本上是一张地图。映射的键成为脚本可用的变量。诀窍是填充此上下文以支持您的查询要求。

例如，在 groovy 中，绑定是上下文（请参阅http://groovy.codehaus.org/Embedding+Groovy）。因此，如果您按照以下方式填充它，您的查询需求将得到满足

上下文/绑定映射

1. <Node name(String), Node object instance(Node)>
2. <Attribute name(String), list of nodes having this attribute(List<Node>)>

当您评估说“A.connections [0]”的脚本时，将在绑定中查找针对键“A”存储的对象。然后将访问返回的对象“连接”属性。由于这是一个列表，因此在 groovy 中允许使用 '[0]' 语法。这将返回索引 0 处的对象。同样，为了支持您的查询要求，您需要填充上下文。

于 2013-07-01T16:39:31.403 回答
0

这取决于你希望你的表现在哪里。

如果您想要快速查询，并且在添加对象时不介意额外的时间/内存，则保留指向具有特定属性的对象的指针数组/列表可能是一个好主意（特别是如果您在设计时知道什么可能的属性可能是）。然后，当添加一个新对象时，说： 

{name: A, attributes:{black, thin, invalid}, connections: {B,C}}

添加指向black列表、thin列表和invalid列表的新指针。对连接的快速查询可能需要将指针列表/数组作为object类的成员。然后，当您创建对象时，为正确的对象添加指针。

如果您不介意较慢的查询并希望在添加对象时优化性能，则链表可能是更好的方法。您可以遍历所有对象，检查每个对象是否满足查询条件。

在这种情况下，保留连接的成员指针仍然是一个好主意，如果（正如您的问题似乎表明的那样）您正在寻找进行多级查询（即A.connections[0].connections[0]。这将导致性能极差，如果通过嵌套循环完成。）

希望这会有所帮助，这实际上取决于您希望最常调用的查询类型。

于 2013-07-01T16:38:22.120 回答
0

用 Java 表达这一点没有问题。只需定义代表节点集的类。假设有一组固定的属性，它可能如下所示：

enum Attribute {
    BLACK, WHITE, THIN, VALID /* etc. */ ;
}
class Node {
    public final String name;
    public final EnumSet<Attribute> attrs
        = EnumSet.noneOf(Attribute.class);
    public final NodeSet connections
        = new NodeSet();

    public Node(String name)
    {
        this.name = name;
    }

    // ... methods for adding attributes and connections
}

然后是代表一组节点的类：

class NodeSet extends LinkedHashSet<Node> {
    /**
     * Filters out nodes with at least one of the attributes.
     */
    public NodeSet with(Attribute... as) {
        NodeSet out = new NodeSet();
        for(Node n : this) {
            for(a : as)
                if (n.attrs.contains(a)) {
                    out.add(n);
                    break;
                }
        }
        return out;
    }

    /**
     * Returns all nodes connected to this set.
     */
    public NodeSet connections() {
        NodeSet out = new NodeSet();
        for(Node n : this)
            out.addAll(n.connections);
        return out;
    }

    /**
     * Returns the first node in the set.
     */
    public Node first() {
        return iterator().next();
    }
}

（我没有检查代码是否编译，它只是一个草图。）然后，假设你有一个NodeSet all所有节点，你可以做类似的事情

all.with(BLACK).first().connections()
于 2013-07-01T16:38:46.620 回答
0

我认为用图表解决这个问题是有道理的。您提到了使用图形数据库的可能性，我认为它可以让您更好地专注于您的问题，而不是编码基础设施。像TinkerPop项目中的TinkerGraph这样的简单内存图将是一个不错的起点。

通过使用 TinkerGraph，您可以访问一种称为Gremlin的查询语言（另请参阅GremlinDocs），它可以帮助回答您在帖子中提出的问题。这是REPL中的一个 Gremlin 会话，它展示了如何构建您呈现的图形以及一些生成您想要的答案的示例图形遍历......这第一部分简单地构造了给出您的示例的图形：

gremlin> g = new TinkerGraph()
==>tinkergraph[vertices:0 edges:0]
gremlin> a = g.addVertex("A",['color':'black','width':'thin','status':'invalid']) 
==>v[A]
gremlin> b = g.addVertex("B",['color':'white','width':'thin','status':'valid'])  
==>v[B]
gremlin> c = g.addVertex("C",['color':'black','width':'thick','status':'invalid'])
==>v[C]
gremlin> a.addEdge('connection',b)                                                
==>e[0][A-connection->B]
gremlin> a.addEdge('connection',c)                                                
==>e[1][A-connection->C]
gremlin> b.addEdge('connection',a)                                                
==>e[2][B-connection->A]
gremlin> c.addEdge('connection',a)                                                
==>e[3][C-connection->A]
gremlin> c.addEdge('connection',b)                                                
==>e[4][C-connection->B]

现在查询：

// black - yields [A,C]
gremlin> g.V.has('color','black')
==>v[A]
==>v[C]

// black.thick - yields C
gremlin> g.V.has('width','thick')
==>v[C]

// A.connections[0].connections[0] - yields A
gremlin> a.out.out[0]
==>v[A]

// black[0].connections[0] - yields B
gremlin> g.V.has('color','black')[0].out[0]
==>v[B]

虽然如果您不熟悉堆栈，这种方法确实会引入一些学习曲线，但我认为您会发现图表适合作为许多问题的解决方案，并且对 TinkerPop 堆栈有一些经验通常会对您遇到的其他场景有所帮助。

于 2013-07-01T18:28:39.523 回答