topic Re: Interesting Problem in Intel® Fortran Compiler

Interesting Problem

JohnNichols — Sat, 16 Jan 2021 18:00:55 GMT

For reasons that are lost to me, I stumbled across ACM Algorithm 787. It is a solution to clique cover problems. Interestingly the .gz file at ACM is corrupt but I found another source.

This is a sample of the math problem of P-NP.

So I downloaded it and it compiles nicely VS 2019 Preview, although interestingly the latest preview will no longer search for fortran files in the complete solution. Another day.

Interestingly the input statement is

c ------------------------------------------------------------------ c c Input/output device numbers passed to iniprt, gmis, outsol: c c in - input device c out - output device c c ------------------------------------------------------------------ integer in,out parameter (in=5,out=6) c ------------------------------------------------------------------ c

The program was clearly written and compiled on Linux machines.

Ok, so if memory from Uni in 1978 serves me correctly 5 is the keyboard and 6 is the screen.

Anyway here are the for and the data file. It is an interestingly little problem.

I need to fix the input, when I get back from being a responsible parent for the morning.

I thought it was of interest.

Re: Interesting Problem

JohnNichols — Sat, 16 Jan 2021 18:02:18 GMT

Windows files for VS 2019

Re: Interesting Problem

JohnNichols — Sat, 16 Jan 2021 20:21:36 GMT

this is the explanation of the code and the problem

Re: Interesting Problem

mecej4 — Sun, 17 Jan 2021 12:22:59 GMT

There are nearly six hundred such packages in the TOMS directory at NETLIB . I do not know why No. 787 is of more interest to you than any of the others.

The holdings there have diverse formats. Many Unix/Linux users would have used some file packaging utility to pack all the directories pertaining to their package and the contents of those directories. One such file packaging utility was the Shell Archive . The following commands in Linux (or a Cygwin shell on Windows) will unpack the archive, compile the sources, run the program and compare the output to the reference output.

gzip -d 787.gz unshar 787 cd Fortran77/Drivers/Sp gfortran driver.f ../../Src/Sp/src.f ./a.out < data > RESn diff -w RES RESn

There are some bugs in the Shar directives in the file, but these do not matter much since there are only two source files to compile and a makefile is not needed for such a simple task.

Re: Interesting Problem

JohnNichols — Sun, 17 Jan 2021 18:58:29 GMT

Interesting challenges in your comments.

1. I studied graph theory at the Australian National University in the 1970s and enjoyed it, although without computers it was not that easy to study. The difference is reading using a candle and having an Alexa read to you. She has a nice voice. My professor was fun and this looked like a bit of fun == are we allowed fun in Fortran

2. I am working on a proposal at the moment that looks to define the minimum information flow to run a transportation network. This is not a simple exercise and as about 100000 people are involved it is about as easy as Overlord

3. P-NP is an interesting Millennial Problem and this is a modest and interesting sample, trying to explain graph theory to non-math people on Friday was interesting, so that started the look

4. It was interesting and I thought you lot might like the problem - although we are the Intel Fortran Forum - we actually can do good in the world - aka Tommy Raskin

5. A sense of humour

6. Being asked on Saturday did we need to get 300 GB a month download capacity for 0.1GB per day on average and 5 GB once per month

7. it looked fun -- and I had not seen the Unix unzip procedure before. I will use Unix and Linux but that does not mean I have to like it.

8. I thought you might be interested - per chance I was wrong

Re: Interesting Problem

JohnNichols — Sun, 17 Jan 2021 19:00:09 GMT

I was interested also because it does not have graphical output and I wanted to see the visual answers.

Re: Interesting Problem

jimdempseyatthecove — Mon, 18 Jan 2021 16:12:22 GMT

>>2. I am working on a proposal at the moment that looks to define the minimum information flow to run a transportation network. This is not a simple exercise and as about 100000 people are involved it is about as easy as Overlord

The above statement is somewhat ambiguous:

1) Is this centralized control?
2) Is this distributed control?
3) Are there private shippers
4) Are there wholly own shippers
5) Is it a push scheduling (central system selects shippers).
6) Is it a pull scheduling (select shippers bid on shipping)
7) ...

