Ngehlobo eledlule ngaba nengxenye - uhlelo lwabafundi abavela kwa-Google. Njalo ngonyaka, abahleli bakhetha amaphrojekthi amaningana we-Open Source, kuhlanganise nezinhlangano ezaziwa kakhulu njenge и . I-Google imema abafundi abavela emhlabeni wonke ukuthi basebenze kulawa maphrojekthi.
Njengombambi qhaza ku-Google Summer of Code 2019, ngenze iphrojekthi ngaphakathi kwelabhulali nenhlangano , ethuthukisa ulimi lwe-Haskell - olunye lwezilimi ezisebenza kahle zokuhlela. I-Alga ngumtapo wezincwadi omele ukumelwa kwamagrafu ku-Haskell. Isetshenziswa, ngokwesibonelo, ku - umtapo wezincwadi we-Github owakha izihlahla ze-semantic, izingcingo kanye namagrafu okuncika ngokusekelwe kukhodi futhi ongaziqhathanisa. Iphrojekthi yami bekuwukwengeza ukumelwa kohlobo oluphephile kumagrafu we-bipartite nama-algorithms alokho kuvezwa.
Kulokhu okuthunyelwe ngizokhuluma ngokusetshenziswa kwami kwe-algorithm yokuhlola igrafu ye-bipartiteness ku-Haskell. Noma i-algorithm ingenye eyisisekelo kakhulu, ukuyisebenzisa kahle ngesitayela esisebenzayo kungithathe izikhathi ezimbalwa futhi kudinga umsebenzi omningi. Ngenxa yalokho, ngizinzile ekusebenzeni ngama-monad transformers.
Mayelana nami
Igama lami nginguVasily Alferov, ngingumfundi owenza unyaka wesine eSt. Petersburg HSE. Ngaphambilini kubhulogi ngibhale и . Njengamanje ngise-internship eNorway, lapho ngisebenzela khona izindlela zokuxazulula le nkinga . Engikuthandayo kufaka phakathi ama-algorithms anepharamitha kanye nezinhlelo zokusebenza.
Mayelana nokuqaliswa kwe-algorithm
Isibikezelo
Abafundi ababamba iqhaza ohlelweni bakhuthazwa kakhulu ukuthi babhale. Banginikeze inkundla yebhulogi . Lesi sihloko siwukuhumusha , ebhalwe yimi lapho ngo-July ngesiNgisi, nesandulelo esifushane.
Donsa Isicelo ngekhodi okukhulunywa ngayo ingatholakala .
Ungafunda ngemiphumela yomsebenzi wami (ngesiNgisi) .
Lokhu okuthunyelwe kuhloselwe ukujwayeza umfundi ngemibono eyisisekelo ekuhleleni okusebenzayo, nakuba ngizozama ukukhumbula yonke imigomo esetshenziswe lapho kufika isikhathi.
Ihlola amagrafu ukubona kabili
I-algorithm yokuhlola igrafu ye-bipartiteness ngokuvamile inikezwa esifundweni sama-algorithms njengenye ye-algorithms yegrafu elula kakhulu. Umbono wakhe uqondile: okokuqala sibeka ama-vertices ngakwesobunxele noma kwesokudla, futhi lapho kutholakala unqenqema olungqubuzanayo, siyagomela ukuthi igrafu ayiyona i-bipartite.
Imininingwane eyengeziwe: okokuqala sibeka i-vertex engxenyeni engakwesokunxele. Ngokusobala, bonke omakhelwane bale vertex kumele balale endaweni efanele. Ngaphezu kwalokho, bonke omakhelwane bomakhelwane bale vertex kumele balale ku-lobe kwesokunxele, njalonjalo. Siyaqhubeka nokwabela amasheya kuma-vertices inqobo nje uma kusekhona ama-vertices engxenyeni exhunyiwe ye-vertex esiqale ngayo esingababelanga omakhelwane. Bese siphinda lesi senzo kuzo zonke izingxenye ezixhunyiwe.
Uma kunomkhawulo phakathi kwama-vertices awela esabelweni esifanayo, akunzima ukuthola umjikelezo oyinqaba kugrafu, owaziwa kabanzi (futhi ngokusobala) ongenakwenzeka kugrafu ephindwe kabili. Uma kungenjalo, sinokuhlukanisa okulungile, okusho ukuthi igrafu i-bipartite.
Ngokuvamile, le algorithm isetshenziswa kusetshenziswa noma . Ngezilimi ezibalulekile, ukusesha okujulile kuvame ukusetshenziswa njengoba kulula kancane futhi akudingi izakhiwo zedatha eyengeziwe. Ngiphinde ngakhetha ukusesha okujulile njengoba kungokwesiko.
Ngakho, sifike isikimu elandelayo. Sinqamula amathwithi egrafu sisebenzisa ukusesha okujulile kuqala futhi sabelane nabo, sishintsha inombolo yokwabelana njengoba sihamba onqenqemeni. Uma sizama ukwabela isabelo ku-vertex esivele inesabelo esabelwe, singasho ngokuphepha ukuthi igrafu ayiyona i-bipartite. Isikhathi lapho wonke ama-vertices abelwa isabelo futhi sesibheke yonke imiphetho, sinokuhlukaniswa okuhle.
Ukuhlanzeka kwezibalo
Ku-Haskell sicabanga ukuthi zonke izibalo ziyi ihlanzekile. Nokho, uma lokhu bekunjalo ngempela, besingeke sibe nayo indlela yokuphrinta noma yini esikrinini. Kube bonke, kuhlanzekile izibalo zivilapha kangangokuthi akekho ihlanzekile izizathu zokubala okuthile. Zonke izibalo ezenzeka ohlelweni ziyaphoqelelwa ngandlela thize ukuba zingene "okungcolile" igama IO.
Ama-Monads ayindlela yokumela izibalo nge imiphumela eHaskell. Ukuchaza ukuthi basebenza kanjani kungaphezu kwalokhu okuthunyelwe. Incazelo enhle necacile ingafundwa ngesiNgisi .
Lapha ngifuna ukuveza ukuthi ngenkathi amanye ama-monads, anjenge-IO, esetshenziswa ngomlingo wokuhlanganisa, cishe zonke ezinye zenziwa kusoftware futhi zonke izibalo kuzo zimsulwa.
Kunemiphumela eminingi futhi ngayinye ine-monad yayo. Lena ithiyori eqinile futhi enhle: wonke ama-monads asebenzisa isikhombimsebenzisi esifanayo. Sizokhuluma ngama-monads amathathu alandelayo:
- Ukuthi i-ea iyisibalo esibuyisela inani lohlobo a noma ephonsa okuhlukile kohlobo u-e. Ukuziphatha kwale monad kufana kakhulu nokuphatha okuhlukile ngezilimi ezibalulekile: amaphutha angabanjwa noma adluliselwe. Umehluko omkhulu ukuthi i-monad isetshenziswa ngokunengqondo ngokuphelele emtatsheni wezincwadi ojwayelekile e-Haskell, kuyilapho izilimi ezibalulekile zivame ukusebenzisa izindlela zesistimu yokusebenza.
- I-State sa iyisibalo esibuyisela inani lohlobo a futhi esikwazi ukufinyelela esimweni esiguqulekayo sohlobo s.
- Mhlawumbe a. I-Maybe monad iveza ukubala okungaphazanyiswa noma nini ngokubuyisela Lutho. Kodwa-ke, sizokhuluma ngokusetshenziswa kwekilasi le-MonadPlus lohlobo lwe-Mhlawumbe, eliveza umphumela ophambene: isibalo esingaphazanyiswa noma nini ngokubuyisela inani elithile.
Ukusetshenziswa kwe-algorithm
Sinezinhlobo ezimbili zedatha, Igrafu a kanye ne-Bigraph ab, eyokuqala emele amagrafu anama mpo abhalwe amanani ohlobo u-a, kanti eyesibili imelela amagrafu angama-bipartite anama vertices angakwesokunxele abhalwe amanani ohlobo u-a nolwesokudla. -ama-vertices aseceleni abhalwe amanani ohlobo b.
Lezi akuzona izinhlobo ezivela kulabhulali ye-Alga. I-alga ayinakho ukumelwa kwamagrafu angama-bipartite angaqondile. Ngenze izinhlobo ezinjengalezi ukuze zicace.
Futhi sizodinga imisebenzi yomsizi enamasiginesha alandelayo:
-- Список соседей данной вершины.
neighbours :: Ord a => a -> Graph a -> [a]
-- Построить двудольный граф по графу и функции, для каждой вершины
-- выдающей её долю и пометку в новой доле, игнорируя конфликтные рёбра.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Список вершин в графе
vertexList :: Ord a => Graph a -> [a]
Сигнатура функции, которую мы будем писать, выглядит так:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Kulula ukubona ukuthi uma phakathi nosesho olujulile-kokuqala sithole unqenqema olungqubuzanayo, umjikelezo oyinqaba ulele phezu kwesitaki sokuphinda. Ngakho-ke, ukuze siyibuyisele, sidinga ukusika yonke into kusukela kusitaki sokuphindaphinda kuze kufike lapho kuvela khona i-vertex yokugcina.
Senza ukusesha okujulile kuqala ngokugcina izinombolo zokwabelana ze-vertex ngayinye. I-recursion stack izogcinwa ngokuzenzakalelayo ngokusetshenziswa kwesigaba Se-Functor se-monad esiyikhethile: sizodinga kuphela ukubeka wonke ama-vertices ukusuka endleleni eya kumphumela obuyiswayo kusukela kumsebenzi wokuphindaphinda.
Umbono wami wokuqala bekuwukusebenzisa i-Ether monad, ebonakala isebenzisa ngqo imiphumela esiyidingayo. Ukuqaliswa kokuqala engikubhalile kwakusondelene kakhulu nale nketho. Eqinisweni, ngaba nokusetshenziswa okuhlanu okuhlukene ngesikhathi esisodwa futhi ekugcineni ngahlala kwenye.
Okokuqala, sidinga ukugcina izihlonzi eziningi ezihlangene - lokhu kuyinto emayelana noMbuso. Okwesibili, sidinga ukukwazi ukumisa lapho kutholakala ukungqubuzana. Lokhu kungaba yi-Monad ye-Either, noma i-MonadPlus yokuthi Mhlawumbe. Umehluko omkhulu ukuthi Noma ikuphi ingabuyisela inani uma isibalo singakamiswa, futhi Mhlawumbe ibuyisela ulwazi olumayelana nalokhu kuphela kuleli cala. Njengoba singadingi inani elihlukile ukuze siphumelele (sesivele ligcinwe kuSifundazwe), sikhetha okuthi Mhlawumbe. Futhi okwamanje lapho sidinga ukuhlanganisa imiphumela yama-monads amabili, aphuma , ehlanganisa ngokunembile le miphumela.
Kungani ngikhethe uhlobo oluyinkimbinkimbi kangaka? Izizathu ezimbili. Okokuqala, ukuqaliswa kuvela kufana kakhulu nokubalulekile. Okwesibili, sidinga ukukhohlisa inani lokubuyisela esimweni sokungqubuzana lapho sibuya kusukela ekuphindaphindeni ukuze sibuyisele iluphu eyinqaba, okulula kakhulu ukuyenza kokuthi Mhlawumbe monad.
Ngakho sithola lokhu kuqaliswa.
{-# 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 <- neigbours v g ]
{-# INLINE onEdge #-}
onEdge :: Part -> a -> PartMonad a
onEdge p v = do m <- get
case v `Map.lookup` m of
Nothing -> 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 <- vertexList g ]
oddCycle :: [a] -> [a]
oddCycle c = tail (dropWhile ((/=) last c) c)
Indawo lapho ibhulokhi iwumongo we-algorithm. Ngizozama ukuchaza ukuthi kwenzekani ngaphakathi kuyo.
- I-inVertex iyingxenye yokusesha okujulile lapho sivakashela khona i-vertex okokuqala ngqa. Lapha sabela inombolo yokwabelana ku-vertex futhi sisebenzise i-OneEdge kubo bonke omakhelwane. Yilapho futhi sibuyisela khona isitaki socingo: uma i-msum ibuyise inani, siphusha i-vertex v lapho.
- I-onEdge iyingxenye lapho sivakashela khona onqenqemeni. Ibizwa kabili onqenqemeni ngalunye. Lapha sibheka ukuthi i-vertex ngakolunye uhlangothi ivakashelwe yini, futhi uyivakashele uma kungenjalo. Uma sivakashelwe, sihlola ukuthi ingabe umphetho uyangqubuzana. Uma kunjalo, sibuyisela inani - phezulu kakhulu kwesitaki sokuphinda, lapho wonke amanye ama-vertices azobekwa lapho ebuya.
- processVertex ihlola i-vertex ngayinye ukuthi ivakashelwe yini futhi isebenzisa i-InVertex kuyo uma kungenjalo.
- I-dfs isebenzisa i-processVertex kuwo wonke ama-vertices.
Yilokho kuphela.
Umlando wegama elithi INLINE
Igama elithi INLINE lalingekho ekusetshenzisweni kokuqala kwe-algorithm; livele kamuva. Lapho ngizama ukuthola ukuqaliswa okungcono, ngathola ukuthi inguqulo engeyona ye-INLINE yayihamba kancane ngokuphawulekayo kwamanye amagrafu. Uma kucatshangelwa ukuthi ngokwezibalo imisebenzi kufanele isebenze ngokufanayo, lokhu kwangimangaza kakhulu. Ngisho nomfokazi, komunye umshini onenguqulo ehlukile ye-GHC kwakungekho umehluko obonakalayo.
Ngemva kokuchitha isonto ngifunda okukhiphayo kwe-GHC Core, ngakwazi ukulungisa inkinga ngomugqa owodwa we-INLINE esobala. Ngesinye isikhathi phakathi kwe-GHC 8.4.4 ne-GHC 8.6.5 isilungiseleli sayeka ukwenza lokhu ngokwaso.
Bengingalindele ukuhlangana nokungcola okunjalo ohlelweni lwe-Haskell. Kodwa-ke, nanamuhla, izithuthukisi kwesinye isikhathi ziyawenza amaphutha, futhi kuwumsebenzi wethu ukubanikeza izeluleko. Isibonelo, lapha siyazi ukuthi umsebenzi kufanele ufakwe emgqeni ngoba ufakwe emgqeni enguqulweni edingekayo, futhi lesi yisizathu sokunikeza umdidiyeli iseluleko.
Kwenzekani ngokulandelayo?
Ngabe sengisebenzisa i-algorithm ye-Hopcroft-Karp namanye ama-monads, futhi kwaba ukuphela kohlelo.
Ngenxa ye-Google Summer of Code, ngithole ulwazi olusebenzayo ezinhlelweni ezisebenzayo, okungagcinanga ngokungisiza ukuthi ngithole i-internship e-Jane Street ehlobo elilandelayo (angiqiniseki ukuthi le ndawo yaziwa kangakanani ngisho naphakathi kwezilaleli ezinolwazi zikaHabr, kodwa ingeyodwa. kwabambalwa lapho ungakwazi khona ehlobo ukuze uhlanganyele ezinhlelweni ezisebenzayo), kodwa futhi wangethula emhlabeni omangalisayo wokusebenzisa le paradigm ngokuzijwayeza, ehluke kakhulu kokuhlangenwe nakho kwami ngezilimi zendabuko.
Source: www.habr.com