CODEWITHSUNDEEP
algorithmgraphgenetic-algorithm
Murat Derya Özen
Murat Derya Özen

Reputation: 2154

Genetic Algorithm to Draw a Graph? Position assignment problem

I have an assignment problem at hand and am wondering how suitable it would be to apply local search techniques to reach a desirable solution (the search space is quite large).

I have a directed graph (a flow-chart) that I would like to visualize on 2-D plane in a way that it is very clear, understandable and easy to read by human-eye. Therefore; I will be assigning (x,y) positions to each vertex. I'm thinking of solving this problem using simulated annealing, genetic algorithms, or any such method you can suggest

Input: A graph G = (V,E)
Output: A set of assignments, {(xi, yi) for each vi in V}. In other words, each vertex will be assigned a position (x, y) where the coordinates are all integers and >= 0.

These are the criteria that I will use to judge a solution (I welcome any suggestions):

Furthermore; I have an initial configuration (assignment of positions to vertices), made by hand. It is very messy and that's why I'm trying to automate the process.

My questions are,

Any help will be greatly appreciated. Thanks.

EDIT: It doesn't need to be fast - not in real-time. Furthermore; |V|=~200 and each vertex has about 1.5 outgoing edges on average. The graph has no disconnected components. It does involve cycles.

Upvotes: 9

Views: 1861

Answers (5)

tskuzzy
tskuzzy

Reputation: 36476

To answer your first question, I must say it depends. It depends on a number of different factors such as:

  • How fast it needs to be (does it need to be done in real-time?)
  • How many vertices there are
  • How many edges there are compared to the number of vertices (i.e. is it a dense or sparse graph?)

If it needs to be done in a real-time, then local search techniques would not be best as they can take a while to run before getting a good result. They would only be fast enough if the size of the graph was small. And if it's small to begin with, you shouldn't have to use local search to begin with.

There are already algorithms out there for rendering graphs as you describe. The question is, at which point does the problem grow too big for them to be effective? I don't know the answer to that question, but I'm sure you could do some research to find out.

Now going on to your questions about implementation of a local search.

From my personal experience, simulated annealing is easier to implement than a genetic algorithm. However I think this problem translates nicely into both settings. I would start with SA though.

For simulated annealing, you would start out with a random configuration. Then you can randomly perturb the configuration by moving one or more vertices some random distance. I'm sure you can complete the details of the algorithm.

For a genetic algorithm approach, you can also start out with a random population (each graph has random coordinates for the vertices). A mutation can be like the perturbation in SA algorithm I described. Recombination can simply be taking random vertices from the parents and using them in the child graph. Again, I'm sure you can fill in the blanks.

The sum up: Use local search only if your graph is big enough to warrant it and if you don't need it to be done super quickly (say less than a few seconds). Otherwise use a different algorithm.

EDIT: In light of your graph parameters, I think you can do just use whichever algorithm is easiest to code. With V=200, even an O(V^3) algorithm would be sufficient. Personally I feel like simulated annealing would be easiest and the best route.

Upvotes: 0

Sherif elKhatib
Sherif elKhatib

Reputation: 45942

function String generateGenetic()
String genetic = "";
for each vertex in your graph
    Generate random x and y;
    String xy = Transform x and y to a fixed-length bit string;
    genetic + = xy;
endfor
return genetic;

write a function double evaluate(String genetic) which will give you a level of statisfaction. (probably based on the how many edges intersect and edges direction.

your program:

int population = 1000;
int max_iterations = 1000;
double satisfaction = 0;
String[] genetics = new String[population]; //this is ur population;
while((satisfaction<0.8)&&(count<max_iterations)){
    for (int i=0;i<population;i++){
        if(evaluate(genetics[i])>satisfaction)
            satisfaction = evaluate(genetics[i]);
        else
            manipulate(genetics[i]);
    }
}

funciton manipulate can flip some bit of the string or multiple bits or a portion that encodes x and y of a vertex or maybe generate completely a new genetic string or try to solve a problem inside it(direct an edge).

Upvotes: 0

stemm
stemm

Reputation: 6050

http://oreilly.com/catalog/9780596529321 - In this book you might find implementation of genetic algorithm for fine visualization of 2D graph.

In similar situations I'm prefer using genetic algorithm. Also you might start with random initialized population - according to my experience after few iterations, you'll find quite good (but also not the best) solution.

Also, using java you're may paralell this algorithm (isolated islands strategy) - it is rather efficient improvement.

Also I'd like to advice you Differential evolution algorithm. From my experience - it finds solution much more quickly than genetic optimization.

Upvotes: 0

MPG
MPG

Reputation: 835

This paper is a pretty good overview of the various approaches. Roberto Tomassia's book is also a good bet.

Upvotes: 1

Leonard Br&#252;nings
Leonard Br&#252;nings

Reputation: 13242

I would suggest looking at http://www.graphviz.org/Theory.php since graphviz is one of the leading open source graph visualizers.

Depending on what the assignment is, maybe it would make sense to use graphviz for the visualization altogether.

Upvotes: 4

Related Questions