## Notes on ensuring Maximum Energy Flow using s-t flow/cut & residual graph

Maximum Flow problem is one of the important problems in combinatorial optimization. It finds feasible solution for flowing energy from one source to another point. Here we are interested to find a minimum energy labeling in a MRF.

Lets define our problem space using directed graph. Every edge denotes a flow and every flow has a capacity (black numbers in diagram) that it can hold. Each time when we make an energy flow we will mark it in the graph in red and obviously it have to be less than the capacity. The excess energy is the difference between incoming and outgoing values. For example E(v1)=1-(4+3)=-6. We can also compute excess energy for a set of veteces, E({v1,v2}). Now we need to consider v1 and v2 as a block and the difference between incoming and outgoing edges must be calculated.  E({v1,v2})=10+1 -(3)=8. We will also get the same result if we compute E(v1) and E(v2) separately and sum them up. Now we will try to explain S-t flow. The main property of a S-t flow is that all the vertice other than source or drain must have an equal value of input and output.
s-t cut is a way where we separate the graph in two parts in such a order that source and drain goes into the second part and then we find the output capacity difference of it. s-t flow can also be represented in term of s-t cut. In terms of s-t flow all other vertices excess energy of 0. So basically the value of flow for s-t flow=E(s) which is similar to write E(s)-E(v) so it is actually an s-t cut.  E(s)-E(v) can’t exceed the capacity.
To solve maximum flow, we can use Residual Graph. Resudual Graph is an undirected graph. In this undirected graph we would remove every edge when it gets saturated in other word we would keep edge of all the graph which has edge less than capacity. So whats our stopping condition? Eventually we will reach to a state where our sink will lose all its edge so its a state where we can’t reach in the end.
So we have got the maximum flow for the capacity of that. From the max value min cut theorem we can say that it would give us the minimum cut.

## TF-IDF and Cosine similarity on Document Rank Retrieval

I was interested in learning about the algorithms that tries to match document and our queries when it tries to match with the documents and returns on a rank from best match to least match. In this blog I have tried to figure out the question why I have to use tf-idf and cosine similarity .

Jaccard similarity coefficient is too straight forward. For a specific search query It figures out the rank depending on the word it has matched in the total number of unique word it has. I think rather than saying like this, if I say formally then it would be a lot more clear. formally it is defined by the division of cardinality of the set of their intersection and the cardinality of the set of unions.

(1) \begin{equation*} Jaccard(A,B)= \frac{ | A \cup B |}{ | A \cap B |} \end{equation*}

Example:
query=ides o march

document1=caesar died in march
document2=the long march

jaccard(query, document1)=1/6
jaccard(query, document2)=1/5

But Jaccard is too binary to be awesome. In real life if a word frequently appears in a document then the other than the query should retrieval the first document instead of the second one but jaccard coefficient does not count the frequency at all, it checks whether the word appears or not, it is boolean. The problem with Boolean queries are that, it often results too many or too few results. When we use AND it becomes too short and for OR the results become too short. So for long query it becomes too choosy and for short queries it shows everything that matches.
We have detected a problem, so now it is time to solve it. We will try to solve it using Term Frequency Waiting. This time we will try to move away from boolean approach. So this time a presence of a word in a document is not enough but their count is also something of our headache. So the same thing of above but this time we will count the words it has appeared. Suppose for the sentence: “in the month of march, they are going for long march” will vote twice for the document when the query is “march”, in fact it will be 2/11.
tf(query, document)= total query words present in document/ total number of words in query and document

Let me remind the scenario once again so that we can detect any possible bug in our assumption, suppose I am looking for a word and one document has it once and the other document has it 10 times. obviously the 10 time will be the one I would more likely be looking for but it won’t be 10 time more important. So we can use log assumption here. So we can do,

(2) \begin{equation*} w= 1+log(tf) \end{equation*}

But guess what? what is the most used word in our conversation? I am pretty sure that “is, are, it” sort of word will get the most frequency rate but it appears in all the documents which won’t help us to do anything at all. In fact we are interested about rare words – the antique one.
So it was the necessity for introducing Inverse Frequency Model. So let me tell you again the rare terms are more important here for now. For example a document full of the, to is not important to recognize the document anymore because it appears in every document. So in this model the more it appears in the documents, it is less important… in other word the important get divided. So lets do it,

(3) \begin{equation*} idf=\frac{N}{df} \end{equation*}

where N= total number of documents we have,
df= the number of document that has our query word
But again it does not increase like a plain line, so lets use logarithmic scale for the same reason as above.

(4) \begin{equation*} idf=Log \frac{N}{df} \end{equation*}

