Create Mathematica/Combinatorica graph with edges that have named vertices

Question

How do I make a Mathematica graph from edges with named vertices? EG:

http://pastebin.com/Se1Nhe3M

I've tried the above and several variations, but Combinatorica never quite accepts it right. Apparently, Graph[] wants coordinate positions, which I want Combinatorica to figure out itself.

AddVertex to EmptyGraph[0] (or whatever) also fails.

GraphUtilities isn't an option, since I want to do fairly complex analysis on my graphs.

This seems like a simple problem. Graphviz easily creates graphs from edges with named vertices, so I'm sure Mathematica can too?

I've read:

ShowGraph[ { {e1,e2}, {e1, e3} }, {e1,e2,e3} ]; // what is the problem here?

but it doesn't seem to help with my specific case.

Answer 1

If you have Mathematica 7, try the built-in GraphPlot:

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]

That will give you the following, for example:

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

There are many options for layout, vertex and edge labeling and style, etc.

Answer 2

If the sticking point is nodes represented as strings and the heavy-duty graph analysis functions want them as integers, you might consider mapping your strings to integers and vice versa:

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"}

Now you have the list of nodes. Next do the mapping to and from integers:

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

You can now easily convert the nodes to and from integers:

numify["Europe"]

4

namify[4]

"Europe"

Convert the whole graph like this:

graph /. s_String -> numify[s]

Note that each is the following utility function, discussed here: ForEach loop in Mathematica

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 3

Since you asked specifically for Combinatorica and since I'm always hesitant to start tromping around on the internal details of a package then perhaps this will help you:

Load Combinatorica using << or Needs if your version needs this. Then using your data:

edges={{"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"}}/.Rule[from_,to_]->{from,to};

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

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

ShowGraph[AddEdges[EmptyGraph[Length[labels]],numberededges], VertexLabel->labels,PlotRange->All]

Now if the autoreformatting hasn't ruined this then I think you might be ready.

I haven't made the edges directed in this and I assume you might want to do that. Hopefully this is enough to get you started.

All this is based on paging back and forth for a few minutes in "Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica" by Pemmaraju and Skiena. I believe anyone trying to use Combinatorica without having this in front of them is just nuts. I wish we could convince them to bring out a new edition of that, fix some of the typos, and get them to make it a little easier for someone who doesn't know all about Combinatorica to be able to use it to get started.

Answer 4

You can convert your edges to an adjacency matrix then use Combinatorica's FromAdjacencyMatrix function.

(* 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 5

Combinatorica Graph[] object is not easy to deal with. Did you try www.sagenb.org? Sage's Graph object is really cool.