🌍 10.7: Graf Örnekleri

from collections import defaultdict

class SocialNetwork:
    """Sosyal ağ graf modeli"""
    
    def __init__(self):
        self.friendships = defaultdict(set)
    
    def add_friendship(self, person1, person2):
        """Çift yönlü arkadaşlık ekle"""
        self.friendships[person1].add(person2)
        self.friendships[person2].add(person1)
    
    def get_friends(self, person):
        """Direkt arkadaşları getir"""
        return self.friendships[person]
    
    def suggest_friends(self, person, limit=3):
        """
        Arkadaş önerisi - 'Ortak arkadaş' yöntemi
        
        Mantık: Seni tanımayan ama seninle ortak arkadaşları olan kişiler
        iyi arkadaş adaylarıdır!
        """
        direct_friends = self.get_friends(person)
        suggestions = defaultdict(int)  # {önerilen: ortak arkadaş sayısı}
        
        # Her arkadaşın arkadaşlarına bak
        for friend in direct_friends:
            for friend_of_friend in self.get_friends(friend):
                # Kendisi veya zaten arkadaş değilse
                if friend_of_friend != person and friend_of_friend not in direct_friends:
                    suggestions[friend_of_friend] += 1
        
        # Ortak arkadaş sayısına göre sırala
        sorted_suggestions = sorted(
            suggestions.items(), 
            key=lambda x: x[1], 
            reverse=True
        )
        
        return sorted_suggestions[:limit]
    
    def mutual_friends(self, person1, person2):
        """İki kişinin ortak arkadaşları"""
        friends1 = self.get_friends(person1)
        friends2 = self.get_friends(person2)
        return friends1.intersection(friends2)


# Sosyal ağ oluştur
network = SocialNetwork()

# Arkadaşlıklar
friendships = [
    ('Ali', 'Veli'), ('Ali', 'Ayşe'), ('Ali', 'Fatma'),
    ('Veli', 'Mehmet'), ('Veli', 'Ayşe'),
    ('Ayşe', 'Zeynep'), ('Ayşe', 'Can'),
    ('Fatma', 'Zeynep'), ('Fatma', 'Deniz'),
    ('Mehmet', 'Can'), ('Zeynep', 'Can')
]

for p1, p2 in friendships:
    network.add_friendship(p1, p2)

print("=== SOSYAL AĞ ANALİZİ ===\n")
print("Arkadaşlık ağı:")
for person in sorted(network.friendships.keys()):
    friends = sorted(network.friendships[person])
    print(f"  {person}: {friends}")

print("\n=== ALİ İÇİN ARKADAŞ ÖNERİLERİ ===")
suggestions = network.suggest_friends('Ali')
for suggested, mutual_count in suggestions:
    print(f"  {suggested} ({mutual_count} ortak arkadaş)")

print("\n=== ORTAK ARKADAŞLAR ===")
print(f"Ali & Mehmet: {network.mutual_friends('Ali', 'Mehmet')}")
print(f"Ali & Can: {network.mutual_friends('Ali', 'Can')}")

from collections import deque, defaultdict

def find_communities(friendships_list):
    """
    Bağlantılı bileşenler = Topluluklar
    
    Her bağlantılı grup ayrı bir topluluk olarak kabul edilir.
    """
    # Graf oluştur
    graph = defaultdict(set)
    for p1, p2 in friendships_list:
        graph[p1].add(p2)
        graph[p2].add(p1)
    
    visited = set()
    communities = []
    
    for person in graph:
        if person not in visited:
            # Yeni topluluk bulduk - BFS ile keşfet
            community = []
            queue = deque([person])
            
            while queue:
                current = queue.popleft()
                if current in visited:
                    continue
                
                visited.add(current)
                community.append(current)
                
                for friend in graph[current]:
                    if friend not in visited:
                        queue.append(friend)
            
            communities.append(sorted(community))
    
    return communities


