标准图API？ [英] Standard graph API?

问题描述

是否对（假设的）标准图API感兴趣（

''graph''表示网络，包括节点和边缘）？是的，我们

有通过（例如）dicts实现图形的标准方法

将节点映射到邻居集，但是如果想要一个图表''s

以其他方式实现，这可能不是最方便的（或

摘要）接口来模拟。拥有与DB-API相似的多态自由可能会很好。人们可以

总是开发工厂或适配器（例如用于PyProtocols）来自/ b
的dict-of-sets版本......


那么，有什么兴趣吗？或者我只是一个想要这个的孤独坚果？


-

马格努斯Lie Hetland罐头面包：切片以来最棒的东西
http://hetland.org bread！" [来自Spongebob Squarepants的罐子]

Is there any interest in a (hypothetical) standard graph API (with
''graph'' meaning a network, consisting of nodes and edges)? Yes, we
have the standard ways of implementing graphs through (e.g.) dicts
mapping nodes to neighbor-sets, but if one wants a graph that''s
implemented in some other way, this may not be the most convenient (or
abstract) interface to emulate. It might be nice to have the kind of
polymorphic freedom that one has with, e.g, with the DB-API. One could
always develop factories or adaptors (such as for PyProtocols) to/from
the dict-of-sets version...

So, any interest? Or am I just a lone nut in wanting this?

--
Magnus Lie Hetland "Canned Bread: The greatest thing since sliced
http://hetland.org bread!" [from a can in Spongebob Squarepants]

推荐答案

Magnus Lie Hetland< mlh< at> furu.idi.ntnu.no>写道：

Magnus Lie Hetland <mlh <at> furu.idi.ntnu.no> writes:

是否对（假设的）标准图API感兴趣（
''graph''表示网络，包括节点和边缘）？

Is there any interest in a (hypothetical) standard graph API (with
''graph'' meaning a network, consisting of nodes and edges)?

我现在不需要一个，但我知道我过去有几次。

对我来说当然是个好主意。我们现在已经有了内置设备，没有

因为我们不应该有一个简单的图形API，至少在库中。


史蒂夫

I don''t need one right now, but I know I have a few times in the past.
Certainly seems like a good idea to me. We''ve got sets as builtins now, no
reason we shouldn''t have a simple graph API, at least in the library.

Steve

Magnus Lie Hetland写道：

Magnus Lie Hetland wrote:

对（假设的）标准图形API有兴趣吗（含
''graph''表示网络，由节点和边缘组成）？是的，我们有通过（例如）dicts将节点映射到邻居集来实现图形的标准方法，但是如果想要一个以其他方式实现的图形，这可能不是最方便（或抽象）的模拟界面。拥有与数据库API一样的多态自由可能会很好。人们可以总是开发工厂或适配器（例如PyProtocols）到/来自版本的dict-of-sets版本......

那么，有什么兴趣吗？或者我只是一个想要这个的绝对坚果？

Is there any interest in a (hypothetical) standard graph API (with
''graph'' meaning a network, consisting of nodes and edges)? Yes, we
have the standard ways of implementing graphs through (e.g.) dicts
mapping nodes to neighbor-sets, but if one wants a graph that''s
implemented in some other way, this may not be the most convenient (or
abstract) interface to emulate. It might be nice to have the kind of
polymorphic freedom that one has with, e.g, with the DB-API. One could
always develop factories or adaptors (such as for PyProtocols) to/from
the dict-of-sets version...

So, any interest? Or am I just a lone nut in wanting this?

马格努斯，

知道我会很感激。它可用于配置

神经网络和逻辑网络;这个api会在哪里构建一个抽象然后编译。它可以更快地表示执行 - 或者只是在解释中运行

树/图表。模式。

我不认为它会得到很多用处，但使用

将是高端的。

wes

Magnus,
A know I''d appreciate it. It could be used to configure
neural nets and logic networks; where this api would make
it easy to build an abstraction then "compile" it into a
faster representation for execution - or just run the
tree/graph in "interpreted" mode.
I don''t think it would get a lot of use, but the use
would be high end.
wes

在文章< sl *************** @ furu.idi.ntnu.no>中，
ml*@furu.idi.ntnu.no （Magnus Lie Hetland）写道：

In article <sl***************@furu.idi.ntnu.no>,
ml*@furu.idi.ntnu.no (Magnus Lie Hetland) wrote:

是的，我们有标准的方法来实现图形（例如）
dicts将节点映射到邻居集，但是如果想要一个以其他方式实现的图形，这可能不是最方便的（或抽象的）模拟界面。

