Erlang 21

digraph




erlang

digraph

मॉड्यूल

संयुक्ताक्षर

मॉड्यूल सारांश

निर्देशित रेखांकन।

विवरण

यह मॉड्यूल लेबल निर्देशित ग्राफ़ का एक संस्करण प्रदान करता है। यहाँ उपलब्ध कराए गए रेखांकन को गैर-उचित निर्देशित रेखांकन क्या बनाता है, कोने के बीच के कई किनारों की अनुमति है। हालाँकि, निर्देशित रेखांकन की प्रथागत परिभाषा का उपयोग यहाँ किया गया है।

  • एक निर्देशित ग्राफ (या सिर्फ "डिग्राफ") एक सेट (V, E) है जो परिमित सेट V का वर्टिकल और निर्देशित किनारों का एक परिमित सेट E (या सिर्फ "किनारों") है। किनारों E का सेट V × V (V का कार्टेशियन उत्पाद स्वयं के साथ) का सबसेट है।

    इस मॉड्यूल में, V को खाली होने की अनुमति है। इस तरह से प्राप्त अद्वितीय खुदाई को खाली खुदाई कहा जाता है। दोनों कोने और किनारों को अद्वितीय एर्लांग शब्दों द्वारा दर्शाया गया है।

  • डिग्राफ को अधिक जानकारी के साथ एनोटेट किया जा सकता है। इस तरह की जानकारी को कोने और खुदाई के किनारों से जोड़ा जा सकता है। एनोटेट किए गए डिग्राफ को एक लेबल डिग्राफ कहा जाता है, और एक शीर्ष या किनारे से जुड़ी जानकारी को एक लेबल कहा जाता है। लेबल Erlang शब्द हैं।

  • एक किनारे e = (v, w) को वर्टेक्स v से निकलना और वर्टेक्स w पर घटना होना कहा जाता है।

  • किसी शीर्ष की डिग्री , उस शीर्ष से निकलने वाले किनारों की संख्या है।

  • किसी शीर्ष की डिग्री उस शिखर पर किनारों की घटना की संख्या है।

  • यदि कोई v से w और घटना पर निकल रहा है, तो w को v का एक आउट-पड़ोसी कहा जाता है, और v को w का एक पड़ोसी कहा जाता है।

  • एक मार्ग P, v [1] से v [k] एक डिग्राफ (V, E) में एक गैर-रिक्त अनुक्रम v [1], v [2], ..., v [k] है, जो कि V में है। E में 1 <= i <k के लिए एक किनारे (v [i], v [i + 1]) है।

  • पथ P की लंबाई k-1 है।

  • पथ पी सरल है यदि सभी कोने अलग-अलग हैं, सिवाय इसके कि पहला और अंतिम कोने समान हो सकते हैं।

  • पथ P एक चक्र है यदि P की लंबाई शून्य और v [1] = v [k] नहीं है।

  • लूप लंबाई का एक चक्र है।

  • एक सरल चक्र एक पथ है जो एक चक्र और सरल दोनों है।

  • एक साइकलिक डिग्राफ बिना साइकिल के डिग्राफ है।

जानकारी का प्रकार

d_cyclicity() = acyclic | cyclic
d_protection() = private | protected
graph()

new/0,1 द्वारा दिया गया एक डिग्राफ।

धार ()
label() = term()
शिखर ()

निर्यात

add_edge (G, V1, V2) -> edge() | {त्रुटि, add_edge_err_rsn ()}
add_edge (जी, वी 1, वी 2, लेबल) -> edge() | {त्रुटि, add_edge_err_rsn ()}
add_edge (जी, ई, वी 1, वी 2, लेबल) ->
edge() | {त्रुटि, add_edge_err_rsn ()}

प्रकार

add_edge/5 G का एज (या संशोधित) एज बनाता है, किनारे के label (नए) label के रूप में। किनारे V1 से निकल रहा है और V2 पर incident है। E वापस करता है।

add_edge(G, V1, V2, Label) add_edge(G, E, V1, V2, Label) बराबर है, जहां E एक निर्मित बढ़त है। निर्मित बढ़त को शब्द ['$e' | N] द्वारा दर्शाया गया है ['$e' | N] , जहां N एक पूर्णांक है = = 0।

add_edge(G, V1, V2) add_edge(G, V1, V2, []) बराबर है।

