ProHoster > GSoC 2019: Grafu bipartitātes pārbaude un monādu transformatori

GSoC 2019: Grafu bipartitātes pārbaude un monādu transformatori

PagājuÅ”ajā vasarā es piedalÄ«jos Google Summer of Code ā€” studentiņu programmā no uzņēmuma Google. Ik gadu organizatori izvēlas vairākus Open Source projektus, tostarp no tādām pazÄ«stamām organizācijām kā Boost.org un The Linux Foundation. Projektu Ä«stenoÅ”anai Google aicina studentus no visas pasaules.Ā 

Kā Google Summer of Code 2019 dalÄ«bnieks, es veicu projektu bibliotēkas ietvaros Alga sadarbÄ«bā ar organizāciju Haskell.org, kas nodarbojas ar Haskell valodas attÄ«stÄ«bu ā€” vienu no pazÄ«stamākajām funkcionālās programmÄ“Å”anas valodām. Alga ir bibliotēka, kas nodroÅ”ina tipiski droÅ”u grafu attēlojumu Haskell valodā. To izmanto, piemēram, bibliotēkā semantic ā€” uzņēmuma Github bibliotēkā, kas konstruē semantiskos kokus, izsaukumu un atkarÄ«bu grafus, un spēj tos salÄ«dzināt. Mans projekts sastāvēja no tipiski droÅ”a attēlojuma pievienoÅ”anas divu daļu grafiem un algoritmu izstrādes Å”im attēlojumam.Ā 

Å ajā ierakstā es stāstÄ«Å”u par savu algoritma izstrādi grafu dvīņu pārbaudei Haskell valodā. Neskatoties uz to, ka algoritms ir viens no visvienkārŔākajiem, tā skaistā pārrakstÄ«Å”ana funkcionālajā stilā man aizņēma vairākas iterācijas un prasÄ«ja diezgan daudz darba. Rezultātā es izstrādāju realizāciju ar monadiskajiem transformatoriem.Ā 

GSoC 2019: Grafu bipartitātes pārbaude un monādu transformatori

Par sevi

Mani sauc VasÄ«lijs Alfjērovs, es esmu ceturtā kursa students Sanktpēterburgas Augstākajā ekonomikas skolā. IepriekÅ” blogā es rakstÄ«ju par savu projektu par parametrizētiem algoritmiem un par ceļojumu uz ZuriHac. Patlaban es esmu prakses periodā Bergenes universitātē Norvēģijā, kur es strādāju pie pieejām uzdevumam List Coloring. Mani interesē parametrizētie algoritmi un funkcionālā programmÄ“Å”ana.

Par algoritma realizāciju

Ievads

Studentiem, kuri piedalās programmā, ieteicams veidot blogu. Man blogam pieŔķirta platforma Summer of Haskell. Å is raksts ir tulkojums raksti, ko es uzrakstÄ«ju tur jÅ«lijā angļu valodā, ar nelielu ievadu.Ā 

Pull Request ar kodu, par kuru iet runa, var atrast Ŕeit.

Par manas darba rezultātiem var lasīt (angļu valodā) Ŕeit.

Raksts paredz, ka lasÄ«tājam bÅ«s pamatzināŔanas funkcionālajā programmÄ“Å”anā, lai gan es cenÅ”os atgādināt visus izmantotos terminus, kad pienāks to kārta.

Grafu pārbaude uz dvÄ«nÄ«buĀ 

Grafu bipartitātes pārbaudes algoritms parasti tiek pasniegts algoritmu kursā kā viens no vienkārŔākajiem grafu algoritmiem. T tā ideja ir vienkārÅ”a: vispirms mēs kaut kādā veidā novietojam virsotnes kreisajā vai labajā daļā, un, atklājot konfliktējoÅ”u malu, apgalvojam, ka graphs nav bipartÄ«ts.

Nedaudz sÄ«kāk: vispirms mēs novietojam kādu virsotni kreisajā daļā. Tas ir acÄ«mredzami, ka visām kaimiņu virsotnēm Å”ai virsotnei jābÅ«t labajā daļā. Pēc tam visām kaimiņu kaimiņu virsotnēm jābÅ«t kreisajā daļā, un tā tālāk. Mēs turpinām pieŔķirt virsotnēm daļas, kamēr komponentē, kurā esam sākuÅ”i, joprojām ir virsotnes, kurām neesam pieŔķīruÅ”i kaimiņus. Tad mēs atkārtojam Å”o darbÄ«bu visām komponentēm.

