# Path: stationary/utils/math_helpers.py
# def kl_divergence_dict(p, q):
#     """
#     Computes the KL-divergence of distributions given as dictionaries.
#     """
#     s = 0.
# 
#     p_list = []
#     q_list = []
# 
#     for i in p.keys():
#         p_list.append(p[i])
#         q_list.append(q[i])
#     return kl_divergence(p_list, q_list)
# 
# Path: stationary/utils/graph.py
# class Graph(object):
#     """Directed graph object intended for the graph associated to a Markov process.
#     Gives easy access to the neighbors of a particular state needed for various
#     calculations.
# 
#     Vertices can be any hashable / immutable python object.
#     """
# 
#     def __init__(self, edges=None):
#         self.out_mapping = defaultdict(lambda: defaultdict(float))
#         self.in_mapping = defaultdict(lambda: defaultdict(float))
#         if edges:
#             self.add_edges(edges)
# 
#     def add_vertex(self, label):
#         self._vertices.add(label)
# 
#     def add_edge(self, source, target, weight=1.):
#         self.out_mapping[source][target] = weight
#         self.in_mapping[target][source] = weight
# 
#     def add_edges(self, edges):
#         try:
#             for source, target, weight in edges:
#                 self.add_edge(source, target, weight)
#         except ValueError:
#             for source, target in edges:
#                 self.add_edge(source, target, 1.0)
# 
#     def vertices(self):
#         """Returns the set of vertices of the graph."""
#         return self.out_mapping.keys()
# 
#     def out_dict(self, source):
#         """Returns a dictionary of the outgoing edges of source with weights."""
#         return self.out_mapping[source]
# 
#     def out_vertices(self, source):
#         """Returns a list of the outgoing vertices."""
#         return self.out_mapping[source].keys()
# 
#     def in_dict(self, target):
#         """Returns a dictionary of the incoming edges of source with weights."""
#         return self.in_mapping[target]
# 
#     def normalize_weights(self):
#         """Normalizes the weights coming out of each vertex to be probability
#         distributions."""
#         # new_edges = []
#         for source in self.out_mapping.keys():
#             total = float(sum(self.out_mapping[source].values()))
#             for target, weight in self.out_mapping.items():
#                 self.out_mapping[target] = weight / total
# 
#     def right_multiply(self, d):
#         """
#         Multiply by a vector (specified as a dict on the vertices) by 
#         viewing the graph as a sparse matrix, i.e.
#         return G*d
#         """
#         s = defaultdict(float)
#         for k in d.keys():
#             for k2, v2 in self.out_dict(k).items():
#                 s[k] += d[k2] * v2
#         return s
# 
#     def left_multiply(self, d):
#         """
#         Multiply by a vector (specified as a dict on the vertices) by 
#         viewing the graph as a sparse matrix, i.e.
#         return d*G
#         """
#         s = defaultdict(float)
#         for k in d.keys():
#             for k2, v2 in self.in_dict(k).items():
#                 s[k] += d[k2] * v2
#         return s
# 
#     def __getitem__(self, k):
#         """Returns the dictionary of outgoing edges. You can access the weight
#         of an edge with g[source][target]."""
#         return self.out_mapping[k]
# 
# Path: stationary/utils/edges.py
# def edges_to_edge_dict(edges):
#     """
#     Converts a list of edges to a transition dictionary taking (source, target)
#     to the transition between the states.
# 
#     Parameters
#     ----------
#     edges: list of tuples
#         Transition probabilities of the form [(source, target, transition
#         probability
# 
#     Returns
#     -------
#     edges, maps 2-tuples of nodes to floats
#     """
# 
#     edge_dict = dict()
#     for e1, e2, v in edges:
#         edge_dict[(e1, e2)] = v
#     return edge_dict


from .math_helpers import kl_divergence_dict
from .graph import Graph
from .edges import edges_to_edge_dict
from nose.tools import assert_almost_equal
    g = Graph(edges)

    for s1 in g.vertices():
        lhs = 0.
        rhs = 0.
        for s2, v in g.out_dict(s1).items():
            if s1 == s2:
                continue
            lhs += stationary[s1] * v
        for s2, v in g.in_dict(s1).items():
            if s1 == s2:
                continue
            rhs += stationary[s2] * v
        assert_almost_equal(lhs, rhs, places=places)


def check_eigenvalue(edges, s, places=3):
    """
    Check that the stationary distribution satisfies the eigenvalue condition.

    Parameters
    ----------
    edges: list of tuples
        transitions of the Markov process
    s: dict
        the stationary distribution
    places: int
        Decimal places of precision to require
    """


