标签: graph

这是一种更通用的问题,不是特定于语言的.更多关于使用的想法和算法.

系统如下:

它在朋友群之间登记小额贷款.Alice并且Bill要去吃午饭,比尔的卡不工作,所以爱丽丝支付他的餐费,10美元.
第二天Bill,Charles在火车站相遇,Chales没有钱买票,所以Bill买了一个,5美元.那天晚些时候从她和朋友那里Alice借了5美元Charles和1美元Bill购买礼物.

现在,假设他们都在系统中注册了这些事务,它看起来像这样:

Alice -> Bill $10
Bill -> Alice $1
Bill -> Charles $5
Charles -> Alice $5

所以,现在,唯一需要做的就是Bill给Alice4美元(他给了她1美元并将他的5 美元Charlie 转移到Alicealredy)并且他们处于初始状态.

如果我们将这个扩展到许多不同的人,拥有多个事务,那么获得尽可能少的事务的最佳算法是什么？

我有一个图表,其中包含未知数量的断开连接的子图.什么是一个好的算法(或Java库)来找到它们？

许多谓词定义了某种通过二元关系定义的边构建的非循环路径,与定义传递闭包非常相似.因此需要通用定义.

请注意,图论中定义的概念不容易与通常预期的匹配.最值得注意的是,我们对边缘的名称不感兴趣.

更糟糕的是,图论也发生了一些变化,引入了步行的概念,注意到了

传统上,路径指的是现在通常称为开放式步行的路径.如今,当没有任何限定地陈述时,路径通常被理解为简单,意味着没有重复顶点(因此没有边缘).(术语链也用于指代所有顶点和边缘都不同的步行.)

所以我的问题是:如何命名和定义此功能？

到目前为止我所做的是定义:

path(Rel_2, Path, X0,X)

第一个论点必须是关系的延续.然后是Path顶点或顶点.

用法示例

n(a, b).
n(b, c).
n(b, a).

?- path(n,Xs, a,X).
Xs = [a], X = a ;
Xs = [a, b], X = b ;
Xs = [a, b, c], X = c ;
false.

履行

:- meta_predicate path(2,?,?,?).

:- meta_predicate path(2,?,?,?,+).

path(R_2, [X0|Ys], X0,X) :-
   path(R_2, Ys, X0,X, [X0]).