Ja ir mala starp virsotnēm, kas iekļūst vienā un tajā paŔā daļā, nav grÅ«ti atrast grafā pāru ciklu, kas, kā plaÅ”i zināms (un pietiekami acÄ«mredzams), ir neiespējams bipartÄ«tā grafikā. Pretējā gadÄ«jumā mums ir pareiza daļas sadalÄ«Å”ana, un tādējādi grafiks ir bipartÄ«ts.

Parasti Å”o algoritmu Ä«steno ar platuma meklÄ“Å”anu vai dziļuma meklÄ“Å”anu. ImperatÄ«vās valodās parasti izmanto dziļuma meklÄ“Å”anu, jo tā ir nedaudz vienkārŔāka un neprasa papildu datu struktÅ«ras. Es arÄ« izvēlējos dziļuma meklÄ“Å”anu kā tradicionālāku.

Tādējādi mēs nonākam pie sekojoŔā shēmas. Mēs apgājam grafu virsotnes ar dziļuma meklÄ“Å”anu un pieŔķiram tām daļas, mainot daļas numuru, pārejot pa malu. Ja mēs mēģinām pieŔķirt daļu virsotnei, kurai jau ir pieŔķirta daļa, varam droÅ”i apgalvot, ka grafiks nav bipartÄ«ts. Tajā brÄ«dÄ«, kad visām virsotnēm ir pieŔķirta daļa, un mēs esam apskatÄ«juÅ”i visas malas, mums ir laba sadalÄ«Å”ana.

Skaitliskā tīrība

Haskellā mēs pieņemam, ka visas aprēķini ir tÄ«ri. Tomēr, ja tā patieŔām bÅ«tu, mums nebÅ«tu iespējas izdrukāt neko uz ekrāna. Kopumā, tÄ«ri aprēķini ir tik slinki, ka neeksistē neviena tÄ«ra iecēloÅ”ana, lai kaut ko aprēķinātu. Visi aprēķini, kas notiek programmā, tā vai citādi tiek piespiesti uz "netÄ«ro" IO monādes.

Monādes ir veids, kā attēlot aprēķinus ar efektiem HaskelÄ«. Skaidrojums par to, kā tie darbojas, pārsniedz Ŕī raksta robežas. Labu un saprotamu aprakstu var izlasÄ«t angļu valodā. Å”eit.

Šeit es gribu norādīt, ka, kamēr dažas monādes, piemēram, IO, ir īstenotas caur kompilatora burvību, praktiski visas pārējās ir īstenotas programmatūras līmenī, un visas to aprēķini ir tīri.

Ir ļoti daudz efektu, un katram ir savs monāde. Tā ir ļoti spēcÄ«ga un skaista teorija: visas monādes Ä«steno to paÅ”u saskarni. Mēs runāsim par nākamajām trim monādēm:

  • Either e a ā€” aprēķins, kas atgriež vērtÄ«bu ar tipu a vai izmet izņēmumu ar tipu e. Å Ä«s monādes uzvedÄ«ba ļoti lÄ«dzinās darbam ar izņēmumiem imperatÄ«vās valodās: kļūdas var tikt noÄ·ertas vai nodotas tālāk. Galvenā atŔķirÄ«ba ir tā, ka monāde ir pilnÄ«gi loÄ£iski Ä«stenota standarta bibliotēkā tajā paŔā HaskelÄ«, savukārt imperatÄ«vās valodās parasti tiek izmantoti operētājsistēmas mehānismi.
  • State s a ā€” aprēķins, kas atgriež vērtÄ«bu ar tipu a un kam ir piekļuve mainÄ«gajam stāvoklim ar tipu s.
  • Maybe a. Monāde Maybe izsaka aprēķinu, kuru jebkurā brÄ«dÄ« var pārtraukt, atgriežot Nothing. Tomēr mēs runāsim par MonadPlus klases Ä«stenoÅ”anu tipam Maybe, kas izsaka pretēju efektu: tas ir aprēķins, kuru jebkurā brÄ«dÄ« var pārtraukt, atgriežot konkrētu vērtÄ«bu.

Algoritma īstenoŔana

Mums ir divi datu tipi, Graph a un Bigraph a b, no kuriem pirmais attēlo grafus ar virsotnēm, kas marķētas ar tipu a, bet otrais attēlo divdaļīgus grafus ar kreisajā pusē esoÅ”ajām virsotnēm, kas marķētas ar tipu a, un labajā pusē esoÅ”ajām virsotnēm, kas marķētas ar tipu b.

