Форум программистов [Powered by Invision Power Board]

Код


n1.addConnection(new Connection("Калинина 50 - Калинина 123",n1,n2,20));
n2.addConnection(new Connection("Калинина123 - М.Амурского 30",n2,n6,22));

Код


public class Node
{
Dijkstra11 dij = new Dijkstra11();
public void addConnection (Connection connection)
    {   
         // Добавление вершин и ребер графа
           dij.addNodes(connection.ConnectionFromNode.getNodeAddress(), connection.ConnectionToNode.getNodeAddress(), connection.getCost());
    }
}

Код


ArrayList <Node>Collection = new ArrayList<Node>();
public void addNodes(String Start, String End, int Weight){ 
    System.out.println("Добавление в граф ребра от "+Start+" до "+ End);
Collection.add(new Node(Start,End,Weight)); 
Collection.add(new Node(End,Start,Weight)); 
}

Код


Dijkstra11 dij = new Dijkstra11();

Код


package ru.vingrad.graph;

import java.util.HashMap;
import java.util.Map;

public class Node {

    private final String title;
    private final Map<Node, Connection> connections = new HashMap<>();

    public Node(String title) {
        this.title = title;
    }

    private void addConnection(Connection connection) {
        Node start = connection.getStart();
        connections.put(start, connection);
    }

    public void connectTo(Node end, int weight) {
        if (connections.containsKey(end)) return;
        Connection connection = new Connection(this, end, weight);
        connections.put(end, connection);
        end.addConnection(connection);
    }

    public String getDescription() {
        StringBuilder sb = new StringBuilder();
        sb.append(title);
        for (Map.Entry<Node, Connection> entry : connections.entrySet()) {
            sb.append(String.format(" {%s | %d}",
                    entry.getKey().getTitle(),
                    entry.getValue().getWeight())
            );
        }
        return sb.toString();
    }

    public String getTitle() {
        return title;
    }
}

Код


package ru.vingrad.graph;

public class Connection {

    private final Node start, end;
    private final int weight;

    public Connection(Node start, Node end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    public int getWeight() {
        return weight;
    }

    public Node getStart() {
        return start;
    }

    public Node getEnd() {
        return end;
    }

    public String getDescription() {
        return String.format("%s -> %s (%d)",
                start.getDescription(),
                end.getDescription(),
                weight
        );
    }
}

Код


package ru.vingrad.graph;

import java.util.ArrayList;
import java.util.List;

public class Test {

    private List<Node> nodes = new ArrayList<>();

    private Node newNode(String title) {
        Node node = new Node(title);
        nodes.add(node);
        return node;
    }

    public void run() {
        nodes.removeAll(nodes);
        Node n1 = newNode("Калинина 50");
        Node n2 = newNode("Калинина 123");
        Node n6 = newNode("М.Амурского 30");
        n1.connectTo(n2, 20);
        n2.connectTo(n6, 22);

        for (Node node : nodes) {
            System.out.println(node.getDescription());
        }
    }

    public static void main(String[] args) {
        new Test().run();
    }
}

Код


Калинина 50 {Калинина 123 | 20}
Калинина 123 {Калинина 50 | 20} {М.Амурского 30 | 22}
М.Амурского 30 {Калинина 123 | 22}

Код


n1.addConnection(new Connection("Калинина 50 - Калинина 123",n1,n2,20));

Код


Collection.add(new Node(Start,End,Weight));

Код


Node(String f, String t, int d)
{
    Nodethis.From = f;
    this.To = t; 
    this.distance = d; 
}

public String getDep()
{
    return this.From; 
} 


public String getDest()
{ 
    return this.To; 
} 


public int getDist()
{ 
    return this.distance; 
} 
}

Код


import java.util.HashMap;
import java.util.Map;

public class Node
{
   
private Address address;
private int CurrentDeviceNumber;
private Map DeviceDatabase;
public int CurrentConnection;
private Map ConnectionDatabase;
private String FullAddress;
private int Num;
 //Dijkstra11 dij = new Dijkstra11();
    public Node (Address addr, int nmb)
    {
        address = addr;
        DeviceDatabase = new HashMap();
        ConnectionDatabase = new HashMap();
        CurrentDeviceNumber=0;
        CurrentConnection=0;
        Num = nmb;
        
     }

    public String addDevice(Device device)
    {
       System.out.print("Добавление устройства в узел "+this.getNodeAddress()+" :");
       System.out.println(device.getDeviceDescription());
       CurrentDeviceNumber++;
       DeviceDatabase.put(CurrentDeviceNumber, device);
       return "OK";
    }

