Scala for (i <- 0 to n) : nice but slow

I was playing around with prime numbers when I noticed that one of the implementations was several times faster than the other one.

Benchmarking the two implementations soon showed that the differences lies mainly in using the nicer

for (i <- 0 to count) {
  // does something here
}

instead of the uglier

var i = 0
while (i < count) {
  // does something here
  i += 1
}

Here the benchmark results for the two loops (running on a 2.7 GHz Intel i7):

Benchmark results of for(i

Looks like the for loop is about 8 times slower than the while loop.

I will still use the for loop where speed does not matter, since it is more concise, but where speed matters I will use the while loop until further notice.

Posted in Development, Scala | Leave a comment

Android Wiki Spiderweb 2.0 released

Version 2.0 of the Wiki Spiderweb application for Android has been released on the Android Market.

Changes in 2.0:

  • Show images from Wikipedia as nodes.
  • Show preview images in search results.
  • Visited connections turn blue.
  • Hide keyboard after search.

Posted in Android, Applications | Leave a comment

Use app version to show a dialog only after update

I decided to enhance my Android app so that it will show a little dialog with the newest features after starting.

If this dialog would show up after every start it would be very annoying.

The goal is to show it only when the user has just installed the app for the first time or after the app was upgraded to a newer version.

The solution is very simple:

  1. Get the current version of the app.
  2. Compare with the last version that the user has accepted.
  3. Show dialog if current version is newer.
  4. Store current version as accepted.

Storing the accepted version in the SharedPreferences is very easy.

Getting the current version of the app is also easy, but it can be difficult to find out how to do it.
The API is somewhat hidden – you ask the package manager to give the PackageInfo and there you can access the current versionName.

Here is a snippet of the code from the onCreate() in my main activity.

	try {
		PackageInfo packageInfo = getPackageManager().getPackageInfo(getPackageName(), 0);
		String currentVersion = packageInfo.versionName;
		SharedPreferences sharedPreferences = PreferenceManager.getDefaultSharedPreferences(this);
		String acceptedVersion = sharedPreferences.getString("pref_acceptedVersion", "");
		if (currentVersion.compareTo(acceptedVersion) > 0) {
			Editor edit = sharedPreferences.edit();
			edit.putString("pref_acceptedVersion", currentVersion);
			edit.commit();
			showMessage(this, getResources().getString(R.string.new_version_message, currentVersion));
		}
	} catch (NameNotFoundException e) {
		e.printStackTrace();
	}

showMessage() is a simple static method that shows a dialog.

	private static void showMessage(Context context, int messageId) {
		showMessage(context, context.getResources().getString(messageId));
	}
	
	private static void showMessage(Context context, String message) {
		new AlertDialog.Builder(context)
		.setMessage(message)
		.setPositiveButton(R.string.ok, new DialogInterface.OnClickListener() {
			@Override
			public void onClick(DialogInterface dialog, int which) {
				dialog.dismiss();
			}
		})
		.show();
	}
Posted in Android, Java, Tips and Tricks | Leave a comment

Android Wiki Spiderweb 1.5 released

Version 1.5 of the Wiki Spiderweb application for Android has been released on the Android Market.

Changes in 1.5:

  • Double tap the empty space to zoom until all nodes fit on the screen.
  • Improved zooming gesture to avoid occasional jumps.
  • Fixed broken help.
  • Fixed selecting nodes from wikipage preview links.

Changes until 1.4:

  • Improved Search to show short description of matching pages.
  • Show entire wikipedia page in preview.
  • Support wider range of screen sizes.
  • Minor bug fixes.

Posted in Android, Applications | Leave a comment

Make an App available on Android 1.5 and small screen

I have always published my simpler Android applications for all Android devices version 1.5 and higher.

I thought this would allow the application to run on the maximal number of devices.

Recently I bought a new Android phone for testing: Huawei U8180 X1 (branded as Orange Stockholm) with Android 2.2.2

To my surprise many of my simpler applications where filtered out on the Android market.
Why?

The explanation for this strange behavior is that the Huawei U8180 has a very small screen but Android 1.5 did not support small screen sizes.
Support for small screens was added with Android 1.6.

How can I make an application run on 1.5 but also on small screens?

The solution is simple:

  1. Switch your application to compile against Android 1.6
  2. Declare the minSdkVersion to be 3 (= Android 1.5)
  3. Declare the targetSdkVersion to be 4 (= Android 1.6)

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
      package="com.example.simpleapp"
      android:versionCode="1"
      android:versionName="1.0">

    <uses-sdk
            android:minSdkVersion="3"
            android:targetSdkVersion="4"
    />

After uploading the APK file to the Android Market you see the following information:

API level: 3-14+
Supported screens: small-xlarge

My Huawei phone can now download the app without problema.

The API you are developing against is now Android 1.6, so you have to be careful to not use any API parts that did not yet exist in 1.5.
One trick to do this is to initially develop against 1.5 and switch only at the end to 1.6.

Posted in Android | Tagged , , , , , | Leave a comment

How Scala influenced my Java Programming

For a while I have been experimenting in my free time with Scala.

While I don’t believe that I will use Scala at work in the near future I have nevertheless noticed that
Scala has changed the way I think in Java.

Immutables

Since Josh Bloch’s fantastic book Effective Java I have used more and more immutable classes in Java

Scala has really driven home this lesson.

Immutables are great for several reasons:

  • guaranteed thread-safe
  • stable hashCode(), so they never get lost in a Set or Map
  • real encapsulation of the data they contain

Since I am a lazy programmer they really come in handy because once they are written I can forget about them.
They will just work.

In Java you have to be a bit careful to make sure that the class is really immutable.
Here the main points:

  • All fields are final
  • The class is final (or all constructors are private)
  • Constructor must copy arguments that are not immutable (e.g. arrays, collections, maps) before assigning them to fields
  • Never give out references to mutable fields (again arrays, collections, maps)
  • make sure that serialization does not break the immutability (for perfectionists)

For good immutable collections I recommend Google Guava.

Tuples

Scala tuples are very handy in a couple of places.

  • methods that need to return multiple values
  • storing composite values in a collection or map
  • grouping several values in an API, but not important enough to make them a separate class (danger: slippery slope!)

In Java it was easy to implement tuples in a type-safe manner.
It is not possible to completely hide the details in the same way that Scala does, but with static imports we can get pretty close.

We will need a few classes for tuples with 2, 3 or more elements.

// Java example implementing a tuple (with 2 elements)
public final class Tuple2<T1, T2> implements Serializable {

	private static final long serialVersionUID = 0L;

	private final T1 value1;
	private final T2 value2;

	public Tuple2(T1 value1, T2 value2) {
		this.value1 = value1;
		this.value2 = value2;
	}

	public T1 getValue1() {
		return value1;
	}

	public T2 getValue2() {
		return value2;
	}

	@Override
	public int hashCode() {
		int hash = 7;
		hash = 31 * hash + (value1 == null ? 23 : value1.hashCode());
		hash = 31 * hash + (value2 == null ? 23 : value2.hashCode());
		return hash;
	}

	@Override
	public boolean equals(Object object) {
		if (object == this) {
			return true;
		}
		if (!(object instanceof Tuple2)) {
			return false;
		}

		Tuple2<?, ?> other = (Tuple2<?, ?>) object;
		return (value1 == null ? other.value1 == null : value1.equals(other.value1)) &&
			(value2 == null ? other.value2 == null : value2.equals(other.value2));
	}

	@Override
	public String toString() {
		return "(" + value1 + "," + value2 + ")";
	}
}
// Java example constructor methods to create tuples
public class Tuples {
	public static <T1, T2> Tuple2<T1, T2> tuple(T1 value1, T2 value2) {
		return new Tuple2<T1, T2>(value1, value2);
	}
	public static <T1, T2, T3> Tuple3<T1, T2, T3> tuple(T1 value1, T2 value2, T3 value3) {
		return new Tuple3<T1, T2, T3>(value1, value2, value3);
	}
}
// Java example using tuples
import static com.example.tuple.Tuples.tuples;
import com.example.tuple.Tuple2;

public class TupleExample {
	public static Tuple2<String, Integer> doSomething() {
		return tuple("Hello", 999);
	}

	public static void main(String[] arguments) {
		Tuple2<String, Integer> t = doSomething();
		System.out.println(t);
	}
}

Please notice that tuples are immutable (if the contained values are immutable).

Internal DSLs

In Scala it is easy to write what some people call internal DSLs.

In Java you are somewhat limited, but fluent APIs are a thrust in the same direction.
Together with builder pattern und static imports you can get rid of a lot of boilerplate code.

A nice example is the new API to specify grid data layout in SWT:

	// Java Fluent API Example (GridDataFactory for SWT)
	GridDataFactory.fillDefaults().grab(true, true).hint(150, 150).applyTo(listBox);

Here is another code snippet to show how static imports can give you a DSL.

// Java static methods for Expression classes
// Expression classes not shown
public class Expressions {
	public static AndExpression and(Expression... expressions) {
		return new AndExpression(expressions);
	}
	public static OrExpression or(Expression... expressions) {
		return new OrExpression(expressions);
	}
	public static NotExpression not(Expression expression) {
		return new NotExpression(expressions);
	}
	public static EqualExpression equal(Expression left, Expression right) {
		return new EqualExpression(left, right);
	}
	public static EqualExpression equal(String variableName, Expression right) {
		return new EqualExpression(var(variableName), right);
	}
	public static EqualExpression equal(String variableName, int value) {
		return new EqualExpression(var(variableName), val(value));
	}
	public static EqualExpression equal(String variableName, int value) {
		return new EqualExpression(left, right);
	}
	public static IntegerValue value(int value) {
		return new IntegerValue(value);
	}
	public static VariableValue var(String variableName) {
		return new VariableValue(variableName);
	}
}
	// Java static imports
	import static com.example.Expressions.*;

	private static Expression ex1 = and(equal(var("x"), value(5)), not(equal(var("y"), value(6))));
	private static Expression ex2 = equal(var("x"), value(5));
	private static Expression ex3 = equal("x", value(5));
	private static Expression ex4 = equal("x", 5);

Until closures in Java 8 have arrived we will still need to write anonymous subclasses in Java if we want to
specify executable code. This severely limits the possibilities for nice DSLs in Java.

Funnily coding in Scala has trained my eyes to (somewhat) ignore the clutter from anonymous subclasses and only look at the relevant code.

	// Scala example to convert a list of integer values into a list of strings
	List(111, 222, 333) map("X" + _)
	// Java example to convert a list of integer values into a list of strings
	// static methods in Converters and interface Converter not shown
	List<Integer> integerList = Arrays.asList(111, 222, 333);
	List<String> stringList = Converters.convert(integerList, new Converter<Integer, String>() {
		@Override
		public String convert(Integer source) {
			return "X" + source;
		}
	}));

