Graphs

""" A Python Class A simple Python graph class, demonstrating the essential facts and functionalities of graphs. Taken from https://www.python-course.eu/graphs_python.php Changed the implementation a little bit to include weighted edges """

class Graph(object):
    def __init__(self, graph_dict=None):
        """ initializes a graph object 
            If no dictionary or None is given, 
            an empty dictionary will be used
        """
        if graph_dict == None:
            graph_dict = {}
        self.__graph_dict = graph_dict

    def vertices(self):
        """ returns the vertices of a graph """
        return list(self.__graph_dict.keys())

    def edges(self):
        """ returns the edges of a graph """
        return self.__generate_edges()

    def add_vertex(self, vertex):
        """ If the vertex "vertex" is not in 
            self.__graph_dict, a key "vertex" with an empty
            dict as a value is added to the dictionary. 
            Otherwise nothing has to be done. 
        """
        if vertex not in self.__graph_dict:
            self.__graph_dict[vertex] = {}

    def add_edge(self, edge,weight=1):
        """ assumes that edge is of type set, tuple or list
        """
        edge = set(edge)
        (vertex1, vertex2) = tuple(edge)
        if vertex1 in self.__graph_dict:
            self.__graph_dict[vertex1][vertex2] = weight
        else:
            self.__graph_dict[vertex1] = {vertex2:weight}

        if vertex2 in self.__graph_dict:
            self.__graph_dict[vertex2][vertex1] = weight
        else:
            self.__graph_dict[vertex2] = {vertex1:weight}


    def __generate_edges(self):
        """ A static method generating the edges of the 
            graph "graph". Edges are represented as sets 
            with one (a loop back to the vertex) or two 
            vertices 
        """
        edges = []
        for vertex in self.__graph_dict:
            for neighbour,weight in self.__graph_dict[vertex].iteritems():
                if (neighbour, vertex, weight) not in edges:
                    edges.append([vertex, neighbour, weight])
        return edges

    def __str__(self):
        res = "vertices: "
        for k in self.__graph_dict:
            res += str(k) + " "
        res += "\nedges: "
        for edge in self.__generate_edges():
            res += str(edge) + " "
        return res

    def adj_mat(self):
        return self.__graph_dict

### Usage:
g = { "a" : {"d":2},
      "b" : {"c":2},
      "c" : {"b":5,  "d":3, "e":5}
    }
graph = Graph(g)
print("Vertices of graph:")
print(graph.vertices())
print("Edges of graph:")
print(graph.edges())
print("Add vertex:")
graph.add_vertex("z")
print("Vertices of graph:")
print(graph.vertices()) 
print("Add an edge:")
graph.add_edge({"a","z"})    
print("Vertices of graph:")
print(graph.vertices())
print("Edges of graph:")
print(graph.edges())
print('Adding an edge {"x","y"} with new vertices:')
graph.add_edge({"x","y"})
print("Vertices of graph:")
print(graph.vertices())
print("Edges of graph:")
print(graph.edges())

Vertices of graph: ['a', 'c', 'b'] Edges of graph: [['a', 'd', 2], ['c', 'b', 5], ['c', 'e', 5], ['c', 'd', 3], ['b', 'c', 2]] Add vertex: Vertices of graph: ['a', 'c', 'b', 'z'] Add an edge: Vertices of graph: ['a', 'c', 'b', 'z'] Edges of graph: [['a', 'z', 1], ['a', 'd', 2], ['c', 'b', 5], ['c', 'e', 5], ['c', 'd', 3], ['b', 'c', 2], ['z', 'a', 1]] Adding an edge {"x","y"} with new vertices: Vertices of graph: ['a', 'c', 'b', 'y', 'x', 'z'] Edges of graph: [['a', 'z', 1], ['a', 'd', 2], ['c', 'b', 5], ['c', 'e', 5], ['c', 'd', 3], ['b', 'c', 2], ['y', 'x', 1], ['x', 'y', 1], ['z', 'a', 1]]

Knowledge graph

https://terminusdb.com/ . Graph database A large number of knowledge graphs have been created, including YAGO, DBpedia, NELL, Freebase [7], and the Google Knowledge Graph [8]

Semantic Web community creating a “web of data” that is readable by machines [14]. While this vision of the Semantic Web remains to be fully realized, parts of it have been achieved. In particular, the concept of linked data [15, 16] has gained traction, as it facilitates publishing and interlinking data on the Web in relational form using the W3C Resource Description Framework (RDF) [17, 18]. (For an introduction to knowledge representation, see e.g. [11, 19, 20]). In this article, we will loosely follow the RDF standard and represent facts in the form of binary relationships, in particular (subject, predicate, object) (SPO) triples, where subject and object are entities and predicate is the relation between them