# Path: stationary/utils/math_helpers.py
# def kl_divergence_dict(p, q):
#     """
#     Computes the KL-divergence of distributions given as dictionaries.
#     """
#     s = 0.
# 
#     p_list = []
#     q_list = []
# 
#     for i in p.keys():
#         p_list.append(p[i])
#         q_list.append(q[i])
#     return kl_divergence(p_list, q_list)
# 
# Path: stationary/utils/graph.py
# class Graph(object):
#     """Directed graph object intended for the graph associated to a Markov process.
#     Gives easy access to the neighbors of a particular state needed for various
#     calculations.
# 
#     Vertices can be any hashable / immutable python object.
#     """
# 
#     def __init__(self, edges=None):
#         self.out_mapping = defaultdict(lambda: defaultdict(float))
#         self.in_mapping = defaultdict(lambda: defaultdict(float))
#         if edges:
#             self.add_edges(edges)
# 
#     def add_vertex(self, label):
#         self._vertices.add(label)
# 
#     def add_edge(self, source, target, weight=1.):
#         self.out_mapping[source][target] = weight
#         self.in_mapping[target][source] = weight
# 
#     def add_edges(self, edges):
#         try:
#             for source, target, weight in edges:
#                 self.add_edge(source, target, weight)
#         except ValueError:
#             for source, target in edges:
#                 self.add_edge(source, target, 1.0)
# 
#     def vertices(self):
#         """Returns the set of vertices of the graph."""
#         return self.out_mapping.keys()
# 
#     def out_dict(self, source):
#         """Returns a dictionary of the outgoing edges of source with weights."""
#         return self.out_mapping[source]
# 
#     def out_vertices(self, source):
#         """Returns a list of the outgoing vertices."""
#         return self.out_mapping[source].keys()
# 
#     def in_dict(self, target):
#         """Returns a dictionary of the incoming edges of source with weights."""
#         return self.in_mapping[target]
# 
#     def normalize_weights(self):
#         """Normalizes the weights coming out of each vertex to be probability
#         distributions."""
#         # new_edges = []
#         for source in self.out_mapping.keys():
#             total = float(sum(self.out_mapping[source].values()))
#             for target, weight in self.out_mapping.items():
#                 self.out_mapping[target] = weight / total
# 
#     def right_multiply(self, d):
#         """
#         Multiply by a vector (specified as a dict on the vertices) by 
#         viewing the graph as a sparse matrix, i.e.
#         return G*d
#         """
#         s = defaultdict(float)
#         for k in d.keys():
#             for k2, v2 in self.out_dict(k).items():
#                 s[k] += d[k2] * v2
#         return s
# 
#     def left_multiply(self, d):
#         """
#         Multiply by a vector (specified as a dict on the vertices) by 
#         viewing the graph as a sparse matrix, i.e.
#         return d*G
#         """
#         s = defaultdict(float)
#         for k in d.keys():
#             for k2, v2 in self.in_dict(k).items():
#                 s[k] += d[k2] * v2
#         return s
# 
#     def __getitem__(self, k):
#         """Returns the dictionary of outgoing edges. You can access the weight
#         of an edge with g[source][target]."""
#         return self.out_mapping[k]
# 
# Path: stationary/utils/edges.py
# def edges_to_edge_dict(edges):
#     """
#     Converts a list of edges to a transition dictionary taking (source, target)
#     to the transition between the states.
# 
#     Parameters
#     ----------
#     edges: list of tuples
#         Transition probabilities of the form [(source, target, transition
#         probability
# 
#     Returns
#     -------
#     edges, maps 2-tuples of nodes to floats
#     """
# 
#     edge_dict = dict()
#     for e1, e2, v in edges:
#         edge_dict[(e1, e2)] = v
#     return edge_dict


# Path: stationary/utils/matrix_checks.py
from .math_helpers import kl_divergence_dict
from .graph import Graph
from .edges import edges_to_edge_dict
from nose.tools import assert_almost_equal

    g = Graph(edges)

    for s1 in g.vertices():
        lhs = 0.
        rhs = 0.
        for s2, v in g.out_dict(s1).items():
            if s1 == s2:
                continue
            lhs += stationary[s1] * v
        for s2, v in g.in_dict(s1).items():
            if s1 == s2:
                continue
            rhs += stationary[s2] * v
        assert_almost_equal(lhs, rhs, places=places)


def check_eigenvalue(edges, s, places=3):
    """
    Check that the stationary distribution satisfies the eigenvalue condition.

    Parameters
    ----------
    edges: list of tuples
        transitions of the Markov process
    s: dict
        the stationary distribution
    places: int
        Decimal places of precision to require
    """


    g = Graph(edges)