new Graph function + combinatorica: various problems

[Cupidio]

Hi,
I'm experiencing some problems in combining the functionalities of
combinatorica and the built-in functions for graphs.

In fact loading combinatorica shadows the built-in Graph function, and
makes its use impossible. But while I need some of the functions in
the combinatorica package (minimum/maximum spanning tree), i prefer
the graphic and "lexical" representation of the built-in Graph[].

How do I "save" Graph[] when I load combinatorica, or how can I make
it come back?

Also (and this looks weird!), when i use ToCombinatoricaGraph[] (in
GraphUtilites package) to convert a graph, the resulting object can be
processed by MaximumSpanningTree[], yielding a correct result, but not
by MinimumSpanningTree[] which returns something like:

MinimumSpanningTree[-Graph:<14,8,Directed>-]

...not even a combinatorica graph object.

Thanks for your help!

[Sjoerd C. de Vries]

I posted on graph conversion a couple of weeks ago.

Shading of Graph can be prevented by prepending the System` context
(System`Graph[...]).

The two versions of conversion yield different plots in GraphPlot.
Also my conversion route both yield minimum and maximum spanning trees
(although for the graphs I tested them, they look identical). The
ToCombinatoricaGraph conversion yields graphs for which (for all
graphs I tested) the minimum spanning tree does not plot.

Clearly, there is room for improvement in the graph area.

<< Combinatorica`
<< GraphUtilities`

myM8Graph = GraphData["ZamfirescuGraph48"]

(* conversion 1 *)
myCombinatoricaGraph =
FromAdjacencyMatrix[Normal[System`AdjacencyMatrix[myM8Graph]]];

myCombinatoricaGraph // ShowGraph
MinimumSpanningTree[myCombinatoricaGraph] // ShowGraph
MaximumSpanningTree[myCombinatoricaGraph] // ShowGraph

(* conversion 2*)
myCombinatoricaGraph = ToCombinatoricaGraph[myM8Graph];

myCombinatoricaGraph // ShowGraph
MinimumSpanningTree[myCombinatoricaGraph] // ShowGraph
MaximumSpanningTree[myCombinatoricaGraph] // ShowGraph

Cheers -- Sjoerd

[Yaroslav Bulatov]

I first asked about dealing with Combinatorica conflicts 2 months ago.
Since then there were several discussions on stackoverflow site on
combining the functionalities result of which is the following
strategy which I have used for the last month without encountering any
conflicts:

Basically use system Graph for everything, use "Graph" to refer to
System graph and "Combinatorica`Graph" to refer to Combinatorica
Graph. Whenever Combinatorica function is needed, write a wrapper that
converts object to Combinatorica`Graph, calls Combinatorica function,
then converts the result back to System Graph if needed.

This requires Combinatorica to be not on on ContextPath. Because
functions like GraphUtilities`ToCombinatoricaGraph add Combinatorica
to ContextPath on each call, use $Post to remove Combinatorica from
ContextPath after each evaluation. Also, because Combinatorica
redefines "System`Element" which breaks another package I use, I load
Combinatorica using "Block[{Element},Needs["Combinatorica`"]]".
GraphUtilities package shadows some built-ins, so its helpful to keep
GraphUtilities out of ContextPath and refer to those functions
explicitly, ie GraphUtilities`EdgeList

I execute the following at the start of each session:

$Post = ($ContextPath =
DeleteCases[$ContextPath,
"Combinatorica`" | "GraphUtilities`"]; #) &;
Block[{Element}, Needs["Combinatorica`"]; Needs["GraphUtilities`"]]

Here's an example of a wrapper that takes list of edges and weights,
calls Combinatorica's MaximumSpanningTree and returns list of edges in
the tree

(* uses combinatorica to find maximum weight spanning tree *)
maxWeightSpanTree[edges_List,weights_List]:=Module[{nums,nodes,nums2nodes=
,nodes2nums,numEdges,combgraph,wCombGraph,combTree},
Block[{Element},Needs["Combinatorica`"]];
$ContextPath=DeleteCases[$ContextPath,"Combinatorica`"];

nodes=Union[fl1@edges];
nums=Range[Length@nodes];
nums2nodes=Thread[nums->nodes];
nodes2nums=Reverse/@nums2nodes;
numEdges=edges/.nodes2nums;
combGraph=Combinatorica`FromUnorderedPairs[numEdges];
wCombGraph=Combinatorica`SetEdgeWeights[combGraph,numEdges,weights];
combTree=Combinatorica`MaximumSpanningTree[wCombGraph];
Combinatorica`ToUnorderedPairs[combTree]/.nums2nodes
];

[another...@googlemail.com]

nice. Can anybody tell me a convenient way to convert an explicit Combinatorica graph g to a System Graph g2 without using wrappers?
Thanks a lot.
Jesch

[Murray Eisenberg]

This was discussed in MathGroup about three years ago. Here are some
functions towards a solution that were provided in responses there.


(* Convert Combinatorica type Graph object to the list of rules expected
by GraphPlot *)

RuleListFromGraph[Graph[edges_, vertices_, ___]] :=
Module[{vrules},
vrules = DeleteCases[
Thread[Range[
Length[vertices]] -> (VertexLabel /.
vertices[[All, 2 ;;]])], _ -> VertexLabel];
Replace[
Transpose[{Rule @@@ (edges[[All, 1]] /. vrules),
EdgeLabel /. edges[[All, 2 ;;]]}], {a_, EdgeLabel} -> a, {1}]]

(* Preserve original coordinates of vertices lost by the above *)
GetVertexCoordinates[Graph[edges_, vertices_, ___]] :=
vertices[[All, 1]]

(* Example *)
g = SetEdgeLabels[
SetVertexLabels[Wheel[4], Range[4]],
Characters["defabc"]];
GraphPlot[RuleListFromGraph[g], VertexLabeling -> True,
VertexCoordinateRules -> GetVertexCoordinates[g]]

--
Murray Eisenberg mur...@math.umass.edu
Mathematics & Statistics Dept.
Lederle Graduate Research Tower phone 413 549-1020 (H)
University of Massachusetts 413 545-2859 (W)
710 North Pleasant Street fax 413 545-1801
Amherst, MA 01003-9305

[Jens]

Thanks a lot. But eventually I want to export the (converted)
System`graph to a specific file format ("graph6"). The conversion to a
List of Edge Rules works fine and suffices for GraphPlot, but not for
exporting. I get the error message: "The element "AdjacencyMatrix
contains a malformed data structure and could not be exported to Graph6
format."

I guess there are some other elements in the System`graph format that
the export function needs.


On 03.05.2012 16:56, Murray Eisenberg wrote:
> this was discussed in MathGroup about three years ago. Here are some

[Szabolcs Horvát]

For a quick solution, you could use something like

System`Graph@Edges[g]

if g is the Combinatorica graph. This will discard the graph layout
(vertex positions on the plane), but will keep the structure (i.e. the
actual graph).

--
Szabolcs Horvát
Visit Mathematica.SE: http://mathematica.stackexchange.com/