1 Тема від FakiNyan Востаннє редагувалося FakiNyan (18.11.2014 12:47:01)

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 14 097
    • Репутація: 5660

Тема: Яким чином представити граф?

Хай. От є деякий неорієнтований граф, його вузли мають номери, а його ребра мають вагу, та можуть мати ще деякі атрибути.
Яким чином його краще представити, за умови, що мені треба буде "ходити" по тих ребрах?
При цьому очевидно, що кожен вузол має знати, в який ще вузол з нього можна перейти.
*********************************************************************************
Я от відразу подумав просто про матрицю, де номери стовбців та строк являються номерами вузлів, і на їх пересіченні буде стояти вага цього переходу. Ну, наприклад, ребро 1-2 важить 50, і от в матриці, mat[1,2]==50.
Але ж перехід з 2 в 1 теж існує, і теж важить 50, то прийшлось би ще додатково заповнювати ту матрицю, і я вважаю це надлишовим + до цього, одна комірка матриці може містити лише якусь одну величину, а нам треба декілька, величин.
************************************************************************************
Далі я подумав, що можна в ті комірки заносити не числа, а класи, котрі будуть містити потрібну кількість полів, які будуть виконувати роль отих атрибутів.
Але чи не краще тоді вже буде створити клас Point, подібний до цього

class Point {

public int MyPoint; //номер точки, котру представляє цей екземпляр класу
public List<int> AvailablePoints; //точки, в котрі можна перейти
}

Але тоді ще треба якось записати вагу кожного переходу, ну що типу перехід 1 -> 2 коштує 50. Але також якось  треба розуміти, що перехід з 2 ->1 теж коштує 50.
І тоді весь граф буде собою представляти

class Graph
{
private List<Point> points;
private SomeTable withWeightsOfEdges;
}

Яким чином це краще організувати?

2 Відповідь від Skyzerks Synx Востаннє редагувалося Skyzerks Synx (18.11.2014 17:38:30)

  • Дата реєстрації: 18.09.2014
  • Повідомлень: 110
    • Репутація: 23

Re: Яким чином представити граф?

FakiNyan написав:

Яким чином це краще організувати?

Тоді може вже ліпше задати його як пряму лінію, обмежену цими двома точками?
Або як варіант використати стек, з умовою, що елементи не повторяються (але це тільки якщо іти в один бік).

3 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 14 097
    • Репутація: 5660

Re: Яким чином представити граф?

нафіга мені стек? яка пряма? шо ви таке кажеет? я не розумію взагалі, навіщо це.
Зробив я то от як

 public class Point
    {
        public int point;
        public List<int> pointsTo;

        public Point(int point, List<int> pointsTo)
        {
            this.point = point;
            this.pointsTo = pointsTo;
        }
    }
  public class Edge
    {
        public int pointOne;
        public int pointTwo;
        public int Length;
        public double Pheromone;
        public double Weight;

        public Edge(int fromPoint, int toPoint, int pathLength)
        {
            pointOne = fromPoint;
            pointTwo = toPoint;
            Length = pathLength;
            Pheromone = 1;
        }
    }
 public class Path
    {
        public List<Point> points { private set; get; }
        public List<Edge> edges { private set; get; } 

        public Path()
        {
            points=new List<Point>();
            edges=new List<Edge>();
        }

        public void AddPoint(int point, List<int> pointsTo)
        {
            points.Add(new Point(point, pointsTo));
        }

        public void AddEdge(int pointOne, int pointTwo, int length)
        {
            edges.Add(new Edge(pointOne,pointTwo,length));
        }

        public void RefreshPheromone()
        {
            foreach (var edge in edges)
            {
                edge.Pheromone = 1;
            }
        }

        public void ChangePheromone(double value)
        {
            foreach (var edge in edges)
            {
                edge.Pheromone += value;
            }
        }
    }

Path - то типу граф, і складається він з набору отих точок і ребер.
Тепер треба зробити, аби точки генерувались самі, використовуючи дані ребер. Тому що зараз я отак це ініціалізую

 Path path = new Path();
            path.AddPoint(1,new List<int>(){2,3,4});
            path.AddPoint(2, new List<int>() { 1, 3, 4 });
            path.AddPoint(3, new List<int>() { 1, 2, 4 });
            path.AddPoint(4, new List<int>() { 1, 2, 3 });

            path.AddEdge(1,2,50);
            path.AddEdge(1, 3, 80);
            path.AddEdge(1, 4, 60);
            path.AddEdge(2, 4, 55);
            path.AddEdge(2, 3, 45);
            path.AddEdge(3, 4, 20);

А мона зробити, що тільки ребра пододавав, а точки самі генеруються.
Ну типу, у нас є ребро 1, 2. Тобто очевидно, що точка 1 має доступ до точки 2, а точка 2 до точки 1. Ну і так само з іншими точками.