If you squint your eyes really hard it looks almost the same, doesn’t it?

In Java 8 this will look (probably) something like this:

	// Java example to convert a list of integer values into a list of strings (using closure)
	// static methods in Converters and interface Converter not shown
	List<Integer> integerList = Arrays.asList(111, 222, 333);
	List<String> stringList = Converters.convert(integerList, (v => "X" + v));

Functional programming

If you have written Java (or another imperative langague) for a long time you probably have some difficulty adjusting to the functional way of doing things.
I certainly do.

But you don’t have to become a tail-recursion fanatic to gain something valuable from the functional programming approach.

Especially if your code must be thread-safe it is very useful to remember one detail about functions:

If your method only looks at its arguments to calculate a return value it is absolutely thread-safe!

This sounds obvious but it is surprising how often people forget this.

Here the check-list whether your method is a pure function:

  • no access to any fields
  • no calls to other methods (except if they are pure functions)
  • arguments must be immutable or not shared between threads

Pure functions are the executable equivalent of immutable data structures.
Easy to write and easy to reason about.

Posted in Development, Java, Scala | Tagged , , , , , , , , | Leave a comment

Android Invasion Published

The free Invasion application for Android has been published on the Android Market.

Thanks to all the encouraging feedback and enthusiastic testers: Adrian, Thomas, Irena