Transportation networks are not typically NP as most routes could quickly be excluded (ship small package from Brisbane to Perth by canoe). Also, while a package ends up going point-to-point, the actual route is something like point-to-distrubutioncenter-to-distributioncenter-to-point. IOW you may have an (N/100000)P problem.

Jim Dempsey

Re: Interesting Problem

JohnNichols — Wed, 20 Jan 2021 18:12:32 GMT

The proposal is interesting, it is essentially about CAT data in the development of the driverless cars is the worst extension.

The problem is there are many variatons on the theme

Intel Fortran is one solution to part of the problem

Re: Interesting Problem

JohnNichols — Wed, 20 Jan 2021 19:21:34 GMT

There is a lot of work going on looking at the interaction of driverless cars and the surrounding environment.

We have been doing some work with monitoring on bridges and getting useful information out of the bridge.

With so many people involved all around the world, it is a challenge to watch the evolution of standards, luckily the automobile industry does have a sound driving influence.

In terms of this algorithm, it is interesting for one of the problems I have been thinking about. You have a driverless car and someone in it collapses, and there is also a young child in the car. Ultimately we want to get them to safety - ie hospital and not stop a car on a highway so a worried child climbs out of the car and gets killed. if you are the driverless system developer your responsibility level is a lot higher than - there is your bicycle go ride it. So the train control for the Channel Tunnel is going to want a death rate not much higher than 1 in a million incidents.

So if you think in network terms in Fortran

first type needed is a node or vertex - and the second type needed is a edge or path - what is the next type -- there are two potential programs you want to link this to - VISSIM or SUMO

Now think of the million things that happen every day on the world's roads and how do you code for it?

Also where do you do the analysis - in the car at the edge of the system or deep in the heart of the system. -- My initial though is to push for edge computing, so to solve an NP problem divide it into many problems and prove it is solvable

Now you have a computer system controlling say 100 million cars in the USA in a morning -- carrying say 150 million people, let us be a bad guy and crash the system?

Re: Interesting Problem

JohnNichols — Wed, 20 Jan 2021 19:23:36 GMT

if I want to solve this problem, of the six people I want to talk to , five of them are on this board.

Re: Interesting Problem

jimdempseyatthecove — Wed, 20 Jan 2021 19:58:06 GMT

>>Now you have a computer system controlling say 100 million cars in the USA

Autonomous control is better.

>>first type needed is a node or vertex - and the second type needed is a edge or path - what is the next type

You may need influences, things external to the mesh that affect path selection. E.g. fire, congestion, ice, beautiful sunset view, fuel, food, charging station, ... It is not just vertex and edge.

Jim Dempsey

Re: Interesting Problem

jimdempseyatthecove — Wed, 20 Jan 2021 20:08:01 GMT

RE: route planning (traveling salesman) type of problem.

I'd suggest setting up the simulation (control program) as if the paths were pneumatic tubes, and the intersections were manifolds connecting the tubes. IOW this becomes a fluid dynamics type of problem. You pressurize the start point, leaving only the desired end point as the exit, then observe which path the fluid predominantly flows. To reduce calculations, the "fluid" could be synthesized as balloons or bubbles within the system. Each path could accommodate only a few.

Jim Dempsey

Re: Interesting Problem

JohnNichols — Wed, 20 Jan 2021 20:59:38 GMT

We have to start somewhere - and I think you just proved my point about this forum.

Re: Interesting Problem

JohnNichols — Wed, 20 Jan 2021 21:14:30 GMT

https://sumo.dlr.de/docs/Developer/CodeStyle.html#templates

if we have a C++ template for use in Visual Studio with this program SUMO - can we use fortran DLL with the C++ template as the linking part?

Re: Interesting Problem

jimdempseyatthecove — Thu, 21 Jan 2021 14:30:24 GMT

>>if we have a C++ template for use in Visual Studio with this program SUMO - can we use fortran DLL with the C++ template as the linking part?

As long as the routines called use BIND(C)/extern "C"

And you follow other recommendations/requirements for interoperability between C and Fortran.

Programming with Mixed Languages Overview (intel.com)

Jim Dempsey