def load_shp(shp_path):
    """ loads a shapefile into a networkx based GeoGraph object

    Args:
        shp_path:  string path to a line or point shapefile

    Returns:
        geograph:  GeoGraph

    """

    # NOTE:  if shp_path is unicode io doesn't work for some reason
    shp_path = shp_path.encode('ascii', 'ignore')
    g = nx.read_shp(shp_path)
    coords = dict(enumerate(g.nodes()))

    driver = ogr.GetDriverByName('ESRI Shapefile')
    shp = driver.Open(shp_path)
    layer = shp.GetLayer()

    spatial_ref = layer.GetSpatialRef()
    proj4 = None
    if not spatial_ref:
        if gm.is_in_lon_lat(coords):
            proj4 = gm.PROJ4_LATLONG
        else:
            warnings.warn("Spatial Reference could not be set for {}".
                format(shp_path))

    else:
        proj4 = spatial_ref.ExportToProj4()

    g = nx.convert_node_labels_to_integers(g)

    return GeoGraph(srs=proj4, coords=coords, data=g)

 def buildNetwork(self):
     '''Method to create NetworkX nodes and edges shapefiles.'''
     try:
         layer = str(self.filelist[self.ui.comboBoxInput.currentIndex()])
         if layer == "Available layers:":
             raise IOError, "Please specify input shapefile layer."
              
         DG1 = nx.read_shp(layer)
         if str(self.ui.lineEditSave.text()) == '':
             raise IOError, "No output directory specified."
              
         WriteNetworkShapefiles(DG1, self.fd, overwrite=True)
         #self.writeNetworkShapefiles(DG1)                        
         if self.ui.checkBoxAdd.isChecked():
             # Get created files
             nodes = self.fd+"/nodes.shp"
             edges = self.fd+"/edges.shp"
             # Add to QGIS instance
             qgis.utils.iface.addVectorLayer(edges, "Network Edges", "ogr")
             qgis.utils.iface.addVectorLayer(nodes, "Network Nodes", "ogr")
          
         self.close()
     except (AttributeError, IOError) as e:
         QtGui.QMessageBox.warning( self, "NetworkX Plugin Error", 
                                          "%s" % e)

    def from_files(cls, shp, csv, **kwargs):
        """
        Parameters
        ----------
        shp : file or string (File, directory, or filename to read).
        csv : string or file handle / StringIO.
        
        Example
        ----------
        NetworkPlan.from_files('networks-proposed.shp', 
                               'metrics-local.csv')
        """

        # Only supports longlat format for now
        # with fiona.open(shp) as shapefile:
        #     # Pass along the projection
        #     if 'proj' in shapefile.crs:
        #         kwargs['proj'] = shapefile.crs['proj']
 
        # Ignore the PROJ.4 header if there
        skip_rows = 0
        with open(csv) as csv_stream:
            if csv_stream.readline().startswith('PROJ.4'):
                skip_rows = 1

        # networkx read_shp fails on unicode paths, so try ascii
        if isinstance(shp, unicode):
            shp = shp.encode("ascii")

        return cls(nx.read_shp(shp), pd.read_csv(csv, skiprows=skip_rows), **kwargs)

 def test_geometryexport(self):
     def testgeom(lyr, expected):
         feature = lyr.GetNextFeature()
         actualwkt = []
         while feature:
             actualwkt.append(feature.GetGeometryRef().ExportToWkt())
             feature = lyr.GetNextFeature()
         assert_equal(sorted(expected), sorted(actualwkt))
     expectedpoints = (
         "POINT (1 1)",
         "POINT (2 2)",
         "POINT (3 3)",
         "POINT (0.9 0.9)",
         "POINT (4 2)"
     )
     expectedlines = (
         "LINESTRING (1 1,2 2)",
         "LINESTRING (2 2,3 3)",
         "LINESTRING (0.9 0.9,4 2)"
     )
     tpath = os.path.join(tempfile.gettempdir(),'shpdir')
     G = nx.read_shp(self.shppath)
     nx.write_shp(G, tpath)
     shpdir = ogr.Open(tpath)
     testgeom(shpdir.GetLayerByName("nodes"), expectedpoints)
     testgeom(shpdir.GetLayerByName("edges"), expectedlines)

 def testload(self):
     expected = nx.DiGraph()
     for p in self.paths:
         expected.add_path(p)
     actual = nx.read_shp(self.shppath)
     assert_equal(sorted(expected.node), sorted(actual.node))
     assert_equal(sorted(expected.edges()), sorted(actual.edges()))

 def testload(self):
     expected = nx.DiGraph()
     map(expected.add_path, self.paths)
     G = nx.read_shp(self.shppath)
     assert_equal(sorted(expected.node), sorted(G.node))
     assert_equal(sorted(expected.edges()), sorted(G.edges()))
     names = [G.get_edge_data(s,e)['Name'] for s,e in G.edges()]
     assert_equal(self.names, sorted(names))

    def test_geometryexport(self):
        expectedpoints_simple = (
            "POINT (1 1)",
            "POINT (2 2)",
            "POINT (3 3)",
            "POINT (0.9 0.9)",
            "POINT (4 2)"
        )
        expectedlines_simple = (
            "LINESTRING (1 1,2 2)",
            "LINESTRING (2 2,3 3)",
            "LINESTRING (0.9 0.9,4.0 0.9,4 2)"
        )
        expectedpoints = (
            "POINT (1 1)",
            "POINT (2 2)",
            "POINT (3 3)",
            "POINT (0.9 0.9)",
            "POINT (4.0 0.9)",
            "POINT (4 2)"
        )
        expectedlines = (
            "LINESTRING (1 1,2 2)",
            "LINESTRING (2 2,3 3)",
            "LINESTRING (0.9 0.9,4.0 0.9)",
            "LINESTRING (4.0 0.9,4 2)"
        )


        tpath = os.path.join(tempfile.gettempdir(), 'shpdir')
        G = nx.read_shp(self.shppath)
        nx.write_shp(G, tpath)
        shpdir = ogr.Open(tpath)
        self.checkgeom(shpdir.GetLayerByName("nodes"), expectedpoints_simple)
        self.checkgeom(shpdir.GetLayerByName("edges"), expectedlines_simple)

        # Test unsimplified 
        # Nodes should have additional point, 
        # edges should be 'flattened'
        G = nx.read_shp(self.shppath, simplify=False)
        nx.write_shp(G, tpath)
        shpdir = ogr.Open(tpath)
        self.checkgeom(shpdir.GetLayerByName("nodes"), expectedpoints)
        self.checkgeom(shpdir.GetLayerByName("edges"), expectedlines)

    def testload(self):

        def compare_graph_paths_names(g, paths, names):
            expected = nx.DiGraph()
            for p in paths:
                expected.add_path(p)
            assert_equal(sorted(expected.node), sorted(g.node))
            assert_equal(sorted(expected.edges()), sorted(g.edges()))
            g_names = [g.get_edge_data(s, e)['Name'] for s, e in g.edges()]
            assert_equal(names, sorted(g_names))
                
        # simplified
        G = nx.read_shp(self.shppath)
        compare_graph_paths_names(G, self.simplified_paths, \
                                    self.simplified_names)
       
        # unsimplified
        G = nx.read_shp(self.shppath, simplify=False)
        compare_graph_paths_names(G, self.paths, self.names)

