Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2012

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

Search the Archive

Re: GraphPath With Edge Weights

  • To: mathgroup at smc.vnet.net
  • Subject: [mg126669] Re: GraphPath With Edge Weights
  • From: Ralph Dratman <ralph.dratman at gmail.com>
  • Date: Wed, 30 May 2012 04:09:42 -0400 (EDT)
  • Delivered-to: l-mathgroup@mail-archive0.wolfram.com
  • References: <201205290945.FAA06632@smc.vnet.net>

That is also what my experience has been recently. In addition, I am
pretty sure some of the built-in graph routines sometimes give wrong
answers. My guess is that some Wolfram-supplied code is building
graphs "by hand" rather than always using common routines. The result
may be that their structures are slightly different from what is
expected, so some other routines fail.

I think the whole graph library needs an overhaul.

Ralph


On Tue, May 29, 2012 at 3:11 PM, Dana DeLouis <dana01 at me.com> wrote:
> Hi.   I like Combinatorica, but I see they are moving many, but not all, of the functions over to the kernel.
> It's causing a lot of problems for me also by having such a mix of packages.
> I see a few key words highlighted in Red, which means there are function names appearing in multiple locations.
>
> It would be nice to see Wolfram just consolidate everything into the kernel, and just get rid of the packages.
>
> My opinion of course.  :>)
>
> ~Dana
>
>
>
>
>
> On May 29, 2012, at 12:22 PM, Ralph Dratman wrote:
>
>> Dana, do you mean, you hope Wolfram consolidates the graph-handling
>> routines? If so, I sure agree. Many routines don't seem to work
>> properly, and bringing in Combinatorica has been catastrophic every
>> time I've tried it.
>>
>> Ralph
>>
>> On Tue, May 29, 2012 at 5:45 AM, Dana DeLouis <dana01 at me.com> wrote:
>>> = = = = = = = = = =
>>> I hope they consolidate Graphics in the next release
>>> HTH  :>)
>>> Dana DeLouis
>>> Mac & Math 8
>>> = = = = = = = = = =
>>>> . . if I compute GraphPath[graph, 1, 3] it returns
>>>>     the unweighted shortest path {1, 3}.
>>>
>>> My opinion is that graphics are so confusing now with multiple overlaps between packages, Combinatorica, and new built in functions in version 8.
>>>
>>> The use of WeightedAdjacencyMatrix appears to solve this problem.
>>> Not sure if it's the best solution.
>>>
>>> Needs["GraphUtilities`"]
>>>
>>> graph=Graph[{UndirectedEdge[1,2],UndirectedEdge[2,3],UndirectedEdge[3,1]},EdgeWeight->{1,2,9}];
>>>
>>> GraphDistance[graph,1,3]
>>> 3.
>>>
>>> GraphPath[graph,1,3]
>>> {1,3}
>>>
>>> // Workaround:
>>>
>>> GraphPath[WeightedAdjacencyMatrix[graph],1,3]
>>> {1,2,3}
>>>
>>> Here is a slightly larger graph (4 points)
>>>
>>> // Setup:
>>>
>>> g=CompleteGraph[4];
>>> wgts = Thread[EdgeList[g]->Range[EdgeCount[g]]];
>>>
>>> // Graph
>>>
>>> g=CompleteGraph[4,
>>> Rule[VertexShapeFunction,List["Name"]],
>>> EdgeWeight->wgts,
>>> EdgeLabels->wgts,
>>> ImagePadding->10,
>>> EdgeLabelStyle->Directive[Blue,Italic,20]
>>> ]
>>>
>>> GraphDistance[g,2,4]
>>> 4.
>>>
>>> GraphPath[WeightedAdjacencyMatrix[g],2,4]
>>> {2,1,4}
>>>
>>> GraphPath[WeightedAdjacencyMatrix[g],2,3]
>>> {2,1,3}
>>>
>>> GraphPath[WeightedAdjacencyMatrix[g],3,4]
>>> {3,1,4}
>>>
>>> = = = = = = = = = =
>>> I hope they consolidate Graphics in the next release
>>> HTH  :>)
>>> Dana DeLouis
>>> Mac & Math 8
>>> = = = = = = = = = =
>>>
>>>
>>>
>>>
>>> On May 28, 5:14 am, Ben <ben... at gmail.com> wrote:
>>>> I can't figure out how to compute a shortest path using GraphPath with
>>>> edge weights. I first define a graph as follows.
>>>>
>>>> graph = Graph[{UndirectedEdge[1,2], UndirectedEdge[2,3],
>>>> UndirectedEdge[3,1]}, EdgeWeight->{1, 2, 9}]
>>>>
>>>> After loading GraphUtilities I compute GraphDistance[graph, 1, 3] and
>>>> it correctly returns the shortest path distance of 3 corresponding to
>>>> the path {1, 2, 3}.  But if I compute GraphPath[graph, 1, 3] it
>>>> returns the unweighted shortest path {1, 3}. Even if I use
>>>> GraphPath[graph, 1, 3, Weighted->True] it still returns the same
>>>> answer of {1, 3}. (Weighted is supposed be True by default anyway.)
>>>> What am I doing wrong?
>>>>
>>>> Thanks.
>>>
>>>
>>>
>



  • Prev by Date: Re: Sqrt of complex number
  • Next by Date: Re: Stop on message?
  • Previous by thread: Re: GraphPath With Edge Weights
  • Next by thread: how to add graphics options in a plot which is already produced and has a manipulator