Re: Combinatorica
- To: mathgroup at smc.vnet.net
- Subject: [mg117902] Re: Combinatorica
- From: Dana DeLouis <dana.del at gmail.com>
- Date: Sun, 3 Apr 2011 06:59:00 -0400 (EDT)
> We have a lot of serious problems with Combiantorica, the main one
> being the ConnectedComponents and HamiltonianQ cannot be used
> together.
Hi. Not an expert here. Not sure of the question, but I'll take a
crack at your question above on ..."ConnectedComponents" and
"HamiltonianQ".
I have Ver 8. They really messed things up with this version. I'm as
confused as ever.
It appears that there is a bug when converting to the Combinatorica
Graph object.
It appears to me that the conversion can not work with Sparse Arrays.
Using "Normal" seems to be a workaround.
(* Your input *)
L=System`Graph[{1\[UndirectedEdge]2,...etc]
HamiltonianGraphQ[L]
True
(* Version 8's new command *)
hc = FindHamiltonianCycle[L]
>> Output here
(* This is to make it readable in this post *)
Apply[List,hc,2]
{{{1,2},{2,4},{4,6},{6,8},{8,7},{7,5},{5,3},{3,1}}}
Needs["Combinatorica`"] //Quiet
g=AdjacencyMatrix[L] //Normal //FromAdjacencyMatrix
ShowGraph[g]
Combinatorica`ConnectedComponents[g]
{{1,2,3,4,5,6,7,8}}
HamiltonianCycle[g]
{1,2,4,5,8,7,6,3,1}
HamiltonianCycle[g,All]
{{1,2,4,5,8,7,6,3,1},{1,3,6,7,8,5,4,2,1}}
I notice that the built-in HamiltonianCycle is different than Combinatorica's.
Is this another bug?
HTH :>)
Dana DeLouis
Ver 8 & Mac
= = = = = = = = = = = = =
On Mar 31, 4:58 am, janos <janostothmeis... at gmail.com> wrote:
> We have a lot of serious problems with Combiantorica, the main one
> being the ConnectedComponents and HamiltonianQ cannot be used
> together. Here is the content of our notebook. (By the way, is there
> any way attachig a file here? Seems to be an old problem.)
>
> At first a graph is constructed
>
> L = Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 3,
> 2 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4, 2 \[UndirectedEdge]
> 6,
> 3 \[UndirectedEdge] 5, 3 \[UndirectedEdge] 7, 4 \[UndirectedEdge]
> 6,
> 5 \[UndirectedEdge] 7, 6 \[UndirectedEdge] 7, 6 \[UndirectedEdge]
> 8,
> 7 \[UndirectedEdge] 8}]
>
> {VertexList[L], EdgeList[L], VertexCount[L], EdgeCount[L]}
>
> ConnectedComponents[
> Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 3 \
> [UndirectedEdge] 1,
> 4 \[UndirectedEdge] 5}, VertexLabels -> "Name", ImagePadding -> 5]]
>
> am = AdjacencyMatrix[L]
>
> AdjacencyGraph[AdjacencyMatrix[L]]
>
> FromAdjacencyMatrix and ToAdjacencyMatrix are not built in.
>
> So far so good. Let us invoke the package.
>
> << Combinatorica`
>
> A lot of functions, like Graph, ConnectedCompomnents will not function
> any more.
>
> Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 3, 2 \
> [UndirectedEdge] 3,
> 2 \[UndirectedEdge] 4, 2 \[UndirectedEdge] 6, 3 \[UndirectedEdge]
> 5,
> 3 \[UndirectedEdge] 7, 4 \[UndirectedEdge] 6, 5 \[UndirectedEdge]
> 7,
> 6 \[UndirectedEdge] 7, 6 \[UndirectedEdge] 8, 7 \[UndirectedEdge]
> 8}]
>
> ConnectedComponents[
> Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 3 \
> [UndirectedEdge] 1,
> 4 \[UndirectedEdge] 5}, VertexLabels -> "Name", ImagePadding -> 5]]
>
> ConnectedComponents[L]
>
> HamiltonianQ is avaliable but it does not work
>
> HamiltonianQ[L]
>
> HamiltonianCycle[L]
>
> AdjacencyGraph[am]
>
> FromAdjacencyMatrix[am]
>
> FromAdjacencyMatrix[nam = Normal[am]]
>
> Use of sparse matrices are discouraged, they are incompatible with
> Combinatorica.
>
> MatrixForm[am]
>
> HamiltonianQ[AdjacencyGraph[am]]
>
> HamiltonianQ[AdjacencyGraph[nam]]
>
> HamiltonianQ[FromAdjacencyMatrix[nam]]
>
> {V[L], M[L]}
>
> {V[AdjacencyGraph[am]], M[AdjacencyGraph[am]]}
>
> {V[AdjacencyGraph[nam]], M[AdjacencyGraph[nam]]}
>
> {V[FromAdjacencyMatrix[nam]], M[FromAdjacencyMatrix[nam]]}