Getting all possible paths of two vertices in a Graph using DFS

As you might have seen, I recently explained something similar, but now I'll find all possible paths. This is pretty much more of the same but it's way more tricky.
Well modify our basic DFS search and do a view more stuff

Input: vertex start, vertex end, list of lists of vertices "paths", list of vertices "path"
Output: boolean, wheter or not I found a path
add start to path
if(start == end)
    return true
else
    mark start as visited
    for each adyacent vertex w of start
        if w is not visited
            boolean found = dfs(w, end, paths, path)
            if found
                add a clone of path to paths
        path.removeLast()
    mark start as non visited
    return false

That's it! It might seem simple but in Java it's a bit longer. Hope it helped!

Read more...

Getting a Graph's path between two vertices using DFS

As you might have seen, I have made a similar post before, but this time, we use another way of going though our graph, it's called Depth First Search, and it's my favourite way as it's nature is recursive, and recursion is fancy :)
Basically, we will now go though our graph with an bucket of paint and a string, every time we see a non visited vertex, we will paint it, tie the string to it and go on, when we cannot advance any futher, we go back pulling from our string, until we see an unvisited vertex, to then repeat. You can kind of think of it like a way to get though a maze.
The algorithm is something like this

Input: a start vertex

mark start as visited

visit start

for each incident edge E of start

w = opposite(start, E) 
if(w is not visited)
mark w as visited
DFS(start)

The output of DFS can be viewed as a tree, with root on Start, every time we visit a node adyacent to start we add it as a child, and we do the same with each of start's children, making a generic tree. There are different kind of edges which we can see in this image.

Output of a DFS showing different kind of edges

Anyways, that is not important for us, what is important is to get the path between two vertex, this is quite easy, same as with BFS, we have to modify mostly the 'visit' part of the algorithm.

Input: a start vertex, an end vertex, and a list L

// This time we won't output anything, just add the path to our list!

mark start as visited

L.addLast(start)

if(start == end)

return true

else

for each incident edge E of start

w = opposite(start, E) 

if(w is not visited)        

found = DFS(start)

if(found) return true

endfor

L.removeLast()

return false

And that's it. With that algorithm we can search for a path between two vertex, we have to add an extra argument, but we can make a method to make everything nicer. Like in this java example.
Hope you find it useful!

Read more...

Getting a Graph's shortest path between two vertices using BFS

Long title indeed, but this is a rather specific entry. I've been working with graphs lately, for university, and I'm afraid there are lots and lots of different properties and algorithms (you can imagine studying that for an exam is a pain in the ass) but well, I tried searching for this on Google with no luck, there are many algorithms for getting the shortest path between two vertex, and many sites say "It can be done using BFS" but they do not explain how.
So, I found a rather nice and easy solution. First of all, let's say G is a simple graph, with no directed edges, and we don't consider edges' weight. I'll use pseudo-code in this entry since it's more CS oriented.
First of all, if you don't know what BFS is, it's Breadth First Search, it's a way of iterate through a graph, in which you go by levels.

BFS Animation

You can see wikipedia for more info, I'll assume you know the algorithm, at least just on paper, the algorithm is like this:

Input: a vertex called start
Let Q be a queue
Q.enqueue(start)
visit start
while(Q is not empty)
    w = Q.dequeue()
    for each adyacent vertex v of w do
        if v is not visited
            mark v as visited
            add v to queue
            visit v

That's it. Basically, when you solve a problem using an algorithm like this, what you want to work on is on the "visit v" part, what we are gonna do is use a map, in which we will save each vertex we visit, and once we reached our end vertex, we simply "go back". A map is a data structure which has a Key and a Value, so we will use the Key as our vertex, and the value will be the vertex' parent, that way we can just go back and return a list of visited vertex' which make the shortest path from START to END.

Input: a vertex called start, and a vertex called end

Output: a list containing the shortest path from start to end, or null if it cannot find a path
Let Q be a queue

Let M be a map
Q.enqueue(start)
map.put(start, null) // Start has no parent!
while(Q is not empty)
    w = Q.dequeue()
    for each adyacent vertex v of w do
        if v is not visited
            mark v as visited
            add v to queue
            if(v == end)

                Let L be a list
                while(v != null)
                    L.addFirst(ww)
                    ww = M.get(ww)
                return L
return null

There it is, hopefully someone will find it useful! Note that basically the only part that changes is the 'visit' part.
I'll leave the Java code just for the sake of it ;) Sorry it's in spanish, as it's from university, but this should not be much problem.

Read more...

Fedora + Xfce on my netbook

I have to admit, I'm suprised with the compatibility and the performance and stability of Fedora on my Netbook, it works even nicer than Ubuntu (or Xubuntu), I'm pretty happy with it :)
I had no major problems getting up and running even though this is the first time I try another distro than Ubuntu or any Ubuntu variation.

Here's an screenshot of my little netbook screen right now

I still have to add some more customization and programs but it's looking lovely so far :)
Definetely reccommended for netbooks, works awesome with Intel Atom processor.

Read more...

About akaikiwi and stuff

As I've now started University I have less time for hobby coding, I'm working on some Java stuff now, as that's what I use at university, I'm working with slick and making some game development, not a full game though, just things like GUI and stuff, once I put together some stuff I'll finish a RPG I was working on :)
About akaikiwi, it's development has drastically stopped, but I plan on finishing it, not now, but soon, I have to do some PHP for work but all Joomla! related (which to be honest I pretty much hate Joomla! awful implementation of MVC but oh well...).
I'd really love to have more time and see more RoR and Django but right now I can't, I want to finish akaikiwi first, although I do take some ideas from those frameworks, I'm really interested in Django on Appengine, I think I'll deploy my next web app there, which is probably gonna be a designer's resource site.
Once I have more free time I'll work on some nice stuff I have on hiatus :)

Read more...