这是为什么大多数图算法不能轻易适应负数的后续问题？.
我认为Shortest Path(SP)在负权重方面存在问题,因为它会沿着路径累加所有权重并尝试找到最小权重.
但我不认为最小生成树(MST)存在负权重问题,因为它只需要单个最小权重边缘而不关心总权重.
我对吗？
我编写了一个递归DFS算法来遍历图:
void Graph<E, N>::DFS(Node n)
{
std::cout << ReadNode(n) << " ";
MarkVisited(n);
NodeList adjnodes = Adjacent(n);
NodeList::position pos = adjnodes.FirstPosition();
while(!adjnodes.End(pos))
{
Node adj = adjnodes.ReadList(pos);
if(!IsMarked(adj))
DFS(adj);
pos = adjnodes.NextPosition(pos);
}
}
然后我用堆栈编写了迭代DFS算法:
template <typename E, typename N>
void Graph<E, N>::IterativeDFS(Node n)
{
Stack<Node> stack;
stack.Push(n);
while(!stack.IsEmpty())
{
Node u = stack.Read();
stack.Pop();
if(!IsMarked(u))
{
std::cout << ReadNode(u) << " ";
MarkVisited(u);
NodeList adjnodes = Adjacent(u);
NodeList::position pos = adjnodes.FirstPosition();
while(!adjnodes.End(pos))
{
stack.Push(adjnodes.ReadList(pos));
pos = adjnodes.NextPosition(pos);
}
} …我注意到一个反复出现的问题是:"什么是语言X的良好网络图库".我和很多图书馆一起玩过,我可以与你分享我的经历.
Python: NetworkX是一个强大的库,它具有内置的可视化功能,但也有一个使用pyGraphviz的Graphviz接口.(pyGraphviz和NetworkX由同一作者撰写).NetworkX是开源的,非常容易使用.
Perl: 开发Circos可视化基因组和其他高度复杂的数据集.它将始终使用圆形布局,但如果您的网络非常大并且其"模块化"分数较低,则它通常是最合适的布局.Circos是开源的.
.Net: NodeXL由Microsoft Research开发,既是Excel的附加组件,也是.Net 3.5库的附加组件.它非常开放(对于微软的标准)并使用Fruchterman-Reingold算法进行可视化.
Java: JUNG2最近发布,也是一个强大的库.具有扩展的可视化和关键指标支持.JUNG2是开源的.
UbiGraph: UbiGraph具有与不同语言的接口,包括Python(和NetworkX具有UbiGraph支持),Ruby,PHP,Java,C,C++,C#,Haskell和OCaml.它使用XML-RPC服务器对网络图进行非常简洁的三维可视化.基本版本是免费的,您必须支付专业版.
独立: 您可以随时使用的现成的货架包,如:Graphviz的(赢,Linux和OSX),Pajek(胜),UCINET(胜),甚至Visio中(胜).
我相信还有更多的软件包,但这些是我自己使用的软件包.还有哪些其他库或包？
我想知道在c ++中快速编写图形的实现.我需要数据结构易于操作和使用图形算法(例如BFS,DFS,Kruskal,Dijkstra ......).我需要这个实现的算法Olympiad,所以更容易编写数据结构更好.
你能建议这样的DS(主要结构或类别以及将在其中的内容).我知道邻接列表和邻接矩阵是主要的可能性,但我的意思是更详细的代码示例.
例如,上次我必须为DFS实现图形时,我想到了这个DS:
struct Edge {
int start;
int end;
struct Edge* nextEdge;
}
然后使用一个大小为n的数组,在第i个位置包含表示从第i个节点开始的边的边缘列表(struct Edge).
但是当在这个图上尝试DFS时,我不得不用大约10个while循环编写50行代码.
有什么'好'的实施？
在使用方面,动态编程和贪婪方法之间的主要区别是什么？
据我所知,贪婪的方法有时会提供最佳解决方案; 在其他情况下,动态编程方法提供了最佳解决方案.
为了使用一种方法(或另一种方法)获得最佳解决方案,是否必须满足任何特定条件？
问候,
是否有除Neo4J以外的任何开源图形数据库？
注意: 为什么不用Neo4J？
Neo4J是开源的,但计算原语(节点数,关系和属性).如果您将其用于商业用途.并且在官方网站上没有任何直接的定价信息.所以可能有潜在的供应商锁定(虽然我刚刚开始我的公司,并且没有预算花钱在软件上.)所以它是不可选择的.
问候,
我对拥有数百万个节点和数千万个边缘的大型网络进行网络分析感兴趣.我希望能够执行诸如从多种格式解析网络,查找连接组件,检测社区以及运行像PageRank这样的中心度量之类的事情.
我被NetworkX所吸引,因为它有一个很好的api,良好的文档,并且多年来一直在积极开发.另外,因为它是在python中,它应该快速开发.
在最近的一个演示文稿中(幻灯片可以在github上找到),它声称:
与许多其他工具不同,NX旨在处理与现代问题相关的规模数据...... NX中的大多数核心算法都依赖于极快的遗留代码.
该演示文稿还指出NetworkX的基本算法是在C/Fortran中实现的.
但是,看一下源代码,看起来NetworkX主要是用python编写的.我对源代码不太熟悉,但我知道有几个例子,其中NetworkX使用numpy进行繁重的提升(后者又使用C/Fortran进行线性代数).例如,该文件networkx/networkx/algorithms/centrality/eigenvector.py使用numpy来计算特征向量.
有没有人知道这种调用优化库如numpy的策略是否在整个NetworkX中非常流行,或者只是少数算法呢？任何人都可以描述与NetworkX相关的其他可扩展性问题吗？
来自NetworkX首席程序员的回复 我在NetworkX邮件列表上提出了这个问题,Aric Hagberg回答说:
NetworkX中使用的数据结构适合于扩展到大问题(例如,数据结构是邻接列表).算法具有各种缩放属性,但您提到的一些属性是可用的(例如,PageRank,连接的组件,边缘数量是线性复杂度).
此时,NetworkX是纯Python代码.邻接结构使用Python字典编码,以牺牲内存和计算速度为代价提供了极大的灵活性.大图会占用大量内存,最终会耗尽.
NetworkX确实将NumPy和SciPy用于主要基于线性代数的算法.在那种情况下,使用NumPy矩阵或SciPy稀疏矩阵将图表表示(复制)为邻接矩阵.这些算法可以受益于NumPy和SciPY中使用的传统C和FORTRAN代码.
在谈到时computing network flows,算法设计手册说:
传统的网络流算法基于增加路径的想法,并重复地从s到t找到正容量的路径并将其添加到流中.可以证明,当且仅当它不包含增广路径时,通过网络的流是最佳的.
我不明白是什么augmenting paths.我用Google搜索,发现:
但他们都参考了上面的引用.
任何人都可以真的清楚地解释一下是augmenting path什么？
我最近通过一个简单的问题很难回答你的求职面试:LinkedIn这样的网站如何有效地显示你与页面上显示的每个人之间的关系距离(第一/第二/第三)(例如,在人们搜索结果中,工作人员列表)在公司等)？
<编辑>我得到了解决方案的基本"技巧":找到"与我的距离"是一种常见的操作(例如,单页上20x +,每次登录会话100次),所以你可以做到"我的距离"的一部分X",缓存它,然后多次重复使用缓存的部分结果,以使其他操作更便宜.我还猜测部分结果很可能是我的二级连接,因为"缓存所有第三级连接"在RAM和CPU中成本太高.</ EDIT>
但是当我试图将这种洞察力转化为解决方案时,我想出了一个笨拙的答案,涉及在网站上创建每个人的二级连接的持久缓存(这将是非常昂贵的性能和复杂的维护),我采取了一种莫名其妙的转向使用布鲁姆过滤器的方式几乎没有技术意义.在这样的答案之后,我不会雇用自己!
后来,当我在没有面试压力的情况下思考问题时,我提出了一个更合理的答案.
构建一种非常快速的方法来获得每批用户ID的第一级连接(批量大小可达~1000？).这可能意味着一个由大量RAM服务器组成的专用集群,它可以将整个网络的第一级连接缓存在内存中.幸运的是,50M会员x平均.每个成员100个连接x每个成员4个字节ID = <25GB缓存在RAM中,这对于价格合理的硬件是可行的.并且每天的更改次数将低于1%,因此保持缓存最新并不太难.(请注意,关系数据库可能是实现此缓存的不良选择,因为"大量随机I/O"访问模式会破坏关系数据库性能.)
当用户登录时,通过获取每个第一级连接的第一级连接来缓存其第二级连接,并粘贴在哈希表中(key =第二级ID,值=连接你的第一级连接数组) .同时缓存您的第一级连接,这样您就可以通过一次回调将第一级和第二级都拉回到远程缓存服务器.用户ID很容易分区,因此像memcached这样的分布式缓存可以很好地解决这个问题.
对于任何用户ID,要查找它是否在您的"网络"中以及它与您(第1,第2,第3)的关系,请执行以下操作:
但我相信有更好的答案.你的是啥呢？如果您想要额外的挑战,请尝试模拟一个inteview情境(无法在Web上查找解决方案).
请注意,问题是关于最佳解决方案,无论LinkedIn今天如何实际执行,我在上面写了自己的答案之后就查了一下.