Posted in Android, Applications | Tagged , , , | Leave a comment

Managing Android Applications with Library Projects

It can be quite challenging to develop an Android application that should be published in several versions on the Android Market.

The main reason for this is the strange and unpredictable way that Android library projects work in Eclipse.

The official documentation explains how to setup library projects
but it does not explain all the quirks and workarounds needed to make them actually work in a real world application.

Another trap is the Proguard integration, which does not work if you have spaces in the path of your Eclipse projects.

Quirk – No Spaces
Make sure there are no spaces in the path to the workspace or the names of the projects.
Proguard (which you really should use to obfuscate your application before publishing) is integrated using a batch file and the batch file does not work correctly with spaces in the path.

Step 1 – Split your project into library and application parts

You probably want to reuse some of the code between projects, so you should create one or more library projects.

It would be easy to create one big library for all your reusable code, but then you would have to depend on the highest Android version which in turn would limit the handsets that your final application can run on.

Because of this I created not one library but several libraries for the different versions of Android.

I currently have the following library projects:

  • AndroidLicensing library project as described in the Android Licensing Guide
  • AndroidLib-1.5 library project with reusable classes – depending on Android 1.5
  • AndroidLib-2.1 library project with reusable classes – depending on Android 2.1 and AndroidLib-1.5

