Graph Utilities

Arithmetic, Decimals and Fractions, Prealgebra, Algebra I, Algebra II, Geometry, Trigonometry, Precalculus, Calculus, Discrete Math, Probability and Statistics, etc.
Forum Rules
By using the Wolfram Faculty Program Forum, you agree not to post any abusive, obscene, vulgar, slanderous, hateful, threatening, or sexually oriented material. Wolfram Faculty Program Forum administrators have the right to remove, edit, move or close any topic at any time should we see fit.

Personal Information: Posts in this forum may be viewed by non-members; however, the forum prohibits non-members from viewing your profile. Although your email address is hidden from both non-members and members, your account is initially configured to allow members to contact you via email through the forum. If you wish to hide your profile, or prohibit others from contacting you directly, you may change these settings by updating your profile through the User Control Panel.

Attachments: Attachments are not currently enabled on this forum. To share a file with others on this site, simply upload your file to the online storage service of your choice and include a link to the file within your post. If your school does not offer an online file storage and sharing service, the following sites provide free basic online file storage and sharing: Mozy, FilesAnywhere, Adrive, and KeepandShare.

Graph Utilities

Postby ttemel » Thu Mar 04, 2010 3:09 pm

I created a (4*4) matrix as a graph and like to use "CostOfPath[g,p]*

but I failed to use it and I do not know why.

Any idea?
User avatar
ttemel
 
Posts: 3
Joined: Wed Mar 03, 2010 8:15 am
Organization: Tilburg University
Department: Development Research Institute

Re: Graph Utilities

Postby Jose_Luis_Gomez » Thu Mar 04, 2010 5:13 pm

Before using CostOfPath you must load the Combinatorica package with the command Needs["Combinatorica`"]
Did you do that? If you didn´t, you must start in a fresh Mathematica session (quit and restart Mathematica), then first evaluate Needs["Combinatorica`"] and after that create your matrix and try CostOfPath.
HTH
José
Mexico
User avatar
Jose_Luis_Gomez
 
Posts: 22
Joined: Wed Feb 03, 2010 7:57 pm
Location: Mexico
Organization: ITESM CEM Mexico
Department: Ciencias Basicas

Re: Graph Utilities

Postby ttemel » Tue Mar 09, 2010 3:00 pm

Dear Gomez,

I did use Needs command and after that I tried to use "CostOfPath" but still I fail to get it run. In fact, there are other commands which are not working at all.

Thanks.

Tugrul
User avatar
ttemel
 
Posts: 3
Joined: Wed Mar 03, 2010 8:15 am
Organization: Tilburg University
Department: Development Research Institute

Re: Graph Utilities

Postby Jose_Luis_Gomez » Tue Mar 09, 2010 10:14 pm

(* Dear Tugrul: I was able to create a small tutorial about the use of CostOfPath *)
(* This is the first time I use Combinatorica, therefore this is for sure Not the most efficient way to do it*)

