Galera estou começando a trabalhar com grafos e matrizes em Java… estou meio perdido quanto a um problema que tenho.
eu tenho que implementar um grafo que seja “movel” variando as posições das arestas…
alguém tem algum projeto similiar ou tem idéia de como me dar uma luz?
até agora tudo o que sei fazer é instanciar a matriz, e colocar os nodos, me perco na hora das arestas…
eu tenho uma classe genérica para colcoar nodos e arestas, mas visualizar tem sido meio dificil… gostaria também se esta classe está correta…
public class GrafoMA <N,A> {
private ArrayList<N> nodelist;
private A [][] matriz;
private int cont=0;
public GrafoMA(int n)
{
nodelist=new ArrayList<N>(n);
matriz=(A [][])(new Object[n][n]);
}
public void addNode(N n){
if (n==null)
throw new IllegalArgumentException ("Nodo Inválido");
else
if(posDoNodo(n)!=-1)
throw new IllegalArgumentException(" Nodo Já Existe");
else{
nodelist.add(n);
cont++;
}
}
public void addEdge(N ori,N dest, A rot){
if (rot==null)
throw new IllegalArgumentException ("Rota Inválida");
if(posDoNodo(ori)!=-1 && posDoNodo(dest)!=-1)
matriz [posDoNodo(ori)] [posDoNodo(dest)]=rot;
else
throw new IllegalArgumentException ("Destino ou origem Inexistente");
}
private int posDoNodo(N n){
return nodelist.indexOf(n);
}
}
Entao, vc eh obrigado a usar matriz?! eh que pelo fato de vc poder colocar um novo ‘Nó’, ja significaria realocar sua matriz (com uma linha e uma coluna a mais), o que seria um saco. No seu caso vc ja esta tentando limitar isso atraves do construtor de GrafoMA, porem nodelist=new ArrayList(n); não vai impedir de incluir novos nodes quando o tamango de nodeList atingir ‘n’, então vc ja teria que controlar isso em addNote (se vc fez new GrafoMA(4), não pode ter mais de 4 nodes, pois se incluir um quinto, aqui matriz [posDoNodo(ori)] [posDoNodo(dest)]=rot; provavelmente vai dar pau)
De qualquer forma, eu faria mais ou menos assim:
public class Teste {
static class Aresta {
private final No de;
private final No para;
private final int tamanho;
public Aresta(No de, No para, int tamanho) {
this.de = de;
this.para = para;
this.tamanho = tamanho;
}
@Override
public String toString() {
return "De " + de + " para " + para + " com tamanho " + tamanho;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((de == null) ? 0 : de.hashCode());
result = prime * result + ((para == null) ? 0 : para.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Aresta other = (Aresta) obj;
if (de == null) {
if (other.de != null)
return false;
} else if (!de.equals(other.de))
return false;
if (para == null) {
if (other.para != null)
return false;
} else if (!para.equals(other.para))
return false;
return true;
}
}
static class No {
private final String nome;
private final Set<Aresta> arestas;
public No(String nome) {
this.nome = nome;
this.arestas = new HashSet<Aresta>();
}
public boolean addAresta(No para, int tamanho) {
return arestas.add(new Aresta(this, para, tamanho));
}
public Set<Aresta> getArestas() {
return Collections.unmodifiableSet(arestas);
}
public String getNome() {
return nome;
}
@Override
public String toString() {
return nome;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((nome == null) ? 0 : nome.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
No other = (No) obj;
if (nome == null) {
if (other.nome != null)
return false;
} else if (!nome.equals(other.nome))
return false;
return true;
}
}
public static void main(String[] args) {
No no1 = new No("no1");
No no2 = new No("no2");
No no3 = new No("no3");
No no4 = new No("no4");
No no5 = new No("no5");
no1.addAresta(no2, 3);
no1.addAresta(no3, 5);
no2.addAresta(no3, 6);
no2.addAresta(no4, 10);
no3.addAresta(no4, 1);
no3.addAresta(no5, 8);
no4.addAresta(no5, 7);
imprime(no1);
imprime(no2);
imprime(no3);
imprime(no4);
imprime(no5);
}
static void imprime(No no) {
System.out.println("Arestas do no " + no);
for (Aresta aresta : no.getArestas()) {
System.out.println(aresta);
}
}
}
Tenta entender ai. Para o que vc tem ai falta soh criar uma classe que gerencia uma lista de ‘nos’, mas nao vejo muito sentido ja que isso seria simplemente um List de No
assim, eu tenho um trabalho e este quer q a gente faça um tobogã, movel, ou seja ele muda conforme o desejado.
digamos que eu tenha uma matriz 7*12 que me daria 84 nodos no total… levando em consideração algumas regras… esse tobogã soh teria 2 possibilidade 1 descer em diagonal e outra ir reto para frente sem descer… a unica outra regra seria que quando chega no chão o tobogã pararia… mas o problmea seria que não se quer a opção mais rapida q seria o ir em diagonal para baixo se quer todas as alternativas de um toboga…
eu pensei em resolver isto fazendo uma matriz… de dxh (comprimento por altura) depois testar metade das arestas do eixo dXh pois o restante seria espelhado…
não sei se fui bem claro…
então eu colcoaria os nodos e as arestas com a classe grafo… e depois faria uma getGrafo para pega-los… mas ainda não pensei como implemnetar o getgrafo…
Se eu entendi bem, vc teria que “descer” a matriz como se fosse um toboga. Supondo que o topo dele fosse na esquerda, vc só poderia fazer movimentos para direita e para baixo. Sendo assim, é um problema de combinatória. Sendo uma matriz (m+1)x(n+1), vc teria como resultado a permutação de (m+n) com repetição de m e repetição de n.
Ou seja: nro total de caminhos= (n+m)!/(n!*m!).
Não sei se é esse seu caso, mas se for fica aí a sugestão
galera assim agora me surgiu uma grande duvida… para montar um grafo… eu necessito de uma lista e de uma matriz… até aqui tudo bem,
a minha duvida é a seguinte…
eu tenho uma lista de nodos… desta lista de nodos eu pego a posição de 1 nodo… e insiro na matriz [x][y] sendo a mesma posição para x e para y?
ou devo fazer algo como um contador e inserir por linha ou por coluna?