Quirk – Adding library dependencies to a library does not update in all projects
When you add a new library dependency to one of your library projects the dependencies from the application projects are not updated.
Workaround: Remove library dependency in your application project and add it again.

Step 2 – Write the application

Now you write the real application and need a new project for it.

Variant 1 – Library Project from the beginning

This is the cleaner variant.

From the start I create this project as a library project and fill it with the application code.

In order to run it we will need to do step 3 immediately.

Variant 2 – Application Project first and then convert it into a Library Project

This is the variant if I do not yet know in how many forms I want to publish the application on the market or if I already have a running application project.

In this case I make it an application project and develop it normally until I decide to proceed to step 3.

Before we go to step 3 simply convert the project into a library project.

Step 3 – Create one application project for every variant on the Market

First you have to have to think how many different deployment types of your application you want to publish on the market.
If you only want to publish the free version it doesn’t matter anyway, but if you plan for a paid version you probably need to decide.

Here is the terminology I use:

  • Pro is the paid version with full features.
  • Demo is the demo version with a few features disabled.
  • Ad is the free version that shows advertisements – it might contain all features of the Pro version or it might limit the functionality a bit.
  • Free is the free version with full features.

It is well worth to think about what you want to achieve by providing several deployment types.

  • The Demo version should have enough limitations so that users are urged to buy the Pro version but not so annoyed that they will simply delete your application.
  • The Ad version should (partially) compensate the lost sales by ad click payments and still incentivate the users to buy the full version.

Here is the example that I am going to use for the rest of this tutorial:

  • MyApplication library project containing the application code – depends on some of the other library projects
  • MyApplicationPro application project – depending on MyApplication
  • MyApplicationDemo application project – depending on MyApplication

Step 4 – Distribute resources and assets between projects

The resources and assets must be distributed between the library projects (especially where your application code lives) and the application projects.

Distribute resources

Feature – Resources are merged from libraries
The various resources found in library and application projects are correctly merged. Even single values (e.g. strings) from application projects override default values in the library projects correctly.

The application projects should not contain any resources that you already have in your library projects.

If you generated the application projects with the Eclipse wizard you probably have some string resources (app_name and hello) and a drawable (icon).
Delete them.

Then copy only the resources you want different for each deployment into the application projects.

The files for the MyApplication example look like this:

If you use custom XML attributes you are in for a bad surprise:

Quirk – Custom XML attributes
For some reason custom XML attributes specified in libraries do not work correctly and are parsed with the namespace of the application project.
This is rather painful. The only workaround is to copy all the XML files that use the custom XML attributes into all application projects and change the namespace.
In my applications these are typically a layout XML files so I have to several duplicates.

This is an example layout file with custom XML attributes for the Pro application project.

<?xml version="1.0" encoding="utf-8"?>
<-- MyApplication Pro - xmlns:example points to 'pro' package -->
<org.obermuhlner.android.lib.ExampleView
    xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:example="http://schemas.android.com/apk/res/ch.obermuhlner.android.myapplication.pro"
    android:id="@+id/exampleView"
    android:layout_width="fill_parent" 
    android:layout_height="fill_parent"
    example:my_text="Hello World"
    example:my_value="123"
    >

This is an example layout file with custom XML attributes for the Demo application project.

<?xml version="1.0" encoding="utf-8"?>
<-- MyApplication Demo - xmlns:example points to 'demo' package-->
<org.obermuhlner.android.lib.ExampleView
    xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:example="http://schemas.android.com/apk/res/ch.obermuhlner.android.myapplication.demo"
    android:id="@+id/exampleView"
    android:layout_width="fill_parent" 
    android:layout_height="fill_parent"
    example:my_text="Hello World"
    example:my_value="123"
    >

Unfortunately I am now forced to maintain two copies of the XML file.

Distribute assets

Quirk – Assets are not merged from libraries
Asset files are only taken from the application project, assets in library projects are ignored.
The only workaround is to copy the assets into all application projects.

Clean AndroidManifest.xml

Quirk – AndroidManifest.xml is not merged from libraries
AndroidManifest.xml files from library projects are not merged with application projects.
Each AndroidManifest.xml in an application project needs to be complete. This will lead to some duplication.

Actually it makes sense to ignore the AndroidManifest.xml from library projects, because you might want to deploy the application on very different devices with different permissions, version and maybe even launching different activities.

A typical AndroidManifest.xml in the application library project looks like this:

<-- MyApplication - main library application -->
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
      package="ch.obermuhlner.android.myapplication"
      android:versionCode="3"
      android:versionName="1.2">
    <uses-sdk android:minSdkVersion="7" />

</manifest>

A typical AndroidManifest.xml in the Pro application project looks like this:

<-- MyApplication Pro -->
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
      package="ch.obermuhlner.android.myapplication.pro"
      android:versionCode="3"
      android:versionName="1.2">
    <uses-sdk android:minSdkVersion="7" />

    <uses-permission android:name="android.permission.READ_PHONE_STATE" />
    <uses-permission android:name="com.android.vending.CHECK_LICENSE" />

    <application
    	android:icon="@drawable/icon"
    	android:label="@string/app_name">
        
        <activity
            android:name="ch.obermuhlner.android.myapplication.ExampleActivity"
            android:label="@string/app_name">
            
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />
                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>        
    </application>
</manifest>

A typical AndroidManifest.xml in the Demo application project looks like this:

<-- MyApplication Demo - no permissions for license checking -->
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
      package="ch.obermuhlner.android.myapplication.demo"
      android:versionCode="3"
      android:versionName="1.2">
    <uses-sdk android:minSdkVersion="7" />

    <application
    	android:icon="@drawable/icon"
    	android:label="@string/app_name">
        
        <activity
            android:name="ch.obermuhlner.android.myapplication.ExampleActivity"
            android:label="@string/app_name">
            
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />
                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>        
    </application>
</manifest>

Your free application should not ask for CHECK_LICENSE, since you want to ask for the minimal permissions that your application needs.
The Android Market will not allow to publish a free application with CHECK_LICENSE permission.

Step 5 – Check the deployment type in the application code

Obviously the application should behave differently depending on the deployment type.

The following code snippet shows how to check the unique id of your application since Android 1.6:

	public static boolean isDemo(Context context) {
		// check application package name in Android 1.6 and later
		return context.getApplicationInfo().packageName.endsWith("demo");
	}

In Android 1.5 the Context.getApplicationInfo() method does not yet exist.

I am still looking for the best workaround in Android 1.5.
For the time being one trick I found was to use a resource with different values in the different deployments:

	public static boolean isDemo(Context context) {
		// check a resource in Android 1.5
		return context.getResources().getInteger(R.integer.magicValue)  == 1;
	}

Another trick involves providing a Java class which only exists in the Demo application and checking it using reflection:

	public static boolean isDemo(Context context) {
		try {
			// make sure the class ch.obermuhlner.android.myapplication.demo.DemoConfig is not obfuscated by proguard
			Class<?> clazz = Class.forName("ch.obermuhlner.android.myapplication.demo.DemoConfig");
			return clazz != null;
		} catch (ClassNotFoundException e) {
			return false;
		}
	}

Step 6 – Test really well

It is difficult to get everything right because the behaviour of library projects is so unpredictable.

Here a little check list:

  • Check pro/demo functionality differences in all deployed versions
  • Check application name and icon in all deployed versions
  • Check resources, such as translated strings in all deployed versions
  • Check assets, such as HTML help files or images in all deployed versions
  • Check licensing behaviour in all deployed versions
  • Create signed and obfuscated application package for all deployed versions
Posted in Android, Development | Tagged , , , | Leave a comment

Using Force-Based Graphs

This is a collection of my experiences using force-based algorithms to draw graphs.

I used this algorithm in the Wiki Spiderweb application.

Here the good points:

  • Easy to implement
  • Natural looking results
  • User interaction is possible
  • Some influence of placement of nodes

Here the problem areas:

  • Computationally intensive: O(n^2)
  • Layout can become jittery and unstable (at least my implementation that uses real elapsed time for the iterations)
  • Difficult to avoid overlapping nodes
  • Nodes can end up very close to each other

Easy to implement

