Разработка редактора изучения теории графов
Основные термины и теоремы теории графов. Задачи на графах. Разработка интерфейса программного комплекса. Определение классов и модулей программы. Программная реализация редактора изучения теории графов. Выбор программной платформы и среды разработки.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 28.05.2019 |
| Размер файла | 2,0 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
return new Dimension(
(int) bounds.getMaxX(),
(int) bounds.getMaxY());
}
/**
* Clears all nodes and edges in this panel's graph.
*/
public void clearAll() {
graph.clearAll();
selected = null;
repaint();
}
private Graph graph;
private ToolBar toolBar;
private Point2D lastMousePoint;
private Point2D rubberBandStart;
private Point2D dragStartPoint;
private Rectangle2D dragStartBounds;
private Object selected;
private static final Color PURPLE = new Color(0.7f, 0.4f, 0.7f);
}
import java.awt.*;
import java.awt.geom.*;
/**
* An edge that is shaped like a straight line.
*/
public class LineEdge extends AbstractEdge {
private LineStyle lineStyle;
private boolean isDirected;
//private double weight;
private String label;
private ArrowHead arrow;
private static final String DEFAULT_LABEL = "";
private static final boolean DEFAULT_DIRECTED = false;
private Color color;
// Constructors
/**
* Constructs a solid line from one node to another node
*/
public LineEdge() {
lineStyle = LineStyle.SOLID;
label = DEFAULT_LABEL;
isDirected = DEFAULT_DIRECTED;
arrow = ArrowHead.NONE;
color = Color.BLACK;
}
/**
* Constructs a solid line from one node to another node, with a supplied
* direction
*
* @param boolean isItDirected whether or not the LineEdge is directed.
*/
public LineEdge(boolean isItDirected) {
lineStyle = LineStyle.SOLID;
label = DEFAULT_LABEL;
isDirected = isItDirected;
arrow = ArrowHead.NONE;
color = Color.BLACK;
}
/**
* Sets the line style property.
*
* @param newValue the new value
*/
public void setLineStyle(LineStyle newValue) {
lineStyle = newValue;
}
/**
* Gets the line style property.
*
* @return the line style
*/
public LineStyle getLineStyle() {
return lineStyle;
}
/**
* Sets the color of this LineEdge.
*/
public void setColor(Color c) {
color = c;
}
/**
* Gets the current color of this LineEdge.
*/
public Color getColor() {
return color;
}
/**
* Gets whether or not this LineEdge is directed
*
* @return whether the LineEdge is directed
*/
public boolean getDirected() {
return isDirected;
}
/**
* Change whether LineEdge is directed.
*
* @param newDirection the new value of isDirected
*/
public void setDirected(boolean newDirection) {
isDirected = newDirection;
}
/**
* Reverses the direction of this LineEdge
*/
public void swapDirection() {
if (isDirected) {
Node s = getStart();
setStart(getEnd());
setEnd(s);
}
}
/**
* Get the weight of a line edge.
*
* @return the weight of a line edge
*/
public String getLabel() {
return label;
}
/**
* Change the weight of a line edge.
*
* @param aWeight the weight of a line edge
*/
public void setLabel(String newLabel) {
label = newLabel;
}
/**
* Draws the line edge
*
* @param g the Graphics2D object that draws this LineEdge
*/
public void draw(Graphics2D g2) {
Color oldColor = g2.getColor();
Stroke oldStroke = g2.getStroke();
g2.setStroke(lineStyle.getStroke());
g2.setColor(color);
g2.draw(getConnectionPoints());
g2.setStroke(oldStroke);
if (!label.equals("")) {
g2.drawString(label, new Double(getConnectionPoints().getBounds().getCenterX()).intValue(),
new Double(getConnectionPoints().getBounds().getCenterY()).intValue());
}
if (isDirected) {
arrow = ArrowHead.V;
double theta =
Math.atan2((getEnd().getY() + getEnd().getSize() / 2) - (getStart().getY() + getStart().getSize() / 2),
(getEnd().getX() + getEnd().getSize() / 2) - (getStart().getX() + getStart().getSize() / 2));
double dx = (getEnd().getSize() / 2) * Math.cos(theta);
double dy = (getEnd().getSize() / 2) * Math.sin(theta);
Point2D.Double p = new Point2D.Double(getStart().getX() + getStart().getSize() / 2, getStart().getY() + getStart().getSize() / 2);
Point2D.Double q = (Point2D.Double) getEnd().getConnectionPoint(p);
p = (Point2D.Double) getStart().getConnectionPoint(q);
arrow.draw(g2, p, q);
}
g2.setColor(oldColor);
}
/**
* Tests whether the line edge contains a point
*
* @param p the point to test
* @return true if this line edge contains p
*/
public boolean contains(Point2D aPoint) {
final double MAX_DIST = 2;
return getConnectionPoints().ptSegDist(aPoint) < MAX_DIST;
}
}
import java.awt.*;
/**
* This class defines line styles of various shapes.
*/
public enum LineStyle {
SOLID, DASHED, THICK, THICKDASHED;
/**
* Gets a stroke with which to draw this line style.
*
* @return the stroke object that strokes this line style
*/
public Stroke getStroke() {
if (this == DASHED) {
return DASHED_STROKE;
}
if (this == SOLID) {
return SOLID_STROKE;
}
if (this == THICK) {
return THICK_STROKE;
}
if (this == THICKDASHED) {
return THICKDASHED_STROKE;
}
return null;
}
/**
* Creates new strokes, either Solid, dashed, or their thick versions.
*/
private static Stroke SOLID_STROKE = new BasicStroke();
private static Stroke THICK_STROKE = new BasicStroke(3.0f);
private static Stroke DASHED_STROKE = new BasicStroke(
1.0f,
BasicStroke.CAP_SQUARE,
BasicStroke.JOIN_MITER,
10.0f,
new float[]{3.0f, 3.0f},
0.0f);
private static Stroke THICKDASHED_STROKE = new BasicStroke(
3.0f,
BasicStroke.CAP_SQUARE,
BasicStroke.JOIN_MITER,
10.0f,
new float[]{6.0f, 6.0f},
0.0f);
}
/**
* A note node that has a yellow background and text.
*/
import java.awt.*;
import java.awt.geom.*;
import java.awt.font.*;
public class NoteNode extends AbstractNode {
private static final int DEFAULT_WIDTH = 30;
private static final int PADDING = 10;
private static final Color DEFAULT_COLOR = Color.WHITE;
private int width; // The AbstractNode field size is used for the height,
// since the width changes when the label increases.
/**
* Construct a square node with a given label.
*
* @param aColor the fill color
*/
public NoteNode(String s) {
setWidth(DEFAULT_WIDTH);
setSize(getDefaultSize());
setColor(DEFAULT_COLOR);
setLabel(s);
}
public void setWidth(int w) {
width = w;
}
public int getWidth() {
return width;
}
public void fitWidth(Graphics2D g) {
Font font = g.getFont();
FontRenderContext context = g.getFontRenderContext();
Rectangle2D bounds = font.getStringBounds(getLabel(), context);
double extent = bounds.getWidth();
double ascent = bounds.getHeight();
setWidth(new Double(extent).intValue() + PADDING);
setSize(new Double(ascent).intValue() + PADDING / 2);
}
/**
* Draws a note node.
*
* @param g The Graphics2D object that does the drawing
*/
public void draw(Graphics2D g) {
Font oldFont = g.getFont();
g.setFont(getFont());
if (getLabel() != "") {
fitWidth(g);
}
Rectangle2D rect = new Rectangle2D.Double(
getX(), getY(), width, getSize());
Color oldColor = g.getColor();
g.setColor(DEFAULT_COLOR);
g.fill(rect);
g.setColor(oldColor);
g.draw(rect);
g.drawString(getLabel(), (float) (getX() + PADDING / 2), (float) (getY() + getSize() / 2 + PADDING / 2));
g.setFont(oldFont);
}
/**
* Tests whether the note node contains a point
*
* @param p the point to test
* @return true if this note node contains p
*/
public boolean contains(Point2D p) {
Rectangle2D rect = new Rectangle2D.Double(
getX(), getY(), width, getSize());
return rect.contains(p);
}
public Rectangle2D getBounds() {
return new Rectangle2D.Double(
getX(), getY(), width, getSize());
}
/**
* Get the best connection point to connect this node with another node.
* This should be a point on the boundary of the shape of this node.
*
* @param other an exterior point that is to be joined with this node
* @return the recommended connection point
*/
public Point2D getConnectionPoint(Point2D other) {
return other;
}
}
import java.awt.*;
import java.awt.geom.*;
/**
* An invisible node that is used in the toolbar to draw an edge.
*/
public class PointNode extends AbstractNode {
/**
* Constructs a point node with coordinates (0, 0)
*/
public PointNode() {
point = new Point2D.Double();
}
/**
* Draws the point node
*/
public void draw(Graphics2D g2) {
}
/**
* Allows for the moving of a point node
*
* @param double dx, the change in the x position
* @param double dy, the change in the y position
*/
public void translate(double dx, double dy) {
point.setLocation(point.getX() + dx,
point.getY() + dy);
}
/**
* Returns if point p is contained within this node.
*
* @param p the point to be tested
* @return false always, since it has no size.
*/
public boolean contains(Point2D p) {
return false;
}
/**
* Gets the Boundaries of the Rectangle
*
* @return Rectangle2D, the rectangle to be gotten
*/
public Rectangle2D getBounds() {
return new Rectangle2D.Double(point.getX(),
point.getY(), 0, 0);
}
/**
* Gets the best connected point between this Point2D and other Point2D.
*
* @param Point2D other, the point this point is trying to connect to
* @return Point2D, the best connected point
*/
public Point2D getConnectionPoint(Point2D other) {
return point;
}
private Point2D point; //a Point on a graph
}
import java.awt.*;
import java.awt.event.*;
import java.beans.*;
import java.lang.reflect.*;
import java.util.*;
import javax.swing.*;
import javax.swing.event.*;
/**
* A component filled with editors for all editable properties of an object.
*/
public class PropertySheet extends JPanel {
/**
* Constructs a property sheet that shows the editable properties of a given
* object.
*
* @param object the object whose properties are being edited
*/
public PropertySheet(Object bean) {
try {
BeanInfo info = Introspector.getBeanInfo(bean.getClass());
PropertyDescriptor[] descriptors = (PropertyDescriptor[]) info.getPropertyDescriptors().clone();
setLayout(new FormLayout());
for (int i = 0; i < descriptors.length; i++) {
PropertyEditor editor = getEditor(bean, descriptors[i]);
if (editor != null) {
add(new JLabel(descriptors[i].getName()));
add(getEditorComponent(editor));
}
}
} catch (IntrospectionException exception) {
exception.printStackTrace();
}
}
/**
* Gets the property editor for a given property, and wires it so that it
* updates the given object.
*
* @param bean the object whose properties are being edited
* @param descriptor the descriptor of the property to be edited
* @return a property editor that edits the property with the given
* descriptor and updates the given object
*/
public PropertyEditor getEditor(final Object bean,
PropertyDescriptor descriptor) {
try {
Method getter = descriptor.getReadMethod();
if (getter == null) {
return null;
}
final Method setter = descriptor.getWriteMethod();
if (setter == null) {
return null;
}
Class type = descriptor.getPropertyType();
PropertyEditor ed = null;
Class editorClass = descriptor.getPropertyEditorClass();
if (editorClass != null) {
ed = (PropertyEditor) editorClass.newInstance();
} else {
ed = PropertyEditorManager.findEditor(type);
}
if (ed == null && Enum.class.isAssignableFrom(type)) {
ed = new EnumEditor(type);
}
if (ed == null) {
return null;
}
final PropertyEditor editor = ed;
Object value = getter.invoke(bean, new Object[]{});
editor.setValue(value);
editor.addPropertyChangeListener(new PropertyChangeListener() {
public void propertyChange(PropertyChangeEvent event) {
try {
setter.invoke(bean,
new Object[]{editor.getValue()});
fireStateChanged(null);
} catch (IllegalAccessException exception) {
exception.printStackTrace();
} catch (InvocationTargetException exception) {
exception.printStackTrace();
}
}
});
return editor;
} catch (InstantiationException exception) {
exception.printStackTrace();
return null;
} catch (IllegalAccessException exception) {
exception.printStackTrace();
return null;
} catch (InvocationTargetException exception) {
exception.printStackTrace();
return null;
}
}
/**
* Wraps a property editor into a component.
*
* @param editor the editor to wrap
* @return a button (if there is a custom editor), combo box (if the editor
* has tags), or text field (otherwise)
*/
public Component getEditorComponent(final PropertyEditor editor) {
String[] tags = editor.getTags();
String text = editor.getAsText();
if (editor.supportsCustomEditor()) {
return editor.getCustomEditor();
} else if (tags != null) {
// make a combo box that shows all tags
final JComboBox comboBox = new JComboBox(tags);
comboBox.setSelectedItem(text);
comboBox.addItemListener(new ItemListener() {
public void itemStateChanged(ItemEvent event) {
if (event.getStateChange() == ItemEvent.SELECTED) {
editor.setAsText(
(String) comboBox.getSelectedItem());
}
}
});
return comboBox;
} else {
final JTextField textField = new JTextField(text, 10);
textField.getDocument().addDocumentListener(new DocumentListener() {
public void insertUpdate(DocumentEvent e) {
try {
editor.setAsText(textField.getText());
} catch (IllegalArgumentException exception) {
}
}
public void removeUpdate(DocumentEvent e) {
try {
editor.setAsText(textField.getText());
} catch (IllegalArgumentException exception) {
}
}
public void changedUpdate(DocumentEvent e) {
}
});
return textField;
}
}
/**
* Adds a change listener to the list of listeners.
*
* @param listener the listener to add
*/
public void addChangeListener(ChangeListener listener) {
changeListeners.add(listener);
}
/**
* Notifies all listeners of a state change.
*
* @param event the event to propagate
*/
private void fireStateChanged(ChangeEvent event) {
for (ChangeListener listener : changeListeners) {
listener.stateChanged(event);
}
}
private ArrayList<ChangeListener> changeListeners = new ArrayList<ChangeListener>();
}
import java.awt.*;
import java.util.*;
import java.awt.geom.*;
/**
* Creates a graph with a random number of edges with respect to the number of
* nodes the user gives.
*/
public class RandomGraph extends SimpleGraph {
private int diameter; //Specifies how large the invisible circle the nodes lie on is.
/**
* Creates a new RandomGraph
*
* @param int d, The diameter of the graph
* @param int n, The number of nodes for the graph
* @param isMoreRandom whether or not the graph randomizes colors and sizes.
*/
public RandomGraph(int d, int n, boolean isMoreRandom) {
Random random = new Random();
diameter = d;
int r = diameter / 2;
double x = r;
double y = r;
double theta = 2 * Math.PI / n;
clearAll();
while (getNodes().size() < n) {
CircleNode c = new CircleNode(Color.WHITE);
if (isMoreRandom) {
c.setColor(new Color(random.nextInt(256), random.nextInt(256), random.nextInt(256)));
}
x = r * Math.sin(-1 * (getNodes().size()) * theta + Math.PI);
y = r * Math.cos(-1 * (getNodes().size()) * theta + Math.PI);
if (isMoreRandom) {
c.setSize(15 + random.nextInt(25));
}
add(c, new Point2D.Double(x + r, y + r));
c.sendIndex(getNodes().size() - 1);
}
randomize(isMoreRandom);
}
/**
* Sets and places the number of edges in the RandomGraph
*
* @param isMoreRandom whether or not the graph randomizes colors and sizes.
*/
public void randomize(boolean isMoreRandom) {
Random random = new Random();
int n = getNodes().size();
int edges = random.nextInt(n * (n - 1) / 2);
int startNdx = 0;
int endNdx = 0;
while (getEdges().size() < edges) {
LineEdge e = new LineEdge(false);
startNdx = random.nextInt(n);
endNdx = random.nextInt(n);
while (endNdx == startNdx) {
endNdx = random.nextInt(n);
}
e.setStart(getNodes().get(startNdx));
e.setEnd(getNodes().get(endNdx));
if (isMoreRandom) {
e.setColor(new Color(random.nextInt(256), random.nextInt(256), random.nextInt(256)));
}
addEdge(e);
}
}
/**
* Gets the array of the 3 default nodes
*
* @return A Node[] that contains the 3 default nodes
*/
public Node[] getNodePrototypes() {
Node[] nodeTypes = {
new CircleNode(Color.BLACK),
new CircleNode(Color.WHITE),
new SquareNode(Color.LIGHT_GRAY)
};
return nodeTypes;
}
/**
* Gets the array of the 2 default edges
*
* @return An Edge[] that contains the 2 default edges
*/
public Edge[] getEdgePrototypes() {
Edge[] edgeTypes = {
new LineEdge(),
new LineEdge(true)
};
return edgeTypes;
}
}
import java.awt.*;
import java.util.*;
/**
* A simple graph with round nodes and straight edges.
*/
public class SimpleGraph extends Graph {
public Node[] getNodePrototypes() {
Node[] nodeTypes = {
//new CircleNode(Color.YELLOW),
new CircleNode(Color.WHITE),
new SquareNode(Color.WHITE), //new NoteNode("Label")
};
return nodeTypes;
}
public Edge[] getEdgePrototypes() {
Edge[] edgeTypes = {
new LineEdge(),
new LineEdge(true)
};
return edgeTypes;
}
}
/**
* A square node that is filled with a color.
*/
import java.awt.*;
import java.awt.geom.*;
public class SquareNode extends AbstractNode {
/**
* Construct a square node with a given size and color.
*
* @param aColor the fill color
*/
public SquareNode(Color aColor) {
setSize(getDefaultSize());
setColor(aColor);
setLabel(getDefaultLabel());
}
/**
* Draws a square node.
*
* @param g The Graphics2D object that does the drawing
*/
public void draw(Graphics2D g) {
Rectangle2D square = new Rectangle2D.Double(
getX(), getY(), getSize(), getSize());
Color oldColor = g.getColor();
g.setColor(getColor());
g.fill(square);
g.setColor(oldColor);
g.draw(square);
g.drawString(getLabel(), (float) (getX() + getSize() / 3), (float) (getY() + getSize() / 1.5));
}
/**
* Tests whether the square node contains a point
*
* @param p the point to test
* @return true if this square node contains p
*/
public boolean contains(Point2D p) {
Rectangle2D rect = new Rectangle2D.Double(
getX(), getY(), getSize(), getSize());
return rect.contains(p);
}
/**
* Get the best connection point to connect this node with another node.
* This should be a point on the boundary of the shape of this node.
*
* @param other an exterior point that is to be joined with this node
* @return the recommended connection point
*/
public Point2D getConnectionPoint(Point2D other) {
Point2D answer;
double centerX = getX() + getSize() / 2;
double centerY = getY() + getSize() / 2;
double dx = other.getX() - getX();
double dy = other.getY() - getY();
double slope = dy / dx;
if (dx == 0) {
if (dy > 0) {
answer = new Point2D.Double(other.getX(), getY());
} else {
answer = new Point2D.Double(other.getX(), getY() + getSize());
}
} else if (dy > centerY && Math.abs(slope) > 1) {
answer = new Point2D.Double(centerX + (1 / slope) * (getSize() / 2), centerY + getSize() / 2);
} else if (dy < centerY && Math.abs(slope) > 1) {
if (other.getY() > centerY) {
answer = new Point2D.Double(centerX + (1 / slope) * (getSize() / 2), centerY + getSize() / 2);
} else {
answer = new Point2D.Double(centerX - (1 / slope) * (getSize() / 2), centerY - getSize() / 2);
}
} else if (Math.abs(slope) < 1 && dx > 0) {
answer = new Point2D.Double(centerX + getSize() / 2, centerY + slope * (getSize() / 2));
} else {
answer = new Point2D.Double(centerX - getSize() / 2, centerY - slope * (getSize() / 2));
}
return answer;
}
}
import java.awt.*;
import java.awt.geom.*;
import java.io.Console;
import java.util.*;
import javax.swing.*;
/**
* A tool bar that contains node and edge prototype icons. Exactly one icon is
* selected at any time.
*/
public class ToolBar extends JPanel {
/**
* Constructs a tool bar with no icons.
*/
public ToolBar(Graph graph) {
group = new ButtonGroup();
tools = new ArrayList<Object>();
JToggleButton grabberButton = new JToggleButton( /*new Icon()
{
public int getIconHeight() { return BUTTON_SIZE; }
public int getIconWidth() { return BUTTON_SIZE; }
public void paintIcon(Component c, Graphics g,
int x, int y)
{
Graphics2D g2 = (Graphics2D) g;
GraphPanel.drawGrabber(g2, x + OFFSET, y + OFFSET);
GraphPanel.drawGrabber(g2, x + OFFSET, y + BUTTON_SIZE - OFFSET);
GraphPanel.drawGrabber(g2, x + BUTTON_SIZE - OFFSET, y + OFFSET);
GraphPanel.drawGrabber(g2, x + BUTTON_SIZE - OFFSET, y + BUTTON_SIZE - OFFSET);
}
}*/);
UIManager.put("ToggleButton.select", Color.WHITE);
SwingUtilities.updateComponentTreeUI(grabberButton);
grabberButton.setToolTipText("Перемещение/Р'ыделение");
ImageIcon mou = new ImageIcon(getClass().getResource("/mou.png"));
System.out.println(mou);
grabberButton.setIcon(mou);
//grabberButton.setSelectedIcon();
group.add(grabberButton);
add(grabberButton);
grabberButton.setSelected(true);
tools.add(null);
Node[] nodeTypes = graph.getNodePrototypes();
for (Node n : nodeTypes) {
add(n);
}
Edge[] edgeTypes = graph.getEdgePrototypes();
for (Edge e : edgeTypes) {
add(e);
}
}
/**
* Gets the node or edge prototype that is associated with the currently
* selected button
*
* @return a Node or Edge prototype
*/
public Object getSelectedTool() {
int i = 0;
for (Object o : tools) {
JToggleButton button = (JToggleButton) getComponent(i++);
if (button.isSelected()) {
return o;
}
}
return null;
}
/**
* Adds a node to the tool bar.
*
* @param n the node to add
*/
public void add(final Node n) {
JToggleButton button = new JToggleButton(new Icon() {
public int getIconHeight() {
return BUTTON_SIZE;
}
public int getIconWidth() {
return BUTTON_SIZE;
}
public void paintIcon(Component c, Graphics g,
int x, int y) {
double width = n.getBounds().getWidth();
double height = n.getBounds().getHeight();
Graphics2D g2 = (Graphics2D) g;
double scaleX = (BUTTON_SIZE - OFFSET) / width;
double scaleY = (BUTTON_SIZE - OFFSET) / height;
double scale = Math.min(scaleX, scaleY);
AffineTransform oldTransform = g2.getTransform();
g2.translate(x, y);
g2.scale(scale, scale);
g2.translate(Math.max((height - width) / 2, 0), Math.max((width - height) / 2, 0));
g2.setColor(Color.black);
n.draw(g2);
g2.setTransform(oldTransform);
}
});
group.add(button);
button.setToolTipText("Узел");
add(button);
tools.add(n);
}
/**
* Adds an edge to the tool bar.
*
* @param n the edge to add
*/
public void add(final Edge e) {
JToggleButton button = new JToggleButton(new Icon() {
public int getIconHeight() {
return BUTTON_SIZE;
}
public int getIconWidth() {
return BUTTON_SIZE;
}
public void paintIcon(Component c, Graphics g,
int x, int y) {
Graphics2D g2 = (Graphics2D) g;
PointNode p = new PointNode();
p.translate(OFFSET, OFFSET);
PointNode q = new PointNode();
g2.setColor(Color.black);
q.translate(BUTTON_SIZE - OFFSET, BUTTON_SIZE - OFFSET);
e.connect(p, q);
g2.translate(x, y);
e.draw(g2);
g2.translate(-x, -y);
}
});
group.add(button);
button.setToolTipText("Ребро");
add(button);
tools.add(e);
}
private ButtonGroup group;
private ArrayList<Object> tools;
private static final int BUTTON_SIZE = 25;
private static final int OFFSET = 4;
}
Размещено на Allbest.ru
...Подобные документы
История возникновения, основные понятия и теоремы теории графов. Способы предоставления графов в компьютере. Матрица смежности, инциденций, списки смежности и массив дуг. Программа определения кратчайшего пути в графах. Язык программирования Delphi.
курсовая работа [823,5 K], добавлен 24.11.2010Основные понятия и определения теории графов: теоремы и способы задания графа, сильная связность графов. Построение блок-схем алгоритма, тестирование разработанного программного обеспечения, подбор тестовых данных, анализ и исправление ошибок программы.
курсовая работа [525,6 K], добавлен 14.07.2012Применение теории графов и алгоритмов на графах среди дисциплин и методов дискретной математики. Граф как совокупность двух множеств. Основные способы численного представления графа. Элементы и изоморфизмы графов. Требования к представлению графов в ЭВМ.
курсовая работа [162,2 K], добавлен 04.02.2011Области применения теории графов. Алгоритм решения задачи поиска инвариантного и полного графа. Реализация программы с графическим интерфейсом пользователя на основе алгоритма. Реализация редактора графа и вывод полученных результатов в понятной форме.
курсовая работа [493,3 K], добавлен 27.12.2008Возникновение информатики во второй половине XX столетия. Теория графов. Понятие и терминология теории графов. Некоторые задачи теории графов. Математическая логика и теория типов. Теория вычислимости и искусственный интеллект.
реферат [247,4 K], добавлен 15.08.2007В статье рассмотрен подход к созданию моделей композитного документооборота на основе аппарата теории графов. Описаны методы детерминирования множеств для разработанной модели, предложена алгебра документооборота с использованием графов.
статья [346,4 K], добавлен 19.04.2006Алгоритмы, использующие решение дополнительных подзадач. Основные определения теории графов. Поиск пути между парой вершин невзвешенного графа. Пути минимальной длины во взвешенном графе. Понятие кратчайшего пути для графов с помощью алгоритма Флойда.
реферат [39,6 K], добавлен 06.03.2010Определение понятия графа как набора вершин и связей между ними. Способы решения задач по программированию согласно теории графов на примерах заданий "Дороги", "Перекрестки", "Скрудж Мак-Дак", используя рекурсивные функции и рекуррентные соотношения.
курсовая работа [36,2 K], добавлен 10.03.2010История и термины теории графов. Описание алгоритма Дейкстры. Математическое решение проблемы определения кратчайшего расстояния от одной из вершин графа до всех остальных. Разработка программы на объектно-ориентированном языке программирования Delphi 7.
контрольная работа [646,9 K], добавлен 19.01.2016Сущность теории графов и сетевого моделирования. Выбор оптимального пути и стоимости переезда коммивояжера с помощью метода ветвей и границ. Разработка программы выбора самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу.
курсовая работа [3,5 M], добавлен 08.08.2013Изучение особенностей растровых и векторных графических редакторов. Создание графического редактора: выбор языка программирования, разработка структуры программы и алгоритма работы. Описание интерфейса программы. Руководство программиста и пользователя.
курсовая работа [1,3 M], добавлен 28.07.2013Понятие теории оптимизации экономических задач. Сущность симплекс-метода, двойственности в линейном программировании. Элементы теории игр и принятия решений, решение транспортной задачи. Особенности сетевого планирования и матричное задание графов.
курс лекций [255,1 K], добавлен 14.07.2011Понятие и основные определения гамильтоновых графов, теоремы их достаточности и особенности методов нахождения циклов. Сущность метода перебора Робертса и Флореса и его улучшение. Задачи отыскания гамильтоновых циклов в графах, создание программы.
курсовая работа [76,5 K], добавлен 01.07.2010Этапы нахождения хроматического числа произвольного графа. Анализ примеров раскраски графа. Характеристика трудоемкости алгоритма раскраски вершин графа Мейниеля. Особенности графов, удовлетворяющих структуру графов Мейниеля, основные классы графов.
курсовая работа [1,1 M], добавлен 26.06.2012Использование теории графов для решения задач. Информационные структуры входных и выходных данных. Иерархическая схема программы. Руководство оператора: назначение и условия выполнения программы. Граф-схема FormCreate, Found, RassUpdate и Search.
курсовая работа [2,5 M], добавлен 07.08.2013Характеристика задачи АВ01, ее выходная и входная информация, выбор и обоснование состава технических средств и средств программной реализации. Разработка алгоритма и программы решения задачи АВ01, руководства пользователя и контрольный пример решения.
курсовая работа [2,1 M], добавлен 21.12.2011Понятие матрицы, определение ее составных частей и границ, обосновывающие теории. Арифметические операции над матрицами, способы их представления в Mathcad. Формирование уравнений цепи на основе теории графов. Характеристика топологических матриц графа.
учебное пособие [982,4 K], добавлен 03.05.2010Использование информационных технологий для планирования размещения оптимальных точек водоснабжения, используя теорию графов. Функциональные возможности разрабатываемого приложения. Программная реализация основных модулей на основе алгоритма Флойда.
курсовая работа [818,3 K], добавлен 31.01.2012Изучение основных понятий и определений теории графов. Рассмотрение методов нахождения кратчайших путей между фиксированными вершинами. Представление математического и программного обоснования алгоритма Флойда. Приведение примеров применения программы.
контрольная работа [1,4 M], добавлен 04.07.2011Понятие и классификация алгоритмов маршрутизации. Основное определение теории графов. Анализ и разработка алгоритмов Дейкстры и Флойда на языке программирования C# для определения наилучшего пути пакетов, передаваемых через сеть. Их сравнительный анализ.
курсовая работа [1,2 M], добавлен 16.05.2015