def find_influencers(friendships_list, top_n=3):
    """
    Etki sahibi kişileri bul - Derece (arkadaş sayısı) analizi
    
    Daha gelişmiş: PageRank, Betweenness Centrality
    """
    degree = defaultdict(int)
    
    for p1, p2 in friendships_list:
        degree[p1] += 1
        degree[p2] += 1
    
    sorted_by_degree = sorted(
        degree.items(),
        key=lambda x: x[1],
        reverse=True
    )
    
    return sorted_by_degree[:top_n]


# Test verileri - iki ayrı topluluk
friendships = [
    # Topluluk 1: Üniversite arkadaşları
    ('Ali', 'Veli'), ('Ali', 'Ayşe'), ('Veli', 'Ayşe'),
    ('Ayşe', 'Fatma'), ('Fatma', 'Veli'),
    
    # Topluluk 2: İş arkadaşları
    ('Can', 'Deniz'), ('Can', 'Elif'),
    ('Deniz', 'Elif'), ('Elif', 'Gül'),
    
    # Topluluk 3: Aile
    ('Hasan', 'Hüseyin')
]

print("=== TOPLULUK TESPİTİ ===\n")
communities = find_communities(friendships)

for i, community in enumerate(communities, 1):
    print(f"Topluluk {i}: {community}")

print(f"\n📊 Toplam {len(communities)} topluluk bulundu")

print("\n=== EN ETKİLİ KİŞİLER (Derece Analizi) ===")
influencers = find_influencers(friendships)
for person, degree in influencers:
    print(f"  {person}: {degree} bağlantı")

import heapq
from collections import defaultdict

class CityNavigation:
    """Şehir navigasyon sistemi"""
    
    def __init__(self):
        # {location: [(neighbor, distance, road_name), ...]}
        self.roads = defaultdict(list)
    
    def add_road(self, loc1, loc2, distance, road_name=""):
        """Çift yönlü yol ekle"""
        self.roads[loc1].append((loc2, distance, road_name))
        self.roads[loc2].append((loc1, distance, road_name))
    
    def find_shortest_path(self, start, end):
        """Dijkstra ile en kısa yol"""
        if start not in self.roads or end not in self.roads:
            return None, float('inf'), []
        
        distances = {loc: float('inf') for loc in self.roads}
        distances[start] = 0
        previous = {loc: (None, "") for loc in self.roads}
        
        pq = [(0, start)]
        visited = set()
        
        while pq:
            dist, current = heapq.heappop(pq)
            
            if current in visited:
                continue
            visited.add(current)
            
            if current == end:
                break
            
            for neighbor, road_dist, road_name in self.roads[current]:
                if neighbor not in visited:
                    new_dist = dist + road_dist
                    if new_dist < distances[neighbor]:
                        distances[neighbor] = new_dist
                        previous[neighbor] = (current, road_name)
                        heapq.heappush(pq, (new_dist, neighbor))
        
        # Yolu oluştur
        path = []
        roads_taken = []
        current = end
        
        while current is not None:
            path.append(current)
            prev_loc, road_name = previous[current]
            if road_name:
                roads_taken.append(road_name)
            current = prev_loc
        
        path.reverse()
        roads_taken.reverse()
        
        return path, distances[end], roads_taken
    
    def print_directions(self, start, end):
        """Yol tarifi yazdır"""
        path, distance, roads = self.find_shortest_path(start, end)
        
        if distance == float('inf'):
            print(f"❌ {start} → {end} arası yol bulunamadı!")
            return
        
        print(f"\n🗺️ YOL TARİFİ: {start} → {end}")
        print(f"📏 Toplam mesafe: {distance} km\n")
        
        for i in range(len(path) - 1):
            from_loc = path[i]
            to_loc = path[i + 1]
            road = roads[i] if i < len(roads) else ""
            print(f"  {i+1}. {from_loc} → {to_loc} ({road})")
        
        print(f"\n✅ Varış: {end}")


# İstanbul haritası (basitleştirilmiş)
nav = CityNavigation()