    public void addConnection (Connection connection)
    {
        CurrentConnection++;
        ConnectionDatabase.put(CurrentConnection, connection);
        // dij.addNodes(connection.ConnectionFromNode.getNodeAddress(), connection.ConnectionToNode.getNodeAddress(), connection.getCost());
       
       // return "OK";
       
    }

   public String getNodeAddress()
    {
       return address.getStreet()+" "+address.getBuilding();
   }
   
   public int getNumber()
   {
       return Num ;
   }
  }

Код


package Networks;

public class Connection {

    public Node ConnectionFromNode;
    public Node ConnectionToNode;
    private String ConnectionName;
    private int ConnectionCost;

    public Connection(String cn, Node fromnode, Node tonode,int cost)
    {
       System.out.println("Добавление канала связи к узлу "+ tonode.getNodeAddress() + " от "+fromnode.getNodeAddress());
       ConnectionCost = cost;
       ConnectionToNode = tonode;
       ConnectionFromNode = fromnode;
       
    }
    public int getCost() {
        return ConnectionCost;
    }
}

Код


import java.util.*;

public class Dijkstra
{ // Начало класса Dijkstra
    ArrayList <Node>Collection = new ArrayList<Node>(); //Список всех вершин
    ArrayList <Node>Route = new ArrayList<Node>();      //Маршрут 
    ArrayList <Node>Waiting = new ArrayList<Node>();    //Список возможных путей

    public String current = null;
    
    int length = 0;                                     // Обнуляем длину
    
    
    public void addNodes(String Start, String End, int Weight)
    {// Начало метода addNodes
        System.out.println("Добавление в граф ребра от "+Start+" до "+ End);
        Collection.add(new Node(Start,End,Weight));
        Collection.add(new Node(End,Start,Weight));
    }//Окончание класса addNodes
    
    void setNext(String nt)
    {//Начало метода setNext
        current = nt;
    }//Окончание метода setNext

    
    void update(ArrayList<Node> wl)
    {//Начало метода update(ArrayList<Node> wl)
        ArrayList<Node> update = new ArrayList<Node>();
        for(Node a:wl)
        {//Начало цикла for(Node a:wl)
            for(Node b:wl)
            {//Начало цикла for(Node b:wl)
                if(a.getDest().equals(b.getDest())&&a.getDist()<b.getDist())
                {//Начало if (если назначение точки А = назначению точки Б и назначение А<Б
                    update.add(b);
                }//Окончание if
            }//Окончание цикла for(Node b:wl)
        }//Окончание цикла for(Node a:wl)
        
        
        for(Node c:update)
        {//Начало цикла for(Node c:update)
            wl.remove(c);
        }//Окончание цикла for(Node c:update)
}//Окончание метода (ArrayList<Node> wl)
    