(* PLEASE SEE THE MATHEMATICA FILE IN: http://homepage.cem.itesm.mx/lgomez/dat ... atorica.nb *)

(* PLEASE SEE THE PDF FILE IN: http://homepage.cem.itesm.mx/lgomez/dat ... torica.pdf *)

(* Use of CostOfPath and ShortestPath *)
(* By José Luis Gómez-Muñoz
http://homepage.cem.itesm.mx/lgomez/
Mexico *)

(* FIRST EXAMPLE: Equally Weighted Graph *)

(* Load the package: *)
Needs["Combinatorica`"]

(* Create a simple, equally weighted graph, and store it in the variable myfirstgraph: *)
myfirstgraph = CompleteGraph[6]

(* Show the graph, including vertex numbers: *)
ShowGraph[myfirstgraph, VertexNumber -> True]

(* For this simple graph, the cost of each path *)
(* is just the length of the path (a path is a *)
(* list of vertex numbers). The path {1,3,5,6} is *)
(* the edge 1 to 3, then 3 to 5, then 5 to 6, *)
(* so 3 edges, without weights, the path has a cost of 3: *)
CostOfPath[myfirstgraph, {1, 3, 5, 6}]

(* This is the path. It is made of 3 edges, therefore without weights its total cost is 3: *)
ShowGraph[Highlight[myfirstgraph, {{{1, 3}, {3, 5}, {5, 6}}}],
VertexNumber -> True]


(* SECOND EXAMPLE: Set different weights for the edges *)

(* Load the package: *)
Needs["Combinatorica`"]

(* Create a graph with weights. The weights that *)
(* are Not specified will be considered as "one" by commands like CostOfPath: *)
mysecondgraph = SetGraphOptions[
CompleteGraph[6],
{{{1, 3}, EdgeWeight -> 0.04},
{{3, 5}, EdgeWeight -> 0.08},
{{5, 6}, EdgeWeight -> 0.11},
{{1, 2}, EdgeWeight -> 0.03},
{{2, 5}, EdgeWeight -> 0.07}
}]


(* Weight were defined for some of the edges of the *)
(* graph that was called mysecondgraph. Now the CostOfPath is *)
(* calculated by adding those weights: *)
CostOfPath[mysecondgraph, {1, 3, 5, 6}]


(* Cost of another path: *)
CostOfPath[mysecondgraph, {1, 2, 5, 6}]


(* Any weight that was not specified is considered to be "one": *)
CostOfPath[mysecondgraph, {1, 2, 5, 6, 4}]


(* ShortestPath find the path with minimum CostOfPath from one initial vertex to a final vertex: *)
ShortestPath[mysecondgraph, 1, 6]

(* By José Luis Gómez-Muñoz
http://homepage.cem.itesm.mx/lgomez/
Mexico *)
User avatar
Jose_Luis_Gomez
 
Posts: 22
Joined: Wed Feb 03, 2010 7:57 pm
Location: Mexico
Organization: ITESM CEM Mexico
Department: Ciencias Basicas

From matrix to graph to CostOfPath

Postby Jose_Luis_Gomez » Fri Mar 12, 2010 8:31 pm

(* Hello again *)

(* I have created another tutorial, clorser to what you need, Tugrul, now showing how to create a weighted-directed-graph from a matrix. The only inconvinience is that disconnected vertices must have a weight (cost) of a large number, say 1000, instead of the usual zero *)

(* PLEASE SEE THE MATHEMATICA FILE IN: http://homepage.cem.itesm.mx/lgomez/data/digraph.nb *)

(* PLEASE SEE THE PDF FILE IN: http://homepage.cem.itesm.mx/lgomez/data/digraph.pdf *)

Needs["Combinatorica`"];

mymatrix = {
{1, 0.10, 0.15, 0.05, 1000},
{0.05, 1, 1000, 1000, 0.05},
{1000, 0.10, 1, 0.15, 1000},
{0.15, 0.05, 1000, 1, 0.20},
{1000, 0.20, 0.05, 0.15, 1}
};

myweights =
Flatten[MapIndexed[
Function[{weight, pos}, {pos, EdgeWeight -> weight}],
mymatrix, {2}], 1];

mygraph = SetGraphOptions[
CompleteGraph[Length[mymatrix], Type -> Directed],
myweights];

CostOfPath[mygraph, {5, 3, 2, 1}]
User avatar
Jose_Luis_Gomez
 
Posts: 22
Joined: Wed Feb 03, 2010 7:57 pm
Location: Mexico
Organization: ITESM CEM Mexico
Department: Ciencias Basicas

Re: Graph Utilities

Postby Crescenzio_Gallo » Thu Apr 29, 2010 9:47 pm

Dear Prof Gomez,
is there a simple method for plotting the weighted graphs of your tutorial along with the weights automatically showed as labels on the corresponding edges?

TIA,
Crescenzio Gallo
--
University of Foggia, Italy
Bioagromed Research Centre
--
University of Foggia, Italy
Bioagromed Research Centre
User avatar
Crescenzio_Gallo
 
Posts: 2
Joined: Fri Feb 26, 2010 6:23 am
Location: Laboratory for quantitative analisys of data
Organization: University of Foggia
Department: Economics, Mathematics and Statistics

Re: Graph Utilities

Postby Jose_Luis_Gomez » Tue May 04, 2010 4:32 pm

(* Dear professor Crescenzio Gallo *)

(* I have improved the second tutorial to include the plots of the directed graph with weights *)

(* PDF version http://homepage.cem.itesm.mx/lgomez/data/digraph.pdf *)

(* Mathematica version http://homepage.cem.itesm.mx/lgomez/data/digraph.nb *)

(* Best regards *)

Needs["Combinatorica`"]

mymatrix = {
{1, 0.10, 0.15, 0.05, 1000},
{0.05, 1, 1000, 1000, 0.05},
{1000, 0.10, 1, 0.15, 1000},
{0.15, 0.05, 1000, 1, 0.20},
{1000, 0.20, 0.05, 0.15, 1}
}

myperm = Permutations[Range[Length[mymatrix]], {2}];
allconnections =
Map[Function[
edge, {edge[[1]] -> edge[[2]], mymatrix[[edge[[1]], edge[[2]]]]}],
myperm];
myconnections = DeleteCases[allconnections, {_, 1000}]

GraphPlot[myconnections, DirectedEdges -> True,
VertexLabeling -> True]

myweights =
Flatten[MapIndexed[
Function[{weight, pos}, {pos, EdgeWeight -> weight}],
mymatrix, {2}], 1]

mygraph = SetGraphOptions[
CompleteGraph[Length[mymatrix], Type -> Directed],
myweights]

myshortestpaths =
Flatten[Table[ShortestPath[mygraph, j, k], {j, 1, 5}, {k, 1, 5}], 1]

myshortestcosts =
Map[Function[{path}, CostOfPath[mygraph, path]], myshortestpaths]

Grid[Transpose[{myshortestpaths, myshortestcosts}], Dividers -> All]

(*Jose*)
(*Mexico*)
User avatar
Jose_Luis_Gomez
 
Posts: 22
Joined: Wed Feb 03, 2010 7:57 pm
Location: Mexico
Organization: ITESM CEM Mexico
Department: Ciencias Basicas

Re: Graph Utilities

Postby Crescenzio_Gallo » Tue May 04, 2010 5:10 pm

Dear Prof Gomez,
thank you very much for the nice arrangement: it works very fine and well, and confirms the way in the meanwhile I tried to solve the problem.

Kind regards,
Enzo Gallo
--
University of Foggia, Italy
Bioagromed Research Centre
User avatar
Crescenzio_Gallo
 
Posts: 2
Joined: Fri Feb 26, 2010 6:23 am
Location: Laboratory for quantitative analisys of data
Organization: University of Foggia
Department: Economics, Mathematics and Statistics


Return to Mathematics and Statistics (Primary/Secondary)

Who is online

Users browsing this forum: No registered users and 0 guests