# Ana yollar
nav.add_road('Kadıköy', 'Üsküdar', 8, 'Sahil Yolu')
nav.add_road('Üsküdar', 'Beşiktaş', 5, 'Boğaz Köprüsü')
nav.add_road('Beşiktaş', 'Taksim', 3, 'İnönü Caddesi')
nav.add_road('Taksim', 'Şişli', 4, 'Halaskargazi Caddesi')
nav.add_road('Kadıköy', 'Maltepe', 10, 'E5')
nav.add_road('Maltepe', 'Kartal', 6, 'E5')
nav.add_road('Beşiktaş', 'Şişli', 5, 'Barbaros Bulvarı')
nav.add_road('Şişli', 'Mecidiyeköy', 2, 'Büyükdere Caddesi')
nav.add_road('Taksim', 'Beyoğlu', 1, 'İstiklal Caddesi')
nav.add_road('Üsküdar', 'Kadıköy', 8, 'Sahil Yolu')

print("=== İSTANBUL NAVİGASYON ===")
nav.print_directions('Kadıköy', 'Taksim')
nav.print_directions('Maltepe', 'Mecidiyeköy')

from collections import defaultdict, deque

class ProjectScheduler:
    """Görev planlama sistemi - DAG tabanlı"""
    
    def __init__(self):
        self.tasks = {}  # {task: {'duration': int, 'deps': []}}
        self.graph = defaultdict(list)  # Bağımlılık grafı
    
    def add_task(self, name, duration, dependencies=None):
        """Görev ekle"""
        deps = dependencies or []
        self.tasks[name] = {'duration': duration, 'deps': deps}
        
        # Graf kenarları: bağımlılık → görev
        for dep in deps:
            self.graph[dep].append(name)
        
        # Bağımlılığı olmayan görevleri de grafta tut
        if name not in self.graph:
            self.graph[name] = []
    
    def topological_sort(self):
        """Kahn algoritması ile topological sort"""
        # In-degree hesapla
        in_degree = defaultdict(int)
        for task in self.tasks:
            in_degree[task] = len(self.tasks[task]['deps'])
        
        # In-degree 0 olan görevlerle başla
        queue = deque([t for t in self.tasks if in_degree[t] == 0])
        result = []
        
        while queue:
            task = queue.popleft()
            result.append(task)
            
            # Bu göreve bağlı olanların in-degree'sini azalt
            for dependent in self.graph[task]:
                in_degree[dependent] -= 1
                if in_degree[dependent] == 0:
                    queue.append(dependent)
        
        # Döngü kontrolü
        if len(result) != len(self.tasks):
            return None  # Döngü var!
        
        return result
    
    def has_cycle(self):
        """Döngü var mı?"""
        return self.topological_sort() is None
    
    def calculate_critical_path(self):
        """Kritik yol ve minimum proje süresi"""
        order = self.topological_sort()
        if order is None:
            return None, None
        
        # En erken başlama zamanları
        earliest_start = {task: 0 for task in self.tasks}
        
        for task in order:
            for dep in self.tasks[task]['deps']:
                dep_end = earliest_start[dep] + self.tasks[dep]['duration']
                earliest_start[task] = max(earliest_start[task], dep_end)
        
        # En son biten görev = proje süresi
        project_duration = max(
            earliest_start[t] + self.tasks[t]['duration'] 
            for t in self.tasks
        )
        
        return order, project_duration
    
    def print_schedule(self):
        """Zamanlama çizelgesi"""
        order, duration = self.calculate_critical_path()
        
        if order is None:
            print("❌ Döngüsel bağımlılık! Planlama yapılamaz.")
            return
        
        print("=== PROJE PLANI ===\n")
        print("Görev Sırası:")
        
        # En erken başlama zamanları
        earliest_start = {task: 0 for task in self.tasks}
        for task in order:
            for dep in self.tasks[task]['deps']:
                dep_end = earliest_start[dep] + self.tasks[dep]['duration']
                earliest_start[task] = max(earliest_start[task], dep_end)
        
        for i, task in enumerate(order, 1):
            info = self.tasks[task]
            deps_str = ', '.join(info['deps']) if info['deps'] else '-'
            start = earliest_start[task]
            end = start + info['duration']
            print(f"  {i}. {task}")
            print(f"     Süre: {info['duration']} gün | Başlangıç: Gün {start} | Bitiş: Gün {end}")
            print(f"     Bağımlılıklar: {deps_str}")
            print()
        
        print(f"📅 Toplam proje süresi: {duration} gün")