Yes, we have the standard ways of implementing graphs through (e.g.)
dicts mapping nodes to neighbor-sets, but if one wants a graph that''s
implemented in some other way, this may not be the most convenient
(or abstract) interface to emulate.

实际上，我对这种标准方式的解释是相当抽象的/>
接口，而不是特定的实例化，如dict-of-sets：

大多数时候，我只是要求iter（G）产生一系列的

图G的顶点，而iter（G [v]）产生一系列邻居

的顶点v。我也是有时使用v in G和在G [v]中的w测试

是否存在顶点或边缘。


这种方法的优点和缺点：


- 你可以使用列表而不是

表示的邻接列表部分中的集合。当

顶点度很小时，这可能会更快，更节省空间。


- 创建测试图很容易作为代码文字


G1 = {

0：[1,2,5]，

1：[0,5]，
2：[0,3,4]，

3：[2,4,5,6]，

4：[2,3， 5,6]，

5：[0,1,3,4]，

6：[3,4]，

}

G2 = {

0：[2,5]，

1：[3,8]，

2：[0,3,5]，

3：[1,2,6,8]，

4：[7]，

5：[0,2]，

6：[3,8]，

7：[4]，

8 ：[1,3,6]，

}


- 任何可索引对象都可以是顶点。顶点标识可以是对你的程序有意义的
。另一方面，这意味着

（除非你知道你的图表来自哪里）你不能依赖

顶点作为具有良好属性的特殊顶点对象你不能

使用像None这样的对象作为标志值，除非你确定它们不会是
顶点。


- 它没有提供一种改变图形的抽象方式（虽然如果G是例如套装的字典，那么'b $ b'相对容易）

- 它不直接代表多图


- 它不直接代表无向图（而是你必须

替换两个有向边缘的无向边缘，希望你的呼叫者

不要误给你一个有向图。）


- 没有表示边的显式对象，尽管你可以使用元组（v，w）或（对于无向边）创建一个集合。这个

在内存使用方面可以是一个优势，但在对象创建数量方面是个缺点。另外它意味着如果你想在边缘存储

信息，你必须使用由边缘索引的字典来代替边缘对象上的属性（可能更好的样式）无论如何

因为它可以防止同一图表上的不同算法与对方的属性相互碰撞

。


- -

David Eppstein

计算机科学系，大学加利福尼亚州，Irvine
http：//www.ics.uci。 edu /~eppstein /

Actually, my interpretation of this standard way is as a fairly abstract
interface, rather than a specific instantiation such as dict-of-sets:
Most of the time, I merely require that iter(G) produces a sequence of
the vertices of graph G, and iter(G[v]) produces a sequence of neighbors
of vertex v. I also sometimes use "v in G" and "w in G[v]" to test
existence of vertices or edges.

Pros and cons of this approach:

- You can use a list instead of a set in the adjacency list part of the
representation. This may be faster and more space efficient when the
vertex degrees are small.

- It''s easy to create test graphs as code literals

G1 = {
0: [1,2,5],
1: [0,5],
2: [0,3,4],
3: [2,4,5,6],
4: [2,3,5,6],
5: [0,1,3,4],
6: [3,4],
}
G2 = {
0: [2,5],
1: [3,8],
2: [0,3,5],
3: [1,2,6,8],
4: [7],
5: [0,2],
6: [3,8],
7: [4],
8: [1,3,6],
}

- Any indexable object can be a vertex. The vertex identities can be
something meaningful to your program. On the other hand, that means
(unless you know where your graph came from) you can''t rely on the
vertices being special vertex objects with nice properties and you can''t
use objects like None as flag values unless you''re sure they won''t be
vertices.

- It doesn''t provide an abstract way of changing the graph (although
that''s relatively easy if G is e.g. a dict of sets)

- It doesn''t directly represent multigraphs

- It doesn''t directly represent undirected graphs (instead you have to
replace an undirected edge by two directed edges and hope your callers
don''t give you a directed graph by mistake).

- There isn''t an explicit object representing an edge, although you can
create one by using a tuple (v,w) or (for undirected edges) a set. This
can be an advantage in terms of memory usage but a disadvantage in terms
of number of object creations. Also it means that if you want to store
information on the edges you have to use a dict indexed by the edge
instead of attributes on an edge object (probably better style anyway
since it prevents different algorithms on the same graph from colliding
with each other''s attributes).

--
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/

这篇关于标准图API？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！