more formally:

(5) \begin{equation*} idf(t,D)= log(tf) \end{equation*}

so now for 1 occurance in 1M will get idf = 6

TF only care about the number of time it appears in the document and idf cares about the rare words. But we need a proper balance of things. It should be rare but at the same time that rare word should appear multiple time in the document. So how would we balance? we can just multiply both of them. tf-idf is the best weighting scheme known.
Let me help you a little bit more with its implementation. When you are done your tf-idf would look like a 1xm vector matrix. somewhat like array.
[It, is, March]=[0.33,0.33,0]
Remember how do we draw vectors? if a vector is represented as [x,y] just ploting line that go through [0,0] and that connects [x,y]. TF-IDF makes it multidimensional nothing else. we have represented something using tf-idf, thats cool, but how would we we retrive ranks? We can make tf-idf matrix for both query and document then calculate vector distance. But here we can face a new problem because of its vector nature. remember that [2,2] and [4,4] represent the same line, just twice as large as the line. Which is a drawback of this tf-idf because it adds the distance between query and document very high. So to get out of this draw back we will introduce cosine similarity. Basically cosine similarity is pretty simple idea, instead of distance now we will calculate the angle between the lines.

(6) \begin{equation*} cos(\theta)=\frac{A \dot B}{| A | | B |} \end{equation*}

so from angle now we can detect the similarity.

## Adding animation on character movement using Libgdx

reviously, we have talked about making a character. But our character was lifeless. It was like moving image left or right. Now it is time to add animation to our character bob so that it look more like a character who has life. Most importantly this time I am writing my own code. This time I am not explaining other’s code in my own word like my previous 2 libgdx blog.

First thing we got to do is, we have to make a sprite-sheet.

We have to store it in the asset directory of android.

Now to contemplate where actually we were rendering our character bob? We have done it in WorldRenderer.java. It has a render() method which is responsible for decoration of the environment.

public void render() {
spriteBatch.begin();
drawBlocks();
drawBob();
spriteBatch.end();

if (debug)
drawDebug();
}


we are more interested about the character animation today so we will be rewriting our drawBob() method today. But before that we must load our textures first in loadTextures() method which is being called in the constructor of this class. What actually we need to load here? We need to load our sprite image. Then we need to divide and split it into frames into a 1D array and then we have to make Animation object using this Array and we also need to define the time each frame will consume. Thats it.

	private static final int        FRAME_COLS = 6;
private static final int        FRAME_ROWS = 5;
Animation                       walkAnimation;
Texture                         walkSheet;
TextureRegion[]                 walkFrames;
TextureRegion                   currentFrame;

float stateTime;

private void loadTextures() {
walkSheet = new  Texture(Gdx.files.internal("animation_sheet.png"));
TextureRegion[][] tmp = TextureRegion.split(walkSheet, walkSheet.getWidth() /
FRAME_COLS, walkSheet.getHeight() / FRAME_ROWS);
walkFrames = new TextureRegion[FRAME_COLS * FRAME_ROWS];
int index = 0;
for (int i = 0; i < FRAME_ROWS; i++) {
for (int j = 0; j < FRAME_COLS; j++) {
walkFrames[index++] = tmp[i][j];
}
}
walkAnimation = new Animation(0.025f, walkFrames);

stateTime = 0f;

bobTexture = new  Texture(Gdx.files.internal("images/bob.png"));
blockTexture = new Texture(Gdx.files.internal("images/block.png"));
}


As I was saying, we need to move to our main focused function drawBob(). To access the sprite frames we need to access to the frames via time elapsed. So we need to keep updating stateTimewith a delta otherwise the same frame will keep appearing. Gdx.graphics.getDeltaTime() returns the time passed since the last call to render() in seconds. So basically I was explaining this code.

private void drawBob() {
Bob bob = world.getBob();
Gdx.gl.glClear(GL10.GL_COLOR_BUFFER_BIT | GL10.GL_DEPTH_BUFFER_BIT);
stateTime += Gdx.graphics.getDeltaTime();
currentFrame = walkAnimation.getKeyFrame(stateTime, true);
spriteBatch.draw(currentFrame, bob.position.x * ppuX, bob.position.y * ppuY, facex*Bob.SIZE * ppuX, Bob.SIZE * ppuY);
}


Bingo! Sprite works. BUT! This is odd because bob is animating its run state all the time even when he is not running, it need to be fixed, right? Actually we have been preparing for this moment from the first day. Remember we are keeping an enum to keep the current state of bob and using controller we are updating bob’s state. So here it will only need a if else condition to check what is the current state of bob. Is he running? Or another word, is user pressing arrow keys? If yes then show this animation:

if (bob.state==bob.state.WALKING){
Gdx.gl.glClear(GL10.GL_COLOR_BUFFER_BIT | GL10.GL_DEPTH_BUFFER_BIT);
stateTime += Gdx.graphics.getDeltaTime();
currentFrame = walkAnimation.getKeyFrame(stateTime, true);
spriteBatch.draw(currentFrame, bob.position.x * ppuX, bob.position.y * ppuY, Bob.SIZE * ppuX, Bob.SIZE * ppuY);

}


and if he is idle show that old static image.

else if(bob.state==bob.state.IDLE){
spriteBatch.draw(bobTexture, bob.position.x * ppuX, bob.position.y * ppuY,Bob.SIZE * ppuX, Bob.SIZE * ppuY);
}


We are good now, aren’t we? Yes we have improved a lot. But still when we move left the bob face in one direction thats what we want so no complain but when we move right bob keep his face to that old direction again! Thats stupid, is not it? So we need to flip the direction of our sprite and image. It is not hard at all. It requires trick. if add negative to the size of the image it will flip the image in X axis. So lets put this function together:

private void drawBob() {
Bob bob = world.getBob();

int facex=1;
if(bob.facingLeft){
facex=-1;
}

if (bob.state==bob.state.WALKING){
Gdx.gl.glClear(GL10.GL_COLOR_BUFFER_BIT | GL10.GL_DEPTH_BUFFER_BIT);
stateTime += Gdx.graphics.getDeltaTime();
currentFrame = walkAnimation.getKeyFrame(stateTime, true);
spriteBatch.draw(currentFrame, bob.position.x * ppuX, bob.position.y * ppuY, facex*Bob.SIZE * ppuX, Bob.SIZE * ppuY);

}
else if(bob.state==bob.state.IDLE){
spriteBatch.draw(bobTexture, bob.position.x * ppuX, bob.position.y * ppuY, facex* Bob.SIZE * ppuX, Bob.SIZE * ppuY);
}

//spriteBatch.draw(bobTexture, bob.position.x * ppuX, bob.position.y * ppuY, Bob.SIZE * ppuX, Bob.SIZE * ppuY);

}


We are basically done!

Now put the hole class together:

package com.me.mygdxgame;

public class WorldRenderer {

private World world;
private OrthographicCamera cam;

/** for debug rendering **/
ShapeRenderer debugRenderer = new ShapeRenderer();

public WorldRenderer(World world) {
this.world = world;
this.cam = new OrthographicCamera(10, 7);
this.cam.position.set(5, 3.5f, 0);
this.cam.update();

spriteBatch = new SpriteBatch();
}

private static final float CAMERA_WIDTH = 10f;
private static final float CAMERA_HEIGHT = 7f;
private SpriteBatch spriteBatch;
private boolean debug = false;
private int width;
private int height;
private float ppuX;	// pixels per unit on the X axis
private float ppuY;	// pixels per unit on the Y axis
public void setSize (int w, int h) {
this.width = w;
this.height = h;
ppuX = (float)width / CAMERA_WIDTH;
ppuY = (float)height / CAMERA_HEIGHT;
}
private void drawBlocks() {

for (Block block : world.getBlocks()) {
spriteBatch.draw(blockTexture, block.position.x * ppuX, block.position.y * ppuY, Block.SIZE * ppuX, Block.SIZE * ppuY);
}

}

/** Textures **/
private Texture bobTexture;
private Texture blockTexture;

private static final int        FRAME_COLS = 6;
private static final int        FRAME_ROWS = 5;
Animation                       walkAnimation;
Texture                         walkSheet;
TextureRegion[]                 walkFrames;
TextureRegion                   currentFrame;

float stateTime;

private void loadTextures() {
walkSheet = new  Texture(Gdx.files.internal("animation_sheet.png"));
TextureRegion[][] tmp = TextureRegion.split(walkSheet, walkSheet.getWidth() /
FRAME_COLS, walkSheet.getHeight() / FRAME_ROWS);
walkFrames = new TextureRegion[FRAME_COLS * FRAME_ROWS];
int index = 0;
for (int i = 0; i < FRAME_ROWS; i++) {
for (int j = 0; j < FRAME_COLS; j++) {
walkFrames[index++] = tmp[i][j];
}
}
walkAnimation = new Animation(0.025f, walkFrames);

stateTime = 0f;

bobTexture = new  Texture(Gdx.files.internal("images/bob.png"));
blockTexture = new Texture(Gdx.files.internal("images/block.png"));
}
public void render() {
spriteBatch.begin();
drawBlocks();
drawBob();
spriteBatch.end();

if (debug)
drawDebug();
}
private void drawBob() {
Bob bob = world.getBob();

int facex=1;
if(bob.facingLeft){
facex=-1;
}

if (bob.state==bob.state.WALKING){
Gdx.gl.glClear(GL10.GL_COLOR_BUFFER_BIT | GL10.GL_DEPTH_BUFFER_BIT);
stateTime += Gdx.graphics.getDeltaTime();
currentFrame = walkAnimation.getKeyFrame(stateTime, true);
spriteBatch.draw(currentFrame, bob.position.x * ppuX, bob.position.y * ppuY, facex*Bob.SIZE * ppuX, Bob.SIZE * ppuY);

}
else if(bob.state==bob.state.IDLE){
spriteBatch.draw(bobTexture, bob.position.x * ppuX, bob.position.y * ppuY, facex* Bob.SIZE * ppuX, Bob.SIZE * ppuY);
}

//spriteBatch.draw(bobTexture, bob.position.x * ppuX, bob.position.y * ppuY, Bob.SIZE * ppuX, Bob.SIZE * ppuY);

}
private void drawDebug() {
// render blocks
debugRenderer.setProjectionMatrix(cam.combined);
debugRenderer.begin(ShapeType.Line);
for (Block block : world.getBlocks()) {
Rectangle rect = block.bounds;
float x1 = block.position.x + rect.x;
float y1 = block.position.y + rect.y;
debugRenderer.setColor(new Color(1, 0, 0, 1));
debugRenderer.rect(x1, y1, rect.width, rect.height);
}
// render Bob
Bob bob = world.getBob();
Rectangle rect = bob.bounds;
float x1 = bob.position.x + rect.x;
float y1 = bob.position.y + rect.y;
debugRenderer.setColor(new Color(0, 1, 0, 1));
debugRenderer.rect(x1, y1, rect.width, rect.height);
debugRenderer.end();
}
}


