01: /*
02: * Copyright (c) 2003-2008, Franz-Josef Elmer, All rights reserved.
03: *
04: * Redistribution and use in source and binary forms, with or without
05: * modification, are permitted provided that the following conditions are met:
06: *
07: * - Redistributions of source code must retain the above copyright notice,
08: * this list of conditions and the following disclaimer.
09: * - Redistributions in binary form must reproduce the above copyright notice,
10: * this list of conditions and the following disclaimer in the documentation
11: * and/or other materials provided with the distribution.
12: *
13: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
14: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
15: * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
17: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
20: * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
21: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
22: * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
23: * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24: */
25: package classycle.graph;
26:
27: /**
28: * Attributes of a graph. The following properties
29: * can be accessed with this interface:
30: * <dl><dt>Girth:</dt><dd>The length of the shortest cycle.</dd>
31: * <dt>Eccentricities:</dt>
32: * <dd>The eccentricity for each vertex of the graph. The eccentricity of
33: * a vertex is the largest <em>distance</em> to other vertices of the
34: * graph. The distance between vertex A and B is defined as the
35: * shortest path from A to B. The distance is infinite if there is
36: * no path from A to B.
37: * <dt>Diameter:</dt><dd>The largest eccentricity.</dd>
38: * <dt>Radius:</dt><dd>The smallest eccentricity.</dd>
39: * <dt>Center:</dt>
40: * <dd>The set of vertices of the graph with the smallest eccentricities.
41: * </dd>
42: * <dt>Maximum fragment sizes:</dt>
43: * <dd>The maximum fragment sizes for each vertex of the graph. The
44: * maximum fragment size of a vertex is defined as the size of the
45: * largest strong component of the graph after the vertex has been
46: * removed.
47: * </dd>
48: * <dt>Best fragment size:</dt>
49: * <dd>The smallest maximum fragment size.</dd>
50: * <dt>Best fragmenters:</dt>
51: * <dd>The set of vertices of the graph with smallest maximum fragment size.
52: * </dd>
53: * </dl>
54: *
55: * @author Franz-Josef Elmer
56: */
57: public interface GraphAttributes extends Attributes {
58: /** Returns the girth. */
59: public int getGirth();
60:
61: /** Returns the radius. */
62: public int getRadius();
63:
64: /** Returns the diameter. */
65: public int getDiameter();
66:
67: /** Returns the vertices of the center. */
68: public Vertex[] getCenterVertices();
69:
70: /**
71: * Returns the eccentricies of all vertices of a {@link StrongComponent}.
72: */
73: public int[] getEccentricities();
74:
75: /**
76: * Returns the maximum fragment sizes of all vertices of
77: * a {@link StrongComponent}.
78: */
79: public int[] getMaximumFragmentSizes();
80:
81: /** Returns the best fragment size. */
82: public int getBestFragmentSize();
83:
84: /**
85: * Returns those vertices of a {@link StrongComponent} where the maximum
86: * fragment size is equal to the best fragment size.
87: */
88: public Vertex[] getBestFragmenters();
89: } //interface
|