Skip to content

Instantly share code, notes, and snippets.

@SamuraiT
SamuraiT / MarkdownParser.py
Last active August 29, 2015 13:56
MarkdownParser example with test code
class MarkdownParser(object):
def convert_to_paragraph(self, mes):
return '<p>{mes}</p>'.format(mes = mes)
@SamuraiT
SamuraiT / Graph.py
Last active August 29, 2015 13:56
this code is originally from http://greenteapress.com/complexity/Graph.py but modified a little
"""
this code is originally from http://greenteapress.com/complexity/Graph.py
modified original code a bit
original author: Allen B.Downey
Copyright 2011 Allen B. Downey.
Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
"""
class Vertex(object):
"""A Vertex is a node in a graph."""
@SamuraiT
SamuraiT / RandomGraph.py
Last active August 29, 2015 13:56
a random graph: G(n,p) which generates graphs with n nodes and edges between any two nodes with the probability (p)
from Graph import (
Graph,
Edge,
Vertex,
)
import random
class RandomGraph(Graph):
"""
create a random graph with the probability (p)
@SamuraiT
SamuraiT / counter.py
Last active August 29, 2015 13:56
counter.py is a counter iterator that counts a number. gen_counter.py is counter which is implemented with a generator
class Counter(object):
"""a counter iterator that counts a number
when you invoke the (next) method"""
def __init__(self):
self.count = 0
def __iter__(self):
return self
@SamuraiT
SamuraiT / bisection.py
Created February 24, 2014 16:05
binary search: implements with the bisection and without any third modules.
import bisect
def bisection(t, target):
"""
takes a sorted list (t) and the (target) value.
returns the index of the (target) value in the list (t) if there
is ,otherwise returns None
"""
i = bisect.bisect_left(t, target)
@SamuraiT
SamuraiT / hashtable.py
Created March 1, 2014 15:56
easy Hashtable implementation from the Think Complexity book.
class LinearMap(object):
def __init__(self):
self.items = []
def add(self, k, v):
self.items.append((k, v))
def get(self, k):
class DictFifo(object):
def __init__(self):
self.nextin = 0
self.nextout = 0
self.data = {}
def append(self, value):
self.data[self.nextin] = value
@SamuraiT
SamuraiT / bfs.py
Last active August 29, 2015 13:56
Breadth-first-search implementation
RandomGraph(Graph):
def bfs(self, v):
"""search graph by a BFS: breadth-first-search"""
worklist = [v]
closed = []
while worklist: # order of growth is O(n)
visited = worklist.pop(0) # O(n)
closed.append(visited) #
@SamuraiT
SamuraiT / samllworldgraph.py
Created March 3, 2014 06:55
small world graph implementation
from RandomGraph import RandomGraph,show_graph
from Graph import *
import string
from random import random, choice
class SmallWorldGraph(RandomGraph):
def rewire(self, p):
vs = self.vertices()
for i, v in enumerate(vs):
@SamuraiT
SamuraiT / samllworldgraph.py
Created March 3, 2014 07:33
Small World Graph implementation with clustering coefficient:C(p) and average path length:L(p) and simple dijkstra
from RandomGraph import RandomGraph,show_graph
from Graph import *
from random import random, randint, choice
from collections import deque
class SmallWorldGraph(RandomGraph):
def rewire(self, p):
vs = self.vertices()