def shp_to_graph(shp_path):
    graph_shp = nx.read_shp(str(shp_path))
    shp = QgsVectorLayer(shp_path, "network", "ogr")
    # parallel edges are excluded of the graph because read_shp does not return a multi-graph, self-loops are included
    #self_loops = [[feat.id(), feat.geometry().asPolyline()[0],feat.attributes()]for feat in shp.getFeatures() if feat.geometry().asPolyline()[0] == feat.geometry().asPolyline()[-1] ]
    # parallel_edges =
    graph = graph_shp.to_undirected(reciprocal=False)
    #column_names = [i.name() for i in shp.pendingFields()]
    #for i in self_loops:
    #    graph.add_edge(i[1],i[1],dict(zip(column_names,i[2])))
    return graph

 def __init__(self, shapefile, edge_weighted_by_distance=True):
     g = nx.read_shp(shapefile)
     mg = max(nx.connected_component_subgraphs(g.to_undirected()), key=len)
     if edge_weighted_by_distance:
         for n0, n1 in mg.edges_iter():
             path = np.array(json.loads(mg[n0][n1]['Json'])['coordinates'])
             distance = np.sum(
                 greate_circle_distance(path[1:,0],path[1:,1], path[:-1,0], path[:-1,1])
             )
             mg.edge[n0][n1]['distance'] = distance
     self.graph = mg
     self._cache = {}
     self._cache_nn = {}

    def test_attributeexport(self):
        def testattributes(lyr, expected):
            feature = lyr.GetNextFeature()
            actualvalues = []
            while feature:
                actualvalues.append(feature.GetGeometryRef().ExportToWkt())
                feature = lyr.GetNextFeature()
            assert_equal(sorted(expected), sorted(actualvalues))

        tpath = os.path.join(tempfile.gettempdir(),'shpdir')
        G = nx.read_shp(self.shppath)
        nx.write_shp(G, tpath)
        shpdir = ogr.Open(tpath)
        nodes = shpdir.GetLayerByName("nodes")

