创建具有已命名顶点的边的 Mathematica/Combinatorica 图

Question

如何根据具有命名顶点的边制作 Mathematica 图？ EG：

http://pastebin.com/Se1Nhe3M

我已经尝试过上述方法和几种变体，但 Combinatorica 从未尝试过 很接受就对了。显然，Graph[]想要坐标 我希望 Combinatorica 能够自行解决这个问题。

AddVertex to EmptyGraph[0] （或其他）也失败。

GraphUtilities 不是一个选择，因为我想做相当复杂的事情 对我的图表进行分析。

这看起来是一个简单的问题。 Graphviz 可以轻松地创建图表 带有命名顶点的边，所以我确信 Mathematica 也可以吗？

我读过：

ShowGraph [ { {e1,e2}, {e1, e3} }, {e1,e2,e3} ]; // 这里有什么问题？

但这似乎对我的具体情况没有帮助。

Answer 1

如果症结在于以字符串表示的节点，并且重型图形分析函数希望将它们作为整数，那么您可能会考虑将字符串映射到整数，反之亦然：

nodes = DeleteDuplicates@Flatten[graph /. Rule -> List]

{"Conga", "Egypt", "Sarah Desert", "Europe", "Arabia", "UK", "Iceland", 
 "Greenland", "Germany", "Russia", "Irakistan", "Austr(al)ia", "China", "Canada",
 "More Russia", "USA", "Andy's Mountains", "Brazil"}

现在您有了节点列表。接下来进行与整数的映射：

each[{i_, s_}, Transpose[{Range@Length@nodes, nodes}],
  numify[s] = i;
  namify[i] = s]

您现在可以轻松地将节点与整数相互转换：

numify["Europe"]

4

namify[4]

"Europe"

像这样转换整个图：

graph /. s_String -> numify[s]

请注意，each 是以下实用程序函数，在此讨论：Mathematica 中的 ForEach 循环

SetAttributes[each, HoldAll];               (* each[pattern, list, body]      *)
each[pat_, lst_, bod_] := ReleaseHold[      (*  converts pattern to body for  *)
  Hold[Cases[Evaluate@lst, pat:>bod];]];    (*   each element of list.        *)

Answer 2

既然您专门要求 Combinatorica 并且因为我总是犹豫是否要开始研究包的内部细节，那么也许这会对您有所帮助：

Load Combinatorica using <<或者如果您的版本需要这个，则需要。然后使用您的数据：

edges={{"Conga" -> "埃及"}, {"埃及" -> “康加鼓”}，{“康加鼓”-> “莎拉沙漠”},
{“莎拉沙漠”-> “康加”}，{“埃及”-> "欧洲"}, {"欧洲" -> “埃及”}，
{“埃及”-> “阿拉伯”}，{“阿拉伯”-> "埃及"}, {"埃及" -> “莎拉沙漠”},
{“莎拉沙漠”-> “埃及”}，{“英国”-> "欧洲"}, {"欧洲" -> “英国”}，
{“英国”-> "冰岛"}, {"冰岛" -> “英国”}，{“英国”-> “格陵兰”}，
{“格陵兰岛”-> “英国”}，{“欧洲”-> “阿拉伯”}，{“阿拉伯”-> “欧洲”}，
{“欧洲”-> “德国”}，{“德国”-> "欧洲"}, {"欧洲" -> “冰岛”}，
{“冰岛”-> "欧洲"}, {"欧洲" -> “莎拉沙漠”},
{“莎拉沙漠”-> “欧洲”}，{“德国”-> “俄罗斯”}，{“俄罗斯”-> “德国”}，
{“德国”-> “阿拉伯”}，{“阿拉伯”-> “德国”}，{“德国”-> “冰岛”}，
{“冰岛”-> “德国”}，{“德国”-> "伊拉克斯坦"}, {"伊拉克斯坦" -> “德国”}，
{“Austr(al)ia”-> “中国”}，{“中国”-> "Austr(al)ia"}, {"阿拉伯" -> “伊拉克斯坦”},
{“伊拉克斯坦”-> “阿拉伯”}，{“加拿大”-> “更多俄罗斯”}，{“更多俄罗斯”-> “加拿大”}，
{“加拿大”-> “美国”}，{“美国”-> “加拿大”}，{“加拿大”-> “安迪的山脉”},
{“安迪的山”-> “加拿大”}，{“更多俄罗斯”-> “俄罗斯”}，
{“俄罗斯”-> “更多俄罗斯”}，{“更多俄罗斯”-> “中国”}，{“中国”-> “更多俄罗斯”}，
{“更多俄罗斯”-> "伊拉克斯坦"}, {"伊拉克斯坦" -> “更多俄罗斯”}，
{“中国”-> "伊拉克斯坦"}, {"伊拉克斯坦" -> “中国”}，{“美国”-> “格陵兰”}，
{“格陵兰岛”-> “美国”}，{“美国”-> “安迪的山脉”},
{“安迪的山”-> “美国”}，{“巴西”-> “莎拉沙漠”},
{“莎拉沙漠”-> “巴西”}，{“巴西”-> “安迪的山脉”},
{“安迪的山”-> “巴西”}，{“俄罗斯”-> “伊拉克斯坦”},
{“伊拉克斯坦”-> "俄罗斯"}}/.Rule[from_,to_]->{from,to};