https://arxiv.org/pdf/1503.00759.pdf

https://towardsdatascience.com/extracting-knowledge-from-knowledge-graphs-e5521e4861a0

Graph Databases

https://medium.com/terminusdb/why-graph-will-win-703373bb5c41

https://www.reddit.com/r/programming/comments/fcc9cl/20_years_from_now_nongraph_databases_will_be/

https://news.ycombinator.com/item?id=22051271 https://nebula-graph.io/ . C++ graph DB https://blog.dgraph.io/ https://news.ycombinator.com/item?id=20575502 . dGraph https://www.zdnet.com/article/you-can-go-your-own-graph-database-way-dgraph-secures-115m-to-pursue-its-opinionated-path/ https://grakn.ai/ https://www.tigergraph.com/ . TigerGraph https://docs.ampligraph.org/en/latest/

https://www.ebayinc.com/stories/blogs/tech/beam-a-distributed-knowledge-graph-store/ . Beam (Apache) https://blog.dgraph.io/post/why-google-needed-graph-serving-system/ https://stats.stackexchange.com/questions/351231/knowledge-graph-how-to-get-into-it

https://mlwhiz.com/blog/2018/12/07/connected_components/

https://www.meetup.com/ko-KR/Graph-Database-in-Silicon-Valley/ https://github.com/Alnaimi-/database-benchmark . Vertica vs Neo4j https://bitnine.net/ https://news.ycombinator.com/item?id=18352754 . Graph database discussion

http://heyrod.com/projects/gv-cookbook.html . GraphViz CookBook https://news.ycombinator.com/item?id=18527104 . Cytoscape.js http://sigmajs.org/ https://github.com/anvaka/VivaGraphJS

https://blog.evjang.com/2018/08/dijkstras.html

https://www.oreilly.com/ideas/fishing-for-graphs-in-a-hadoop-data-lake https://news.ycombinator.com/item?id=16230910 - discussion http://aosabook.org/en/500L/dagoba-an-in-memory-graph-database.html https://mrpandey.github.io/d3graphTheory/ https://liveramp.com/engineering/efficiently-analyzing-600-billion-edge-graph-real-time/ http://ontodia.org/ platform to build web applications for exploration and visualization of graph data https://www.blazegraph.com/ https://aws.amazon.com/neptune/ http://book.validatingrdf.com/index.html

Graph Search and Visualization in JS

https://github.com/anvaka/ngraph.path . JS graph Quadtree

KD-Tree(K-мерное дерево), специальная 'геометрическая' структура данных, которая позволяет разбить K-мерное пространство на 'меньшие части', посредством сечения этого самого пространства гиперплоскостями(K > 3), плоскостями (K = 3), прямыми (K = 2 https://habrahabr.ru/post/312882/

Метод оптимизации Нелдера — Мида. Python https://habrahabr.ru/post/332092/ https://habrahabr.ru/post/344378/

https://jeremykun.com/2017/11/08/binary-search-on-graphs/

http://aosabook.org/en/500L/dagoba-an-in-memory-graph-database.html https://www.voxxed.com/2017/03/handling-billions-of-edges-graph-database/ https://blog.grakn.ai/modelling-data-with-hypergraphs-edff1e12edf0 https://medium.com/@chetcorcos/introduction-to-parsers-644d1b5d7f3d https://python-graph-gallery.com/

Load balancing

https://blog.envoyproxy.io/introduction-to-modern-network-load-balancing-and-proxying-a57f6ff80236 https://news.ycombinator.com/item?id=16151879

JavaScript Graphs WebGL

https://github.com/ericdrowell/ElGrapho https://github.com/graphistry/pygraphistry https://github.com/alx/parasol https://news.ycombinator.com/item?id=19598372

Maps

https://andrewcooke.github.io/choochoo/rtree . spatial search https://habrahabr.ru/post/346714/ OpenStreetMap https://news.ycombinator.com/item?id=16149725 LeafLet

Search

midium.com/@forwidur Max Grigorev https://habrahabr.ru/post/346884/ Reindexer - text search https://habrahabr.ru/post/354034/ Text search

https://news.ycombinator.com/item?id=18582469 https://dzone.com/articles/how-to-build-a-google-search-autocomplete How to Build a Google Search Autocomplete https://dzone.com/articles/searching-shouldnt-be-so-hard

https://news.ycombinator.com/item?id=15676681 Search https://www.youtube.com/watch?v=1-Xoy5w5ydM BitFunnel https://dl.acm.org/citation.cfm?id=3080789 BitFunnel