# Yazılım projesi örneği
project = ProjectScheduler()

# Görevler ve bağımlılıkları
project.add_task('Gereksinim Analizi', 5)
project.add_task('Veritabanı Tasarımı', 3, ['Gereksinim Analizi'])
project.add_task('API Tasarımı', 4, ['Gereksinim Analizi'])
project.add_task('Frontend Tasarımı', 3, ['Gereksinim Analizi'])
project.add_task('Backend Geliştirme', 10, ['Veritabanı Tasarımı', 'API Tasarımı'])
project.add_task('Frontend Geliştirme', 8, ['Frontend Tasarımı', 'API Tasarımı'])
project.add_task('Entegrasyon', 4, ['Backend Geliştirme', 'Frontend Geliştirme'])
project.add_task('Test', 5, ['Entegrasyon'])
project.add_task('Deploy', 2, ['Test'])

project.print_schedule()

from collections import deque, defaultdict

class WebCrawler:
    """
    BFS tabanlı Web Crawler simülasyonu
    
    Gerçek dünyada: requests + BeautifulSoup kullanılır
    """
    
    def __init__(self):
        # Simüle edilmiş web sayfaları
        self.web = {
            'ana-sayfa': ['hakkimizda', 'urunler', 'blog'],
            'hakkimizda': ['ana-sayfa', 'iletisim', 'ekip'],
            'urunler': ['ana-sayfa', 'urun-1', 'urun-2', 'urun-3'],
            'blog': ['ana-sayfa', 'yazi-1', 'yazi-2'],
            'iletisim': ['ana-sayfa', 'hakkimizda'],
            'ekip': ['hakkimizda', 'iletisim'],
            'urun-1': ['urunler', 'urun-2'],
            'urun-2': ['urunler', 'urun-1', 'urun-3'],
            'urun-3': ['urunler'],
            'yazi-1': ['blog', 'yazi-2'],
            'yazi-2': ['blog', 'yazi-1']
        }
    
    def crawl_bfs(self, start_url, max_pages=10):
        """BFS ile sayfaları tara"""
        visited = set()
        queue = deque([(start_url, 0)])  # (url, derinlik)
        crawled = []
        
        while queue and len(crawled) < max_pages:
            url, depth = queue.popleft()
            
            if url in visited:
                continue
            
            # "Sayfayı indir" (simülasyon)
            if url in self.web:
                visited.add(url)
                crawled.append({'url': url, 'depth': depth})
                
                # Linkleri keşfet
                for link in self.web[url]:
                    if link not in visited:
                        queue.append((link, depth + 1))
        
        return crawled
    
    def build_link_graph(self):
        """Link grafı oluştur"""
        return dict(self.web)
    
    def calculate_pagerank(self, iterations=10, damping=0.85):
        """
        Basitleştirilmiş PageRank algoritması
        
        Her sayfanın "önemini" hesaplar.
        """
        pages = list(self.web.keys())
        n = len(pages)
        
        # Başlangıç: eşit değerler
        pagerank = {page: 1.0 / n for page in pages}
        
        for _ in range(iterations):
            new_pr = {}
            
            for page in pages:
                # Bu sayfaya link veren sayfalar
                incoming = [p for p in pages if page in self.web.get(p, [])]
                
                rank_sum = 0
                for inc_page in incoming:
                    # Gelen sayfanın rankını, link sayısına böl
                    outgoing_links = len(self.web.get(inc_page, []))
                    if outgoing_links > 0:
                        rank_sum += pagerank[inc_page] / outgoing_links
                
                new_pr[page] = (1 - damping) / n + damping * rank_sum
            
            pagerank = new_pr
        
        return pagerank


