7
$\begingroup$

I know this is a longshot, and it's a rather broad question, but hopefully someone can help. Is there a simple or fast way to find Steiner Trees for unit polygons using Mathematica? By unit polygon, I mean a polygon with side lengths of 1.

I can't hypothesize a simple method for approximating Steiner trees so any help is greatly appreciated. For reference, the Steiner tree solutions for a unit square looks like so:

Steiner tree

$\endgroup$

2 Answers 2

6
$\begingroup$

Take a look at GeoSteiner v5.1 which is available for free download at http://www.geosteiner.com. It is generally considered to be the best solver of these problems available. I have been working on trying to compile it on my Mac so that I could then call it from within Mathematica. Unfortunately, I keep getting a couple of compiler errors which seem to be related to the Mac's standard implementation of libtools.

I myself would be very interested to know if anyone has successfully complied GeoSteiner on the Mac and, if so, how did they do it? It would be great to have this powerful software accessible within Mathematica.

Update

With some very kind help from Szabolcs I was able to get GeoSteiner working on my Mac. In the hope it may help someone else here is how I did it:

To install GeoSteiner on a new system proceed as follows:

  1. Install Xcode from the Mac App Store.

  2. Install Command Line Tools by executing the following from Terminal:

    xcode-select -install
    
  3. Accept the Xcode license by executing the following from Terminal:

    xcodebuild -license
    
  4. Download the MacPorts package file that applies to your version of OS X and install it by double-clicking on the package.

  5. Install libtool from MacPorts by executing the following from Terminal: sudo port install libtool

  6. Quit and restart Terminal. Execute the following from Terminal to verify that GeoSteiner works:

    ./configure
    make
    ./demo1
    

To periodically update MacPorts execute the following from Terminal:

sudo port selfupdate

Followed by:

port upgrade outdated
$\endgroup$
2
  • $\begingroup$ I had no problems compiling it with ./configure and make on macOS 10.13.5. $\endgroup$
    – Szabolcs
    Commented Jun 3, 2018 at 13:19
  • $\begingroup$ Any idea how to do this on windows? Been trying, but can’t get it to work $\endgroup$
    – Joseph Eck
    Commented Jun 8, 2018 at 4:44
2
$\begingroup$

After nearly 4 years I had occasion to again compile GeoSteiner 5.1. I'll publish how I got it working on the Mac in the hope it may help someone else.

Proceed as follows on Mac Monterey 12.3.1:

  1. Install Xcode from the Mac App Store.

  2. Install Command Line Tools by executing the following from Terminal: xcode-select —install

  3. Accept the Xcode license by executing the following from Terminal: xcodebuild -license

  4. Over a year ago I switched from MacPorts to Homebrew. I already had glibtool installed on my system so I didn’t need to bother with installing it again. You may need to install it.

  5. Download geosteiner-5.1.tar from the GeoSteiner website and unzip the tarball in a directory. This will become your build directory and GeoSteiner will be run from this location without being globally installed on the system. See the GeoSteiner documentation if you want the software to be globally accessible.

  6. Copy “lpkit.h” and “hash.h” in the “lp_solve_2.3” subdirectory and paste them into the build directory.

  7. Add #include <sys/time.h> to the start of the file prng_aes256.c in the build directory.

  8. Run the following two commands from inside the build directory using terminal: ./configure make CFLAGS=-Wno-error

The GeoSteiner software should compile without any error messages. You may get a warning about comparing a pointer to a null character constant, but this can be ignored. Test with the command: ./demo1

You can access the output from GeoSteiner from Mathematica using: RunProcess[$SystemShell, All, ...]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.