标签: directed-graph

使用点有向图语言,是否可以创建具有不同rankdir的子图？

我尝试了以下,但没有奏效.尽管子图中存在rankdir ="TB",但两个图都是从左到右.

digraph g {
    rankdir="LR";
    LEFT->RIGHT;
    clusterrank="local";

    subgraph cluster1 { 
        rankdir="TB";    
        node[style=filled];         
        color=black;
        TOP->BOTTOM;                
    }   
}

是否有其他语法可以在同一个图表中获得上/下和左/右图,或者这是不可能的？

我可以轻松地为有向图的节点定义数据类型.

data Node = Node String [Node] derving (Show, Read)

我可以使用show函数将图形保存到文件中,然后使用read恢复它.但是,节目不会应付一个周期.是否有一种保存和恢复图形的简单方法？

我需要在google appengine中存储一个大而动态的无向图,这是最好的方法吗？图形表示必须能够支持快速拉出一组顶点(用于在页面上渲染)和来自特定顶点的所有链接,以及跨图形的路径寻找(尽管最佳路径并不是真正需要的,只是一个公平的好的一个)

我对这个主题的看法:最明显的方法是有一个顶点模型和一个引用两个顶点的边缘模型,但听起来它最终会为每个操作使用大量的查询,我想知道是否有一种更好的方法(可能以某种方式将链接信息构建到每个顶点)

给定一个在有向图中保持边的表,如下所示:

CREATE TABLE edges ( 
    from_here int not null, 
    to_there  int not null
)

获取特定节点的不同无向链接数量的最佳方法是什么？没有任何重复的有向边,也没有任何节点直接链接到它们自己,我只是想避免计算重复的无向边(例如(1,2)和(2,1))两次.

这有效,但NOT IN闻起来对我不好:

SELECT COUNT(*)
FROM edges
WHERE from_here = 1
   OR (to_there = 1 AND from_here NOT IN (
        SELECT to_there 
        FROM edges 
        WHERE from_here = 1
   ))

PostgreSQL特定的解决方案对此很好.

对于我的论文,我需要绘制一些概率控制流程图.即控制流程图,边缘上描绘的概率.

我发现图形工具看起来非常有用,因为它可以使用现有图形的深层复制,我的图形非常相似.

所以我的问题是,如果有可能在边缘上/旁边绘制边缘属性(或一些字符串)？如果它不可能或非常复杂,那么在这种情况下是否有更好的工具？

编辑: 我需要有向边,甚至可以在2个节点之间创建循环并具有不同的值.这也有可能吗？所以我可以看到两个值？到现在为止,我可以看到带有双向边的有向图,但它只有一个值.

因此,例如在networkx中(参考Hooked),它看起来像:

G = nx.MultiDiGraph()
G.add_edge(0,1)
G.add_edge(1,0)
labels = {(0,1):'foo', (1,0):'bar'}

这样'foo'和'bar'都可见,你可以看到它们连接的方向.

但是当networkx呈现它时,我得到1个带有1个标签的双向边缘.

我有一个有向图(N, A),每个节点n[i]都有一个值v[i]和一个阈值t[i].对于每个箭头(n[i], n[j]),不变量v[i] <= v[j]成立.我需要有效地实现以下操作:

• increaseThreshold(i, x):设置t[i] = max(t[i], x).这是微不足道的,只是为了完整性.
• increaseValue(i, x):v[i] = max(v[i], x)根据需要设置和增加其他值,以便保持上述不变量.
• evaluate(i):如果返回true v[i] < t[i]

最简单的实现将存储v[i],t[i]以及每个节点的传出箭头.在increaseValue(i, x),它会沿着所有传出箭头传播值(使用一组"开放"节点,就像许多其他图形算法一样).v[i]与每个节点一起存储,evaluate(i)是微不足道的.

由于increaseValue比其他操作更频繁,这种急切的方法似乎是浪费.所以我想知道,如果v[i]根据需要重新计算一些惰性传播可能会更有效.对于这一点,我想保持w[i]作为最大的是x来自increaseValue(i, x)和计算v[j]时的飞行evaluate(j)需要它.它可以计算为有路径的w[i]所有节点的最大值.实际上,一旦我知道,确切的值无关紧要,我可以停止计算.n[i]n[j]v[j] >= t[j]v[j]

不幸的是,这种惰性算法的效率非常低,因此即使increaseValue频率高于数量级,它也不会得到回报evaluate.

我想,一些"部分懒惰"的算法可能会更好,但这只是我的直觉,我无法用它取得任何进展. …

我需要回答这个问题:给定一个依赖图中的节点,通过它们自己的传递依赖对其依赖者进行分组,这些依赖会受特定的起始节点的影响.

换句话说,给定依赖图中的节点,找到直接依赖的集合的集合,其直接依赖于从该特定起始节点导出的公共依赖.

例如,给出伪代码:

let a = 1
let b = 2
let c = a + b
let d = a + b
let e = a
let f = a + e
let g = c + d

你可以计算这个图:

如果我们用作a起始节点,我们可以看到a两者的依赖性,c并且d具有依赖性g.并且f有依赖e和a.

请注意,a根本没有任何影响b,因此在决定如何对依赖者进行分组时不应将其考虑在内a.

使用a作为起始节点,我们想要获得这些分组的依赖集:

groups = {{c, d}, {e, f}}

c并且d具有直接或传递的下游关系,并且e也 …

我想使用看起来很棒的GraphSharp库,但该项目没有文档.

具体来说,我对使用布局引擎感兴趣,对WPF控件不感兴趣.我只想计算给定图形和布局算法的布局(节点的位置).

有没有人有任何关于如何使用GraphSharp的建议,提示和链接.

我有一些列表中包含可变数量的元素.每个列表都已排序,但排序算法未知.我想将列表合并到一个大列表中,该列表包含相同顺序的所有列表,没有重复.

示例输入:

1. XS,M,L,XL
2. S,M,XXL
3. XXS,XS,S,L

预期结果:

• XXS,XS,S,M,L,XL,XXL

通过匹配输入序列来获得预期结果,以便以正确的顺序获得包含每个输入序列的元素的合并结果,如下所示:

    XS   M L XL
       S M      XXL
XXS XS S   L
-------------------
XXS XS S M L XL XXL

如果存在具有不明确位置的元素,则该函数应通知.在这里,它将是XXL(它可以保持在M,L或XL之后)并且我需要在XL之后手动指定其位置(因为在这里我知道排序算法并且可以帮助).我想要定义每两个元素的对,每个元素按照原始列表的顺序排列.从这个可以建立完整的列表.

我需要存储有向图(不一定是非循环的),以便尽可能快地删除节点.我不介意存储额外的数据,以便确切地知道删除节点时必须经过哪些边缘.

如果我存储边缘列表(作为节点索引对),那么当杀死某个节点时,我必须在整个列表中搜索源或目标为n的边.这对我的申请来说太贵了.通过在节点中存储一些额外的数据可以避免这种搜索吗？

一个想法是让每个节点存储自己的源和目标,作为两个单独的列表.当节点n被杀死时,它的列表也被杀死.但是,与节点n相关联的所有目标/来源如何知道更新自己的列表(即,从列表中消除已解散的节点)？这需要一些昂贵的搜索......

可以避免吗？

谢谢.