标签: directed-graph

Erlang有向图模块通过改变状态让我感到惊讶.

在Erlang中处理其他数据结构模块时,例如sets模块,传入的数据结构的实例是未修改的.该函数返回一个新的,更改的版本,例如

>S = sets:new().
>sets:size(S).
0
>T = sets:add_element(S, "element").
>sets:size(S).
0
>sets:size(T).
1

这不是处理有向图模块时的行为.

>G = digraph:new().
>digraph:no_vertices(G).
0
>digraph:add_vertex(G, "vertex").
>digraph:no_vertices(G).
1

首先,为什么有向图库在这方面有所不同？

其次,更重要的是,digraph模块如何针对现有绑定添加新状态？

我假设状态存储在另一个进程中,digraph模块使用现有的和未改变的绑定G进行识别.是这种情况吗？或者是否有其他方法可以修改与绑定相关联的状态？

我们得到一个图表,其中包含以下事实:

edge(a,b)
edge(a,c)
edge(b,a)
edge(c,d)
edge(d,d)
edge(d,e)
edge(e,f)
edge(f,g)
edge(g,e)

我们被要求定义一个规则,cycle(X)确定是否存在从节点开始的循环X.

我真的迷失了如何做到这一点,我试图遍历节点并检查下一个节点是否会再次成为起始节点,但我似乎无法让它工作

我必须为SVG有向图添加一些交互功能.

到目前为止,我想要显示的图表是从点文件生成并呈现为SVG.我想知道是否有一些简单的方法可以为这样的SVG文档添加交互性(可能使用Javascript).

我需要的是当鼠标越过一个节点时显示一些信息,并可以比较两个节点.

由于我的模型是自动生成的,我宁愿保留点生成的SVG,并使用单独的Javascript添加其他信息.

我正在为我正在使用的数据结构寻找数学形式,以便我可以找到相关的定理和算法.

假设您有以下内容:

• 主题的有向无环图.
• 在每个主题中,主题,一组文档中的项目和一组组中的项目之间存在一个或多个关系.
• 这些组可能是一个简单的集合,也可能最终成为DAG.它们用于管理文档与主题的关联的可见性.

直到最近我才遇到超图,这些超图似乎相关但过于笼统.这个数据结构有形式吗？如果没有,可以用数学术语更简洁地描述它吗？

来自维基百科的伪代码:

function Dijkstra(Graph, source):
 2      for each vertex v in Graph:                                // Initializations
 3          dist[v] := infinity ;                                  // Unknown distance function from source to v
 4          previous[v] := undefined ;                             // Previous node in optimal path from source
 5      end for ;
 6      dist[source] := 0 ;                                        // Distance from source to source
 7      Q := the set of all nodes in Graph ;                       // All nodes in the graph are unoptimized - thus are in Q
 8      while …

是否有一个已经实现的数据结构,我可以使用它来分配给一个对象(在我的情况下是一个Edge),一个整数？我正在从一个文件,10密耳顶点,60密耳边缘读取图形,并使用地图(cost.put(e,cost))为每个边缘分配成本.

我以这种方式创建成本图:

costs = new HashMap<Edge,Integer>();

它给出的例外是:

java.lang.OutOfMemoryError: Java heap space
    at java.util.HashMap.resize(Unknown Source)
    at java.util.HashMap.addEntry(Unknown Source)
    at java.util.HashMap.put(Unknown Source) 

我试图在Graphviz中创建一个图例/键,其中不仅包含文本,还包含节点和边.虽然我已经阅读过这篇文章,但HTML表格似乎与我正在尝试的内容无关.

现在,我使用的代码是:

digraph G {
fontname="Helvetica";
labelloc=t;
rankdir=LR;
label="Course Graph";

node[style=filled, fontname="Helvetica", colorscheme=greens3, color=1];

subgraph cluster_key {
    rank=min;

    label="Key";
    rankdir=LR;

    kc1[label="Course", peripheries=2, color=2];
    k1[shape=plaintext, style=solid, label="Required Course"]
    prereq[label="Course 1"];
    kc2[label="Course 2"];
    prereq->kc2;
    k2[shape=plaintext, style=solid, label="Course 1 is a prerequisite for Course 2"]
    coreq1[label="Course 1"];
    coreq2[label="Course 2"];
    coreq1->coreq2[dir=both];
    k3[shape=plaintext, style=solid, label="Course 1 and Course 2 are corequisite"]

    or[style="dashed", color="black", shape="diamond", label="OR"];
    or1[label="Course 1"];
    or1 -> or[style="dashed", dir="none"];
    or2[label="Course 2"];
    or2 -> or[style="dashed", dir="none"];
    kc3[label="Course 3"]
    or->kc3;
    k4[shape=plaintext, style=solid, label="You …

WITH RECURSIVE我是PostgreSQL 的新手。我有一个相当标准的递归查询，它遵循邻接列表。如果我有，例如：

1 -> 2
2 -> 3
3 -> 4
3 -> 5
5 -> 6

它产生：

1
1,2
1,2,3
1,2,3,4
1,2,3,5
1,2,3,5,6

我想要的是：

1,2,3,4
1,2,3,5,6

但我不知道如何在 Postgres 中做到这一点。这似乎是“选择最长的路径”或“选择不包含在另一条路径中的路径”。我也许可以看到如何通过连接本身来做到这一点，但这似乎效率很低。

一个示例查询是：

WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (
   SELECT g.id, g.link, g.data, 1, ARRAY[g.id], false
   FROM graph g
  UNION ALL
   SELECT g.id, g.link, g.data, sg.depth + 1, path || g.id, g.id = ANY(path)
   FROM graph g, search_graph sg
   WHERE g.id = sg.link AND NOT cycle …

我有一个有向无环图和该图中的原点顶点v。
我怎样才能访问所有可以从 到达的顶点v，这样如果我访问v1我已经访问了所有具有 和 边的顶点v1？

例子：

/-----V
A->B->C

从 开始A，C必须访问之后B。
我尝试只进行 BFS 并检查每个顶点的父级，如果没有访问它们，则重新添加它以供以后使用，但事实证明这太慢了，我相信可以O(v^2)。

了解该图在某种程度上是二元的可能会有所帮助，每个顶点最多将由两个顶点指向。在另一个方向上，每个顶点都指向很多顶点。

我想生成一个有向图,其中包含指定数量的周期及其各自的长度.例如,图表应包含:

2 cycles of the size 3 
1 cycle of the size 5

• 这样的算法是否已经存在？如果没有,那么解决这个问题的方法是什么？详细地,给出以下参数:

  1. 顶点的数量(例如,15)
  2. 组件数量(例如2)
  3. 必须在图中的循环(例如,{3循环,3循环,5循环})

• 我只发现了几种能够检测现有图形中循环的算法(例如,Tarjan).您是否认为可以使用循环检测算法生成具有特定循环量的图形？