## How to create simple menu in libgdx

Actually making menu using libgdx is pretty easy, but most probably because of the lack of tutorial or (proper SEO) initially it took me a little more time then usual to make it done, It has become easier for me when I have a look at their test cases provided. Let me share a simplified code with you guys. Here in this tutorial we will write code for a button that starts the game.

In our main method we have to run a new instance of LwjglApplication class which requires an ApplicationListener to launch. So we need to implement ApplicationListener for sure. As the Game class provides few extra benefit like setting which screen to show up and things. So in this blog I will be extending Game class. Game class has a setScreen method just changing it decides which method will be shown in the screen. We want to take advantage of it in future when the button will get pressed so I am sending a self instance of this class.

//MainMenuGame.java

public class MainMenuGame extends Game {
@Override
public void create() {
}
}


Now we will be writing the code we are interested about. We will extend the screen class as it is required for setScreen(). We need to create a Stage to add our button which handles the viewing region and at the same time takes care of the input actions so we need to send it to input process as well.

stage = new Stage();
Gdx.input.setInputProcessor(stage);


We need to define the skin of our button which is basically the background color, fonts and so on.

BitmapFont bfont=new BitmapFont();
bfont.scale(1);


Now we need to define the style of our button, which is TextButtonStyle. Here will get a lot of options to deal with. we can define what colors will it take when the mouse is over it, when the button is pressed and so on. and then finally we can create our TextButtion. Then we can set the position of it and add it to the stage.

import com.badlogic.gdx.Game;

public class MenuScreen implements Screen {
Skin skin;
Stage stage;
SpriteBatch batch;

Game g;
create();
this.g=g;
}

create();
}
public void create(){
batch = new SpriteBatch();
stage = new Stage();
Gdx.input.setInputProcessor(stage);

// A skin can be loaded via JSON or defined programmatically, either is fine. Using a skin is optional but strongly
// recommended solely for the convenience of getting a texture, region, etc as a drawable, tinted drawable, etc.
skin = new Skin();
// Generate a 1x1 white texture and store it in the skin named "white".
Pixmap pixmap = new Pixmap(100, 100, Format.RGBA8888);
pixmap.setColor(Color.GREEN);
pixmap.fill();

// Store the default libgdx font under the name "default".
BitmapFont bfont=new BitmapFont();
bfont.scale(1);

// Configure a TextButtonStyle and name it "default". Skin resources are stored by type, so this doesn't overwrite the font.
TextButtonStyle textButtonStyle = new TextButtonStyle();
textButtonStyle.up = skin.newDrawable("white", Color.DARK_GRAY);
textButtonStyle.down = skin.newDrawable("white", Color.DARK_GRAY);
textButtonStyle.checked = skin.newDrawable("white", Color.BLUE);
textButtonStyle.over = skin.newDrawable("white", Color.LIGHT_GRAY);

textButtonStyle.font = skin.getFont("default");

// Create a button with the "default" TextButtonStyle. A 3rd parameter can be used to specify a name other than "default".
final TextButton textButton=new TextButton("PLAY",textButtonStyle);
textButton.setPosition(200, 200);

}

