Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: new Graph function + combinatorica: various problems

• To: mathgroup at smc.vnet.net
• Subject: [mg116404] Re: new Graph function + combinatorica: various problems
• From: Yaroslav Bulatov <yaroslavvb at gmail.com>
• Date: Sun, 13 Feb 2011 05:50:12 -0500 (EST)
• References: <ij2v05$7uu$1@smc.vnet.net>

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
];


On Feb 11, 1:20 am, Cupidio <andreatacche... at gmail.com> wrote:
> 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!