path(_R_2, [], X,X, _).
path(R_2, [X1|Ys], X0,X, Xs) :-
   call(R_2, X0,X1),
   non_member(X1, Xs),
   path(R_2, …

我使用Chart.js库绘制条形图,它工作正常,但现在我想破坏条形图并在同一画布中制作折线图.我尝试过这两种方法来清除画布:

var grapharea = document.getElementById("barChart").getContext("2d");

grapharea.destroy();

var myNewChart = new Chart(grapharea, { type: 'radar', data: barData, options: barOptions });

第二种方式:

var grapharea = document.getElementById("barChart").getContext("2d");

grapharea.clear();

var myNewChart = new Chart(grapharea, { type: 'radar', data: barData, options: barOptions });

我称之为正确吗？OnButtonClick我调用这个使用相同画布的函数.

所以,这是我正在尝试的功能的一部分.

我不希望代码太复杂.

我有一个单词列表,例如

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

单词链序列的概念是下一个单词以最后一个单词结尾的字母开头.

(编辑:每个单词不能多次使用.除此之外没有其他限制.)

我希望输出给出最长的单词链序列,在这种情况下是:

['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

我不确定该怎么做,我尝试过不同的尝试.其中一个......

如果我们从列表中的特定单词开始,此代码正确地找到单词链,例如单词[0](所以'giraffe'):

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

word_chain = []

word_chain.append(words[0])

for word in words:
    for char in word[0]:

       if char == word_chain[-1][-1]:
            word_chain.append(word)

print(word_chain)

输出:

['giraffe', 'elephant', 'tiger', 'racoon']

但是,我想找到最长的单词链(如上所述).

我的方法:所以,我尝试使用我编写和循环的上述工作代码,使用列表中的每个单词作为起点,找到每个单词[0],单词[1],单词[2]的单词链然后我尝试通过使用if语句找到最长的单词链,并将长度与前一个最长的链进行比较,但我无法正确完成它,我真的不知道这是怎么回事.

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

word_chain = []
max_length = 0
for starting_word_index in range(len(words) - …

为什么BFS和DFS O(V + E)的运行时间,特别是当有一个节点具有可以从顶点到达的节点的有向边时,就像在以下站点中的此示例中一样

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

基本上,我遇到的问题是图例重叠了我试图绘制的gnuplot图,如下图所示.

以下是我用于绘制数据的命令.

> set log y
> plot "datafile1.txt" using 2:4 with lines,
  "datafile1.txt" using 2:6 with lines,
  "datafile2.txt" using 2:4 with lines,
  "datafile2.txt" using 2:6 with lines

以下是我用于绘制数据的数据文件1的一部分.

Dimension:  259 Timing: 36111 seconds,  9 seconds
Dimension:  260 Timing: 37860 seconds,  9 seconds
Dimension:  261 Timing: 39477 seconds,  6 seconds
Dimension:  262 Timing: 41215 seconds,  5 seconds
Dimension:  263 Timing: 41827 seconds,  5 seconds
Dimension:  264 Timing: 42738 seconds,  11 seconds
Dimension:  265 Timing: 42972 seconds,  14 seconds
Dimension:  266 …

请注意,图表表示为邻接列表.

我听说有两种方法可以在图表中找到一个循环:

1. 保留一个布尔值数组,以跟踪您之前是否访问过某个节点.如果你的新节点用完了(没有点击你已经存在的节点),那么只需回溯并尝试不同的分支.

2. 来自Cormen的CLRS或Skiena的那个:对于无向图中的深度优先搜索,有两种类型的边,树和背.当且仅当存在后沿时,该图具有循环.

有人可以解释一下图的后边缘是什么,以及上述两种方法之间的差异是什么.

谢谢.

更新: 这是在两种情况下检测周期的代码.Graph是一个简单的类,为了简单起见,将所有图形节点表示为唯一编号,每个节点都有其相邻的相邻节点(g.getAdjacentNodes(int)):

public class Graph {

  private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};

  public int[] getAdjacentNodes(int v) {
    return nodes[v];
  }

  // number of vertices in a graph
  public int vSize() {
    return nodes.length;
  }

}

用于检测无向图中的循环的Java代码:

    public class DFSCycle {

    private boolean marked[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    // s - starting node
    public DFSCycle(Graph g, int s) {
        this.g = g;
        this.s = …

是否有免费(如"欢呼"),与graphviz或其他图形的Linux兼容,交互式可视化编辑器？ aptitude好像在画一个空白.

编辑:"欢呼"意味着"啤酒"和"演讲". meta-edit:我想它应该是"像海滩一样自由".

编辑2:也许一个合适的svg编辑器将是一个更现实的目标.我基本上想要一些可以用来方便地创建标记形状和连接它们的线的集合.实际上,从这些数据中提取图形可能会更具理论意义,因为它包括语义数据(图形)和表示数据(它在屏幕上的排列方式,使用的颜色等).有没有办法用inkscape或其他一些免费的矢量图形编辑器方便地布置标记的形状？我真的需要重新排列节点,并且(重新)在其中流动文本,以最大的方便发生.

我也意识到这确实是一个超级用户的问题.当我找到一个似乎可能为我提供答案的现有问题时,我打算将它重新发布在那里:dia.

编辑3:dia似乎很有用,除了它似乎不可能以任何有用的方式(即除插入手动换行符之外的任何方式)获取节点对象的文本内容.这是一种交易破坏者,因为它破坏了大部分便利因素,这是我以这种方式做事的动机而不是文本编辑器或笔和纸.但是它支持某种事件模型和基于Python的脚本,所以我将稍微挖掘一下,看看我是否可以使用python来包装文本以响应内容更改.除非你们中的一个人有更好的想法..？基本上我想要通过GUI交互显式设置节点大小,并让内容换行和重新缩放(在一定的字体大小范围内)以适应它.富文本非常有用.

换句话说,这实际上是一个有效的SO问题,因为它似乎需要编码.

节点和顶点之间有什么区别(如果有的话)？看完无数的网站后我找不到答案!甚至我的书都没有指明它所以我有点迷茫!

值得一提的是,除了在图形中使用它被称为"顶点"而在树中使用时称为"节点"这一事实时,我正在寻找差异.