def mappingOneDay():
	for i in range(13340):
		try:
			g = nx.read_shp('./Graph/edges.shp')
			G = nx.Graph()
			G.add_edges_from(g.edges())
			filename = './data/' + str(i) + '.txt'
			Graph = MapReader().mapGraph
			mappingOneTaxi(filename, Graph, G)
			del g
			del G
		except Exception,e:
			fp = open('log_taxi.txt','a')
			fp.write(str(e)+'\n'+str(i)+'.txt'+'\n')
			fp.close()

def read_shp_to_graph(shp_path):
    graph_shp = nx.read_shp(str(shp_path), simplify=True)
    shp = QgsVectorLayer(shp_path, "network", "ogr")
    graph = nx.MultiGraph(graph_shp.to_undirected(reciprocal=False))
    # parallel edges are excluded of the graph because read_shp does not return a multi-graph, self-loops are included
    all_ids = [i.id() for i in shp.getFeatures()]
    ids_incl = [i[2]['feat_id'] for i in graph.edges(data=True)]
    ids_excl = set(all_ids) - set(ids_incl)
    request = QgsFeatureRequest().setFilterFids(list(ids_excl))
    excl_features = [feat for feat in shp.getFeatures(request)]
    ids_excl_attr = [[i.geometry().asPolyline()[0], i.geometry().asPolyline()[-1], i.attributes()] for i in excl_features]
    column_names = [i.name() for i in shp.dataProvider().fields()]
    for i in ids_excl_attr:
        graph.add_edge(i[0], i[1], attr_dict=dict(zip(column_names,i[2])))
    return graph

    def test_missing_attributes(self):
        G = nx.DiGraph()
        A = (0, 0)
        B = (1, 1)
        C = (2, 2)
        G.add_edge(A, B, foo=100)
        G.add_edge(A, C)

        nx.write_shp(G, self.path)
        H = nx.read_shp(self.path)

        for u, v, d in H.edges(data=True):
            if u == A and v == B:
                assert_equal(d['foo'], 100)
            if u == A and v == C:
                assert_equal(d['foo'], None)

    def test_attributeexport(self):
        def testattributes(lyr, graph):
            feature = lyr.GetNextFeature()
            while feature:
                coords = []
                ref = feature.GetGeometryRef()
                last = ref.GetPointCount() - 1
                edge_nodes = (ref.GetPoint_2D(0), ref.GetPoint_2D(last))
                name = feature.GetFieldAsString('Name')
                assert_equal(graph.get_edge_data(*edge_nodes)['Name'], name)
                feature = lyr.GetNextFeature()

        tpath = os.path.join(tempfile.gettempdir(), 'shpdir')

        G = nx.read_shp(self.shppath)
        nx.write_shp(G, tpath)
        shpdir = ogr.Open(tpath)
        edges = shpdir.GetLayerByName("edges")
        testattributes(edges, G)

 def test_geometryexport(self):
     expectedpoints = (
         "POINT (1 1)",
         "POINT (2 2)",
         "POINT (3 3)",
         "POINT (0.9 0.9)",
         "POINT (4 2)"
     )
     expectedlines = (
         "LINESTRING (1 1,2 2)",
         "LINESTRING (2 2,3 3)",
         "LINESTRING (0.9 0.9,4 2)"
     )
     tpath = os.path.join(tempfile.gettempdir(),'shpdir')
     G = nx.read_shp(self.shppath)
     nx.write_shp(G, tpath)
     shpdir = ogr.Open(tpath)
     self.checkgeom(shpdir.GetLayerByName("nodes"), expectedpoints)
     self.checkgeom(shpdir.GetLayerByName("edges"), expectedlines)

    def __init__(self, shp, csv, **kwargs):
        self.shp_p, self.csv_p = shp, csv
        self.priority_metric = kwargs['prioritize'] if 'prioritize' in kwargs else 'population'

        # logger.info('Asserting Input Projections Match')
        # self._assert_proj_match(shp, csv)

        from geometryIO import load
        proj4 = load(shp)[0]
        self.measure = 'haversine' if 'longlat' in proj4 else 'euclidean'

        # Load in and align input data
        logger.info('Aligning Network Nodes With Input Metrics')
        self._network, self._metrics = prep_data( nx.read_shp(shp),
                                                  # pd.read_csv(csv, header=1),
                                                  pd.read_csv(csv),
                                                  loc_tol = self.TOL)

        logger.info('Computing Pairwise Distances')
        self.distance_matrix = self._distance_matrix()
         
        if len(self.distance_matrix[(self.distance_matrix > 0) & (self.distance_matrix < self.TOL)]) > 0:
            logger.error("""Dataset Contains Edges, Less Than {tolerance} Meters! 
                          This can result in incorrect alignment of metrics and network, 
                          where fake nodes are incorrectly assigned metrics. 
                          This error is resolved by buffering your input data.""".format(tolerance=self.TOL))

        # Set the edge weight to the distance between those nodes
        self._weight_edges()
        
        logger.info('Directing Network Away From Roots')
        # Transform edges to a rooted graph
        self.direct_network()

        # Assert that the netork is a tree
        self.assert_is_tree()

        # Build list of fake nodes
        self.fake_nodes = self.fakes(self.metrics.index)

        #Fillna values with Zero
        self._metrics = self.metrics.fillna(0)

    min_distance = None
    for node in graph.nodes():
        distance = calc_distance(node[1], node[0], latitude, longitude)
        if closest_node == None:
            closest_node = node
            min_distance = distance
        elif distance < min_distance:
            closest_node = node
            min_distance = distance
    return closest_node

