Mathematica 9 is now available
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: [mg126653] Re: GraphPath With Edge Weights
  • From: Dana DeLouis <dana01 at me.com>
  • Date: Tue, 29 May 2012 05:45:48 -0400 (EDT)
  • Delivered-to: l-mathgroup@mail-archive0.wolfram.com

> . . 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: Stop on message?
  • Next by Date: Re: Print TraditionalForm
  • Previous by thread: GraphPath With Edge Weights
  • Next by thread: Re: GraphPath With Edge Weights