    void Remove(ArrayList<Node> coll,String nt)
    {//Начало метода Remove(ArrayList<Node> coll,String nt)
        ArrayList<Node> move = new ArrayList<Node>();
        for(Node a:coll)
        {//Начало цикла for(Node a:coll)
            if(nt.equals(a.getDest()))
                move.add(a);
        }//Окончание цикла for(Node a:coll)
        
        
        for(Node a:move)
        {//Начало цикла  for(Node a:move)
            if(coll.contains(a))
                coll.remove(a);
        }//Окончание  цикла for(Node a:move)
    }//Окончание метода Remove(ArrayList<Node> coll,String nt)
    
    
    void linkRoute(ArrayList<Node> rt)
    {//Начало метода linkRoute(ArrayList<Node> rt)
        ArrayList<Node> linkroute = new ArrayList<Node>();
        int last = rt.size()-1;
        for(int i=rt.size()-2;i>-1;i--)
        {//Начало цикла for
            if(!rt.get(last).getDep().equals(rt.get(i).getDest()))
            {
                linkroute.add(rt.get(i));
            }
            else 
                if(rt.get(last).getDep().equals(rt.get(i).getDest()))
                { 
                    last = i; 
                } 
        }//Окончание цикла for
        
        for(Node a:linkroute)
        { 
            rt.remove(a); 
        } 
    }//Окончание метода linkRoute(ArrayList<Node> rt)
    
    
    void toWait(String nt)
    {//Начало метода toWait 
        Remove(Collection,current); 
        for(Node a:Collection)
        { //Начало цикла  for(Node a:Collection)
            if(nt.equals(a.getDep()))
            { 
                Waiting.add(new Node(a.getDep(),a.getDest(),a.getDist()+length)); 
            }
        } //Окончание цикла  for(Node a:Collection)
        
        for(Node b:Waiting)
        { //Начало цикла  for(Node a:Collection)
            if(Collection.contains(b)) 
                Collection.remove(b); 
        } //Окончание цикла for(Node a:Collection)
        update(Waiting); 
    } //Окончание метода toWait
    
    
    boolean selectNext(ArrayList<Node> wl)
    { //Начало метода selectNext(ArrayList<Node> wl)
        if(wl.isEmpty())
        { //Начало цикла if(wl.isEmpty()), если WaitingList равен 0
            System.out.println("Невозможно найти путь!"); 
            return false; 
        } //Окончание цикла if(wl.isEmpty()), если WaitingList равен 0
        else
            if(wl.size() == 1)
            { //Начало цикла, если WaitingList равен 1
                current = wl.get(0).getDest(); 
                length =  wl.get(0).getDist();
                Route.add(Route.size(), wl.get(0)); 
                wl.remove(wl.get(0)); 
            } //Окончание цикла, если WaitingList равен 1
            else
            { //Начало цикла, если WaitingList не равен 1
                Node s = wl.get(0); 
                for(Node a:wl)
                { 
                    if(a.getDist()<s.getDist())
                    { 
                        s = a; 
                    } 
                } 
                current = s.getDest(); 
                length =  s.getDist(); 
                Route.add(Route.size(), s); 
                wl.remove(s);//удалить элемент s из WaitingList
            } //Окончание цикла, если WaitingList не равен 1
        return true; 
    } //Окончание метода selectNext(ArrayList<Node> wl)
    
    
    public void wrap(String start, String stop)
    { //Начало метода wrap(String start, String stop) (Нахождение пути)
        current = start; 
        System.out.println("Попытка нахождения пути от "+start+" до "+stop);
        
        for(int i=0;;i++)
        { 
            if(stop.equals(current))
            { 
                //Route.add(); 
                break;
            } 
            toWait(current);
            if(selectNext(Waiting)) 
                continue; 
            else 
                break; 
        } 
        
        if(!Route.isEmpty()&&Route.get(Route.size()-1).getDest().equals(stop))
        { 
            linkRoute(Route); 
            System.out.print(Route.get(0).getDep()+" -> "); 
            for(Node a:Route)
            { 
                System.out.print(a.getDest()+", ");
            } 
            System.out.print("Стоимость: "+Route.get(Route.size()-1).getDist()+"\n"); 
        } 
        else 
            System.err.println("Нет возможных путей от "+start+" до "+stop); 
    }//Окончание метода wrap(String start, String stop) (Нахождение пути)

} 

class Node{ 
public String From; 
public String To; 
public int distance;


Node(String f, String t, int d)
{
    this.From = f;
    this.To = t; 
    this.distance = d; 
}

public String getDep()
{
    return this.From; 
} 


public String getDest()
{ 
    return this.To; 
} 


public int getDist()
{ 
    return this.distance; 
} 
}

Код


//Начало метода update(ArrayList<Node> wl)
//Начало цикла  for(Node a:Collection)
//Окончание цикла for(Node a:Collection)

Цитата(k0rvin @ 4.5.2012, 09:12)

Подобного вида комментарии:

Код


//Начало метода update(ArrayList<Node> wl)
//Начало цикла  for(Node a:Collection)
//Окончание цикла for(Node a:Collection)

бесполезны чуть более, чем полностью, советую их удалить, чтобы не мешали.

Код


 private final Map<Node, Connection> connections = new HashMap<>();

Цитата(poloten4ek @ 4.5.2012, 10:38

)

Можно ли так сделать?

Цитата(LSD @ 4.5.2012, 10:05)

Цитата(poloten4ek @ 4.5.2012, 10:38

)

Можно ли так сделать?

Или в качестве value используй коллекцию или http://guava-libraries.googlecode.com/svn/tags/release03/javadoc/com/google/common/collect/Multimap.html.

Цитата(poloten4ek @ 4.5.2012, 09:38)

Насколько мне известно, в мапах ключ может иметь только одно значение (поправьте, если не прав). То есть, допустим:
key=Калинина 123; Value= {key=Калинина 50; value = 10}
А если нужно сделать несколько соединений в один узел? Мапы "съедят" это?
key=Калинина 123; Value= {key=Калинина 50; value = 10}
key=Калинина 123; Value= {key=К.Маркса 20; value = 20}
...
Можно ли так сделать?

Код


n1 = Node title:"Калинина 123"
n2 = Node title:"Калинина 50"
n3 = Node title:"К.Маркса 20"
c1 = Connection start:n1, end:n2, weight:20
c2 = Connection start:n1, end:n3, weight:10

n1.connections:{
    key:n2 => value:c1,
    key:n3 => value:c2
}

n2.connections:{
    key:n1 => value:c1
}

n3.connections:{
    key:n1 => value:c2
}