Monday, September 21, 2015

Angular modal directive with one-way-binding to object

Being new in AngularJS I wanted to see how can I easily build a Modal window with this awesome framework everyone's been talking about.

Well, one way to do it was using the angular-ui bootstrap which was pretty nice for a first shot, but I didn't like having so much in the controller.

Another problem that I faced was when modifying something in the Modal window, it was immediately reflected back on my original object. This was because a two-way binding was set between the two. This is easily fixed by using angular copy.

Then I started looking into how I could move all this code inside a directive so that everything can be re-used. I managed that, but the angular copy didn't go away.

Having to angular copy everything wasn't really something I did like so much.

I've started looking into the angular code and found that with some little changes I could add a whole new operator besides @, =, &; one that could do exactly what I need it to do: one-way-binding to an object.

I've submitted the code on GitHub and the guys were very helpful in sharing some of their ideas on the matter.(if you wonder why the CI build failed, well, I implemented and tested everything on v1.2.16 and ported the code to the current version and it seemed like I miss typed something in the regex expression. I wasn't about to commit that right away as much as I was looking for some input on the idea)

Based on that input I've come up with a whole new approach to the problem. You can check it up on where a functional example is provided.

As you can see in the example, in the index.html file, I'm using two directives, one named modal that will handle the Modal window and it can be used globally so we don't need to write the same code all over again, and the second directive that handles the content itself, which can be quite anything.

This has been taken and modified from a stack overflow answer in which S Hasan was so helpful to also provide a working example.

If you are wondering why the on-hide function looks like that

it is because I didn't want to pollute the controller with unnecessary code. This is the same as well for all other places I've used this approach.

Now if we were to refer to:

The one-way-bind-person is a naming convention based on one-way-bind- and entity name which we want to one-way bind into the directive.

The on-save is going to be the function that gets triggered when the OK button is clicked and mainly the save is happening and we can use as below:

The onSave function is called in order to return the function vm.savePerson that was passed in so that it can be called with the person parameter.

The person parameter is an object on the directive's scope which is added in the directive's link function:

This is also the place where the one-way binding happens. The parentValueWatch function returns the reference to the parent value, vm.selectedPerson, and when that changes, the onParentValueChange function is going to copy the contents of the vm.selectedPerson over to the directive's scope object person .

I am watching for a reference change only(if you need to watch for the properties of an object or if you pass in an array, then use $watchCollection)

Post references:
Next steps:
  • Would be nice to have an extension point in AngularJS in which we could define our own operators so that less and more organized code could be written.

Thursday, September 10, 2015

Shortest path and back

This Stack Overflow question reminded me of a very interesting problem, whose solution is difficult to find online (in fact I can no longer find it mentioned, though I might be forgetting the exact terminology).

The problem is this:

Given a graph, find the shortest path from a source s to a destination d and back to s. We will call this the shortest path and back problem, or the shortest round trip problem.

A naive algorithm is to simply use Dijkstra's algorithm, or any shortest path algorithm, to find a shortest path from s to t, remove its edges from the graph, then find a return path in the new graph. We can easily find examples for which this fails though.

The correct algorithm involves solving the minimum cost maximum flow problem. This is solved quite easily with the Edmonds-Karp algorithm, where the Breadth-First search used to find the shortest augmenting paths at each step is replaced with the Bellman-Ford algorithm.

I'll leave the details as an exercise, but give an algorithm that is easier to understand if you're not too familiar with flow networks. You can use this algorithm to figure out the flow solution, since the two are actually equivalent.

It goes like this (also available on the SO link):

  • Find a shortest path s -> d with any algorithm that can do this (Dijkstra if no negative costs, Bellman-Ford otherwise);
  • Replace the edges of this shortest path with directed arcs directed from towards s. For example, if your shortest path is s -> x -> y -> z -> d, replace the edge (s, x) with the directed arc x -> s(x, y) with the directed arc y -> x etc.
    Also negate the costs of these arcs. For example, if 
    (x, y) had cost c, the directed arc y -> x will have cost -c;
  • Find a shortest path from s to d in this new graph. You'll have to use an algorithm that works with negative edges now;
  • Remove the edges that appear in both of the shortest paths. What you're left with is the cycle you're after.

  • As an example, consider the following graph. 

    The first shortest we find is 1 -> 2 -> 3 -> 4, of cost 12. We transform our graph to:

    Notice the negated costs. We then find another shortest path in this new graph, which can only be 1 -> 3 -> 2 -> 4, of cost 14.

    We have used the edge (2, 3) in both shortest paths, so we ignore it and draw our solution shortest path and back:

    Which has total cost 26. Notice that if we had applied the naive algorithm, we would have selected 1 -> 4 as the second path, which would have led to a cost of 28.

    You can also solve this problem on UVA, where you can practice your implementation of the algorithm.