#############################################################################

print "Loading road network into memory..."

graph = networkx.read_shp("split_roads/split_roads.shp")
print "graph has %d nodes and %d edges" % (len(graph.nodes()),
                                           len(graph.edges()))

graph = networkx.connected_component_subgraphs(graph.to_undirected()).next()

print "Calculating road lengths..."

num_roads = len(graph.edges())
num_done = 0
for node1,node2 in graph.edges():
    if num_done % 1000 == 0:
        print "  %d%% done" % int(100 * float(num_done) / float(num_roads))
    num_done = num_done + 1

    wkt = graph[node1][node2]['Wkt']

	def __init__(self):
		self.MapData = nx.read_shp('./map/111.shp')

import networkx as nx
import numpy as np
import pandas as pd
import json
import smopy
import matplotlib.pyplot as plt

import matplotlib as mpl
mpl.rcParams['figure.dpi'] = mpl.rcParams['savefig.dpi'] = 300
# g = nx.read_shp("eotroads_49/eotroads_49.shp")
g = nx.read_shp("data/tl_2013_06_prisecroads.shp")
print len(g.edges())
# print g.adjacency_list()
sgs = list(nx.connected_component_subgraphs(g.to_undirected()))
sg = sgs[0]

for element in sgs:
	if element.order() > sg.order():
		sg = element

print sg.order()
print len(sg.edges())
print sg.adjacency_list()

# pos2 = (36.6026, -121.9026)
# pos1 = (34.0569, -118.2427)
#Silicon Valley
# pos0 = (37.3627, -122.0323)
#LA
pos1 = (34.045536, -118.446065)