Sunday 27 August 2017

Graph Connectivity in Python

Interested algorithm in Python Graps Repo, checking connectivity of two vertex in O(1) memory usage! Algorithm with description on github. Till the next time!

Thursday 17 August 2017

New Repository: Python Graphs!

I have a new repo on my github: Python-Graphs. There are just few very basic graph algorithms; in fact variations of one, say, Any First Search.

def afs(g, s):
    bag = data_structure()
    bag.add(s)
    while bag is not empty:
        tile = bag.pop()
        if tile is not marked:
            mark(tile)
            for x in adj_list(tile):
                bag.add(x)


Depends what is plugged as a data_structure, we have dfs, bfs, or Minimum Spanning Tree algorithm, with some modification, of course. For example using data structure LIFO stack we have Depth First Search:

def dfs(g, v):
    if v is not marked:
        mark(v)
        for w in adj_list(v):
            dfs(g, w)

FIFO stack gave as Breadth First Search, etc..
Amount of problems which can be solved using graphs is huge, we even say: "If you have problem and can make graph from it, do it and problem solved":). Code as usually on github. Thats all, thank you, enjoy!

Thursday 3 August 2017

Java Rational

Hi all, I had an idea: create Rational, Bigrational and Complex(not done yet) classes in Java to allow exact computation  - get rid of rounding errors. Rational can be initialized in various ways, for example using String; after the end of the computation, there are toDecimal methods, to print result as a decimal or BigDecimal in the case of BigRational. Ther is no overflow check, so we have to make a decision which class to use. Code as usually on github. Enjoy!