Intel® Fortran Compiler
Build applications that can scale for the future with optimized code designed for Intel® Xeon® and compatible processors.

Interesting Problem

JohnNichols
Valued Contributor III
1,182 Views

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. 

0 Kudos
14 Replies
JohnNichols
Valued Contributor III
1,179 Views

Windows files for VS 2019

0 Kudos
JohnNichols
Valued Contributor III
1,158 Views

this is the explanation of the code and the problem

0 Kudos
mecej4
Honored Contributor III
1,139 Views

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.

0 Kudos
JohnNichols
Valued Contributor III
1,113 Views

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

 

0 Kudos
JohnNichols
Valued Contributor III
1,112 Views

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

0 Kudos
jimdempseyatthecove
Honored Contributor III
1,082 Views

>>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

0 Kudos
JohnNichols
Valued Contributor III
1,041 Views

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

0 Kudos
JohnNichols
Valued Contributor III
1,034 Views

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 

<And you do not want to use Python> 

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?

 

0 Kudos
JohnNichols
Valued Contributor III
1,033 Views

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

0 Kudos
jimdempseyatthecove
Honored Contributor III
1,030 Views

>>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

0 Kudos
JohnNichols
Valued Contributor III
1,018 Views

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

 

0 Kudos
JohnNichols
Valued Contributor III
1,014 Views

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? 

 

0 Kudos
jimdempseyatthecove
Honored Contributor III
995 Views

>>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

0 Kudos
jimdempseyatthecove
Honored Contributor III
1,026 Views

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

0 Kudos
Reply