This is the basic implementation:

	public boolean simulate(float time) {
		for (Node node1 : nodes) {
			for (Node node2 : nodes) {
				if (node1 == node2) {
					continue;
				}
				
				float distanceSquare = getDistanceSquare(node1, node2);
				
				float deltaX = node1.x-node2.x;
				float deltaY = node1.y-node2.y;
				
				node1.forceX += repulsionForce * deltaX / distanceSquare;
				node1.forceY += repulsionForce * deltaY / distanceSquare;
			}
		}

		for (Connection connection : connections) {
			float deltaX = connection.node2.x - connection.node1.x;
			float deltaY = connection.node2.y - connection.node1.y;

			float attractionX = attractionForce * deltaX;
			float attractionY = attractionForce * deltaY;

			connection.node1.forceX += attractionX;
			connection.node1.forceY += attractionY;

			connection.node2.forceX += -attractionX;
			connection.node2.forceY += -attractionY;
		}

		boolean moving = false;
		for (Node node : nodes) {
			node.speedX = minAbs(MAX_SPEED, (node.speedX + node.forceX) * damping);
			node.speedY = minAbs(MAX_SPEED, (node.speedY + node.forceY) * damping);
			
			if (node.speedX > NOT_MOVING_THRESHOLD || node.speedY > NOT_MOVING_THRESHOLD) {
				moving = true;
			}

			if (!node.drag && !node.fix) {
				node.x += node.speedX * time;
				node.y += node.speedY * time;
			}

			node.forceX = 0;
			node.forceY = 0;
		}
		
		return moving;
	}

In the Wiki Spiderweb application I have a few modifications to this basic algorithm.
All of these changes modify the repulsion/attraction functions to adapt for some concrete issues I had with small screen estate, overlapping nodes, …

Natural looking results

This is of course a personal opinion, but I like the organic looking results and find the aesthetically pleasing.

Interactive

Since the algorithm is iterative it is easy to implement interaction with the graph as it moves the nodes around.

First we render the nodes after every iteration of the algorithm.
This turns the graph into a dynamic and not something that just presents a final result.

Second we allow the user to drag nodes around.
The algorithm will simply continue to move the other nodes around, which results in a natural looking dragging of the connected nodes.

Some influence of placement of nodes.

The client code does not have much influence about the actual placement of nodes.

One of the few things it can control is the initial placement of new nodes.

In the Wiki Spiderweb application new nodes are initially placed at a random location close to the parent node.
Since they are all very close to each other the new nodes will have a strong repulsion force, which leads to an explosion effect where the new nodes look like an expanding cloud.
The central parent node tends to move very little, since it is equally repulsed from all its child nodes.
Already existing nodes are pushed outwards by the expanding cloud of new nodes.

The current implementation simply randomizes the x,y coordinates inside small boundaries.
The new nodes are therefore initially placed in a small square. This is actually noticeable if there are enough new nodes.
To improve this the new nodes could be placed randomly inside a circular radius instead of a square region.

If the new nodes are of different types (I am planning to add images and grouping nodes for chapters in the Wiki application) it would be possible to place the new nodes
grouped by type.

Computationally intensive: O(n^2)

The basic algorithm is square and the only optimization possible is to make n as small as possible.

The obvious way to do this is to sort the nodes into groups and only run the algorithm with nodes close to each other.

I plan to sort the nodes into quadrants and let the nested loops of a single quadrant iterate over the 8 neighbor quadrants.
If the forces of far away nodes are considered important, the nodes of each quadrant could be aggregated into a single node and only this node would be used for the repulsion function.

Layout can become jittery and unstable

At least my implementation that uses real elapsed time for the iterations shows this behavior.

Adaptive cooling would probably solve this issue.

Difficult to avoid overlapping nodes.

The algorithm treats nodes as points without size.
But in reality I want to show text or images in the nodes, so many of them will overlap each other.

I attempted several modifications of the algorithm to avoid overlapping nodes but was not happy with the results.
These modifications tried to make the repulsion function aware of whether any nodes where overlapping.
Unfortunately did lead to unstable local minimas, so that the graph became jittery and did not find a stable solution.
Maybe a smarter function without any discontinuities would work.

I also plan to investigate the PRISM algorithm as soon as I have time.

Nodes can end up very close to each other.

Graphs with many interconnected nodes can end up with some nodes being forced very close to each other.

Posted in Development | Tagged , , , | Leave a comment

Android Wiki Spiderweb Trial 1.1 released

The free trial version 1.1 of the Wiki Spiderweb application for Android has been released on the Android Market.

This allows to experiment with the application without having to spend money.

Only the Search functionality that is not available in the trial version.

You can still manually set the Start Page in the Settings if you want to look at another starting point.

Posted in Android, Applications | Tagged , , , | Leave a comment