# collections

py自带的一些好用的数据结构...
https://docs.python.org/2/library/collections.html

`from collections import Counter, deque, defaultdict`

# itertools

```>>> from itertools import product, combinations
>>> a = 'ABCD'; b='EFG'
>>> for p in product(a,b):
print p
...
('A', 'E')
('A', 'F')
('A', 'G')
('B', 'E')
('B', 'F')
('B', 'G')
('C', 'E')
('C', 'F')
('C', 'G')
('D', 'E')
('D', 'F')
('D', 'G')
>>> for c in combinations(a, 2): print c
...
('A', 'B')
('A', 'C')
('A', 'D')
('B', 'C')
('B', 'D')
('C', 'D')
>>> for p in permutations(b,2): print p
...
('E', 'F')
('E', 'G')
('F', 'E')
('F', 'G')
('G', 'E')
('G', 'F')
```

# bitmap

### use bitmap for combinations (2^N possibilities)

(N elements, each element 2 choices)
`for mask in xrange(1<<N): ...`

### set/clean Kth bit

set: `bm |= 1<<k`

clean: `bm &= ~(1<<k)`

### count nb of 1s in a bitmap

`bin(bm).count('1')`

# networkx

### constructing graph

```>>> import networkx as nx
>>> G = nx.DiGraph() # use `Graph` for undired graph, `MultiGraph` for dup-edges
>>> G.add_node('a') # any hashable obj can be used as node index
>>> G.add_edge(1,3) # if G is undired(`Graph`), 1-->3 and 3-->1 will be added
>>> G.nodes()
['a', 1, 2, 3]
>>> G.edges()
[(1, 2), (1, 3)]
>>> G.nodes()
['a', 1, 2, 3]
>>> G.edges()
[(1, 2), (1, 3)]
>>> G[1] # outgoing edges from a node
{2: {}, 3: {}}
>>> G[1][2]['color']='blue' # easily add edge properties
>>> G[1]
{2: {'color': 'blue'}, 3: {}}
>>> G.edge
{'a': {}, 1: {2: {'color': 'blue', 'capacity': 1}, 3: {}}, 2: {}, 3: {}}
>>> G.node['a']['cat']='string node' # can also be: G.add_node('a', cat='string node')
>>> G.node
{'a': {'cat': 'string node'}, 1: {}, 2: {}, 3: {}}
```

### DiGraph: topo-sort, cycle-detection, strongly connected component

```>>> import networkx as nx
>>> G = nx.DiGraph()
>>> list( nx.strongly_connected_components(G) )
[set(['b']), set(['a']), set([2]), set([3]), set([1])]
>>> nx.topological_sort(G)
[1, 2, 3, 'a', 'b']
>>> list( nx.simple_cycles(G) )
[[1, 3], [1, 2, 3], ['a', 'b']]
>>> list( nx.strongly_connected_components(G) )
[set(['a', 'b']), set([1, 2, 3])]
>>> nx.shortest_path(G,1,'a')
[1, 3, 4, 'a']
>>> nx.shortest_path(G,1,'a')
[1, 3, 4, 'a']
>>> nx.shortest_path_length(G,1,'a')
3
>>> nx.shortest_path_length(G,1,'a','weight') # set attribut edge 'weight' as weight, (if not present, weight=1 )
4
```

### Undirected Graph: connected component, MST

```>>> G = nx.Graph()
>>> list( nx.connected_components(G) )
[set(['a', 'b']), set([1, 2, 3])]
>>> mst =  nx.minimum_spanning_tree(G) # returns a new graph
>>> mst.edges()
[('a', 'b'), (1, 2), (1, 3)]
>>> G.add_edge(1,3,weight=2) # mst takes attribut 'weight', if no present, weight=1
>>> nx.minimum_spanning_tree(G).edges()
[('a', 'b'), (1, 2), (2, 3)]
```

### maxflow

```>>> import networkx as nx
>>> G = nx.DiGraph()
>>> flow_value, flow_dict = nx.maximum_flow(G, 'x', 'y')
>>> flow_value
3.0
>>> print(flow_dict['x']['b'])
1.0
```

### maximum matching

NB: maximum matching != maximal matching...
there are maximum-matching functions for general undir graph (`max_weight_matching`) and for bipartitie graph (`maximum_matching`), the one for bipartite graph is faster, the general one takes O(V**3).

```>>> G = nx.Graph()
>>> mate = nx.max_weight_matching(G, maxcardinality=True)#mate[v] == w if node v
is matched to node w.
>>> mate
{2: 3, 3: 2, 4: 5, 5: 4}
>>> nx.is_bipartite(G)
True
>>> mate=nx.bipartite.maximum_matching(G)
>>> mate
{1: 2, 2: 1, 3: 4, 4: 3}
```

and there are vertex cover algorithms as well......

# pulp

```>>> from pulp import *
>>> x = LpVariable("x", 0, 3)
>>> y = LpVariable("y", 0, 1, 'Integer') # var category can be integer
>>> prob = LpProblem("myProblem", LpMinimize)
>>> prob += x + y <= 2 # add constraint
>>> prob += -4*x + y # add objective
>>> status = prob.solve() # solve using default solver
>>> status = prob.solve(GLPK(msg = 0)) # or use glpk solver
>>> LpStatus[status]
'Optimal'
>>> value(prob.objective) # see objective value
-8.0
>>> value(x) # see variable value
2.0
```