Skip to content

Instantly share code, notes, and snippets.

View darkhipo's full-sized avatar

Dmitri I. Arkhipov darkhipo

  • University of California Irvine
  • Irvine California
View GitHub Profile
@darkhipo
darkhipo / .screenrc
Created December 6, 2018 19:01 — forked from joaopizani/.screenrc
A killer GNU Screen Config
# the following two lines give a two-line status, with the current window highlighted
hardstatus alwayslastline
hardstatus string '%{= kG}[%{G}%H%? %1`%?%{g}][%= %{= kw}%-w%{+b yk} %n*%t%?(%u)%? %{-}%+w %=%{g}][%{B}%m/%d %{W}%C%A%{g}]'
# huge scrollback buffer
defscrollback 5000
# no welcome message
startup_message off
@darkhipo
darkhipo / bipartition.py
Created July 9, 2017 01:24
In Addition, A Bi-Partition
ArcMatchingDatum = coll.namedtuple('ArcMatchingDatum', ['inMatching' ])
NodeMatchingDatum = coll.namedtuple('NodeMatchingDatum', ['visited'])
def dfs_helper(snodes, G):
sniter, do_stop = iter(snodes), False
visited, visited_uids = set(), set()
while(not do_stop):
try:
stack = [ next(sniter) ]
while len(stack) > 0:
@darkhipo
darkhipo / max_flow.py
Last active July 9, 2017 01:26
Maximum Flow, Painfully Slow
import uuid
def fast_get_mfps_flow(mfps):
flow_from_s = {n for n in mfps.G.setOfNodes if n.uid == mfps.sourceNodeUid}.pop().datum.flowOut
flow_to_t = {n for n in mfps.G.setOfNodes if n.uid == mfps.terminalNodeUid}.pop().datum.flowIn
if( (flow_to_t - flow_from_s) > 0.00):
raise Exception('Infeasible s-t flow')
return flow_to_t
@darkhipo
darkhipo / augment.py
Last active July 9, 2017 01:20
Augment your Graph with an Augmenting Path
def augment(augmentingPath, H):
augmentingPath = list(augmentingPath)
H_as_dict = digraph_to_dict(H)
new_nodes = frozenset({})
new_arcs = frozenset({})
visited_nodes = frozenset({})
visited_arcs = frozenset({})
bottleneck_residualCapacity = min( augmentingPath, key=lambda a: a.datum.residualCapacity ).datum.residualCapacity
for x in augmentingPath: