alpha041

40 Reputation

4 Badges

8 years, 38 days

MaplePrimes Activity


These are replies submitted by alpha041

@Markiyan Hirnyk 

please explain how.

suppose 1th-level objective function is 3x1+2x2-4y1 and 2th level objective function is 2y1+3x2, and problem has only constraint : x1+x2-y1<=3

how can we solve it in maple?

@Carl Love 

our ampl code is:

restart:

randomize(2): #Needed to get nontrivial minimal paths.

N:= 100:  #Number of vertices

E:= 2300: #Number if directed edges

CartProdSeq:= proc(L::seq(list))

local Seq,i,j;

option `Copyright (C) 2007, Joseph Riel. All rights reserved.`;

    eval({subs(Seq=seq, foldl(Seq

                              , [cat(i,1..nargs)]

                              , seq(cat(i,j)=L[j],j=nargs..1,-1)

                             ))});

end proc:


AllPossibleEdges:= [
     (CartProdSeq([$1..N], [$1..N]) minus
           {seq([k,k], k= 1..N)}
      )[]
]:

Edges:= combinat:-randcomb(AllPossibleEdges, E):

Weights1:= RandomTools:-Generate(list(float(method= uniform), E)):

WeightedEdges1:= {zip(`[]`, Edges, Weights1)[]}:

G1:= GraphTheory:-Graph(WeightedEdges1);

GRAPHLN(directed, weighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100], Array(%id = 18446744074187374710), `GRAPHLN/table/1`, Matrix(%id = 18446744074216096014))

Weights2:= RandomTools:-Generate(list(float(method= uniform), E)):

WeightedEdges2:= {zip(`[]`, Edges, Weights2)[]}:

G2:= GraphTheory:-Graph(WeightedEdges2);

GRAPHLN(directed, weighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100], Array(%id = 18446744074187375070), `GRAPHLN/table/2`, Matrix(%id = 18446744074198802974))

(Path1,Cost1):= GraphTheory:-DijkstrasAlgorithm(G1, 1, N)[];

[1, 31, 52, 58, 54, 14, 100], .199037223686419

(Path2,Cost2):= GraphTheory:-DijkstrasAlgorithm(G2, 1, N)[];

[1, 49, 24, 5, 14, 100], .418737682605255

Path_to_Edges:= proc(P::list)
local k;
     {seq([P[k], P[k+1]], k= 1..nops(P)-1)}
end proc:


PPath1:= Path_to_Edges(Path1);

{[1, 31], [14, 100], [31, 52], [52, 58], [54, 14], [58, 54]}

PPath2:= Path_to_Edges(Path2);

{[1, 49], [5, 14], [14, 100], [24, 5], [49, 24]}

G3:= GraphTheory:-Graph(PPath1 union PPath2);

GRAPHLN(directed, unweighted, [1, 5, 14, 24, 31, 49, 52, 54, 58, 100], Array(%id = 18446744074187376150), `GRAPHLN/table/3`, 0)

ApplyWeights:= proc(G1::GraphTheory:-Graph, G2::GraphTheory:-Graph)
#Apply the weights from G1 to G2.
uses GT= GraphTheory;
local W:= GT:-WeightMatrix(G1, copy= false);
     GT:-Graph(
          map(e-> [e, W[e[]]], GT:-Edges(G2, weights= false))
     )
end proc:          

G4:= ApplyWeights(G1, G3);

G5:= ApplyWeights(G2, G3);

..........................................

but ApplyWeights has no output.

in other words.ApplyWeights does not return G4 and G5 

if it works,please upload the worksheet.

thanks

@Carl Love 

we have:

G1:= GraphTheory:-Graph(WeightedEdges1);

G2:= GraphTheory:-Graph(WeightedEdges2);

so G1 and G2 have the same edges but different weights.

moreover according to:

(Path1,Cost1):= GraphTheory:-DijkstrasAlgorithm(G1, 1, N)[];

(Path2,Cost2):= GraphTheory:-DijkstrasAlgorithm(G2, 1, N)[];

path1's edges set is a subset of G1's edges set and path2 edges set is a subset of G2's edges set. in G3, we want path1 edges and path2 edges have the weights that they have in G1. also in G4, path1 edges and path2 edges should have the weights that they have in G2.

G3 and G4 are defined as below:

G3:= GraphTheory:-Graph(PPath1 union PPath2);

G4:= GraphTheory:-Graph(PPath1 union PPath2);

so if [a,b] be coomon edge in path1 and path2, we have no problem. because [a,b] in G1 has a weight w1 and in G2 has a weight w2.

@Carl Love 

i tried this code
it works.
but G3:= GraphTheory:-Graph(PPath1 union PPath2) isn't a weighted graph. since G3 is union of path1 and path2, we expect that weights of it's edges are weights of edges of ppath1 and ppath2.how can we do this?

 

@Carl Love 

@Carl Love 

Dear Carl love

I sincerely thank you for your guidance

@Carl Love 

Dear Carl love

I sincerely thank you for your guidance

@Carl Love 

link:

http://www.mediafire.com/view/7b4pafbh4wd03aw/MyWorksheet-alpha041.mw

@Carl Love 

Dear Carl love

Unfortunately GraphTheory:-Graph({Path1[], Path2[]}); does not work.

this error was shown:

Error, (in GraphTheory:-Graph) invalid argument

Hi

i have two questions about paths in graph package:

1. suppose we have:

path1=[1,3,5,7,9]

path2=[1,2,3,6,7,8,9]

if we want to create a graph that it's edges are edges of path1 and edges of path2,how can we do this?

edge set of our graph should be {[1,3],[3,5],[5,7],[7,9],[1,2],[2,3],[3,6],[6,7],[7,8],[8,9]}

2. suppose p is an arbitrary path on a given weighted graph G

how can i calculate weight of p (that is sum of it's edges weights) in maple ?

thanks very much for your help

@Carl Love 

thanks dear Carl love

please also answer this questions:

in your code,i want to create a subgraph of G that contains only edges on path 1 and path 2 (path 1 is minimal cost path with weights w1 and path 2 is minimal cost path with weights w2),how can i do this?

i trid GG := GraphTheory-Graph(Path1 union  Path2) but error was shown.

Page 1 of 1