public void render (float delta) {
Gdx.gl.glClearColor(0.2f, 0.2f, 0.2f, 1);
Gdx.gl.glClear(GL10.GL_COLOR_BUFFER_BIT);
stage.act(Math.min(Gdx.graphics.getDeltaTime(), 1 / 30f));
stage.draw();
Table.drawDebug(stage);
}

@Override
public void resize (int width, int height) {
stage.setViewport(width, height, false);
}

@Override
public void dispose () {
stage.dispose();
skin.dispose();
}

@Override
public void show() {
// TODO Auto-generated method stub

}

@Override
public void hide() {
// TODO Auto-generated method stub

}

@Override
public void pause() {
// TODO Auto-generated method stub

}

@Override
public void resume() {
// TODO Auto-generated method stub

}
}


Now we will add callback function. When the key is pressed a callback function of addaction will get triggered and via our previously passed game we will change setScreen.

textButton.addListener(new ChangeListener() {
public void changed (ChangeEvent event, Actor actor) {
//System.out.println("Clicked! Is checked: " + button.isChecked());
textButton.setText("Starting new game");
g.setScreen( new GameScreen());

}
});


Altogether:

package com.sadafnoor.RainyDay.Views;
public class MenuScreen implements Screen {
Skin skin;
Stage stage;
SpriteBatch batch;
Game g;
create();
this.g=g;
}
create();
}
public void create(){
batch = new SpriteBatch();
stage = new Stage();
Gdx.input.setInputProcessor(stage);
// A skin can be loaded via JSON or defined programmatically, either is fine. Using a skin is optional but strongly
// recommended solely for the convenience of getting a texture, region, etc as a drawable, tinted drawable, etc.
skin = new Skin();
// Generate a 1x1 white texture and store it in the skin named "white".
Pixmap pixmap = new Pixmap(100, 100, Format.RGBA8888);
pixmap.setColor(Color.GREEN);
pixmap.fill();
// Store the default libgdx font under the name "default".
BitmapFont bfont=new BitmapFont();
bfont.scale(1);
// Configure a TextButtonStyle and name it "default". Skin resources are stored by type, so this doesn't overwrite the font.
TextButtonStyle textButtonStyle = new TextButtonStyle();
textButtonStyle.up = skin.newDrawable("white", Color.DARK_GRAY);
textButtonStyle.down = skin.newDrawable("white", Color.DARK_GRAY);
textButtonStyle.checked = skin.newDrawable("white", Color.BLUE);
textButtonStyle.over = skin.newDrawable("white", Color.LIGHT_GRAY);
textButtonStyle.font = skin.getFont("default");
// Create a button with the "default" TextButtonStyle. A 3rd parameter can be used to specify a name other than "default".
final TextButton textButton=new TextButton("PLAY",textButtonStyle);
textButton.setPosition(200, 200);
// Add a listener to the button. ChangeListener is fired when the button's checked state changes, eg when clicked,
// Button#setChecked() is called, via a key press, etc. If the event.cancel() is called, the checked state will be reverted.
// ClickListener could have been used, but would only fire when clicked. Also, canceling a ClickListener event won't
// revert the checked state.
public void changed (ChangeEvent event, Actor actor) {
//System.out.println("Clicked! Is checked: " + button.isChecked());
textButton.setText("Starting new game");
g.setScreen( new GameScreen());
}
});
}
public void render (float delta) {
Gdx.gl.glClearColor(0.2f, 0.2f, 0.2f, 1);
Gdx.gl.glClear(GL10.GL_COLOR_BUFFER_BIT);
stage.act(Math.min(Gdx.graphics.getDeltaTime(), 1 / 30f));
stage.draw();
Table.drawDebug(stage);
}
@Override
public void resize (int width, int height) {
stage.setViewport(width, height, false);
}
@Override
public void dispose () {
stage.dispose();
skin.dispose();
}
@Override
public void show() {
// TODO Auto-generated method stub
}
@Override
public void hide() {
// TODO Auto-generated method stub
}
@Override
public void pause() {
// TODO Auto-generated method stub
}
@Override
public void resume() {
// TODO Auto-generated method stub
}
}