Šie nav tipi no Alga bibliotēkas. Alga nesatur attēlojumu nenoteiktiem divdaļīgiem grafiem. Es izveidoju tipus tādus, lai tie būtu saprotami.

Mums arÄ« bÅ«s nepiecieÅ”ams palÄ«gfunkcijas ar Ŕādām parakstēm:

-- Blakus Ŕo virsotni
neighbours :: Ord a => a -> Graph a -> [a]

-- BÅ«vēt divdaļīgu grafu, pamatojoties uz grafu un funkciju, kas katrai virsotnei sniedz tās daļu un atzÄ«mi jaunajā daļā, ignorējot konfliktējoŔās malas.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā -> Graph a
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā -> Bigraph b c

-- Virsotņu saraksts grafā
vertexList :: Ord a => Graph a -> [a]
Funkcijas paraksts, kuru mēs rakstÄ«sim, izskatās Ŕādi:

type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)

Nav grÅ«ti pamanÄ«t, ka, ja dziļumā meklÄ“Å”anas procesā mēs atrodam konfliktējoÅ”o malu, neparastais cikls ir virs rekursijas steka. Tādējādi, lai to atjaunotu, mums nepiecieÅ”ams nogriezt visu no rekursijas steka lÄ«dz pirmajam pēdējās virsotnes ievadÄ«jumam.

Mēs Ä«stenosim dziļuma meklÄ“Å”anu, uzturot asociatÄ«vu masÄ«vu ar daļu numuriem katrai virsotnei. Rekursijas steku automātiski uzturēs izvēlētās monādes Functor klases realizācija: bÅ«s vien jādod visas virsotnes ceļā rezultātā, ko atgriež rekursÄ«vā funkcija.

Man pirmā ideja bija izmantot monādu Either, kas, Ŕķiet, realizē tieÅ”i tos efektus, kas mums nepiecieÅ”ami. Mans pirmais rakstÄ«tais realizējums bija ļoti tuvu Å”im variantam. PatiesÄ«bā man kādu brÄ«di bija piecas dažādas realizācijas, un es beigās apstājos pie citas.

Pirmkārt, mums ir nepiecieÅ”ams uzturēt asociatÄ«vu masÄ«vu ar daļu identifikatoriem ā€” tas ir kaut kas attiecÄ«bā uz State. Otrkārt, mums jāspēj apstāties, ja tiek konstatēts konflikts. Tas var bÅ«t vai nu Monad for Either, vai MonadPlus for Maybe. Galvenā atŔķirÄ«ba ir tā, ka Either var atgriezt vērtÄ«bu, ja aprēķins nav pārtraukts, bet Maybe Ŕādā gadÄ«jumā atgriež tikai informāciju par to. Tā kā mums nav nepiecieÅ”ama atseviŔķa vērtÄ«ba panākumu gadÄ«jumā (tā jau ir saglabāta State), mēs izvēlamies Maybe. Bet tajā brÄ«dÄ«, kad mums jāapvieno divu monādu efekti, iznāk monādes transformatori, kas tieÅ”i kombinē Å”os efektus.

Kāpēc es izvēlējos tik sarežģītu tipu? Divi iemesli. Pirmkārt, realizācija iznāk ļoti lÄ«dzÄ«ga imperatÄ«vai. Otrkārt, mums ir nepiecieÅ”ams manipulēt ar vērtÄ«bu, kas tiek atgriezta konfliktā, kad atgriežamies no rekursijas, lai atjaunotu nepāra ciklu, un to ir daudz vienkārŔāk darÄ«t ar Maybe monādu.

Tādējādi mēs iegūstam tādu realizāciju.

