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.
>>>
>>>
>>>
>
- References:
- Re: GraphPath With Edge Weights
- From: Dana DeLouis <dana01@me.com>
- Re: GraphPath With Edge Weights