# Test
crawler = WebCrawler()

print("=== WEB CRAWLER ===\n")
print("Başlangıç: ana-sayfa")
print("Max sayfa: 10\n")

results = crawler.crawl_bfs('ana-sayfa', max_pages=10)

print("Taranan sayfalar:")
for page in results:
    indent = "  " * page['depth']
    print(f"{indent}📄 {page['url']} (derinlik: {page['depth']})")

print(f"\n✅ Toplam {len(results)} sayfa tarandı")

print("\n=== PAGERANK ANALİZİ ===\n")
pagerank = crawler.calculate_pagerank()

# Sırala ve yazdır
sorted_pr = sorted(pagerank.items(), key=lambda x: x[1], reverse=True)
for page, rank in sorted_pr[:5]:
    bar = "█" * int(rank * 100)
    print(f"  {page:15} {rank:.4f} {bar}")

from collections import deque

def solve_maze(maze, start, end):
    """
    BFS ile labirent çöz
    
    maze: 2D grid (0=yol, 1=duvar)
    start: (row, col) başlangıç
    end: (row, col) hedef
    
    Returns: En kısa yol veya None
    """
    rows, cols = len(maze), len(maze[0])
    
    # 4 yön: yukarı, aşağı, sol, sağ
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    visited = set()
    queue = deque([(start, [start])])  # ((row, col), path)
    
    while queue:
        (row, col), path = queue.popleft()
        
        # Hedefe ulaştık mı?
        if (row, col) == end:
            return path
        
        if (row, col) in visited:
            continue
        visited.add((row, col))
        
        # 4 yöne bak
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # Sınırlar içinde mi?
            if 0 <= new_row < rows and 0 <= new_col < cols:
                # Duvar değil ve ziyaret edilmemiş mi?
                if maze[new_row][new_col] == 0 and (new_row, new_col) not in visited:
                    queue.append(((new_row, new_col), path + [(new_row, new_col)]))
    
    return None  # Yol bulunamadı


def print_maze_solution(maze, path):
    """Labirenti ve çözümü yazdır"""
    rows, cols = len(maze), len(maze[0])
    path_set = set(path) if path else set()
    
    # Semboller: █=duvar, ·=yol, ★=çözüm, S=başlangıç, E=bitiş
    for r in range(rows):
        row_str = ""
        for c in range(cols):
            if (r, c) == path[0] if path else False:
                row_str += "🟢"  # Başlangıç
            elif (r, c) == path[-1] if path else False:
                row_str += "🔴"  # Bitiş
            elif (r, c) in path_set:
                row_str += "🟨"  # Çözüm yolu
            elif maze[r][c] == 1:
                row_str += "⬛"  # Duvar
            else:
                row_str += "⬜"  # Boş yol
        print(row_str)


# Örnek labirent
maze = [
    [0, 0, 1, 0, 0, 0],
    [1, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1, 0],
    [0, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 0]
]

start = (0, 0)
end = (5, 5)

print("=== LABİRENT ÇÖZME ===\n")
print("Orijinal labirent (⬛=duvar, ⬜=yol):")
for row in maze:
    print("".join("⬛" if cell == 1 else "⬜" for cell in row))

print("\nBaşlangıç:", start)
print("Hedef:", end)

path = solve_maze(maze, start, end)

if path:
    print(f"\n✅ Çözüm bulundu! ({len(path)} adım)")
    print("\nÇözüm (🟢=başlangıç, 🔴=bitiş, 🟨=yol):")
    print_maze_solution(maze, path)
    print("\nYol:", " → ".join(str(p) for p in path))
else:
    print("\n❌ Çözüm bulunamadı!")