标签: directed-graph

我正在寻找一种在PHP中绘制有向图的方法.(如http://upload.wikimedia.org/wikipedia/commons/0/08/Directed_acyclic_graph.png).我希望它能像GD一样输出图像来创建图形图像.

我在这上面搜索了很多,但我只能找到很多用于绘制图形的库(带条等),而不是有向图.

PS我试过通过system()使用dot(linux程序),但不幸的是我没有权限在服务器上这样做.此外,我没有权利在服务器上安装PHP扩展和类似的东西,所以它应该使用普通的PHP(理想情况下只包括一个文件).

提前致谢.

这就是生成的图形当前的外观: 以下是此代码:

  digraph {
  rankdir=TB;
  subgraph cluster01 {
    label="1.fázis"

    aSTART;
    node [shape = doublecircle]; a001; 
    node [shape = ellipse];

    aSTART -> a0 [ penwidth = 3 label = "0" ];
    a0 -> a00 [ penwidth = 3 label = "0" ];  
    a00 -> a001 [ penwidth = 3 label = "1" ];


    a0 -> aSTART [ label = "1" ];  
    a00 -> a00 [ label = "0" ];  
    a001 -> a0 [ label = "0"];
    a001 -> aSTART [ label …

我想实现一个函数,该函数在有向循环图G中找到来自源顶点V的所有可能顶点的所有可能路径.

性能现在没关系,我只是想了解算法.我已经阅读了深度优先搜索算法的定义,但我并不完全理解该怎么做.

我没有在这里提供任何完整的代码,因为我不知道如何:

• 存储结果(连同A-> B-> C->我们还应该存储A-> B和A-> B-> C);
• 代表图(有向图？元组列表？);
• 要使用多少递归(处理每个相邻的顶点？).

如何在Erlang中的有向循环图中找到形成一个给定源顶点的所有可能路径？

UPD:基于到目前为止的答案,我必须重新定义图形定义:它是一个非非循环图形.我知道如果我的递归函数遇到一个循环,它就是一个无限循环.为了避免这种情况,我可以检查当前顶点是否在结果路径的列表中 - 如果是,我停止遍历并返回路径.

UPD2:感谢发人深省的评论!是的,我需要找到所有简单路径,这些路径没有从一个源顶点到所有其他源的循环.

在这样的图表中:

使用源顶点A算法应找到以下路径:

• A,B
• A,B,C
• A B C D
• 广告
• A,d,C
• A,d,C,B

下面的代码完成了这项工作,但是对于具有更多20个顶点的图形它是不可用的(我猜它是递归错误的东西 - 占用太多内存,永远不会结束):

dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
            dfs(Neighbours,[Source],[],Graph,Source),
ok.


dfs([],Paths,Result,_Graph,Source) ->
    ?DBG("There are no more neighbours left for vertex ~w~n", [Source]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source) ->
    ?DBG("///The neighbour to check is ~w, other neighbours are: ~w~n",[Neighbour,Other_neighbours]),
    ?DBG("***Current result: ~w~n",[Result]),
    New_result = …

我想使用Jackson 2.3.3进行有向图的反序列化/序列化.我想出的结构大致如下:

public Class Graph {
    private final Set<Node> nodes;
    public Graph(Set<Node> nodes) { ... }
    public Set<Node> getNodes() { ... }
}

@JsonIdentityInfo(
        generator = ObjectIdGenerators.PropertyGenerator.class,
        property = "name")
public Class Node {
    private final String name;
    private final Set<Edge> edges;
    public Node(String name, Set<Edge> edges) { ... }
    public String getName() { ... }
    public Set<Edge> getEdges() { ... }
}

@JsonIdentityInfo(
        generator = ObjectIdGenerators.PropertyGenerator.class,
        property = "name")
public Class Edge {
    private final String name;
    private final …

我很困惑,我非常感谢一些帮助.我目前正在学习算法,但我不知道从哪里开始.

我最近得到了代码(我们只是真的完成了理论,所以看到代码让我害怕我的核心)我已经被赋予了修改这段代码的任务,从文本文件中获取细节并将其放在图表中.文本文件与此类似.

Trout is-a fish
Fish has gills
Fish has fins
Fish is food
Fish is-an animal

在那里还有更多.我只是想知道.我怎么开始这整件事？我有一百万个问题要问,但是如果我知道如何使用文本文件分配顶点,我觉得我可以解决这些问题？我提供的代码和必须编辑的代码如下.任何帮助都会很棒,如果你愿意,只需向正确的方向努力.

(另外,在addEdge类中,重要的是什么？我知道它是遍历边缘的"成本",但我如何分配权重？)

谢谢!

public class Graph {
    private final int MAX_VERTS = 20;
    private final int INFINITY = 1000000;
    private Vertex vertexList[]; // list of vertices
    private int adjMat[][]; // adjacency matrix
    private int nVerts; // current number of vertices
    private int nTree; // number of verts in tree
    private DistPar sPath[]; // array for shortest-path data
    private int currentVert; // current vertex …

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

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

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

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

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

考虑从第一个节点1到一些最终节点(没有更多的外边缘)遍历的有向图.图中的每条边都有与之相关的概率.总结将所有可能的最终节点返回的每条可能路径的概率1.(这意味着,我们保证最终到达最终节点之一.)

如果图中的循环不存在,问题将很简单.不幸的是,在图中可能出现相当复杂的循环,其可以遍历无限次(概率随着每次循环遍历而成倍增加,显然).

是否有通用算法来找到到达每个最终节点的概率？

一个特别令人讨厌的例子:

我们可以将边表示为矩阵(从行(节点)x到行(节点)的概率y在条目中(x,y))

{{0, 1/2, 0, 1/14, 1/14, 0, 5/14}, 
 {0, 0, 1/9, 1/2, 0, 7/18, 0}, 
 {1/8, 7/16, 0, 3/16, 1/8, 0, 1/8}, 
 {0, 1, 0, 0, 0, 0, 0}, 
 {0, 0, 0, 0, 0, 0, 0}, 
 {0, 0, 0, 0, 0, 0, 0}, 
 {0, 0, 0, 0, 0, 0, 0}}

或者作为有向图:

起始节点1为蓝色,最终节点5,6,7为绿色.所有边缘都标记为从它们始发的节点开始时遍历它们的概率.

这有从起始节点1到最终节点的八条不同路径:

{{1/14, {1, 5}}, {5/14, {1, 7}}, {7/36, …

我尝试使用以下代码来绘制 的度分布networkx.DiGraph G：

def plot_degree_In(G):
    in_degrees = G.in_degree()
    in_degrees=dict(in_degrees)
    in_values = sorted(set(in_degrees.values()))
    in_hist = [list(in_degrees.values()).count(x) for x in in_values]

    plt.figure() 
    plt.grid(False)
    plt.loglog(in_values, in_hist, 'r.') 
    #plt.loglog(out_values, out_hist, 'b.') 
    #plt.legend(['In-degree', 'Out-degree'])
    plt.xlabel('k')
    plt.ylabel('p(k)')
    plt.title('Degree Distribution')
    plt.xlim([0, 2*100**1])

但后来我意识到这不是正确的做法，所以我将其更改为：

def plot_degree_dist(G):
    degree_hist = nx.degree_histogram(G) 
    degree_hist = np.array(degree_hist, dtype=float)
    degree_prob = degree_hist/G.number_of_nodes()
    plt.loglog(np.arange(degree_prob.shape[0]),degree_prob,'b.')
    plt.xlabel('k')
    plt.ylabel('p(k)')
    plt.title('Degree Distribution')
    plt.show()

但这给了我一个没有数据的空图。

我正在尝试为客户状态迁移制作有向图或桑基图（任何都可以）。数据如下所示，count 表示从当前状态迁移到下一个状态的用户数。

**current_state         next_state          count**
New Profile              Initiated           37715
Profile Initiated          End               36411
JobRecommended             End                6202
New                        End                6171
ProfileCreated             JobRecommended     5799
Profile Initiated          ProfileCreated     4360
New                        NotOpted           3751
NotOpted                   Profile Initiated  2817
JobRecommended             InterestedInJob    2542
IntentDetected             ProfileCreated     2334
ProfileCreated             IntentDetected     1839
InterestedInJob            Applied            1671
JobRecommended             NotInterestedInJob 1477
NotInterestedInJob         ProfileCreated     1408
IntentDetected             End                1325
NotOpted                   End                1009
InterestedInJob            ProfileCreated     975
Applied                    IntentDetected     912
NotInterestedInJob         IntentDetected     720
Applied                    ProfileCreated     701
InterestedInJob            End                673

我编写了一个构建 sankey 的代码，但该图不易阅读。寻找可读的有向图。这是我的代码：

    df = pd.read_csv('input.csv')

    x = …

这可能与功能数据结构有关，但我没有找到有关此主题的标签。

假设我有一个语法树类型Tree，它通过简单地共享公共子表达式来组织为 DAG。例如，

data Tree = Val Int | Plus Tree Tree

example :: Tree
example = let x = Val 42 in Plus x x

然后，在这个语法树类型上，我有一个纯函数simplify :: Tree -> Tree，当给定 a 的根节点时，它Tree通过首先简化该根节点的子节点来简化整个树，然后处理根节点本身的操作。

由于simplify是纯函数，并且某些节点是共享的，因此我们希望不会simplify在这些共享节点上多次调用。

问题来了。整个数据结构是不变的，共享对程序员是透明的，因此似乎无法确定两个节点是否实际上是同一个节点。

在处理所谓的“打结”结构时也会出现同样的问题。通过打结，我们为原本无限的数据结构生成了有限的数据表示，例如let xs = 1 : xs in xs。这里xs本身是有限的，但调用map succ它并不一定会产生有限的表示。

这些问题可以归结为：当数据被组织在一个不变的有向图中时，我们如何避免重新访问同一个节点，做重复的工作，甚至在图恰好是循环的时候导致不终止？

我想到的一些想法：

1. 将Tree类型扩展为Tree a，使每个节点都拥有一个额外的a. 生成图形时，将每个节点与一个唯一a值相关联。尽管垃圾收集器可能随时移动任何堆对象，但内存地址应该在这里有效。
2. 对于语法树示例，我们可能会STRef (Maybe Tree)在简化版本的每个节点中存储 …