{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE ScopedTypeVariables #-}

data Part = LeftPart | RightPart

otherPart :: Part -> Part
otherPart LeftPart = RightPart
otherPart RightPart = LeftPart

type PartMap a = Map.Map a Part
type OddCycle a = [a]

toEither :: Ord a => PartMap a -> a -> Either a a
toEither m v = case fromJust (v `Map.lookup` m) of
                    LeftPart -> Left v
                    RightPart -> Right v

type PartMonad a = MaybeT (State (PartMap a)) [a]

detectParts :: forall a. Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)
detectParts g = case runState (runMaybeT dfs) Map.empty of
                    (Just c, _) -> Left $ oddCycle c
                    (Nothing, m) -> Right $ toBipartiteWith (toEither m) g
    where
        inVertex :: Part -> a -> PartMonad a
        inVertex p v = ((:) v) <$ do modify $ Map.insert v p
                                      let q = otherPart p
                                      msum [ onEdge q u | u  a -> PartMonad a
        onEdge p v = do m  inVertex p v
                            Just q -> do guard (q /= p)
                                         return [v]

        processVertex :: a -> PartMonad a
        processVertex v = do m <- get
                             guard (v `Map.notMember` m)
                             inVertex LeftPart v

        dfs :: PartMonad a
        dfs = msum [ processVertex v | v  [a]
        oddCycle c = tail (dropWhile ((/=) last c) c)

Block where ā€” tas ir algoritma kodols. Es centÄ«Å”os izskaidrot, kas notiek tā iekÅ”ienē.

  • inVertex ā€” tā ir daļa no dziļumā meklÄ“Å”anas, kurā mēs vispirms apmeklējam virsotni. Å eit mēs pieŔķiram virsotnei daļu skaitu un palaidam onEdge visiem kaimiņiem. Tā ir arÄ« vieta, kur mēs atjaunojam izsaukumu steku: ja msum atgrieza vērtÄ«bu, mēs tur pieliekam virsotni v.
  • onEdge ā€” tas ir daļa, kur mēs apmeklējam malu. To izsauc divreiz katrai malai. Å eit mēs pārbaudām, vai virsotne no otras puses ir apmeklēta, un apmeklējam to, ja tā nav. Ja jau ir apmeklēta, pārbaudām, vai mala ir konfliktējoÅ”a. Ja tā ir, atgriežam vērtÄ«bu ā€” paÅ”galveno rekursijas kaudzi, kurai pēc tam pievienosies visas pārējās virsotnes.
  • processVertex pārbauda katrai virsotnei, vai tā ir apmeklēta, un izsauc inVertex, ja tā nav.
  • dfs izsauc processVertex uz visām virsotnēm.

Uz Ŕo brīdi viss.

Vārda INLINE vēsture

Vārds INLINE nebija pirmajā algoritma realizācijā, tas parādījās vēlāk. Kad es centos atrast labāku realizāciju, es atklāju, ka dažos grafos versija bez INLINE darbojās ievērojami lēnāk. Ņemot vērā to, ka semantiski funkcijām vajadzētu darboties vienādi, tas mani ļoti pārsteidza. Vēl dīvaināk ir tas, ka citā datorā ar citu GHC versiju nebija redzamu izmaiņu.

Pēc tam, kad es veltÄ«ju nedēļu GHC Core izvades lasÄ«Å”anai, es spēju atrisināt problēmu ar vienu rindu ar skaidro INLINE. Kaut kur starp GHC 8.4.4 un GHC 8.6.5 optimizators pārstāja to darÄ«t pats.

Es negaidÄ«ju sastapt tik daudz netÄ«rÄ«bas programmÄ“Å”anā Haskell. Tomēr optimizatori pat mÅ«sdienās dažreiz pieļauj kļūdas, un mÅ«su uzdevums ir sniegt viņiem norādes. Piemēram, Å”eit mēs zinām, ka funkcijai jābÅ«t inlinētai, jo tā ir iekļauta imperatÄ«vā versijā, un tādēļ ir iemesls dot kompilatoram norādi.

Kas notika tālāk?

Tālāk es īstenoju Hopkrofta-Karpa algoritmu ar citām monādēm, un uz to programma beidzās.

Pateicoties Google Summer of Code, es ieguvu praktisku pieredzi funkcionālajā programmÄ“Å”anā, kas ne tikai palÄ«dzēja man iekļūt prakses vietā Jane Street nākamajā vasarā (neesmu pārliecināts, cik pazÄ«stams ir Å”is vieta pat starp zinātnieku auditoriju Habrā, bet tas ir viens no nedaudzajiem, kur vasarā var nodarboties ar funkcionālo programmÄ“Å”anu), bet arÄ« iepazÄ«stināja ar apbrÄ«nojamo Å”o paradigmu praktisko pielietojumu pasauli, kas ievērojami atŔķiras no manas pieredzes tradicionālajās valodās.

Avots: habr.com

Iegādājieties uzticamu tÄ«mekļa hostingu ar DDoS aizsardzÄ«bu, VPS VDS serveriem šŸ”„ Iegādājieties uzticamu tÄ«mekļa hostingu ar DDoS aizsardzÄ«bu, VPS VDS serveriem | ProHoster