Topological Sort - Which Tasks Should Be Executed First

Birbirine bağımlı olan işleri dikkate alacak şekilde graph'ı sıralar. Graph'ın directed olması gerekir. Açıklaması şöyle.

The minimum spanning tree ensures that your internet traffic gets delivered even when cables break.

Topological sort is used in project planning to decide which tasks should be executed first.

Disjoint sets help you efficiently calculate currency conversions between NxN currencies in linear time

Graph coloring can in theory be used to decide which seats in a cinema should remain free during a infectious disease outbreak.

Detecting strongly connected components helps uncover bot networks spreading misinformation on Facebook and Twitter.

DAGs are used to perform very large computations distributed over thousands of machines in software like Apache Spark and Tensorflow

Graph içinde cycle yani döngüler olmamalı. Yani Directed Acyclic olmalı. Açıklaması şöyle.

For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG)

Graph Algoritmaları

Algoritmalar

Algoritmaları şeklen gösteren bir link burada

1. Breadth First Search. LeetCode Breadth First Search yazısına bakabilirsiniz

2. Depth First Search

3. Dijkstra's Shortest Path

4. Cycle Detection

5. Strongly Connected

6. Topological Sorting

7. Graph Coloring

8. Maximum Flow

9. Matching

10. Minimum Spanning Tree

11. B+ Tree

Tam olarak Graph Veri Yapısı sayılmasa da not almak istedim. Temel kural şöyle.

Root hariç her düğümde 3 pointer ve en az 1 leaf node olmalı.

Graph Nerede Kullanılır

1. Optimization Problems

Açıklaması şöyle.

Algorithms like Dijkstra's enable your navigation system / GPS to decide which roads you should drive on to reach a destination.

The Hungarian Algorithm can assign each Uber car to people looking for a ride (an assignment problem)

Chess, Checkers, Go and Tic-Tac-Toe are formulated as a game tree (a degenerate graph) and can be "solved" using brute-force depth or breadth first search, or using heuristics with minimax or A*

Flow networks and algorithms like maximum flow can be used in modelling utilities networks (water, gas, electricity), roads, flight scheduling, supply chains.

2. Specialized types of graphs
Açıklaması şöyle.

Bayesian networks were used by NASA to select an operating system for the space shuttle

Neural networks are used in language translation, image synthesis (such as fake face generation), color recovery of black-and-white images, speech synthesis

Graph İçin Temel Bilgiler

1. Düğüm

Vertex veya node olarak adlandırılır.

2. Directed Graph
Tek yönlüdür. Şöyledir.

A —> B —> <— C 
     |
     v
     E <— F —> D —> G

X -> <- Y

node : neighbors
  A  :  [B]
  B  :  [C, E]
  C  :  [B]
  D  :  [G]
  E  :  []
  F  :  [E, D]
  G  :  []
  X  :  [Y]
  Y  :  [X]

3. Undirected Graph
Düğümler arasında yön bilgisi yoktur. Çizgiler için genellikle bir ağırlık verilir.

A--5--B
|   /
2  3
| /
 C

4. Graph İçin Kullanılan Temel Veri Yapıları
Sparse olan graph'lar için adjacency list - komşuluk listesi - kullanılır. Dolu olan graph'larda ise adjaceny matrix kullanılır. Adjaceny list şuna benzer.

* 1   -> 2   4
* 2   -> 3   1
* 3   -> 2   4
* 4   -> 3   1

Düğümün komşularını saklamak için vector, list, hashmap gibi herhangi bir veri yapısı kullanılabilir. Basit bir Java örneği

public class SimpleAdjacencyList {
    private Map<Integer, List<Vertex>> adjacencyList = new HashMap<>();
}

Yukarıdaki kodda Map Value değeri için şöyle bir sınıf tanımlamak daha iyi olabilir.

public class DirectedGraphNode {
    String val;
    List<DirectedGraphNode> neighbors;
}

Session Fixation Nedir ?

Giriş

Açıklaması şöyle

What is Session Fixation?

In Session Fixation attacks, the attacker hijacks a valid user session. We said that we sign the cookie in order to be sure that no one can hijack another user's valid session. But what if the attacker has his own valid session and tries to associate it with another user? in this case he can perform actions on behalf of the victim.

The problems occur when we are not generating new sessionIds(unique identifier) on actions like Login.

How can the Attacker do this?

One of the cases is when attacker has physical access to the computer. As an attacker, I go to the university and I choose one of the shared computers, then I sign into my account on the vulnerablewebsite.com and then without doing the logout (which normally destroys the session in the server store), I leave an open login page on vulnerablewebsite.com and before that I have to copy my valid sessionId. Now the victim is using this computer and if the victim signs in, the attacker sessionId is associated with the victim's account. 

Yani A kişisi giriş (login) yaptıktan sonra çıkış (log out) yapmıyor. Daha B kişisi geliyor ve  giriş yapıyor. Sunucu ikinci kişi için yeni bir session id üretmek yerine A kişisine ait session id değerini kullanmaya devam ediyor. Böylece A kişisi B kişisinin bilgilerine erişebilir

Çözüm

Her giriş işleminde yeni bir session id üretmek

Server Side Public License (SSPL) Lisans

Giriş

Server Side Public License (SSPL) başarılı açık kaynak projeler tarafından kullanılıyor. Amaç bulut sağlayıcılarının açık kaynak projeyi yeniden paketleyerek gelir elde edip, açık kaynak projeye hiç bir katkıda bulunmamasını önlemek.