यदि एज एक चक्रीय {error, {bad_edge, Path}} में एक चक्र का निर्माण करेगा, {error, {bad_edge, Path}} वापस आ गया है। यदि G पहले से ही मूल्य E साथ एक किनारे है, तो एक अलग जोड़ी को जोड़ते हुए, {error, {bad_edge, [V1, V2]}} वापस कर दिया गया है। यदि V1 या V2 से कोई भी {error, {bad_vertex, G का एक शीर्ष नहीं है, तो {error, {bad_vertex, V }} वापस आ जाता है, V = V1 या V = V2

add_vertex (G) -> vertex()
add_vertex (G, V) -> vertex()
add_vertex (जी, वी, लेबल) -> vertex()

प्रकार

add_vertex/3 बनाता है (या संशोधित) शीर्ष G के डिग्राफ G , वर्टेक्स के label (नए) label के रूप में। V लौटाता है।

add_vertex(G, V) add_vertex(G, V, []) बराबर है।

add_vertex/1 लेबल के रूप में खाली सूची का उपयोग करके एक शीर्ष बनाता है, और बनाए गए शीर्ष को वापस करता है। बनाया गया शीर्ष शब्द ['$v' | N] शब्द द्वारा दर्शाया गया है ['$v' | N] , जहां N एक पूर्णांक है = = 0।

del_edge (जी, ई) -> सच

प्रकार

डिलेट्स एज E डिग्राफ G

del_edges (जी, किनारों) -> सच

प्रकार

सूची में किनारों को हटा देता है खुदाई करने वाले G से Edges

डेल_पथ (जी, वी 1, वी 2) -> सच

प्रकार

खुदाई G से किनारों को तब तक हटाती है जब तक कि V1 से वर्टेक्स V2 तक कोई paths न हो।

नियोजित प्रक्रिया का एक स्केच:

  • V2 में V1 से V2 तक एक मनमाना simple path v [1], v [2], ..., v [k] का पता लगाएं।

  • V [i] से emanating G सभी किनारों को हटा दें और 1 <= i <k (v के लिए i [1 +] के लिए incident (कई किनारों सहित) करें।

  • तब तक दोहराएं जब तक कि V1 और V2 बीच कोई रास्ता न हो।

del_vertex (जी, वी) -> सच

प्रकार

डिलेट्स वर्टेक्स V से डिग्राफ G V पर V या incident से emanating किसी भी किनारों को भी हटा दिया जाता है।

del_vertices (G, कार्यक्षेत्र) -> सत्य

प्रकार

सूची में शीर्षों को हटाता है, डिग्राफ G से Vertices

हटाना (G) -> सच है

प्रकार

डिलीट करता है G । यह कॉल महत्वपूर्ण है क्योंकि ईटीएस के साथ डिग्राफ को लागू किया जाता है। ईटीएस तालिकाओं का कोई कचरा संग्रह नहीं है। हालाँकि, डिग्राफ को हटा दिया जाता है यदि डिग्रेट बनाने वाली प्रक्रिया समाप्त हो जाती है।

एज (जी, ई) -> {ई, वी 1, वी 2, लेबल} | असत्य

प्रकार

रिटर्न {E, V1, V2, Label} , जहां Label V1 से emanating किनारे E का label है और डिग्राफ G V2 पर incident । यदि डिग्राफ G का कोई किनारा E मौजूद नहीं है, तो false लौटा दी जाती है।

किनारों (G) -> किनारों

प्रकार

कुछ अनिर्दिष्ट क्रम में, डिग्राफ G के सभी किनारों की सूची लौटाता है।

किनारों (जी, वी) -> किनारों

प्रकार

कुछ अनिर्दिष्ट क्रम में, डिग्राफ G V या incident से emanating सभी किनारों की सूची लौटाता है।

get_cycle (G, V) -> कार्यक्षेत्र | असत्य

प्रकार

यदि लंबाई का एक simple cycle दो या अधिक वर्टेक्स V माध्यम से मौजूद है, तो चक्र को एक सूची [V, ..., V] कोने के रूप में लौटाया जाता है। यदि V माध्यम से एक loop मौजूद है, तो लूप को एक सूची [V] रूप में लौटाया जाता है। यदि V माध्यम से कोई भी चक्र मौजूद नहीं है, तो false लौटा दी जाती है।

get_path/3 का उपयोग V माध्यम से एक सरल चक्र खोजने के लिए किया जाता है।

get_path (G, V1, V2) -> कार्यक्षेत्र | असत्य

प्रकार

डिग्राफ G वर्टेक्स V2 से वर्टेक्स V2 तक एक simple path खोजने की कोशिश करता है। पथ को सूची [V1, ..., V2] के रूप में लौटाता है, या false यदि V1 से V2 तक कोई सरल पथ एक या अधिक मौजूद नहीं है।

डिग्राफ G को गहराई-पहले तरीके से निकाला गया है, और पहले पाया गया मार्ग वापस आ गया है।

get_short_cycle (G, V) -> कार्यक्षेत्र | असत्य

प्रकार

डिग्राफ G वर्टेक्स V के माध्यम से यथासंभव simple cycle को खोजने की कोशिश करता है। चक्र को सूची [V, ..., V] के रूप में लौटाता है या false यदि V माध्यम से कोई सरल चक्र मौजूद नहीं है। ध्यान दें कि V माध्यम से एक loop को सूची [V, V] रूप में लौटाया गया है।

get_short_path/3 का उपयोग V माध्यम से एक सरल चक्र खोजने के लिए किया जाता है।

get_short_path (G, V1, V2) -> कार्यक्षेत्र | असत्य

प्रकार

डिग्राफ G वर्टेक्स V2 से वर्टेक्स V2 तक यथासंभव simple path खोजने की कोशिश करता है। पथ को सूची [V1, ..., V2] के रूप में लौटाता है, या false यदि V1 से V2 तक कोई सरल पथ एक या अधिक मौजूद नहीं है।

Digraph G को चौड़ाई-प्रथम तरीके से ट्रेस किया जाता है, और पहले पाया गया पथ वापस आ जाता है।

in_degree (G, V) -> पूर्णांक ()> = 0

प्रकार

डिग्राफ G के वर्टेक्स V की in-degree लौटाता है।

in_edges (जी, वी) -> किनारों

प्रकार

कुछ अनिर्दिष्ट क्रम में, डिग्राफ G के सभी किनारों की incident की सूची देता है।

in_neighbours (G, V) -> वर्टेक्स

प्रकार

कुछ अनिर्दिष्ट क्रम में, डिग्राफ G के V के सभी in-neighbors की सूची देता है।

जानकारी (G) -> जानकारी सूची

प्रकार

Digraph G का वर्णन करने वाले {Tag, Value} जोड़े की सूची लौटाता है। निम्नलिखित जोड़े लौटे हैं:

  • {cyclicity, Cyclicity} , जहां new दिए गए विकल्पों के अनुसार Cyclicity cyclic या cyclic

  • {memory, NoWords} , जहाँ NoWords तालिकाओं को आवंटित किए गए शब्दों की संख्या है।

  • {protection, Protection} , जहाँ Protection protected या private , new लिए दिए गए विकल्पों के अनुसार।

नया () -> graph()

new([]) बराबर।

नया (प्रकार) -> graph()

प्रकार

Type में विकल्पों के अनुसार गुणों के साथ एक empty digraph लौटाता है:

cyclic

Digraph (डिफ़ॉल्ट) में cycles अनुमति देता cycles

acyclic

डिग्राफ को चक्रीय रखा जाना है।

protected

अन्य प्रक्रियाएं डिग्राफ (डिफ़ॉल्ट) पढ़ सकती हैं।

private

खुदाई को केवल बनाने की प्रक्रिया द्वारा पढ़ा और संशोधित किया जा सकता है।

यदि कोई अपरिचित प्रकार का विकल्प T निर्दिष्ट है या Type एक उचित सूची नहीं है, तो एक badarg अपवाद उठाया जाता है।

no_edges (G) -> पूर्णांक ()> = 0

प्रकार

डिग्राफ G के किनारों की संख्या लौटाता है।

no_vertices (G) -> पूर्णांक ()> = 0

प्रकार

Digraph G के कोने की संख्या लौटाता है।

out_degree (G, V) -> पूर्णांक ()> = 0

प्रकार

डिग्राफ G के वर्टेक्स V की out-degree लौटाता है।

out_edges (G, V) -> किनारा

प्रकार

कुछ अनिर्दिष्ट क्रम में, डिग्राफ G V से emanating सभी किनारों की एक सूची देता है।

out_neighbours (G, V) -> कार्यक्षेत्र

प्रकार

कुछ अनिर्दिष्ट क्रम में डिग्राफ G के सभी out-neighbors की सूची लौटाता है।

वर्टेक्स (जी, वी) -> {वी, लेबल} | असत्य

प्रकार

{V, Label} लौटाता है, जहां Label डिग्राफ G के वर्टेक्स V का label है, या false अगर डिग्राफ G का कोई वर्टेक्स V मौजूद नहीं है।

vertices (G) -> कार्यक्षेत्र

प्रकार

कुछ अनिर्दिष्ट क्रम में, डिग्राफ G के सभी कोने की सूची लौटाता है।

यह भी देखें

digraph_utils(3) , ets(3)