<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> has at least one vertex, and <code class="keyw">false</code> if it does not.</p>
<p>See also <code class="func">DigraphHasNoVertices</code> (<a href="chap6_mj.html#X78E16B8B7DF55B59"><span class="RefLink">6.1-2</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is the unique digraph with zero vertices, and <code class="keyw">false</code> otherwise.</p>
<p>See also <code class="func">DigraphHasAVertex</code> (<a href="chap6_mj.html#X82DBFFF17E708803"><span class="RefLink">6.1-1</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> has loops, and <code class="keyw">false</code> if it does not. A loop is an edge with equal source and range.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is antisymmetric, and <code class="keyw">false</code> if it is not.</p>
<p>A digraph is <em>antisymmetric</em> if whenever there is an edge with source <code class="code">u</code> and range <code class="code">v</code>, and an edge with source <code class="code">v</code> and range <code class="code">u</code>, then the vertices <code class="code">u</code> and <code class="code">v</code> are equal.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is bipartite, and <code class="keyw">false</code> if it is not. A digraph is bipartite if and only if the vertices of <var class="Arg">digraph</var> can be partitioned into two non-empty sets such that the source and range of any edge of <var class="Arg">digraph</var> lie in distinct sets. Equivalently, a digraph is bipartite if and only if it is 2-colorable; see <code class="func">DigraphGreedyColouring</code> (<a href="chap7_mj.html#X7AB7200D831013C1"><span class="RefLink">7.3-16</span></a>).</p>
<p>See also <code class="func">DigraphBicomponents</code> (<a href="chap5_mj.html#X7F1B5A2782F598B1"><span class="RefLink">5.4-13</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is a complete bipartite digraph, and <code class="keyw">false</code> if it is not.</p>
<p>A digraph is a <em>complete bipartite digraph</em> if it is bipartite, see <code class="func">IsBipartiteDigraph</code> (<a href="chap6_mj.html#X860CFB0C8665F356"><span class="RefLink">6.2-3</span></a>), and there exists a unique edge with source <code class="code">i</code> and range <code class="code">j</code> if and only if <code class="code">i</code> and <code class="code">j</code> lie in different bicomponents of <var class="Arg">digraph</var>, see <code class="func">DigraphBicomponents</code> (<a href="chap5_mj.html#X7F1B5A2782F598B1"><span class="RefLink">5.4-13</span></a>).</p>
<p>Equivalently, a bipartite digraph with bicomponents of size <span class="SimpleMath">\(m\)</span> and <span class="SimpleMath">\(n\)</span> is complete precisely when it has <span class="SimpleMath">\(2mn\)</span> edges, none of which are multiple edges.</p>
<p>See also <code class="func">CompleteBipartiteDigraph</code> (<a href="chap3_mj.html#X8795B0AD856014FA"><span class="RefLink">3.5-14</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is complete, and <code class="keyw">false</code> if it is not.</p>
<p>A digraph is <em>complete</em> if it has no loops, and for all <em>distinct</em> vertices <code class="code">i</code> and <code class="code">j</code>, there is exactly one edge with source <code class="code">i</code> and range <code class="code">j</code>. Equivalently, a digraph with <span class="SimpleMath">\(n\)</span> vertices is complete precisely when it has <span class="SimpleMath">\(n(n - 1)\)</span> edges, no loops, and no multiple edges.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>This property returns <code class="keyw">true</code> if <var class="Arg">digraph</var> is a complete multipartite digraph, and <code class="keyw">false</code> if not.</p>
<p>A digraph is a <em>complete multipartite digraph</em> if and only if its vertices can be partitioned into at least two maximal independent sets, where every possible edge between these independent sets occurs in the digraph exactly once.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is empty, and <code class="keyw">false</code> if it is not. A digraph is <em>empty</em> if it has no edges.</p>
<p><code class="func">IsNullDigraph</code> is a synonym for <code class="func">IsEmptyDigraph</code>. See also <code class="func">IsNonemptyDigraph</code> (<a href="chap6_mj.html#X7E14AE1F7CA23141"><span class="RefLink">6.2-12</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>A digraph is an equivalence digraph if and only if the digraph satisfies all of <code class="func">IsReflexiveDigraph</code> (<a href="chap6_mj.html#X8462D8E2792B23F6"><span class="RefLink">6.2-13</span></a>), <code class="func">IsSymmetricDigraph</code> (<a href="chap6_mj.html#X81B3EA7887219860"><span class="RefLink">6.2-14</span></a>) and <code class="func">IsTransitiveDigraph</code> (<a href="chap6_mj.html#X7F0835667F29F0C0"><span class="RefLink">6.2-16</span></a>). A partial order <var class="Arg">digraph</var> corresponds to an equivalence relation.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is functional and each node has only one in-neighbour.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>Returns <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is nonempty, and <code class="keyw">false</code> if it is not. A digraph is <em>nonempty</em> if it has at least one edge.</p>
<p>See also <code class="func">IsEmptyDigraph</code> (<a href="chap6_mj.html#X7E894CCF7B1C27AE"><span class="RefLink">6.2-7</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is reflexive, and <code class="keyw">false</code> if it is not. A digraph is <em>reflexive</em> if it has a loop at every vertex.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is symmetric, and <code class="keyw">false</code> if it is not.</p>
<p>A <em>symmetric digraph</em> is one where for each non-loop edge, having source <code class="code">u</code> and range <code class="code">v</code>, there is a corresponding edge with source <code class="code">v</code> and range <code class="code">u</code>. If there are <code class="code">n</code> edges with source <code class="code">u</code> and range <code class="code">v</code>, then there must be precisely <code class="code">n</code> edges with source <code class="code">v</code> and range <code class="code">u</code>. In other words, a symmetric digraph has a symmetric adjacency matrix <code class="func">AdjacencyMatrix</code> (<a href="chap5_mj.html#X7DC2CD70830BEE60"><span class="RefLink">5.2-1</span></a>).</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is a tournament, and <code class="keyw">false</code> if it is not.</p>
<p>A tournament is an orientation of a complete (undirected) graph. Specifically, a tournament is a digraph which has a unique directed edge (of some orientation) between any pair of distinct vertices, and no loops.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<p>This property is <code class="keyw">true</code> if the digraph <var class="Arg">digraph</var> is transitive, and <code class="keyw">false</code> if it is not. A digraph is <em>transitive</em> if whenever <code class="code">[ i, j ]</code> and <code class="code">[ j, k ]</code> are edges of the digraph, then <code class="code">[ i, k ]</code> is also an edge of the digraph.</p>
<p>Let <span class="SimpleMath">\(n\)</span> be the number of vertices of an arbitrary digraph, and let <span class="SimpleMath">\(m\)</span> be the number of edges. For general digraphs, the methods used for this property use a version of the Floyd-Warshall algorithm, and have complexity <span class="SimpleMath">\(O(n^3)\)</span>. However for digraphs which are topologically sortable [<code class="func">DigraphTopologicalSort</code> (<a href="chap5_mj.html#X785C30378064CF47"><span class="RefLink">5.1-10</span></a>)], then methods with complexity <span class="SimpleMath">\(O(m + n + m \cdot n)\)</span> will be used when appropriate.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this property is recomputed every time it is called.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EdgeWeights</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EdgeWeightsMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of lists of integers, floats or rationals.</p>
<p><code class="code">EdgeWeights</code> returns the list of lists of edge weights of the edges of the digraph <var class="Arg">digraph</var>.</p>
<p>More specifically, <code class="code">weights[i][j]</code> is the weight given to the <code class="code">j</code>th edge from vertex <code class="code">i</code>, according to the ordering of edges given by <code class="code">OutNeighbours(digraph)[i]</code>.</p>
<p>The function <code class="code">EdgeWeights</code> returns an immutable list of immutable lists, whereas the function <code class="code">EdgeWeightsMutableCopy</code> returns a copy of <code class="code">EdgeWeights</code> which is a mutable list of mutable lists.</p>
<p>The edge weights of a digraph cannot be computed and must be set either using <code class="code">SetEdgeWeights</code> or <code class="func">EdgeWeightedDigraph</code> (<a href="chap6_mj.html#X7E14055A84A52A07"><span class="RefLink">6.3-2</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EdgeWeightedDigraph</code>( <var class="Arg">digraph</var>, <var class="Arg">weights</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A digraph or <code class="keyw">fail</code></p>
<p>The argument <var class="Arg">digraph</var> may be a digraph or a list of lists of integers, floats or rationals.</p>
<p><var class="Arg">weights</var> must be a list of lists of integers, floats or rationals of an equal size and shape to <code class="code">OutNeighbours(digraph)</code>, otherwise it will fail.</p>
<p>This will create a digraph and set the EdgeWeights to <var class="Arg">weights</var>.</p>
<p>If <var class="Arg">digraph</var> is a connected digraph with edge weights, then this attribute returns a digraph which is a minimum spanning tree of <var class="Arg">digraph</var>.</p>
<p>A <em>spanning tree</em> of a digraph is a subdigraph with the same vertices but a subset of its edges that form an undirected tree. It is <em>minimum</em> if it has the smallest possible total weight for a spanning tree of that digraph.</p>
<p>If the argument <var class="Arg">digraph</var> is mutable, then the return value of this attribute is recomputed every time it is called.</p>
<p>If <var class="Arg">digraph</var> is an edge-weighted digraph, this attribute returns a record describing the paths of lowest total weight (the <em>shortest paths</em>) connecting each pair of vertices. If the optional argument <var class="Arg">source</var> is specified and is a vertex of <varclass="Arg">digraph</var>, then the output will only contain information on paths originating from that vertex.</p>
<p>In the two-argument form, the value returned is a record containing three components: <code class="code">distances</code>, <code class="code">parents</code> and <code class="code">edges</code>. Each of these is a list of integers with one entry for each vertex <code class="code">v</code> as follows:</p>
<ul>
<li><p><code class="code">distances[v]</code> is the total weight of the shortest path from <var class="Arg">source</var> to <code class="code">v</code>.</p>
</li>
<li><p><code class="code">parents[v]</code> is the final vertex before <code class="code">v</code> on the shortest path from <var class="Arg">source</var> to <code class="code">v</code>.</p>
</li>
<li><p><code class="code">edges[v]</code> is the index of the edge of lowest weight going from <code class="code">parents[v]</code> to <code class="code">v</code>.</p>
</li>
</ul>
<p>Using these three components together, you can find the shortest edge weighted path to all other vertices from a starting vertex.</p>
<p>If no path exists from <var class="Arg">source</var> to <code class="code">v</code>, then <code class="code">parents[v]</code> and <code class="code">edges[v]</code> will both be <code class="keyw">fail</code>. The distance from <var class="Arg">source</var> to itself is considered to be 0, and so both <code class="code">parents[<var class="Arg">source</var>]</code> and <code class="code">edges[<var class="Arg">source</var>]</code> are <code class="keyw">fail</code>. Edge weights can have negative values, but there is currently no implemented method for this operation if a negative-weighted cycle exists.</p>
<p>In the one-argument form, the value returned is also a record containing components <code class="code">distances</code>, <code class="code">parents</code> and <code class="code">edges</code>, but each of these will instead be a list of lists in which the <code class="code">i</code>th entry is the list that corresponds to paths starting at <code class="code">i</code>.</p>
<p>For a simple way of finding the shortest path between two specific vertices, see <code class="func">EdgeWeightedDigraphShortestPath</code> (<a href="chap6_mj.html#X7DAF81B779BD9165"><span class="RefLink">6.3-6</span></a>). See also the non-weighted operation <code class="func">DigraphShortestPath</code> (<a href="chap5_mj.html#X80E9D645843973A6"><span class="RefLink">5.4-24</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EdgeWeightedDigraphShortestPath</code>( <var class="Arg">digraph</var>, <var class="Arg">source</var>, <var class="Arg">dest</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A pair of lists, or <code class="keyw">fail</code>.</p>
<p>If <var class="Arg">digraph</var> is an edge-weighted digraph with vertices <var class="Arg">source</var> and <var class="Arg">dest</var>, this operation returns a directed path from <var class="Arg">source</var> to <var class="Arg">dest</var> with the smallest possible total weight. The output is a pair of lists <code class="code">[v, a]</code> of the form described in <code class="func">DigraphPath</code> (<a href="chap5_mj.html#X8039170B82A32257"><span class="RefLink">5.4-23</span></a>).</p>
<p>If <span class="SimpleMath">\(\textit{source} = \textit{dest}\)</span> or no path exists, then <code class="keyw">fail</code> is returned.</p>
<p>If <var class="Arg">digraph</var> contains a negative-weighted cycle, then there is currently no applicable method for this attribute.</p>
<p>See <code class="func">EdgeWeightedDigraphShortestPaths</code> (<a href="chap6_mj.html#X7EDB9C9A840F6A84"><span class="RefLink">6.3-5</span></a>). See also the non-weighted operation <code class="func">DigraphShortestPath</code> (<a href="chap5_mj.html#X80E9D645843973A6"><span class="RefLink">5.4-24</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximumFlow</code>( <var class="Arg">digraph</var>, <var class="Arg">start</var>, <var class="Arg">destination</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of lists of integers.</p>
<p>If <var class="Arg">digraph</var> is an edge-weighted digraph with vertices <var class="Arg">start</var> and <var class="Arg">destination</var>, this returns a record representing the maximum flow from <var class="Arg">start</var> to <var class="Arg">destination</var> in the digraph.</p>
<p>A <em>flow</em> is a function from the weighted edges of <var class="Arg">digraph</var> to the positive real numbers, such that:</p>
<ul>
<li><p>Each edge's flow is no more than its weight;
</li>
<li><p>For each vertex other than <var class="Arg">start</var> and <var class="Arg">destination</var>, the sum of flows for all incoming edges is equal to the sum of flows for all outgoing edges;</p>
</li>
<li><p>The sum of flows of edges leaving <var class="Arg">start</var> is equal to the sum of flows of edges entering <var class="Arg">destination</var> (this sum is denoted <span class="SimpleMath">\(M\)</span>).</p>
</li>
</ul>
<p>A <em>maximum flow</em> is a flow that maximises the value of <span class="SimpleMath">\(M\)</span>.</p>
<p>The flow is represented as a list of lists where each entry is a number representing the flow on the edge in the corresponding position in <code class="code">OutNeighbours(<var class="Arg">digraph</var>)</code>. Note that the value <span class="SimpleMath">\(M\)</span> of the flow can be found with <code class="code">Sum(DigraphMaximumFlow(<var class="Arg">digraph</var>, <var class="Arg">start</var>, <var class="Arg">destination</var>)[<var class="Arg">start</var>])</code>.</p>
<p>This attribute is computed by an implementation of the push–relabel maximum flow algorithm, which has time complexity <span class="SimpleMath">\(O(v^2 e)\)</span> where <span class="SimpleMath">\(v\)</span> is the number of vertices of the digraph, and <span class="SimpleMath">\(e\)</span> is the number of edges.</p>
<p>This operation returns a random edge-weighted digraph.</p>
<p>Its behaviour is the same as that of <code class="func">RandomDigraph</code> (<a href="chap3_mj.html#X86CF9F66788B2A24"><span class="RefLink">3.4-1</span></a>) but the returned digraph will additionally have the <code class="func">EdgeWeights</code> (<a href="chap6_mj.html#X8639092D8689333D"><span class="RefLink">6.3-1</span></a>) attribute populated with random unique weights from the set <code class="code">[1 .. m]</code> where <code class="code">m</code> is the number of edges in the digraph.</p>
<p>If the optional first argument <var class="Arg">filt</var> is present, then this should specify the category or representation the digraph being created will belong to. For example, if <var class="Arg">filt</var> is <code class="func">IsMutableDigraph</code> (<a href="chap3_mj.html#X7D7EDF83820ED6F5"><span class="RefLink">3.1-2</span></a>), then the digraph being created will be mutable, if <var class="Arg">filt</var> is <code class="func">IsImmutableDigraph</code> (<a href="chap3_mj.html#X7CAFAA89804F80BD"><span class="RefLink">3.1-3</span></a>), then the digraph will be immutable. If the optional first argument <var class="Arg">filt</var> is not present, then <codeclass="func">IsImmutableDigraph</code> (<a href="chap3_mj.html#X7CAFAA89804F80BD"><span class="RefLink">3.1-3</span></a>) is used by default.</p>
--> --------------------
--> maximum size reached
--> --------------------
¤ Dauer der Verarbeitung: 0.15 Sekunden
(vorverarbeitet)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