labels={“加拿大”、“美国”、“格陵兰岛”、“巴西”、“安迪山脉”、“英国”、“冰岛”、“德国”、“欧洲”、“俄罗斯”、“更多俄罗斯”、“伊拉克斯坦”、“阿拉伯”、“中国”、“澳大利亚”、“埃及”、“萨拉沙漠”、“康加”}；

numberededges=Partition[Flatten[edges/.Thread[Rule[labels,Range[Length[labels]]]]],2];

ShowGraph[AddEdges[EmptyGraph[长度[标签]],numberededges],
VertexLabel->labels,PlotRange->All]

现在，如果自动重新格式化没有破坏这一点，那么我想您可能已经准备好了。

我还没有在这方面做出指导，我想你可能想这样做。
希望这足以让您开始。

所有这些都是基于在 Pemmaraju 和 Skiena 所著的《计算离散数学：组合数学和图论与 Mathematica》中来回翻页几分钟。我相信任何试图在没有这个的情况下使用 Combinatorica 的人都是疯子。我希望我们能够说服他们推出该版本的新版本，修复一些拼写错误，并让他们让那些完全不了解 Combinatorica 的人能够更轻松地使用它来开始使用。

Answer 3

您可以将边转换为邻接矩阵，然后使用 Combinatorica 的 FromAdjacencyMatrix 函数。

(* Converts lists of edges into adjacency matrix, saving "nodename->column #" mapping into global variable nodeMap *)
graph2mat[edges_] := Module[{nodes, mat, n},
   nodes = Sequence @@@ edges // Union // Sort;
   nodeMap = (# -> (Position[nodes, #] // Flatten // First)) & /@ 
     nodes;
   mat = (({#1, #2} -> 1) & @@@ (edges /. nodeMap)) // SparseArray // 
     Normal;
   n = Max[Length[#] & /@ {mat, Transpose[mat]}];
   PadRight[mat, {n, n}]
   ];

g = FromAdjacencyMatrix[graph2mat[{"a" -> "b", "b" -> "a"}]];
reverseNodeMap = Reverse /@ nodeMap;
MaximumClique[g] /. reverseNodeMap

Answer 4

Combinatorica Graph[] 对象并不容易处理。您尝试过 www.sagenb.org 吗？ Sage 的 Graph 对象真的很酷。

Answer 5

如果您有 Mathematica 7，请尝试内置的 GraphPlot< /a>：

GraphPlot[{"Conga" -> "Egypt", "Egypt" -> "Conga", 
  "Conga" -> "Sarah Desert", "Sarah Desert" -> "Conga", 
  "Egypt" -> "Europe", "Europe" -> "Egypt", "Egypt" -> "Arabia", 
  "Arabia" -> "Egypt", "Egypt" -> "Sarah Desert", 
  "Sarah Desert" -> "Egypt", "UK" -> "Europe", "Europe" -> "UK", 
  "UK" -> "Iceland", "Iceland" -> "UK", "UK" -> "Greenland", 
  "Greenland" -> "UK", "Europe" -> "Arabia", "Arabia" -> "Europe", 
  "Europe" -> "Germany", "Germany" -> "Europe", "Europe" -> "Iceland",
   "Iceland" -> "Europe", "Europe" -> "Sarah Desert", 
  "Sarah Desert" -> "Europe", "Germany" -> "Russia", 
  "Russia" -> "Germany", "Germany" -> "Arabia", "Arabia" -> "Germany",
   "Germany" -> "Iceland", "Iceland" -> "Germany", 
  "Germany" -> "Irakistan", "Irakistan" -> "Germany", 
  "Austr(al)ia" -> "China", "China" -> "Austr(al)ia", 
  "Arabia" -> "Irakistan", "Irakistan" -> "Arabia", 
  "Canada" -> "More Russia", "More Russia" -> "Canada", 
  "Canada" -> "USA", "USA" -> "Canada", 
  "Canada" -> "Andy's Mountains", "Andy's Mountains" -> "Canada", 
  "More Russia" -> "Russia", "Russia" -> "More Russia", 
  "More Russia" -> "China", "China" -> "More Russia", 
  "More Russia" -> "Irakistan", "Irakistan" -> "More Russia", 
  "China" -> "Irakistan", "Irakistan" -> "China", 
  "USA" -> "Greenland", "Greenland" -> "USA", 
  "USA" -> "Andy's Mountains", "Andy's Mountains" -> "USA", 
  "Brazil" -> "Sarah Desert", "Sarah Desert" -> "Brazil", 
  "Brazil" -> "Andy's Mountains", "Andy's Mountains" -> "Brazil", 
  "Russia" -> "Irakistan", "Irakistan" -> "Russia"}, 
 DirectedEdges -> True]

这将为您提供以下内容，例如：

alt text http:// img638.imageshack.us/img638/7803/plotm.png

布局、顶点和边标记以及样式等有很多选项。